[zeromq-dev] Proposal for a revised zlist API

[Goswin von Brederlow]

Hi,

I've gone over the zlist API and redesigned it according to some ideas
we had last month (partly for the zring class). I tried this out on
zlist to see how the ideas would fit but the idea would be to change
all the classes where appropriate so they behave the same.

Preparing for that I defined common types:
------------------------------------------

typedef int (zcommon_compare_fn) (void *item1, void *item2);
typedef void (zcommon_free_fn) (void **item, void *user);
typedef void * (zcommon_dup_fn) (void *item, void *user);

The first change is that the free callback now takes an void ** so
that it is compatible with destructors.

The other (and new) is that both free and dup take a second argument.
I've added a new field "void *user" to the container. The field is
initialized to the address of the container itself but it is free for
use by the user for whatever he wants. The field is then passed to the
free and dup callback whenever they get invoked. For an example how
this is usefull look at zcertstore.c:

    static void
    s_zcertstore_cert_destroy (zcert_t **cert_p, zcertstore_t *store)
    {
        zcert_t *cert = *cert_p;
        if (cert) {
            zhash_delete (store->cert_hash, zcert_public_txt (cert));
            zcert_destroy (cert_p);
        }
    }

Without this the zcertstore could not use a free callback but would
have to destroy certs manually.


Changed cursor handling:
------------------------

I changed the cursor to point at the pointer to the current object
instead of directly pointing to the current object. This simplifies
several things:

- no special cases for empty lists
- allows inserting items before the current one
- allows removing the current item without destroying the cursor

Overall the cursor is more stable and will be kept valid across
modifications.

I renamed zlist_push to zlist_prepend because I think it better
describes what happens and is used in other classes too (e.g.
zmsg_prepend).

I implemented a destructive removal (zlist_remove) and non-destructive
removal (zlist_take), both of which act on the current item pointed to
by the cursor and will advance the cursor to the next.

Since zlist_remove no longer takes a "void *item" argument specific
items can't be removed anymore without getting the cursor pointed at
them. To make this simple zlist_find() will use the compare callback
(or item address) to advance the cursor to the item and also return
the item.

Note: By setting the compare callback and passing the right argument
(cast to void*) to zlist_find one can find items by different methods.
For example in zloop.c readers are searched by their sock field:

    static int
    s_reader_compare (void *reader_, void *sock_)
    {   
        s_reader_t *reader = reader_;
        assert (reader);
        zsock_t *sock = (zsock_t*)sock_;
        if (reader->sock == sock)
            return 0;
        else
            return 1;
    }

I also added a zlist_insert_sorted that uses the containers compare
function to skip all items less than the new one and then insert it. I
used this in zdir.c to create the directory and file lists in sorted
order from the start instead of sorting them multiple times later.
This makes things more expensive [O(n^2) instead of O(n * log n)] but
I assumed directories are kept small enough that that doesn't matter.
Don't use it for news or mail dirs. If it becomes a problem it can be
changed to sort once after building the lists instead of on insert.


Affect on other classes:
------------------------

A lot of classes used zlist_pop in a loop to remove all items. Most of
those I changed to use a free callback instead. Others I changed to
use zmq_take or zmq_remove depending on context.

One thing that might be worth adding to zlist (and other containers)
is a function to empty the container without destroying the container
itself. This seem to get used a few times and currently requires
calling zlist_remove in a loop till the list ist empty.

The other thing that I saw quite often is iterating over the contents
of a list. Maybe it would make sense to provide a macro for this, like

FOR_EACH (zlist, item_t *, item) {
  // do something with item
}

If so I would define FOR_EACH, TAKE_EACH. FOR_EACH leaves the list
unchanged while TAKE_EACH removes but does not destroy each item.



Anyway, I've pushed all the zlist changes into a branch of my czmq fork:

https://github.com/Q-Leap-Networks/czmq/commits/feature-zlist

I've hopefully changed all other classes correctly to follow the new
API. They pass all the self tests at least. Have a look and try it out
and let me know if you think this improves the API.

MfG
	Goswin