![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to HTHash.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Public] / libwww / Library / src|
Return to HTHash.c CVS log | Up to [Public] / libwww / Library / src |
1.1 frystyk 1: /*
2: ** HASH TABLE CLASS
3: **
4: ** This HashTable class implements a simple hash table to keep
5: ** objects associated with key words.
6: **
7: ** Author:
8: ** JP John Punin
9: **
10: */
11:
12: #include "wwwsys.h"
13: #include "HTUtils.h"
14: #include "HTString.h"
15: #include "HTHash.h"
16:
17: /*
18: (
19: Creation and Deletion Methods
20: )
21:
22: These methods create and deletes a Hash Table
23: */
24:
25: PUBLIC HTHashtable * HTHashtable_new (int size)
26: {
27: HTHashtable *newHashtable;
28: int c = size > 0 ? size : HT_L_HASH_SIZE;
29: if ((newHashtable = (HTHashtable *) HT_CALLOC(1, sizeof (HTHashtable))) == NULL)
30: HT_OUTOFMEM("HTHashtable_new");
31:
32: if((newHashtable->table = (void **) HT_CALLOC(c, sizeof (void *))) == NULL)
33: HT_OUTOFMEM("HTHashtable_new");
34:
35: newHashtable->count = 0;
36: newHashtable->size = c;
37: return newHashtable;
38: }
39:
40: PUBLIC BOOL HTHashtable_delete (HTHashtable *me)
41: {
42: if (me) {
1.2 ! kahan 43: int i;
1.1 frystyk 44: for(i = 0; i< me->size; i++) {
45: HTList * l = (HTList *)me->table[i];
46: if (l) {
47: HTList *cur = l;
1.2 ! kahan 48: keynode *kn;
1.1 frystyk 49: while ((kn = (keynode *) HTList_nextObject(cur))) {
50: HT_FREE(kn->key);
51: HT_FREE(kn);
52: }
53: HTList_delete(l);
54: }
55: }
56: HT_FREE(me->table);
57: HT_FREE(me);
58: return YES;
59: }
60: return NO;
61: }
62:
63: PRIVATE int hash_number (const char *key, int size)
64: {
65: int hash = 0;
66:
67: if (key) {
68: const char * ptr = key;
69: for(; *ptr; ptr++)
70: hash = (int) ((hash*3 + (*(unsigned char*)ptr)) % size);
71: }
72: return hash;
73: }
74:
75: /*
76: (
77: Add an Element to a HashTable
78: )
79: */
80:
1.2 ! kahan 81: PUBLIC BOOL HTHashtable_addObject (HTHashtable *me, const char *key,
1.1 frystyk 82: void *newObject)
83: {
84: if(me) {
85: int size = me->size;
86: int i = hash_number(key,size);
87: HTList *l = (HTList *)me->table[i];
1.2 ! kahan 88: keynode *kn;
1.1 frystyk 89: if(!l)
90: l = me->table[i] = HTList_new();
91: if ((kn = (keynode *) HT_CALLOC(1, sizeof (keynode))) == NULL)
92: HT_OUTOFMEM("HTHashtable_addObject");
93: StrAllocCopy(kn->key,key);
94: kn->object = newObject;
95: HTList_addObject(l,kn);
96: me->count++;
97: return YES;
98: }
99: return NO;
100: }
1.2 ! kahan 101:
! 102: /*
! 103: (
! 104: Remove an Element from the HashTable
! 105: )
! 106: */
! 107:
! 108: PUBLIC BOOL HTHashtable_removeObject (HTHashtable *me, const char *key)
! 109: {
! 110: if(me) {
! 111: int size = me->size;
! 112: int i = hash_number(key,size);
! 113: HTList *l = (HTList *)me->table[i];
! 114: if(l) {
! 115: HTList *cur = l;
! 116: keynode *kn;
! 117: while ((kn = (keynode *) HTList_nextObject(cur))) {
! 118: if(!strcmp(key,kn->key)) {
! 119: HTList_removeObject(l,kn);
! 120: me->count--;
! 121: return YES;
! 122: }
! 123: }
! 124: }
! 125: }
! 126: return NO;
! 127: }
! 128:
1.1 frystyk 129: /*
130: (
131: Search for an Element in a Hash Table
132: )
133: */
134:
135: PUBLIC void *HTHashtable_object (HTHashtable * me, const char *key)
136: {
137: if(me) {
138: int size = me->size;
139: int i = hash_number(key,size);
140: HTList * l = (HTList *)me->table[i];
141: if (l) {
142: HTList *cur = l;
1.2 ! kahan 143: keynode *kn;
1.1 frystyk 144: while ((kn = (keynode *) HTList_nextObject(cur))) {
145: if(!strcmp(key,kn->key))
146: return kn->object;
147: }
148: }
149: }
150: return NULL;
151: }
152:
153: /*
154: (
155: Size of a Hash Table
156: )
157: */
158:
1.2 ! kahan 159: PUBLIC int HTHashtable_count (HTHashtable *me)
1.1 frystyk 160: {
161: if(me)
162: return me->count;
163: return -1;
164: }
165:
166: /*
167: (
1.2 ! kahan 168: Walk all Elements in the HashTable
! 169: )
! 170: */
! 171:
! 172: PUBLIC BOOL HTHashtable_walk (HTHashtable *me,
! 173: int (*walkFunc)(HTHashtable *,char *, void *))
! 174: {
! 175: if(me) {
! 176: int i, j;
! 177: for(i = 0; i< me->size; i++) {
! 178: HTList *l = (HTList *)me->table[i];
! 179: if(l) {
! 180: HTList *cur = l;
! 181: keynode *kn, *nextkn;
! 182: for(kn = (keynode *)HTList_nextObject(cur); kn; kn = nextkn) {
! 183: j = walkFunc(me, kn->key, kn->object);
! 184: if(j == 0)
! 185: return YES;
! 186: nextkn = (keynode *)HTList_nextObject(cur);
! 187: if (j < 0) {
! 188: HTList_removeObject(l, kn);
! 189: me->count--;
! 190: }
! 191: }
! 192: }
! 193: }
! 194: return YES;
! 195: }
! 196: return NO;
! 197: }
! 198:
! 199: /*
! 200: (
1.1 frystyk 201: Extract in a dynamic array all keys of the Hash Table
202: )
203: */
204:
1.2 ! kahan 205: PUBLIC HTArray * HTHashtable_keys (HTHashtable *me)
1.1 frystyk 206: {
207: if(me) {
208: HTArray *keys = HTArray_new(me->count);
209: int i;
210:
211: for(i = 0; i< me->size; i++) {
212: HTList * l = (HTList *)me->table[i];
213: if (l) {
214: HTList *cur = l;
1.2 ! kahan 215: keynode *kn;
1.1 frystyk 216: while ((kn = (keynode *) HTList_nextObject(cur))) {
217: char * nkey = NULL;
218: StrAllocCopy(nkey,kn->key);
219: HTArray_addObject(keys,nkey);
220: }
221: }
222: }
223: return keys;
224: }
225: return NULL;
226: }
227:
228: /*
229: (
230: Print the keys of the Hash Table
231: )
232: */
233:
234: PUBLIC void HTHashtable_print (HTHashtable *me)
235: {
236: HTArray *keys = HTHashtable_keys(me);
237: int i;
238: HTPrint("Printing Hash Table of size %d\n", HTArray_size(keys));
239: for(i = 0; i< HTArray_size(keys); i++) {
240: HTPrint("Key %d %s\n",i,HTArray_data(keys)[i]);
241: }
242: for(i = 0; i< HTArray_size(keys); i++) {
243: HT_FREE(HTArray_data(keys)[i]);
244: }
245: HTArray_delete(keys);
246: }
247: