/* #define _HASH_INTERNAL_DEBUG 1 */ /*----------------------------------------------------------- * Name: hash.c * Created: Thu Sep 8 02:47:41 1994 * Author: Jonathan DeKock * DESCR: hash table functions */ #include #include /*#include */ #include #include #include #include #include /******************* Global Variables **********************/ static HASH_ErrorProc HASH_Handler = (HASH_ErrorProc) HASH_DefaultHandler; const char *HASH_errlist[] = { "unknown error", "memory error", "hash table corrupted", "invalid hash index", "invalid argument", "no member matching key", }; /* static const char *tfs[] = { "False", "True", }; */ /******************* Internal Macros ***********************/ #define tfm(a) ((a) ? tfs[1] : tfs[0]) /* Returns "True" or "False" */ /* Intrusive Macros for Next and Key */ #define NextP(h, d) *(DATA_PTR*)((char*)d + h->next_offset) #define KeyP(h, d) ((DATA_PTR) ((h->attr & HASH_EmbeddedKey) ? \ ((char*)d + h->key_offset) : \ *(DATA_PTR*)((char*)d + h->key_offset))) /*----------------------------------------------------------- * Name: HMacro_SetAttr() * Created: Mon Sep 26 19:44:16 1994 * Author: Jonathan DeKock * DESCR: sets a given attribute of list */ #define HMacro_SetAttr(h, attr, val, ptr) \ switch (attr) {\ case HASH_Intrusive:\ val = va_arg(ap, int);\ h->attr = (enum HASH_ATTR)((val) ? h->attr | HASH_Intrusive : h->attr & ~HASH_Intrusive);\ break;\ case HASH_NonIntrusive:\ val = va_arg(ap, int);\ h->attr = (enum HASH_ATTR)((!val) ? h->attr | HASH_Intrusive : h->attr & ~HASH_Intrusive);\ break;\ case HASH_EmbeddedKey:\ val = va_arg(ap, int);\ h->attr = (enum HASH_ATTR)((val) ? h->attr | HASH_EmbeddedKey : h->attr & ~HASH_EmbeddedKey);\ break;\ case HASH_ReportChange:\ val = va_arg(ap, int);\ h->attr = (enum HASH_ATTR)((val) ? h->attr | HASH_ReportChange : h->attr & ~HASH_ReportChange);\ break;\ case HASH_ReportAccess:\ val = va_arg(ap, int);\ h->attr = (enum HASH_ATTR)((val) ? h->attr | HASH_ReportAccess : h->attr & ~HASH_ReportAccess);\ break;\ case HASH_NextOffset:\ val = va_arg(ap, int);\ h->next_offset = val;\ h->attr = (enum HASH_ATTR)(h->attr | HASH_Intrusive);\ break;\ case HASH_KeyOffset:\ val = va_arg(ap, int);\ h->key_offset = val;\ break;\ case HASH_DynamicResize:\ val = va_arg(ap, int);\ h->resize = val;\ break;\ case HASH_HashFunction:\ ptr = va_arg(ap, DATA_PTR);\ h->hash = (HASH_HashProc)ptr;\ break;\ case HASH_LookupFunction:\ ptr = va_arg(ap, DATA_PTR);\ h->lookup = (HASH_LookupProc)ptr;\ break;\ case HASH_DestroyFunction:\ ptr = va_arg(ap, DATA_PTR);\ h->destroy = (HASH_DestroyProc)ptr;\ break;\ default:\ attr = 0;\ break;\ } /******************* Function Definitions ******************/ /*----------------------------------------------------------- * Name: HASH_Create() * Created: Thu Sep 8 02:53:32 1994 * Author: Jonathan DeKock * DESCR: creates a hash table */ HASH_TABLE *HASH_Create(unsigned size, int first, ...) { va_list ap; enum HASH_ATTR attr; int val; DATA_PTR ptr; HASH_TABLE *h; #ifdef HASH_DEBUG if (!size) { if (HASH_Handler) { (HASH_Handler)(NULL, HASH_BadArgument, "HASH_Create()"); } return(NULL); } #endif if (!(h = New(HASH_TABLE))) { if (HASH_Handler) { (HASH_Handler)(h, HASH_MemoryErr, "HASH_Create()"); } return(NULL); } if (!(h->array.data = NewArray(DATA_PTR, size))) { if (HASH_Handler) { (HASH_Handler)(h, HASH_MemoryErr, "HASH_Create()"); } Delete(h); return(NULL); } h->size = size; h->count = 0; h->resize = 0; h->next_offset = sizeof(DATA_PTR); h->key_offset = 0; h->attr = (enum HASH_ATTR) 0; h->hash = (HASH_HashProc)HASH_DefaultHashFunction; h->lookup = (HASH_LookupProc)HASH_DefaultLookupFunction; h->destroy = NULL; va_start(ap, first); for (attr = (enum HASH_ATTR)first; attr; attr = va_arg(ap, enum HASH_ATTR)) { HMacro_SetAttr(h, attr, val, ptr); if (!attr) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_Create()"); } Delete(h->array.data); Delete(h); va_end(ap); return(NULL); } } va_end(ap); #ifdef HASH_DEBUG if (h->attr & HASH_ReportChange) { printf("HASH TABLE: 0x%.8x Create() => %s, %s, %s\n", h, (h->attr & HASH_Intrusive) ? "Intrusive" : "Container", (h->attr & HASH_ReportChange) ? "Report Change" : "No Change Report", (h->attr & HASH_ReportAccess) ? "Report Access" : "No Access Report"); if (h->resize) printf("HASH TABLE: 0x%.8x initial size = %u, resizeable at count/size > %u\n", h, h->size, h->resize); else printf("HASH TABLE: 0x%.8x static size = %u\n", h, h->size); if (h->attr & HASH_Intrusive) { printf("HASH TABLE: 0x%.8x key offset = %u, next offset = %u\n", h, h->key_offset, h->next_offset); } else { printf("HASH TABLE: 0x%.8x key offset = %u\n", h, h->key_offset); } printf("HASH TABLE: 0x%.8x functions: hash = 0x%.8x, lookup = 0x%.8x, destroy = 0x%.8x\n", h, h->hash, h->lookup, h->destroy); } #endif #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif return(h); } /*----------------------------------------------------------- * Name: HASH_SetAttributes() * Created: Mon Sep 26 19:51:27 1994 * Author: Jonathan DeKock * DESCR: sets the attributes of the hash table */ void HASH_SetAttributes(HASH_TABLE *h, int first, ...) { va_list ap; enum HASH_ATTR attr; int val; DATA_PTR ptr; #ifdef HASH_DEBUG if (!h) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_SetAttributes()"); } return; } #endif va_start(ap, first); for (attr = (enum HASH_ATTR)first; attr; attr = va_arg(ap, enum HASH_ATTR)) { HMacro_SetAttr(h, attr, val, ptr); if (!attr) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_SetAttributes()"); } va_end(ap); return; } #ifdef HASH_DEBUG if (h->count > 0) { if (attr & (HASH_EmbeddedKey | HASH_Intrusive | HASH_NextOffset | HASH_KeyOffset | HASH_HashFunction | HASH_LookupFunction)) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_SetAttributes()"); } return; } } #endif } va_end(ap); #ifdef HASH_DEBUG if (h->attr & HASH_ReportChange) { printf("HASH TABLE: 0x%.8x SetAttributes() => %s, %s, %s\n", h, (h->attr & HASH_Intrusive) ? "Intrusive" : "Container", (h->attr & HASH_ReportChange) ? "Report Change" : "No Change Report", (h->attr & HASH_ReportAccess) ? "Report Access" : "No Access Report"); if (h->resize) printf("HASH TABLE: 0x%.8x initial size = %u, resizeable at count/size > %u\n", h, h->size, h->resize); else printf("HASH TABLE: 0x%.8x static size = %u\n", h, h->size); if (h->attr & HASH_Intrusive) { printf("HASH TABLE: 0x%.8x key offset = %u, next offset = %u\n", h, h->key_offset, h->next_offset); } else { printf("HASH TABLE: 0x%.8x key offset = %u\n", h, h->key_offset); } printf("HASH TABLE 0x%.8x functions: hash = 0x%.8x, lookup = 0x%.8x, destroy = 0x%.8x\n", h, h->hash, h->lookup, h->destroy); } #endif #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif } /*----------------------------------------------------------- * Name: HASH_GetAttributes() * Created: Mon Sep 26 19:55:21 1994 * Author: Jonathan DeKock * DESCR: retrieves the attributes of a hash table */ void HASH_GetAttributes(HASH_TABLE *h, int first, ...) { va_list ap; enum HASH_ATTR attr; DATA_PTR *ptr; int *val; unsigned short *sh; #ifdef HASH_DEBUG if (!h) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_SetAttributes()"); } return; } #endif va_start(ap, first); for (attr = (enum HASH_ATTR)first; attr; attr = va_arg(ap, enum HASH_ATTR)) { switch (attr) { case HASH_Intrusive: val = va_arg(ap, int*); *val = (h->attr & HASH_Intrusive) ? True : False; break; case HASH_NonIntrusive: val = va_arg(ap, int*); *val = (h->attr & HASH_Intrusive) ? False : True; break; case HASH_EmbeddedKey: val = va_arg(ap, int*); *val = (h->attr & HASH_EmbeddedKey) ? True : False; break; case HASH_ReportChange: val = va_arg(ap, int*); *val = (h->attr & HASH_ReportChange) ? True : False; break; case HASH_ReportAccess: val = va_arg(ap, int*); *val = (h->attr & HASH_ReportAccess) ? True : False; break; case HASH_NextOffset: sh = va_arg(ap, unsigned short *); *sh = (h->attr & HASH_NextOffset) ? True : False; break; case HASH_KeyOffset: sh = va_arg(ap, unsigned short *); *sh = (h->attr & HASH_KeyOffset) ? True : False; break; case HASH_DynamicResize: val = va_arg(ap, int*); *val = h->resize; break; case HASH_HashFunction: ptr = va_arg(ap, DATA_PTR*); *ptr = (DATA_PTR)h->hash; break; case HASH_LookupFunction: ptr = va_arg(ap, DATA_PTR*); *ptr = (DATA_PTR)h->lookup; break; case HASH_DestroyFunction: ptr = va_arg(ap, DATA_PTR*); *ptr = (DATA_PTR)h->destroy; break; default: if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_GetAttributes()"); } va_end(ap); return; } } va_end(ap); #ifdef HASH_DEBUG if (h->attr & HASH_ReportAccess) { printf("HASH TABLE: 0x%.8x GetAttributes() => %s, %s, %s\n", h, (h->attr & HASH_Intrusive) ? "Intrusive" : "Container", (h->attr & HASH_ReportChange) ? "Report Change" : "No Change Report", (h->attr & HASH_ReportAccess) ? "Report Access" : "No Access Report"); if (h->resize) printf("HASH TABLE: 0x%.8x initial size = %u, resizeable at count/size > %u\n", h, h->size, h->resize); else printf("HASH TABLE: 0x%.8x static size = %u\n", h, h->size); if (h->attr & HASH_Intrusive) { printf("HASH TABLE: 0x%.8x key offset = %u, next offset = %u\n", h, h->key_offset, h->next_offset); } else { printf("HASH TABLE: 0x%.8x key offset = %u\n", h, h->key_offset); } printf("HASH TABLE 0x%.8x functions: hash = 0x%.8x, lookup = 0x%.8x, destroy = 0x%.8x\n", h, h->hash, h->lookup, h->destroy); } #endif #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif } /*----------------------------------------------------------- * Name: HASH_ChangeSize() * Created: Mon Sep 26 20:09:16 1994 * Author: Jonathan DeKock * DESCR: modifies the size of the hash table to x */ void HASH_ChangeSize(HASH_TABLE *h, unsigned size) { unsigned index; #ifdef HASH_DEBUG if (!h || !size) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_ChangeSize()"); } } if (h->attr & HASH_ReportChange) { printf("HASH TABLE: 0x%.8x Resizing to %u slots\n", h, size); } #endif if (h->attr & HASH_Intrusive) { DATA_PTR *array = NewArray(DATA_PTR, size); DATA_PTR moving; unsigned old; if (!array) { if (HASH_Handler) { (HASH_Handler)(h, HASH_MemoryErr, "HASH_ChangeSize()"); } return; } else { for (old = 0; old < h->size; old++) { while ((moving = h->array.data[old])) { h->array.data[old] = NextP(h, moving); index = (h->hash)(KeyP(h, moving), size); #ifdef HASH_DEBUG if (index >= size) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadIndex, "HASH_ChangeSize()"); } return; } #endif NextP(h, moving) = array[index]; array[index] = moving; } } Delete(h->array.data); h->array.data = array; } } else { HASH_CONTAINER **array = NewArray(HASH_CONTAINER*, size); HASH_CONTAINER *moving; unsigned old; if (!array) { if (HASH_Handler) { (HASH_Handler)(h, HASH_MemoryErr, "HASH_ChangeSize()"); } return; } else { for (old = 0; old < h->size; old++) { while ((moving = h->array.cont[old])) { h->array.cont[old] = moving->next; index = (h->hash)(KeyP(h, moving->data), size); #ifdef HASH_DEBUG if (index >= size) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadIndex, "HASH_ChangeSize()"); } return; } #endif moving->next = array[index]; array[index] = moving; } } Delete(h->array.cont); h->array.cont = array; } } h->size = size; } /*----------------------------------------------------------- * Name: HASH_ClearFn() * Created: Thu Sep 8 14:56:40 1994 * Author: Jonathan DeKock * DESCR: clears all items from a hash table */ void HASH_ClearFn(HASH_TABLE* h, HASH_DestroyProc destroy) { int index; #ifdef HASH_DEBUG if (!h) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_Clear()"); } return; } #endif if (h->attr & HASH_Intrusive) { DATA_PTR data; for (index = 0; index < h->size; index++) { /* Run thru all the indicies */ while ((data = h->array.data[index])) { /* each item on list */ h->array.data[index] = NextP(h, data); #ifdef HASH_DEBUG NextP(h, data) = NULL; #endif if (destroy) { (destroy)(data); } } } } else { HASH_CONTAINER *cont; for (index = 0; index < h->size; index++) { /* Run thru all the indicies */ while ((cont = h->array.cont[index])) { /* each item on list */ h->array.cont[index] = cont->next; if (destroy) { (destroy)(cont->data); } #ifdef HASH_DEBUG cont->next = NULL; cont->data = NULL; #endif Delete(cont); } } } h->count = 0; #ifdef HASH_DEBUG if (h->attr & HASH_ReportChange) { printf("HASH TABLE: 0x%.8x Clear(0x%.8x)\n", h, destroy); } #endif #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif } /*----------------------------------------------------------- * Name: HASH_DestroyFn() * Created: Thu Sep 8 15:10:10 1994 * Author: Jonathan DeKock * DESCR: completely destroys a hash table */ void HASH_DestroyFn(HASH_TABLE* h, HASH_DestroyProc destroy) { #ifdef HASH_DEBUG if (!h) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_Clear()"); } return; } #endif HASH_ClearFn(h, destroy); Delete(h->array.data); #ifdef HASH_DEBUG if (h->attr & HASH_ReportChange) { printf("HASH TABLE: 0x%.8x Destroy(0x%.8x)\n", h, destroy); } #endif Delete(h); } /*----------------------------------------------------------- * Name: HASH_Insert() * Created: Thu Sep 8 15:37:07 1994 * Author: Jonathan DeKock * DESCR: insert an item into a table */ DATA_PTR HASH_Insert(HASH_TABLE* h, DATA_PTR data) { DATA_PTR key; unsigned index; #ifdef HASH_DEBUG if (!h || !data) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_Insert()"); } return(NULL); } #endif key = KeyP(h, data); #ifdef HASH_DEBUG if (!key) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_Insert()"); } return(NULL); } #endif /* check if we are going to have to re-hash the entire thing (dynamic) */ if ((h->resize) && (h->count >= (h->resize)*(h->size))) { /* we must resize */ unsigned new_size = h->size*2; HASH_ChangeSize(h, new_size); } index = (h->hash)(key, h->size); #ifdef HASH_DEBUG if (index >= h->size) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadIndex, "HASH_Insert()"); } return(NULL); } #endif if (h->attr & HASH_Intrusive) { NextP(h, data) = h->array.data[index]; h->array.data[index] = data; } else { HASH_CONTAINER *cont = New(HASH_CONTAINER); if (!cont) { if (HASH_Handler) { (HASH_Handler)(h, HASH_MemoryErr, "HASH_Insert()"); } return(NULL); } cont->data = data; cont->next = h->array.cont[index]; h->array.cont[index] = cont; } h->count++; #ifdef HASH_DEBUG if (h->attr & HASH_ReportChange) { printf("HASH TABLE: 0x%.8x Insert(0x%.8x, 0x%.8x) (%u) count = %u\n", h, data, key, index, h->count); } #endif #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif return(data); } /*----------------------------------------------------------- * Name: HASH_RemoveFn() * Created: Thu Sep 8 16:11:12 1994 * Author: Jonathan DeKock * DESCR: removes an item from a hash table given key */ void HASH_RemoveFn(HASH_TABLE *h, DATA_PTR data, HASH_DestroyProc destroy) { unsigned index; #ifdef HASH_DEBUG if (!h || !data) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_Remove()"); } return; } #endif index = (h->hash)(KeyP(h, data), h->size); #ifdef HASH_DEBUG if (index >= h->size) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadIndex, "HASH_Remove()"); } return; } #endif if (h->attr & HASH_Intrusive) { DATA_PTR tmp, prev; /* Find Prev */ for (tmp = h->array.data[index], prev = NULL; tmp; prev = tmp, tmp = NextP(h, tmp)) { if (tmp == data) break; } #ifdef HASH_DEBUG if (!tmp) { if (HASH_Handler) { (HASH_Handler)(h, HASH_NoMember, "HASH_Remove()"); } return; } #endif if (prev) { NextP(h, prev) = NextP(h, data); } else { h->array.data[index] = NextP(h, data); } #ifdef HASH_DEBUG NextP(h, data) = NULL; #endif if (destroy) { (destroy)(data); } } else { HASH_CONTAINER *cont, *prev; for (cont = h->array.cont[index], prev = NULL; cont; prev = cont, cont = cont->next) { if (cont->data == data) break; } #ifdef HASH_DEBUG if (!cont) { if (HASH_Handler) { (HASH_Handler)(h, HASH_NoMember, "HASH_Remove()"); } return; } #endif if (prev) { prev->next = cont->next; } else { h->array.cont[index] = cont->next; } if (destroy) { (destroy)(cont->data); } #ifdef HASH_DEBUG cont->next = NULL; cont->data = NULL; #endif Delete(cont); } h->count--; #ifdef HASH_DEBUG if (h->attr & HASH_ReportChange) { printf("HASH TABLE: 0x%.8x Remove(0x%.8x, 0x%.8x) count = %u\n", h, data, destroy, h->count); } #endif #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif } /*----------------------------------------------------------- * Name: HASH_RemoveByKeyFn() * Created: Thu Sep 8 16:11:12 1994 * Author: Jonathan DeKock * DESCR: removes an item from a hash table given key */ void HASH_RemoveByKeyFn(HASH_TABLE *h, DATA_PTR key, HASH_DestroyProc destroy) { unsigned index; DATA_PTR data; #ifdef HASH_DEBUG if (!h || !key) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_RemoveByKey()"); } return; } #endif index = (h->hash)(key, h->size); #ifdef HASH_DEBUG if (index >= h->size) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadIndex, "HASH_RemoveByKey()"); } return; } #endif if (h->attr & HASH_Intrusive) { DATA_PTR prev; for (data = h->array.data[index], prev = NULL; data; prev = data, data = NextP(h, data)) { if ((h->lookup)(KeyP(h, data), key)) break; /* found it */ } #ifdef HASH_DEBUG if (!data) { if (HASH_Handler) { (HASH_Handler)(h, HASH_NoMember, "HASH_RemoveByKey()"); } return; } #endif if (prev) { NextP(h, prev) = NextP(h, data); } else { h->array.data[index] = NextP(h, data); } #ifdef HASH_DEBUG NextP(h, data) = NULL; #endif if (destroy) { (destroy)(data); } } else { HASH_CONTAINER *cont, *prev; for (cont = h->array.cont[index], prev = NULL; cont; prev = cont, cont = cont->next) { if ((h->lookup)(KeyP(h, cont->data), key)) break; /* Found it */ } #ifdef HASH_DEBUG if (!cont) { if (HASH_Handler) { (HASH_Handler)(h, HASH_NoMember, "HASH_Remove()"); } return; } #endif if (!cont) /* JW 6/1/98 fix for case when item not found */ return; if (prev) { prev->next = cont->next; } else { h->array.cont[index] = cont->next; } data = cont->data; if (destroy) { (destroy)(cont->data); } #ifdef HASH_DEBUG cont->next = NULL; cont->data = NULL; #endif Delete(cont); } h->count--; #ifdef HASH_DEBUG if (h->attr & HASH_ReportChange) { printf("HASH TABLE: 0x%.8x RemoveByKey(0x%.8x, 0x%.8x) %u => 0x%.8x, count = %u\n", h, key, destroy, index, data, h->count); } #endif #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif } /*----------------------------------------------------------- * Name: HASH_ReHash() * Created: Thu Sep 8 17:09:25 1994 * Author: Jonathan DeKock * DESCR: re-hashes an item, due to change in key. */ void HASH_ReHash(HASH_TABLE *h, DATA_PTR data, DATA_PTR old_key) { unsigned index; DATA_PTR key; #ifdef HASH_DEBUG if (!h || !data || !old_key) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_ReHash()"); } return; } #endif key = KeyP(h, data); #ifdef HASH_DEBUG if (!key) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_ReHash()"); } return; } #endif index = (h->hash)(old_key, h->size); #ifdef HASH_DEBUG if (index >= h->size) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadIndex, "HASH_ReHash()"); } return; } #endif if (h->attr & HASH_Intrusive) { DATA_PTR prev, tmp; for (tmp = h->array.data[index], prev = NULL; tmp && tmp != data; prev = tmp, tmp = NextP(h, tmp)); #ifdef HASH_DEBUG if (tmp) { if (HASH_Handler) { (HASH_Handler)(h, HASH_NoMember, "HASH_ReHash()"); } return; } #endif if (prev) { NextP(h, prev) = NextP(h, data); } else { h->array.data[index] = NextP(h, data); } NextP(h, data) = NULL; index = (h->hash)(key, h->size); #ifdef HASH_DEBUG if (index >= h->size) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadIndex, "HASH_ReHash()"); } return; } #endif if (h->array.data[index]) NextP(h, data) = h->array.data[index]; h->array.data[index] = data; } else { HASH_CONTAINER *prev, *tmp; for (tmp = h->array.cont[index], prev = NULL; tmp && tmp->data != data; prev = tmp, tmp = tmp->next); #ifdef HASH_DEBUG if (tmp) { if (HASH_Handler) { (HASH_Handler)(h, HASH_NoMember, "HASH_Remove()"); } return; } #endif if (prev) { prev->next = tmp->next; } else { h->array.cont[index] = tmp->next; } tmp->next = NULL; index = (h->hash)(key, h->size); #ifdef HASH_DEBUG if (index >= h->size) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadIndex, "HASH_Remove()"); } return; } #endif if (h->array.cont[index]) tmp->next = h->array.cont[index]; h->array.cont[index] = tmp; } #ifdef HASH_DEBUG if (h->attr & HASH_ReportChange) { printf("HASH TABLE: 0x%.8x ReHash(0x%.8x, 0x%.8x, 0x%.8x)\n", h, data, old_key, key); } #endif #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif } /*----------------------------------------------------------- * Name: HASH_Lookup() * Created: Thu Sep 8 20:23:56 1994 * Author: Jonathan DeKock * DESCR: looks up an item in the hash table */ DATA_PTR HASH_Lookup(HASH_TABLE* h, DATA_PTR key) { unsigned index; DATA_PTR data; #ifdef HASH_DEBUG if (!h || !key) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_Lookup()"); } return(NULL); } #endif index = (h->hash)(key, h->size); #ifdef HASH_DEBUG if (index >= h->size) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadIndex, "HASH_Lookup()"); } return(NULL); } #endif if (h->attr & HASH_Intrusive) { for (data = h->array.data[index]; data; data = NextP(h, data)) { if ((h->lookup)(KeyP(h, data), key)) break; } } else { HASH_CONTAINER *cont; for (cont = h->array.cont[index]; cont; cont = cont->next) { if ((h->lookup)(KeyP(h, cont->data), key)) break; } if (cont) data = cont->data; else data = NULL; } #ifdef HASH_DEBUG if (h->attr & HASH_ReportAccess) { if (data) printf("HASH TABLE: 0x%.8x Lookup(0x%.8x) = 0x%.8x\n", h, key, data); else printf("HASH TABLE: 0x%.8x Lookup(0x%.8x) = NULL\n", h, key); } #endif #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif return(data); } /*----------------------------------------------------------- * Name: HASH_Process() * Created: Thu Sep 8 20:33:11 1994 * Author: Jonathan DeKock * DESCR: runs function on every item in table */ void HASH_Process(HASH_TABLE *h, HASH_ProcessProc fn) { unsigned index; #ifdef HASH_DEBUG if (!h || !fn) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_Process()"); } return; } if (h->attr & HASH_ReportAccess) { printf("HASH TABLE: 0x%.8x Process(0x%.8x) started\n", h, fn); } #endif if (h->attr & HASH_Intrusive) { DATA_PTR data; for (index = 0; index < h->size; index++) { for (data = h->array.data[index]; data; data = NextP(h, data)) { (fn)(data); } } } else { HASH_CONTAINER *cont; for (index = 0; index < h->size; index++) { for (cont = h->array.cont[index]; cont; cont = cont->next) { (fn)(cont->data); } } } #ifdef HASH_DEBUG if (h->attr & HASH_ReportAccess) { printf("HASH TABLE: 0x%.8x Process(0x%.8x) complete\n", h, fn); } #endif #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif } /*----------------------------------------------------------- * Name: HASH_ProcessPlus() * Created: Thu Sep 8 20:42:48 1994 * Author: Jonathan DeKock * DESCR: process a hash table with second argument */ void HASH_ProcessPlus(HASH_TABLE *h, HASH_ProcessPlusProc fn, DATA_PTR arg2) { unsigned index; #ifdef HASH_DEBUG if (!h || !fn) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_ProcessPlus()"); } return; } if (h->attr & HASH_ReportAccess) { printf("HASH TABLE: 0x%.8x ProcessPlus(0x%.8x, 0x%.8x) started\n", h, fn, arg2); } #endif if (h->attr & HASH_Intrusive) { DATA_PTR data; for (index = 0; index < h->size; index++) { for (data = h->array.data[index]; data; data = NextP(h, data)) { (fn)(data, arg2); } } } else { HASH_CONTAINER *cont; for (index = 0; index < h->size; index++) { for (cont = h->array.cont[index]; cont; cont = cont->next) { (fn)(cont->data, arg2); } } } #ifdef HASH_DEBUG if (h->attr & HASH_ReportAccess) { printf("HASH TABLE: 0x%.8x ProcessPlus(0x%.8x, 0x%.8x) complete\n", h, fn, arg2); } #endif #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif } /*----------------------------------------------------------- * Name: HASH_GetNext() * Created: Thu Sep 8 20:46:38 1994 * Author: Jonathan DeKock * DESCR: iteration support for hash tables * Modified to have last_cont in HASH_TABLE, instead of static. * still we CAN NOT do HASH_Iterate on the same hash_table, though. */ DATA_PTR HASH_GetNext(HASH_TABLE *h, DATA_PTR current) { unsigned index; DATA_PTR data; HASH_CONTAINER *cont = NULL; #ifdef HASH_DEBUG if (!h) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_Iterate()"); } return(NULL); } #endif if (!current) { /* Find first item */ for (index = 0; ((index < h->size) && (!(h->array.data[index]))); index++); if (index < h->size) { if (h->attr & HASH_Intrusive) { data = h->array.data[index]; } else { cont = h->array.cont[index]; data = cont->data; } } else { data = NULL; /* table is empty */ } } else { if (h->attr & HASH_Intrusive) { data = NextP(h, current); if (!data) { /* current was last one on last_index */ index = (h->hash)(KeyP(h, current), h->size); #ifdef HASH_DEBUG if (index >= h->size) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadIndex, "HASH_Iterate()"); } return(NULL); } #endif for (index++; ((index < h->size) && (!(h->array.data[index]))); index++); if (index < h->size) data = h->array.data[index]; else data = NULL; /* current was last one in table */ } } else { #if 0 HASH_CONTAINER *cont; #endif if ((h->last_cont) && (h->last_cont->data == current)) cont = h->last_cont; else { /* LAST_CONTAINER is messed up ?? */ index = (h->hash)(KeyP(h, current), h->size); /* get index of current and find its cont */ #ifdef HASH_DEBUG if (index >= h->size) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadIndex, "HASH_Iterate()"); } return(NULL); } #endif for (cont = h->array.cont[index]; ((cont) && (cont->data != current)); cont = cont->next); } #ifdef HASH_DEBUG if (!cont) { /* failed to find current's container must have been deleted!!!! */ if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_Iterate()"); } return(NULL); } #endif if (!cont->next) { /* current was last one in index */ index = (h->hash)(KeyP(h, cont->data), h->size); for (index++; ((index < h->size) && (!(h->array.cont[index]))); index++); if (index < h->size) cont = h->array.cont[index]; else cont = NULL; /* current is the absolute LAST */ } else { cont = cont->next; } if (cont) data = cont->data; else data = NULL; } } h->last_cont = cont; #ifdef HASH_DEBUG if (h->attr & HASH_ReportAccess) { printf("HASH TABLE: 0x%.8x Iterate() currently at 0x%.8x\n", h, data); } #endif #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif return(data); } /*----------------------------------------------------------- * Name: HASH_ToArray() * Created: Thu Sep 8 23:49:47 1994 * Author: Jonathan DeKock * DESCR: reallocates array and coverts the hash table into it */ DATA_PTR *HASH_ToArray(HASH_TABLE *h, DATA_PTR *array, unsigned *size) { unsigned index; unsigned array_index = 0; #ifdef HASH_DEBUG if (!h) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_ToArray()"); } } #endif if (!array) { array = NewArray(DATA_PTR, h->count); if (!array) { if (HASH_Handler) { (HASH_Handler)(h, HASH_MemoryErr, "HASH_ToArray()"); } return(NULL); } } if (h->attr & HASH_Intrusive) { DATA_PTR data; for (index = 0; index < h->size; index++) { for (data = h->array.data[index]; data; data = NextP(h, data)) { array[array_index++] = data; } } } else { HASH_CONTAINER *cont; for (index = 0; index < h->size; index++) { for (cont = h->array.cont[index]; cont; cont = cont->next) { array[array_index++] = cont->data; } } } #ifdef HASH_DEBUG if (h->attr & HASH_ReportAccess) { printf("HASH TABLE: 0x%.8x ToArray(0x%.8x, %u) count\n", h, array, h->count); } #endif if (size) *size = h->count; #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif return(array); } /*----------------------------------------------------------- * Name: HASH_FromArray() * Created: Thu Sep 8 23:53:36 1994 * Author: Jonathan DeKock * DESCR: converts an array to a hash table */ HASH_TABLE *HASH_FromArray(HASH_TABLE *h, DATA_PTR *array, unsigned size) { unsigned index; #ifdef HASH_DEBUG if (!array) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_FromArray()"); } } #endif if (!h) { h = HASH_Create(size, 0); /* create default hash table */ } else { HASH_ClearFn(h, NULL); } for (index = 0; index < size; index++) { HASH_Insert(h, array[index]); } #ifdef HASH_DEBUG if (h->attr & HASH_ReportChange) { printf("HASH TABLE: 0x%.8x FromArray(0x%.8x, %u) complete\n", h, array, h->count); } #endif #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif return(h); } /*----------------------------------------------------------- * Name: HASH_ToLinkedList() * Created: Fri Sep 9 00:01:14 1994 * Author: Jonathan DeKock * DESCR: converts a hash table to a linked list */ LINKED_LIST *HASH_ToLinkedList(HASH_TABLE *h, LINKED_LIST *ll) { unsigned index; #ifdef HASH_DEBUG if (!h) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_ToLinkedList()"); } } #endif if (!ll) ll = LL_Create(0); if (h->attr & HASH_Intrusive) { DATA_PTR data; for (index = 0; index < h->size; index++) { for (data = h->array.data[index]; data; data = NextP(h, data)) { LL_Add(ll, data); } } } else { HASH_CONTAINER *cont; for (index = 0; index < h->size; index++) { for (cont = h->array.cont[index]; cont; cont = cont->next) { LL_Add(ll, cont->data); } } } #ifdef HASH_DEBUG if (h->attr & HASH_ReportAccess) { printf("HASH TABLE: 0x%.8x ToLinkedList(0x%.8x) complete\n", h, ll); } #endif #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif return(ll); } /*----------------------------------------------------------- * Name: HASH_FromLinkedList() * Created: Fri Sep 9 00:04:37 1994 * Author: Jonathan DeKock * DESCR: converts a linked list into a hash table */ HASH_TABLE *HASH_FromLinkedList(HASH_TABLE *h, LINKED_LIST *ll) { DATA_PTR data; #ifdef HASH_DEBUG if (!ll) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_FromLinkedList()"); } } #endif if (!h) { h = HASH_Create(ll->count, 0); /* create default hash table */ } else { HASH_ClearFn(h, NULL); } LL_Iterate(ll, data) { HASH_Insert(h, data); } #ifdef HASH_DEBUG if (h->attr & HASH_ReportChange) { printf("HASH TABLE: 0x%.8x FromLinkedList(0x%.8x, %u) complete\n", h, ll, h->key_offset); } #endif #ifdef _HASH_INTERNAL_DEBUG HASH_Verify(h); #endif return(h); } /*----------------------------------------------------------- * Name: HASH_SetHandler() * Created: Fri Sep 9 00:12:23 1994 * Author: Jonathan DeKock * DESCR: sets the hash table handler */ HASH_ErrorProc HASH_SetHandler(HASH_ErrorProc fn, char *name) { HASH_ErrorProc tmp; #ifdef HASH_DEBUG if (name) printf("HASH TABLE: Handler changed to %s() = 0x%.8x\n", name, fn); if (name) printf("HASH TABLE: Handler changed to = 0x%.8x\n", fn); #endif tmp = HASH_Handler; HASH_Handler = fn; return(tmp); } /*----------------------------------------------------------- * Name: HASH_DefaultHandler() * Created: Fri Sep 9 00:13:56 1994 * Author: Jonathan DeKock * DESCR: default Handler for a hash table */ void HASH_DefaultHandler(HASH_TABLE *h, enum HASH_ERROR num, char *fn) { #ifdef HASH_DEBUG FILE *out = stdout; #else FILE *out = stderr; #endif fflush(stdout); fflush(stderr); fprintf(out, "HASH TABLE: 0x%.8x Error in function %s: \"%s\"\n", (u_int)h, fn, HASH_errlist[num]); fflush(out); } /*----------------------------------------------------------- * Name: HASH_Verify() * Created: Wed Sep 14 13:58:27 1994 * Author: Jonathan DeKock * DESCR: verifies a hash table */ int HASH_Verify(HASH_TABLE *h) { int ret = 1; unsigned index; unsigned count = 0; if (h->attr & HASH_Intrusive) { DATA_PTR data; for (index = 0; index < h->size; index++) { for (data = h->array.data[index]; data; data = NextP(h, data)) { count++; /* check that key hashes to index */ if (((h->hash)(KeyP(h, data), h->size)) != index) { ret = 0; #ifdef _HASH_INTERNAL_DEBUG printf("HASH TABLE: 0x%.8x Verify() found 0x%.8x (key 0x%.8x = %u) incorrectly hashed at %u\n", h, data, KeyP(h, data), (h->hash)(KeyP(h, data),h->size), index); #endif if (HASH_Handler) { (HASH_Handler)(h, HASH_TableCorrupted, "HASH_Verify()"); } } } } } else { HASH_CONTAINER *cont; for (index = 0; index < h->size; index++) { for (cont = h->array.cont[index]; cont; cont = cont->next) { count++; if (!cont->data) { ret = 0; #ifdef _HASH_INTERNAL_DEBUG printf("HASH TABLE: 0x%.8x Verify() found container 0x%.8x without data\n", h, cont); #endif if (HASH_Handler) { (HASH_Handler)(h, HASH_TableCorrupted, "HASH_Verify()"); } } /* check that key hashes to index */ if (((h->hash)(KeyP(h, cont->data), h->size)) != index) { ret = 0; #ifdef _HASH_INTERNAL_DEBUG printf("HASH TABLE: 0x%.8x Verify() found 0x%.8x (key 0x%.8x = %u) incorrectly hashed at %u\n", h, cont->data, KeyP(h, cont->data), (h->hash)(KeyP(h, cont->data), h->size), index); #endif if (HASH_Handler) { (HASH_Handler)(h, HASH_TableCorrupted, "HASH_Verify()"); } } } } } if (count != h->count) { ret = 0; #ifdef _HASH_INTERNAL_DEBUG printf("HASH TABLE: 0x%.8x Verify() found count incorrect at %u, table thinks %u\n", h, count, h->count); #endif if (HASH_Handler) { (HASH_Handler)(h, HASH_TableCorrupted, "HASH_Verify()"); } } #ifdef _HASH_INTERNAL_DEBUG if (!ret) printf("HASH TABLE: 0x%.8x is NOT valid\n", h); #endif return(ret); } /*----------------------------------------------------------- * Name: HASH_Print() * Created: Fri Sep 9 00:18:24 1994 * Author: Jonathan DeKock * DESCR: prints a table out. */ void HASH_Print(HASH_TABLE *h, HASH_PrintProc print) { unsigned index; if (!print) print = (HASH_PrintProc) HASH_DefaultPrinter; HASH_Verify(h); printf("HASH TABLE: 0x%.8x attributes: %s, %s, %s\n", (u_int)h, (h->attr & HASH_Intrusive) ? "Intrusive" : "Container", (h->attr & HASH_ReportChange) ? "Report Change" : "No Change Report", (h->attr & HASH_ReportAccess) ? "Report Access" : "No Access Report"); if (h->resize) printf("HASH TABLE: 0x%.8x initial size = %u, resizeable at count/size > %u\n", (u_int)h, h->size, h->resize); else printf("HASH TABLE: 0x%.8x static size = %u\n", (u_int)h, h->size); if (h->attr & HASH_Intrusive) { printf("HASH TABLE: 0x%.8x key offset = %u, next offset = %u\n", (u_int)h, h->key_offset, h->next_offset); } else { printf("HASH TABLE: 0x%.8x key offset = %u\n", (u_int)h, h->key_offset); } printf("HASH TABLE: 0x%.8x functions: hash = 0x%.8x, lookup = 0x%.8x, destroy = 0x%.8x\n", (u_int)h, (u_int)h->hash, (u_int)h->lookup, (u_int)h->destroy); if (h->attr & HASH_Intrusive) { DATA_PTR data; for (index = 0; index < h->size; index++) { for (data = h->array.data[index]; data; data = NextP(h, data)) { (print)(index, data, KeyP(h, data)); } } } else { HASH_CONTAINER *cont; for (index = 0; index < h->size; index++) { for (cont = h->array.cont[index]; cont; cont = cont->next) { (print)(index, cont->data, KeyP(h, cont->data)); } } } } /*----------------------------------------------------------- * Name: HASH_DefaultPrinter() * Created: Wed Sep 14 13:56:13 1994 * Author: Jonathan DeKock * DESCR: default printer for hash table elt */ void HASH_DefaultPrinter(unsigned index, DATA_PTR data, DATA_PTR key) { printf("%3d: 0x%.8x key = 0x%.8x = \"%s\"\n", index, (u_int)data, (u_int)key, (char *)key); } /*----------------------------------------------------------- * Name: HASH_GetContainer() * Created: Thu Sep 15 20:37:36 1994 * Author: Jonathan DeKock * DESCR: gets a hash's container */ HASH_CONTAINER *HASH_GetContainer(HASH_TABLE *h, DATA_PTR data) { HASH_CONTAINER *cont = NULL; unsigned index; #ifdef HASH_DEBUG if (!h || !data) { if (HASH_Handler) { (HASH_Handler)(h, HASH_BadArgument, "HASH_GetContainer()"); } return(NULL); } if (h->attr & HASH_Intrusive) { if (HASH_Handler) { (HASH_Handler)(h, HASH_TableCorrupted, "HASH_GetContainer()"); } return(NULL); } #endif for (index = 0; index < h->size; index++) { for (cont = h->array.cont[index]; cont; cont = cont->next) { if (cont->data == data) break; } if (cont) break; } return(cont); } /*----------------------------------------------------------- * Name: HASH_DefaultHashFunction() * Created: Fri Sep 9 00:50:26 1994 * Author: Jonathan DeKock * DESCR: attempts to randomly hash a character string */ unsigned HASH_DefaultHashFunction(char *key, unsigned size) { register unsigned long int ret = 0; do { ret = ((ret << 1) ^ (((unsigned)*key)*31)); } while (*(++key)); return(ret%size); } /*----------------------------------------------------------- * Name: HASH_DefaultLookupFunction() * Created: Fri Sep 9 01:06:56 1994 * Author: Jonathan DeKock * DESCR: lookup function for char strings */ int HASH_DefaultLookupFunction(char *k1, char *k2) { for (; ((*k1) && ((*k1) == (*k2))); k1++, k2++); return(!(*k1 | *k2)); } .