[Python-Dev] Google Summer of Code proposal: New class for work with binary trees AVL and RB as with the standard dictionary.

[Vladimir 'Yu' Stepanov]

Hye-Shik Chang wrote:
> On 4/25/06, Vladimir 'Yu' Stepanov <vys at renet.ru> wrote:
>   
>> Thanks for the answer, but after application of a patch on python-2.4.3
>> I could not compile it. A conclusion of a stage of compilation in the
>> attached file.
>>
>>     
>
> Aah.  The patch is for Python in Subversion trunk.  I think you can
> add the following line somewhere in collectionsmodule.c to avoid
> to error.
>
> #define Py_ssize_t int
>
> Thank you!
>
> Hye-Shik
>
>   
Thanks! I have compared realizations. The object collections.rbtree works
very well. Why it still extends in the form of a patch?

Speed of work can be compared to speed of work of the standard
dictionary. Here comparative results of speed of work. My module concedes
in speed of work of that realization without the index on a parental
element and allocation is used goes two objects on each element.

There is an offer on improvement of its work. To add new exceptions for
indication of the fact of blocking, for example:
Exception
|__ StandartError
    |__ LockError
        |__ FreezeError
        |__ RDLockError
        |__ WRLockError

That speed of work was is high enough for check on each kind of blocking
it is necessary to check only one identifier. For example these macro:
---------------------------------------------------------------------
void
_lock_except(int lockcnt) {
        if (lockcnt > 0) {
                if ((lockcnt&1) == 0)
                        PyErr_SetNone(PyExc_RDLockError);
                else
                        PyErr_SetNone(PyExc_FreezeLockError);
        } else
                PyErr_SetNone(PyExc_WRLockError);
}

#define wrlock_SET(x,r) if ((x)->ob_lockcnt != 0) {     \
                                _lock_except((x)->ob_lockcnt); \
                                return r;               \
                        }                               \
                        (x)->ob_lockcnt = -1
#define wrlock_UNSET(x) (x)->ob_lockcnt = 0

#define rdlock_SET(x,r) if ((x)->ob_lockcnt < 0) {      \
                                _lock_except((x)->ob_lockcnt); \
                                return r;               \
                        }                               \
                        (x)->ob_lockcnt += 2
#define rdlock_UNSET(x) (x)->ob_lockcnt -= 2

#define freezelock_SET(x, r) if ((x)->ob_lockcnt < 0) { \
                                _lock_except((x)->ob_lockcnt); \
                                return r;               \
                        }                               \
                        (x)->ob_lockcnt |= 1;
---------------------------------------------------------------------

In object the counter in the form of an integer with a sign should be
certain - ob_lockcnt:
---------------------------------------------------------------------
struct newobject {
        PyObject_HEAD // or PyObject_HEAD_VAR
        ...
        int     ob_lockcnt;
        ...
};
---------------------------------------------------------------------

And by any call depending on if the method only reads data of object, the
sequence rdlock_* should be used. Example:
---------------------------------------------------------------------
PyObject *
method_for_read_something(PyObject *ob) {
        rdlock_SET(ob, NULL);
        ... do something ...
        if (failure)
                goto failed;
        ... do some else ...
        rdlock_UNSET(ob);
        Py_INCREF(Py_None);
        return Py_None;
failed:
        rdlock_UNSET(ob);
        return NULL;
}
---------------------------------------------------------------------

If the given method can make any critical changes that the sequence
wrlock_* should be used. Example:
---------------------------------------------------------------------
PyObject *
method_for_some_change(PyObject *ob) {
        wrlock_SET(ob, NULL);
        ... do something ...
        if (failure)
                goto failed;
        ... do some else ...
        wrlock_UNSET(ob);
        Py_INCREF(Py_None);
        return Py_None;
failed:
        wrlock_UNSET(ob);
        return NULL;
}
---------------------------------------------------------------------

If the object needs to be frozen, it is equivalent to installation of
constant blocking on reading. Thus it is possible to establish blocking on
already readable object.

For the open iterators it is necessary to carry out opening of blocking on
reading. Closing can be carried out or on end of work of iterator, or on its
closing:
---------------------------------------------------------------------
PyObject *
map_object_keys(PyObject *ob) {
        rdlock_SET(ob, NULL);
        ... allocate iterator and initialize ...
}


map_object_keys_iter_destroy(PyObject *ob) {
        ... destroy data ...
        rdlock_UNSET(ob);
}
---------------------------------------------------------------------