On Wed, Nov 15, 2006 at 02:18:48AM +0000, Daniel P. Berrange wrote: > The attached patch adds a couple of new APIs to the hash table object to > allow various different ways of iterating over the contents of the hash > table. The methods are: > > virHashForEach > virHashRemoveSet > virHashSearch > > Docs for these methods are all inline. Compared to previous patch a logic > flaw in the virHashRemoveSet method was fixed prevently some severe memory > corruption! The APIs are okay, I'm just wondering if the iterator should not return an int allowing to break the iteration, but admitedly that would make it close to the search. So it's fine as-is. > Regards, > Dan. > -- > |=- Red Hat, Engineering, Emerging Technologies, Boston. +1 978 392 2496 -=| > |=- Perl modules: http://search.cpan.org/~danberr/ -=| > |=- Projects: http://freshmeat.net/~danielpb/ -=| > |=- GnuPG: 7D3B9505 F3C9 553F A1DA 4AC2 5648 23C1 B3DF F742 7D3B 9505 -=| > Index: src/hash.c > =================================================================== > RCS file: /data/cvs/libvirt/src/hash.c,v > retrieving revision 1.10 > diff -c -r1.10 hash.c > *** src/hash.c 21 Sep 2006 15:24:37 -0000 1.10 > --- src/hash.c 15 Nov 2006 02:34:00 -0000 > *************** > *** 473,478 **** > --- 473,597 ---- > } > } > > + > + /** > + * virHashForEach > + * @table: the hash table to process > + * @iter: callback to process each element > + * @data: opaque data to pass to the iterator > + * > + * Iterates over every element in the hash table, invoking the > + * 'iter' callback. The callback must not call any other virHash* > + * functions, and in particular must not attempt to remove the > + * element. > + * > + * Returns 0 on completion, -1 on failure > + */ It could be useful and cheap to return the number of item traversed if there was no failure. > + int virHashForEach(virHashTablePtr table, virHashIterator iter, const void *data) { > + int i; > + > + if (table == NULL || iter == NULL) > + return (-1); > + > + for (i = 0 ; i < table->size ; i++) { > + virHashEntryPtr entry = table->table + i; > + while (entry) { > + if (entry->valid) { > + iter(entry->payload, entry->name, data); > + } > + entry = entry->next; > + } > + } > + return 0; > + } > + > + /** > + * virHashRemoveSet > + * @table: the hash table to process > + * @iter: callback to identify elements for removal > + * @f: callback to free memory from element payload > + * @data: opaque data to pass to the iterator > + * > + * Iterates over all elements in the hash table, invoking the 'iter' > + * callback. If the callback returns a non-zero value, the element > + * will be removed from the hash table & its payload passed to the > + * callback 'f' for de-allocation. > + * > + * Returns 0 on success, -1 on failure > + */ Same thing, we could return the number of item deallocated, callbacks make hard to keep the count. > + int virHashRemoveSet(virHashTablePtr table, virHashSearcher iter, virHashDeallocator f, const void *data) { > + int i; > + > + if (table == NULL || iter == NULL) > + return (-1); > + > + for (i = 0 ; i < table->size ; i++) { > + virHashEntryPtr prev = NULL; > + virHashEntryPtr entry = &(table->table[i]); > + > + while (entry && entry->valid) { > + if (iter(entry->payload, entry->name, data)) { > + f(entry->payload, entry->name); > + if (entry->name) > + free(entry->name); > + if (prev) { > + prev->next = entry->next; > + free(entry); > + } else { > + if (entry->next == NULL) { > + entry->valid = 0; > + entry->name = NULL; > + } else { > + entry = entry->next; > + memcpy(&(table->table[i]), entry, > + sizeof(virHashEntry)); > + free(entry); > + entry = NULL; > + } > + } > + table->nbElems--; > + } > + prev = entry; > + if (entry) { > + entry = entry->next; > + } else { > + entry = NULL; > + } > + } > + } > + return 0; > + } Iterating when removing entries which are first in the list is a bit tricky but that's looks fine. > + /** > + * virHashSearch: > + * @table: the hash table to search > + * @iter: an iterator to identify the desired element > + * @data: extra opaque information passed to the iter > + * > + * Iterates over the hash table calling the 'iter' callback > + * for each element. The first element for which the iter > + * returns non-zero will be returned by this function. > + * The elements are processed in a undefined order > + */ > + void *virHashSearch(virHashTablePtr table, virHashSearcher iter, const void *data) { > + int i; > + > + if (table == NULL || iter == NULL) > + return (NULL); > + > + for (i = 0 ; i < table->size ; i++) { > + virHashEntryPtr entry = table->table + i; > + while (entry) { > + if (entry->valid) { > + if (iter(entry->payload, entry->name, data)) > + return entry->payload; > + } > + entry = entry->next; > + } > + } > + return (NULL); > + } Minor stylistic issue I tend to use return(value); and you use sometime return (value); or return value; but it's really not a serious problem :-) > /************************************************************************ > * * > * Domain and Connections allocations * > *************** > *** 770,772 **** > --- 889,899 ---- > xmlMutexUnlock(conn->domains_mux); > return(ret); > } > + /* > + * Local variables: > + * indent-tabs-mode: nil > + * c-indent-level: 4 > + * c-basic-offset: 4 > + * tab-width: 4 > + * End: > + */ > Index: src/hash.h > =================================================================== > RCS file: /data/cvs/libvirt/src/hash.h,v > retrieving revision 1.5 > diff -c -r1.5 hash.h > *** src/hash.h 9 Apr 2006 13:11:22 -0000 1.5 > --- src/hash.h 15 Nov 2006 02:34:00 -0000 > *************** > *** 33,39 **** > * > * Callback to free data from a hash. > */ > ! typedef void (*virHashDeallocator) (void *payload, char *name); > > /* > * Constructor and destructor. > --- 33,41 ---- > * > * Callback to free data from a hash. maybe update the comment > */ > ! typedef void (*virHashDeallocator) (void *payload, const char *name); > ! typedef void (*virHashIterator) (const void *payload, const char *name, const void *data); > ! typedef int (*virHashSearcher) (const void *payload, const char *name, const void *data); > > /* > * Constructor and destructor. > *************** > *** 62,67 **** > --- 64,75 ---- > */ > void *virHashLookup(virHashTablePtr table, const char *name); > /* * Iterators */ > + > + > + int virHashForEach(virHashTablePtr table, virHashIterator iter, const void *data); > + int virHashRemoveSet(virHashTablePtr table, virHashSearcher iter, virHashDeallocator f, const void *data); > + void *virHashSearch(virHashTablePtr table, virHashSearcher iter, const void *data); > + > #ifdef __cplusplus > } > #endif All minor comments, please commit once reviewed :-) Daniel -- Red Hat Virtualization group http://redhat.com/virtualization/ Daniel Veillard | virtualization library http://libvirt.org/ veillard@xxxxxxxxxx | libxml GNOME XML XSLT toolkit http://xmlsoft.org/ http://veillard.com/ | Rpmfind RPM search engine http://rpmfind.net/