- From: Wayne Davison <wayne@clari.net>
- Date: Wed, 9 Aug 2000 13:09:02 -0700 (PDT)
- To: www-lib@w3.org
Here's another enhancement to lib-www, this time to the hash-table
functionality.
I needed to be able to delete individual elements from a hash-table,
plus I wanted to be able to walk through all associated elements in
a table without having to ask for a list of all keys and then
looking each one up. The result is the addition of two functions:
HTHashtable_removeObject() and HTHashtable_walk()
When I created the hash-walking function, I used a favorite hash
optimization of mine -- the user-called function can return a value
that either stops the walk, deletes the current object, or continues
onward. Having the calling function delete the current element is
much more efficient than having the user's hash-walk function do a
lookup based on the key (since the caller already knows exactly
where the current object is) and it also makes it possible for the
user's function to decide to delete any other element that they need
to delete without adversely affecting the walking sequence (since we
can safely use the pointer to the current object to continue the
walk rather than saving off a "next" pointer and hoping that the
user somehow avoids deleting that one).
Other changes:
+ I got rid of a few useless variable initializations in HTHash.c
(when the variables were being set to a value immediately
following the init value).
+ I removed some superfluous spaces that I saw.
..wayne..
---8<------8<------8<------8<---cut here--->8------>8------>8------>8---
Index: Library/src/HTHash.c
@@ -39,13 +39,13 @@
PUBLIC BOOL HTHashtable_delete (HTHashtable *me)
{
- int i = 0;
if (me) {
+ int i;
for(i = 0; i< me->size; i++) {
HTList * l = (HTList *)me->table[i];
if (l) {
HTList *cur = l;
- keynode *kn = NULL;
+ keynode *kn;
while ((kn = (keynode *) HTList_nextObject(cur))) {
HT_FREE(kn->key);
HT_FREE(kn);
@@ -78,14 +78,14 @@
)
*/
-PUBLIC BOOL HTHashtable_addObject (HTHashtable *me, const char *key ,
+PUBLIC BOOL HTHashtable_addObject (HTHashtable *me, const char *key,
void *newObject)
{
if(me) {
int size = me->size;
int i = hash_number(key,size);
HTList *l = (HTList *)me->table[i];
- keynode *kn = NULL;
+ keynode *kn;
if(!l)
l = me->table[i] = HTList_new();
if ((kn = (keynode *) HT_CALLOC(1, sizeof (keynode))) == NULL)
@@ -98,8 +98,36 @@
}
return NO;
}
+
/*
(
+ Remove an Element from the HashTable
+)
+*/
+
+PUBLIC BOOL HTHashtable_removeObject (HTHashtable *me, const char *key)
+{
+ if(me) {
+ int size = me->size;
+ int i = hash_number(key,size);
+ HTList *l = (HTList *)me->table[i];
+ if(l) {
+ HTList *cur = l;
+ keynode *kn;
+ while ((kn = (keynode *) HTList_nextObject(cur))) {
+ if(!strcmp(key,kn->key)) {
+ HTList_removeObject(l,kn);
+ me->count--;
+ return YES;
+ }
+ }
+ }
+ }
+ return NO;
+}
+
+/*
+(
Search for an Element in a Hash Table
)
*/
@@ -112,7 +140,7 @@
HTList * l = (HTList *)me->table[i];
if (l) {
HTList *cur = l;
- keynode *kn = NULL;
+ keynode *kn;
while ((kn = (keynode *) HTList_nextObject(cur))) {
if(!strcmp(key,kn->key))
return kn->object;
@@ -128,7 +156,7 @@
)
*/
-PUBLIC int HTHashtable_count (HTHashtable *me)
+PUBLIC int HTHashtable_count (HTHashtable *me)
{
if(me)
return me->count;
@@ -137,12 +165,44 @@
/*
(
- Extract in a dynamic array all keys of the Hash Table
+ Walk all Elements in the HashTable
)
*/
+PUBLIC BOOL HTHashtable_walk (HTHashtable *me,
+ int (*walkFunc)(HTHashtable *,char *, void *))
+{
+ if(me) {
+ int i, j;
+ for(i = 0; i< me->size; i++) {
+ HTList *l = (HTList *)me->table[i];
+ if(l) {
+ HTList *cur = l;
+ keynode *kn, *nextkn;
+ for(kn = (keynode *)HTList_nextObject(cur); kn; kn = nextkn) {
+ j = walkFunc(me, kn->key, kn->object);
+ if(j == 0)
+ return YES;
+ nextkn = (keynode *)HTList_nextObject(cur);
+ if(j < 0) {
+ HTList_removeObject(l, kn);
+ me->count--;
+ }
+ }
+ }
+ }
+ return YES;
+ }
+ return NO;
+}
+
+/*
+(
+ Extract in a dynamic array all keys of the Hash Table
+)
+*/
-PUBLIC HTArray * HTHashtable_keys (HTHashtable *me)
+PUBLIC HTArray * HTHashtable_keys (HTHashtable *me)
{
if(me) {
HTArray *keys = HTArray_new(me->count);
@@ -152,7 +212,7 @@
HTList * l = (HTList *)me->table[i];
if (l) {
HTList *cur = l;
- keynode *kn = NULL;
+ keynode *kn;
while ((kn = (keynode *) HTList_nextObject(cur))) {
char * nkey = NULL;
StrAllocCopy(nkey,kn->key);
Index: Library/src/HTHash.html
@@ -49,9 +49,15 @@
Add an Element to a HashTable
</H2>
<PRE>
-extern BOOL HTHashtable_addObject (HTHashtable *me, const char *key , void *newObject);
+extern BOOL HTHashtable_addObject (HTHashtable *me, const char *key, void *newObject);
</PRE>
<H2>
+ Remove an Element from a HashTable
+</H2>
+<PRE>
+extern BOOL HTHashtable_removeObject (HTHashtable *me, const char *key);
+</PRE>
+<H2>
Search for an Element in a Hash Table
</H2>
<PRE>
@@ -62,6 +68,23 @@
</H2>
<PRE>
extern int HTHashtable_count (HTHashtable *me);
+</PRE>
+<H2>
+ Walk all the elements in a Hash Table
+</H2>
+<P>
+Walking the hashtable calls the specified function pointer with each key
+and object that is in the hash table. If the callback function returns 0,
+the walking stops. If it returns a negative number, the current element
+is removed from the hash table. Return a positive number to keep going.
+<P>
+Note that it is legal for the walkFunc to call HTHashtable_removeObject()
+on any element in the current hash table <B>except</B> the current one (if
+you intend to keep going, that is). The only legal way to delete the
+current element while continuing to walk the table is to use the negative
+return value.
+<PRE>
+extern BOOL HTHashtable_walk (HTHashtable *me, int (*walkFunc)(HTHashtable *, char *, void *));
</PRE>
<H2>
Extract in a dynamic array all keys of the Hash Table
---8<------8<------8<------8<---cut here--->8------>8------>8------>8---
Received on Wednesday, 9 August 2000 16:09:05 UTC