/***********************************************************************/ /* Open Visualization Data Explorer */ /* (C) Copyright IBM Corp. 1989,1999 */ /* ALL RIGHTS RESERVED */ /* This code licensed under the */ /* "IBM PUBLIC LICENSE - Open Visualization Data Explorer" */ /***********************************************************************/ #include #include #include #include #undef STATS typedef struct hashElement *HashElement; typedef struct leaf *Leaf; typedef struct directory Directory; typedef struct pageTable PageTable; typedef struct leafBlock LeafBlock; typedef struct leafCache LeafCache; #define MAX_D 24 #define LEAF_LEN 8 #define LEAF_WRAP 0x07 #define LEAF_SHIFT 3 #define MAGIC_PSEUDOKEY 0xffffffff /* * Want to make sure pages come from large arena. Each element must * contain the pseudokey, so is no smaller than 4 bytes. */ #define ELTS_PER_PAGE ((1024/sizeof(PseudoKey)) + 1) /* * Want to make sure the leaf blocks are allocated from the large arena. */ #define LEAVES_PER_BLOCK ((1024/sizeof(struct leaf)) + 1) struct hashElement { union { HashElement next; PseudoKey pseudoKey; } u; }; struct leaf { int depth; int reference; HashElement elements[LEAF_LEN]; }; struct leafBlock { LeafBlock *next; struct leaf leaves[LEAVES_PER_BLOCK]; }; struct leafCache { LeafBlock *blocks; Leaf freeList; int nextInBlock; #ifdef STATS int currLeaves, maxLeaves; #endif }; struct directory { int depth; int mask; Leaf *leaves; LeafCache leafCache; }; struct pageTable { int nPages; /* Number of pages allocated */ int nPageSlots; /* Current length of pageTable */ int nextEltNum; /* index of next available element */ int eltsPerPage; /* number of elements per page */ int pageSize; /* bytes per page */ int eltSize; /* bytes per element */ HashElement nextElt; /* pointer to next available element */ HashElement *pagePtrs; /* page pointers */ HashElement freeList; /* free list */ #ifdef STATS int currElts, maxElts; #endif }; struct hashTable { Directory directory; PageTable pageTable; int dataSize; long directoryMask; int directoryLength; int getNextPage; int getNextElement; PseudoKey (*hash)(); int (*cmp)(); #ifdef STATS int nInserts, nCollisions; int nSearches, nSuccesses, nMismatches; #endif }; #define LEAF_INDEX(pseudoKey) ((pseudoKey) & LEAF_WRAP) #define LEAF_INCREMENT(leafIndex) ((++leafIndex) & LEAF_WRAP) #define DATA_PTR(elt) (Element)(((char *)elt) + sizeof(struct hashElement)) static int maskBits[] = { 0x00000000, 0x00000001, 0x00000003, 0x00000007, 0x0000000F, 0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF, 0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF, 0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF, 0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF, 0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF, 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF }; static int powers_of_2[] = { 0x00000001, 0x00000002, 0x00000004, 0x00000008, 0x00000010, 0x00000020, 0x00000040, 0x00000080, 0x00000100, 0x00000200, 0x00000400, 0x00000800, 0x00001000, 0x00002000, 0x00004000, 0x00008000, 0x00010000, 0x00020000, 0x00040000, 0x00080000, 0x00100000, 0x00200000, 0x00400000, 0x00800000, 0x01000000, 0x02000000, 0x04000000, 0x08000000 }; static Error _initPageTable(PageTable *, int); static void _deletePageTable(PageTable *); static HashElement _getFreeElement(PageTable *); static Error _initDirectory(Directory *); static void _deleteDirectory(Directory *); static Error _InsertHash(HashTable, void *, PseudoKey); static int _InsertHashLeaf(HashTable, PseudoKey, Leaf, void *); static Error _expandHash(HashTable); static Error _splitLeaf(HashTable, int, Leaf); static HashElement _QueryHashElement(HashTable, Key); static void _initLeafCache(LeafCache *); static void _freeLeaf(LeafCache *, Leaf); static Leaf _getFreeLeaf(LeafCache *); static void _deleteLeafCache(LeafCache *); #if 0 static Error _hashCheck(HashTable); static void _freeElement(PageTable *, HashElement); #endif HashTable DXCreateHash(int dataSize, PseudoKey (*hash)(), int (*cmp)()) { HashTable hashTable; hashTable = (HashTable)DXAllocate(sizeof(struct hashTable)); if (! hashTable) return NULL; /* * Round to word boundary */ if (dataSize & 0x3) hashTable->dataSize = (dataSize & 0xffffffc) + 0x0000004; else hashTable->dataSize = dataSize; hashTable->hash = hash; hashTable->cmp = cmp; if (! _initDirectory(&hashTable->directory)) { DXFree((Pointer)hashTable); return NULL; } hashTable->directoryMask = maskBits[hashTable->directory.depth]; hashTable->directoryLength = powers_of_2[hashTable->directory.depth]; if (! _initPageTable(&hashTable->pageTable, dataSize)) { _deleteDirectory(&hashTable->directory); DXFree((Pointer)hashTable); return NULL; } #ifdef STATS hashTable->nInserts = 0; hashTable->nCollisions = 0; hashTable->nSearches = 0; hashTable->nSuccesses = 0; hashTable->nMismatches = 0; #endif return hashTable; } Error DXDestroyHash(HashTable hashTable) { if (! hashTable) return OK; _deleteDirectory(&hashTable->directory); _deletePageTable(&hashTable->pageTable); #ifdef STATS DXMessage("%d insertions, %d collisions", hashTable->nInserts, hashTable->nCollisions); DXMessage("%d searches, %d successes, %d mismatches", hashTable->nSearches, hashTable->nSuccesses, hashTable->nMismatches); #endif DXFree((Pointer)hashTable); return OK; } Element DXQueryHashElement(HashTable hashTable, Key key) { HashElement elt; #ifdef STATS hashTable->nSearches ++; #endif if (NULL == (elt = _QueryHashElement(hashTable, key))) return NULL; else { #ifdef STATS hashTable->nSuccesses ++; #endif return DATA_PTR(elt); } } Error DXDeleteHashElement(HashTable hashTable, Key key) { HashElement elt; if (NULL != (elt = _QueryHashElement(hashTable, key))) elt->u.pseudoKey = 0; return OK; } Error DXInsertHashElement(HashTable hashTable, void *data) { PseudoKey pseudoKey; int status; PseudoKey (*hash)(); #ifdef STATS hashTable->nInserts ++; #endif if (NULL == (hash = hashTable->hash)) pseudoKey = *(PseudoKey *)data; else pseudoKey = (*hash)((Key)data); /* * pseudoKey 0 is illegal. It implies that an entry is empty. * So, we increment pseudokeys by 1, unless its -1. */ if (pseudoKey == (PseudoKey)-1) { DXSetError(ERROR_INTERNAL, "invalid hash key (0xffffffff)"); return ERROR; } pseudoKey += 1; status = _InsertHash(hashTable, data, pseudoKey); return status; } Error DXInitGetNextHashElement(HashTable hashtab) { if (hashtab == NULL) return ERROR; hashtab->getNextPage = 0; hashtab->getNextElement = 0; return OK; } Element DXGetNextHashElement(HashTable hashtab) { PageTable *pagetab; HashElement element, nextelt; HashElement *pages; int pageNum, eltNum; int eltSize, eltsInPage; int nPages; if (! hashtab) return ERROR; pagetab = &hashtab->pageTable; if ((pageNum = hashtab->getNextPage) >= (nPages = pagetab->nPages)) return NULL; eltNum = hashtab->getNextElement; pages = pagetab->pagePtrs; eltSize = pagetab->eltSize; if (pageNum == nPages-1) eltsInPage = pagetab->nextEltNum; else eltsInPage = ELTS_PER_PAGE; nextelt = (HashElement)(((char *)pages[pageNum]) + eltNum*eltSize); while (pageNum < nPages) { element = nextelt; eltNum ++; if (eltNum >= eltsInPage) { eltNum = 0; if (++pageNum < nPages) { if (pageNum == nPages-1) eltsInPage = pagetab->nextEltNum; else eltsInPage = ELTS_PER_PAGE; nextelt = pages[pageNum]; } } else nextelt = (HashElement)((char *)element + eltSize); if (element->u.pseudoKey) { hashtab->getNextPage = pageNum; hashtab->getNextElement = eltNum; return DATA_PTR(element); } } return NULL; } static HashElement _QueryHashElement(HashTable hashTable, Key key) { PseudoKey pseudoKey; int bucketNum; Leaf leaf; int slot, start, found; HashElement element; PseudoKey (*hash)(); int (*cmp)(); cmp = hashTable->cmp; hash = hashTable->hash; if (hash) pseudoKey = (*hash)(key); else pseudoKey = *(PseudoKey *)key; pseudoKey += 1; bucketNum = (pseudoKey >> LEAF_SHIFT) & hashTable->directoryMask; leaf = hashTable->directory.leaves[bucketNum]; start = LEAF_INDEX(pseudoKey); found = 0; slot = start; do { if ((element = leaf->elements[slot]) == NULL) break; if ((element->u.pseudoKey == pseudoKey) && (!cmp || !(*cmp)(key, DATA_PTR(element)))) { found = 1; break; } #ifdef STATS hashTable->nMismatches ++; #endif slot = LEAF_INCREMENT(slot); } while (slot != start); if (! found) return NULL; else return element; } static Error _initPageTable(PageTable *pagetab, int dataSize) { int eltSize; eltSize = sizeof(struct hashElement) + dataSize; eltSize = (eltSize + (sizeof(long)-1)) & ~(sizeof(long)-1); pagetab->nPages = 0; pagetab->nPageSlots = 0; pagetab->eltsPerPage = ELTS_PER_PAGE; pagetab->nextEltNum = pagetab->eltsPerPage; /* force alloc of first page */ pagetab->pageSize = pagetab->eltsPerPage * eltSize; pagetab->eltSize = eltSize; pagetab->pagePtrs = NULL; pagetab->freeList = NULL; #ifdef STATS pagetab->currElts = 0; pagetab->maxElts = 0; #endif return OK; } #if 0 static void _freeElement(PageTable *pagetab, HashElement elt) { elt->u.next = pagetab->freeList; pagetab->freeList = elt; #ifdef STATS pagetab->currElts ++; #endif } #endif static HashElement _getFreeElement(PageTable *pagetab) { HashElement element; if (pagetab->freeList) { element = pagetab->freeList; pagetab->freeList = pagetab->freeList->u.next; } else { if (pagetab->nextEltNum == pagetab->eltsPerPage) { /* * If no page table slot is available, must make room for more. */ if (pagetab->nPages == pagetab->nPageSlots || !pagetab->pagePtrs) { /* * If this is the first, allocate pagePtrs table. Otherwise, * increase the size */ if (! pagetab->pagePtrs) { pagetab->nPageSlots = 1; pagetab->pagePtrs = (HashElement *)DXAllocate (pagetab->nPageSlots * sizeof(HashElement)); } else { pagetab->nPageSlots *= 2; pagetab->pagePtrs = (HashElement *)DXReAllocate( (Pointer)pagetab->pagePtrs, pagetab->nPageSlots * sizeof(HashElement)); } if (pagetab->pagePtrs == NULL) return NULL; } pagetab->pagePtrs[pagetab->nPages] = (HashElement)DXAllocate(pagetab->pageSize); if (! pagetab->pagePtrs[pagetab->nPages]) return NULL; pagetab->nextElt = pagetab->pagePtrs[pagetab->nPages]; pagetab->nextEltNum = 0; pagetab->nPages++; } element = pagetab->nextElt; pagetab->nextEltNum ++; pagetab->nextElt = (HashElement)((char *)pagetab->nextElt + pagetab->eltSize); } element->u.pseudoKey = 0; #ifdef STATS if ((++(pagetab->currElts)) > pagetab->maxElts) pagetab->maxElts = pagetab->currElts; #endif return element; } static void _deletePageTable(PageTable *pagetab) { int i; if (pagetab->pagePtrs) { for (i = 0; i < pagetab->nPages; i++) if (pagetab->pagePtrs[i]) { DXFree((Pointer)pagetab->pagePtrs[i]); pagetab->pagePtrs[i] = NULL; } DXFree((Pointer)pagetab->pagePtrs); pagetab->pagePtrs = NULL; } #ifdef STATS DXMessage("elements: %d current, %d max", pagetab->currElts, pagetab->maxElts); #endif } static Error _initDirectory(Directory *directory) { int nBuckets; _initLeafCache(&(directory->leafCache)); nBuckets = 1; directory->depth = 0; directory->mask = maskBits[0]; directory->leaves = (Leaf *)DXAllocate(nBuckets * sizeof(Leaf)); if (! directory->leaves) return ERROR; directory->leaves[0] = _getFreeLeaf(&(directory->leafCache)); directory->leaves[0]->depth = 0; directory->leaves[0]->reference = 1; return OK; } static void _deleteDirectory(Directory *directory) { _deleteLeafCache(&(directory->leafCache)); if (directory->leaves) DXFree((Pointer)directory->leaves); #ifdef STATS DXMessage("Directory length: %d", powers_of_2[directory->depth]); #endif } static Error _InsertHash(HashTable hashTable, void *data, PseudoKey pseudoKey) { int bucketNum; Leaf leaf; int found; bucketNum = (pseudoKey >> LEAF_SHIFT) & hashTable->directoryMask; leaf = hashTable->directory.leaves[bucketNum]; found = _InsertHashLeaf(hashTable, pseudoKey, leaf, data); if (found == 1) { return OK; } else if (found == 0) { /* * If leaf isn't shared, expand the directory. */ if (leaf->depth == hashTable->directory.depth) if (! _expandHash(hashTable)) return ERROR; /* * Now expand the leaf */ if (! _splitLeaf(hashTable, bucketNum, leaf)) return ERROR; /* * Now try insertion again recursively */ return _InsertHash(hashTable, data, pseudoKey); } else { return ERROR; } } static Error _expandHash(HashTable hashTable) { int oldNBuckets; int oldLength; int i; Directory *dir; dir = &hashTable->directory; oldNBuckets = powers_of_2[dir->depth]; oldLength = oldNBuckets * sizeof(Leaf *); for (i = 0; i < oldNBuckets; i++) dir->leaves[i]->reference ++; dir->leaves = (Leaf *)DXReAllocate((Pointer)dir->leaves, 2*oldLength); if (! dir->leaves) return ERROR; memcpy((char *)dir->leaves+oldLength, (char *)dir->leaves, oldLength); dir->depth ++; hashTable->directoryMask = maskBits[dir->depth]; hashTable->directoryLength = powers_of_2[dir->depth]; return OK; } static int _InsertHashLeaf(HashTable hashTable, PseudoKey pseudoKey, Leaf leaf, void *data) { int slot, start; int found; HashElement element; int (*cmp)(); cmp = hashTable->cmp; start = LEAF_INDEX(pseudoKey); /* * Look for either an empty slot in the leaf or one that * matches the key. */ found = 0; slot = start; do { element = leaf->elements[slot]; if (element == NULL || ! element->u.pseudoKey) { found = 1; break; } if ((element->u.pseudoKey == pseudoKey) && (!cmp || !(*cmp)((Key)data, DATA_PTR(element)))) { found = 1; break; } #ifdef STATS hashTable->nCollisions ++; #endif slot = LEAF_INCREMENT(slot); } while (slot != start); if (found) { if (! element) { element = _getFreeElement(&hashTable->pageTable); if (! element) return -1; } if (! element->u.pseudoKey) element->u.pseudoKey = pseudoKey; if (hashTable->dataSize) memcpy(DATA_PTR(element), data, hashTable->dataSize); leaf->elements[slot] = element; } return found; } #if 0 static Error _hashCheck(HashTable hashTable) { int nBuckets; int i, j; Directory *dir; Leaf leaf; dir = &hashTable->directory; nBuckets = powers_of_2[dir->depth]; for (i = 0; i < nBuckets; i++) { leaf = hashTable->directory.leaves[i]; for (j = 0; j < LEAF_LEN; j++) if (leaf->elements[j] != NULL && ((((int)leaf->elements[j]) < 0x00ffffff) || (((int)leaf->elements[j]) > 0x30000000))) return ERROR; } return OK; } #endif static Error _splitLeaf(HashTable hashTable, int bucketNum, Leaf leaf) { Leaf leaf0, leaf1; int mask; int i, count; HashElement elt, elt0; Leaf which; int slot, start, bit; int knt0, knt1; elt0 = leaf->elements[0]; for (i = 1; i < LEAF_LEN; i++) { elt = leaf->elements[i]; if (elt->u.pseudoKey != elt0->u.pseudoKey) break; } if (i == LEAF_LEN) { DXSetError(ERROR_INTERNAL, "excessive hash key collisions"); return NULL; } leaf0 = _getFreeLeaf(&(hashTable->directory.leafCache)); if (! leaf0) return NULL; leaf1 = _getFreeLeaf(&(hashTable->directory.leafCache)); if (! leaf1) return NULL; leaf0->depth = leaf1->depth = leaf->depth+1; mask = bucketNum & maskBits[leaf->depth]; count = powers_of_2[hashTable->directory.depth - leaf->depth]; for (i = 0; i < count; i++) { bucketNum = mask | i << leaf->depth; if (i & 0x01) { hashTable->directory.leaves[bucketNum] = leaf1; leaf1->reference ++; } else { hashTable->directory.leaves[bucketNum] = leaf0; leaf0->reference ++; } } bit = 1 << (leaf->depth + LEAF_SHIFT); knt0 = knt1 = 0; for (i = 0; i < LEAF_LEN; i++) { elt = leaf->elements[i]; start = LEAF_INDEX(elt->u.pseudoKey); if (elt->u.pseudoKey & bit) { which = leaf1; knt1++; } else { which = leaf0; knt0++; } for (slot = start; ; slot = LEAF_INCREMENT(slot)) if (! which->elements[slot]) { which->elements[slot] = elt; break; } } _freeLeaf(&(hashTable->directory.leafCache), leaf); return OK; } static void _initLeafCache(LeafCache *lc) { lc->blocks = NULL; lc->nextInBlock = -1; lc->freeList = NULL; #ifdef STATS lc->currLeaves = 0; lc->maxLeaves = 0; #endif } static void _freeLeaf(LeafCache *lc, Leaf leaf) { *((Leaf *)leaf) = lc->freeList; lc->freeList = leaf; #ifdef STATS lc->currLeaves --; #endif } static Leaf _getFreeLeaf(LeafCache *lc) { int i; Leaf leaf; if (lc->freeList) { leaf = lc->freeList; lc->freeList = *((Leaf *)leaf); } else { if (lc->blocks == NULL || lc->nextInBlock == LEAVES_PER_BLOCK) { LeafBlock *lb; lb = (LeafBlock *)DXAllocate(sizeof(struct leafBlock)); if (!lb) return NULL; lb->next = lc->blocks; lc->blocks = lb; lc->nextInBlock = 0; } leaf = lc->blocks->leaves + lc->nextInBlock++; } leaf->depth = -1; leaf->reference = 0; for (i = 0; i < LEAF_LEN; i++) leaf->elements[i] = NULL; #ifdef STATS if ((++(lc->currLeaves)) > lc->maxLeaves) lc->maxLeaves = lc->currLeaves; #endif return leaf; } static void _deleteLeafCache(LeafCache *lc) { LeafBlock *this, *next; this = lc->blocks; while(this != NULL) { next = this->next; DXFree((Pointer)this); this = next; } #ifdef STATS DXMessage("leaves: %d current, %d max", lc->currLeaves, lc->maxLeaves); #endif }