[Python-3000] Two proposals for a new list-like type: one modest, one radical

[Daniel Stutzbach]

On 4/23/07, Neal Norwitz <nnorwitz at gmail.com> wrote:
> On 4/23/07, Daniel Stutzbach <daniel at stutzbachenterprises.com> wrote:
> > Replace list() with the BList.
>
> I looked over this patch and have various questions/comments.  In
> rough priority order:

Thanks for taking the time to look over the code.  I greatly appreciate it.

> I'm concerned about the moderately heavy use of macros wrt to debugging.

Yes, some of the debugging code is a little hairy and needs a clean-up.

I originally had written a prototype for BLists in Python and used
function decorators to indicate which invariants the function must
maintain.  This was immensely helpful during development.  C doesn't
have function decorators, so I went with some very hairy macros.
Perhaps it would be better to go with something more like this:

PyObject *some_function(PyObject *self, some_other_args)
{
    PyObject *ret;

    check_invariants(self);

    // do some stuff
    if (some_condition) {
        ret = case1;
        goto done;
    }

    // do some more stuff

 done:
    check_return_invariants(self, VALID_RW, VALID_PARENT)
    return ret;
}

> I noticed the use of alloca().  This isn't used in the core anywhere
> (except a few uses on Windows).  That might be an issue.  I didn't
> check how it was used.

These were the result of converting code that was doing malloc/free's
to be more efficient.  They could all be converted to ordinary
variable declarations now.

> I noticed that calculating the height was recursive.  Not sure where
> this function was called from, but does it handle blists which contain
> themselves?

Yes.  If the ->leaf flag is true, the BList node contains user objects
which will not be recursed on (ever if they are also BList nodes).  If
the ->flag is false, the BList node contains other BList nodes that
are part of the same data structure.

Also, FWIW, the maximum height (and therefore recursion depth) of a
BList on a 32-bit machine is 16 (assuming the maximum children per
node is 128, as I have used).

> Have you tried running this code under regrtest.py with the -R flag to
> check for memory leaks?

I hadn't heard of regrtest.py, so I re-invented the wheel.

I ran the code through the list and sequence unit tests, as well as
several additional unit tests that I wrote.  For each test, I setup
things up so that when compiled in debug mode it runs the test, counts
the total number of references in the interpreter, runs the test
again, and confirms that the total number of references have not
changed.

> There were C++ (//) style comments and C99 declarations of variables.
> These would have to be changed if included in the core.  Also, size_t
> and Py_ssize_t should be used throughout.  (ssize_t should be
> Py_ssize_t).  I noticed a bunch of ints and unsigneds.  Although I
> also noticed you used PyIndex_Check().

Is there a document that describes the right times to use int vs
size_t vs Py_ssize_t?

-- 
Daniel Stutzbach, Ph.D.             President, Stutzbach Enterprises LLC