Annotation of libwww/Library/src/HTHash.c, revision 1.1
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: int i = 0;
! 43: if (me) {
! 44: for(i = 0; i< me->size; i++) {
! 45: HTList * l = (HTList *)me->table[i];
! 46: if (l) {
! 47: HTList *cur = l;
! 48: keynode *kn = NULL;
! 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:
! 81: PUBLIC BOOL HTHashtable_addObject (HTHashtable *me, const char *key ,
! 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];
! 88: keynode *kn = NULL;
! 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: }
! 101: /*
! 102: (
! 103: Search for an Element in a Hash Table
! 104: )
! 105: */
! 106:
! 107: PUBLIC void *HTHashtable_object (HTHashtable * me, const char *key)
! 108: {
! 109: if(me) {
! 110: int size = me->size;
! 111: int i = hash_number(key,size);
! 112: HTList * l = (HTList *)me->table[i];
! 113: if (l) {
! 114: HTList *cur = l;
! 115: keynode *kn = NULL;
! 116: while ((kn = (keynode *) HTList_nextObject(cur))) {
! 117: if(!strcmp(key,kn->key))
! 118: return kn->object;
! 119: }
! 120: }
! 121: }
! 122: return NULL;
! 123: }
! 124:
! 125: /*
! 126: (
! 127: Size of a Hash Table
! 128: )
! 129: */
! 130:
! 131: PUBLIC int HTHashtable_count (HTHashtable *me)
! 132: {
! 133: if(me)
! 134: return me->count;
! 135: return -1;
! 136: }
! 137:
! 138: /*
! 139: (
! 140: Extract in a dynamic array all keys of the Hash Table
! 141: )
! 142: */
! 143:
! 144:
! 145: PUBLIC HTArray * HTHashtable_keys (HTHashtable *me)
! 146: {
! 147: if(me) {
! 148: HTArray *keys = HTArray_new(me->count);
! 149: int i;
! 150:
! 151: for(i = 0; i< me->size; i++) {
! 152: HTList * l = (HTList *)me->table[i];
! 153: if (l) {
! 154: HTList *cur = l;
! 155: keynode *kn = NULL;
! 156: while ((kn = (keynode *) HTList_nextObject(cur))) {
! 157: char * nkey = NULL;
! 158: StrAllocCopy(nkey,kn->key);
! 159: HTArray_addObject(keys,nkey);
! 160: }
! 161: }
! 162: }
! 163: return keys;
! 164: }
! 165: return NULL;
! 166: }
! 167:
! 168: /*
! 169: (
! 170: Print the keys of the Hash Table
! 171: )
! 172: */
! 173:
! 174: PUBLIC void HTHashtable_print (HTHashtable *me)
! 175: {
! 176: HTArray *keys = HTHashtable_keys(me);
! 177: int i;
! 178: HTPrint("Printing Hash Table of size %d\n", HTArray_size(keys));
! 179: for(i = 0; i< HTArray_size(keys); i++) {
! 180: HTPrint("Key %d %s\n",i,HTArray_data(keys)[i]);
! 181: }
! 182: for(i = 0; i< HTArray_size(keys); i++) {
! 183: HT_FREE(HTArray_data(keys)[i]);
! 184: }
! 185: HTArray_delete(keys);
! 186: }
! 187:
Webmaster