1 /***********************************************************************/
2 /* Open Visualization Data Explorer */
3 /* (C) Copyright IBM Corp. 1989,1999 */
4 /* ALL RIGHTS RESERVED */
5 /* This code licensed under the */
6 /* "IBM PUBLIC LICENSE - Open Visualization Data Explorer" */
7 /***********************************************************************/
8
9 #include <dxconfig.h>
10
11 #include <string.h>
12 #include <stdio.h>
13 #include <dx/dx.h>
14
15 #undef STATS
16
17 typedef struct hashElement *HashElement;
18 typedef struct leaf *Leaf;
19 typedef struct directory Directory;
20 typedef struct pageTable PageTable;
21 typedef struct leafBlock LeafBlock;
22 typedef struct leafCache LeafCache;
23
24 #define MAX_D 24
25 #define LEAF_LEN 8
26 #define LEAF_WRAP 0x07
27 #define LEAF_SHIFT 3
28
29 #define MAGIC_PSEUDOKEY 0xffffffff
30
31 /*
32 * Want to make sure pages come from large arena. Each element must
33 * contain the pseudokey, so is no smaller than 4 bytes.
34 */
35 #define ELTS_PER_PAGE ((1024/sizeof(PseudoKey)) + 1)
36
37 /*
38 * Want to make sure the leaf blocks are allocated from the large arena.
39 */
40 #define LEAVES_PER_BLOCK ((1024/sizeof(struct leaf)) + 1)
41
42 struct hashElement
43 {
44 union
45 {
46 HashElement next;
47 PseudoKey pseudoKey;
48 } u;
49 };
50
51 struct leaf
52 {
53 int depth;
54 int reference;
55 HashElement elements[ LEAF_LEN ];
56 };
57
58 struct leafBlock
59 {
60 LeafBlock *next;
61 struct leaf leaves[ LEAVES_PER_BLOCK ];
62 };
63
64 struct leafCache
65 {
66 LeafBlock *blocks;
67 Leaf freeList;
68 int nextInBlock;
69 #ifdef STATS
70 int currLeaves, maxLeaves;
71 #endif
72 };
73
74 struct directory
75 {
76 int depth;
77 int mask;
78 Leaf *leaves;
79 LeafCache leafCache;
80 };
81
82 struct pageTable
83 {
84 int nPages; /* Number of pages allocated */
85 int nPageSlots; /* Current length of pageTable */
86 int nextEltNum; /* index of next available element */
87 int eltsPerPage; /* number of elements per page */
88 int pageSize; /* bytes per page */
89 int eltSize; /* bytes per element */
90 HashElement nextElt; /* pointer to next available element */
91 HashElement *pagePtrs; /* page pointers */
92 HashElement freeList; /* free list */
93 #ifdef STATS
94 int currElts, maxElts;
95 #endif
96 };
97
98 struct hashTable
99 {
100 Directory directory;
101 PageTable pageTable;
102
103 int dataSize;
104
105 long directoryMask;
106 int directoryLength;
107
108 int getNextPage;
109 int getNextElement;
110
111 PseudoKey ( *hash ) ();
112 int ( *cmp ) ();
113
114 #ifdef STATS
115 int nInserts, nCollisions;
116 int nSearches, nSuccesses, nMismatches;
117 #endif
118
119 };
120
121 #define LEAF_INDEX(pseudoKey) ((pseudoKey) & LEAF_WRAP)
122 #define LEAF_INCREMENT(leafIndex) ((leafIndex+1) & LEAF_WRAP)
123
124 #define DATA_PTR(elt) (Element)(((char *)elt)+sizeof(struct hashElement))
125
126 static int maskBits[] =
127 {
128 0x00000000,
129 0x00000001, 0x00000003, 0x00000007, 0x0000000F,
130 0x0000001F, 0x0000003F, 0x0000007F, 0x000000FF,
131 0x000001FF, 0x000003FF, 0x000007FF, 0x00000FFF,
132 0x00001FFF, 0x00003FFF, 0x00007FFF, 0x0000FFFF,
133 0x0001FFFF, 0x0003FFFF, 0x0007FFFF, 0x000FFFFF,
134 0x001FFFFF, 0x003FFFFF, 0x007FFFFF, 0x00FFFFFF,
135 0x01FFFFFF, 0x03FFFFFF, 0x07FFFFFF, 0x0FFFFFFF
136 };
137
138 static int powers_of_2[] =
139 {
140 0x00000001, 0x00000002, 0x00000004, 0x00000008,
141 0x00000010, 0x00000020, 0x00000040, 0x00000080,
142 0x00000100, 0x00000200, 0x00000400, 0x00000800,
143 0x00001000, 0x00002000, 0x00004000, 0x00008000,
144 0x00010000, 0x00020000, 0x00040000, 0x00080000,
145 0x00100000, 0x00200000, 0x00400000, 0x00800000,
146 0x01000000, 0x02000000, 0x04000000, 0x08000000
147 };
148
149 static Error _initPageTable( PageTable *, int );
150 static void _deletePageTable( PageTable * );
151 static HashElement _getFreeElement( PageTable * );
152 static Error _initDirectory( Directory * );
153 static void _deleteDirectory( Directory * );
154 static Error _InsertHash( HashTable, void *, PseudoKey );
155 static int _InsertHashLeaf( HashTable, PseudoKey, Leaf, void * );
156 static Error _expandHash( HashTable );
157 static Error _splitLeaf( HashTable, int, Leaf );
158 static HashElement _QueryHashElement( HashTable, Key );
159 static void _initLeafCache( LeafCache * );
160 static void _freeLeaf( LeafCache *, Leaf );
161 static Leaf _getFreeLeaf( LeafCache * );
162 static void _deleteLeafCache( LeafCache * );
163
164 #if 0
165 static Error _hashCheck( HashTable );
166 static void _freeElement( PageTable *, HashElement );
167 #endif
168
169
170 HashTable
DXCreateHash(int dataSize,PseudoKey (* hash)(),int (* cmp)())171 DXCreateHash( int dataSize, PseudoKey ( *hash ) (), int ( *cmp ) () )
172 {
173 HashTable hashTable;
174
175 hashTable = ( HashTable ) DXAllocate( sizeof( struct hashTable ) );
176
177 if ( ! hashTable )
178 return NULL;
179
180 /*
181 * Round to word boundary
182 */
183 if ( dataSize & 0x3 )
184 hashTable->dataSize = ( dataSize & 0xffffffc ) + 0x0000004;
185 else
186 hashTable->dataSize = dataSize;
187
188 hashTable->hash = hash;
189 hashTable->cmp = cmp;
190
191 if ( ! _initDirectory( &hashTable->directory ) ) {
192 DXFree( ( Pointer ) hashTable );
193 return NULL;
194 }
195
196 hashTable->directoryMask = maskBits[ hashTable->directory.depth ];
197 hashTable->directoryLength = powers_of_2[ hashTable->directory.depth ];
198
199 if ( ! _initPageTable( &hashTable->pageTable, dataSize ) ) {
200 _deleteDirectory( &hashTable->directory );
201 DXFree( ( Pointer ) hashTable );
202 return NULL;
203 }
204
205 #ifdef STATS
206 hashTable->nInserts = 0;
207 hashTable->nCollisions = 0;
208 hashTable->nSearches = 0;
209 hashTable->nSuccesses = 0;
210 hashTable->nMismatches = 0;
211 #endif
212
213 return hashTable;
214 }
215
216
217 Error
DXDestroyHash(HashTable hashTable)218 DXDestroyHash( HashTable hashTable )
219 {
220 if ( ! hashTable )
221 return OK;
222
223 _deleteDirectory( &hashTable->directory );
224 _deletePageTable( &hashTable->pageTable );
225
226 #ifdef STATS
227 DXMessage( "%d insertions, %d collisions",
228 hashTable->nInserts, hashTable->nCollisions );
229 DXMessage( "%d searches, %d successes, %d mismatches",
230 hashTable->nSearches, hashTable->nSuccesses, hashTable->nMismatches );
231 #endif
232
233 DXFree( ( Pointer ) hashTable );
234 return OK;
235 }
236
237
238 Element
DXQueryHashElement(HashTable hashTable,Key key)239 DXQueryHashElement( HashTable hashTable, Key key )
240 {
241 HashElement elt;
242
243 #ifdef STATS
244 hashTable->nSearches ++;
245 #endif
246
247 if ( NULL == ( elt = _QueryHashElement( hashTable, key ) ) )
248 return NULL;
249 else {
250 #ifdef STATS
251 hashTable->nSuccesses ++;
252 #endif
253 return DATA_PTR( elt );
254 }
255 }
256
257 Error
DXDeleteHashElement(HashTable hashTable,Key key)258 DXDeleteHashElement( HashTable hashTable, Key key )
259 {
260 HashElement elt;
261
262 if ( NULL != ( elt = _QueryHashElement( hashTable, key ) ) )
263 elt->u.pseudoKey = 0;
264
265 return OK;
266 }
267
268
269 Error
DXInsertHashElement(HashTable hashTable,void * data)270 DXInsertHashElement( HashTable hashTable, void *data )
271 {
272 PseudoKey pseudoKey;
273 int status;
274 PseudoKey ( *hash ) ();
275
276 #ifdef STATS
277 hashTable->nInserts ++;
278 #endif
279
280 if ( NULL == ( hash = hashTable->hash ) )
281 pseudoKey = *( PseudoKey * ) data;
282 else
283 pseudoKey = ( *hash ) ( ( Key ) data );
284
285 /*
286 * pseudoKey 0 is illegal. It implies that an entry is empty.
287 * So, we increment pseudokeys by 1, unless its -1.
288 */
289 if ( pseudoKey == ( PseudoKey ) - 1 ) {
290 DXSetError( ERROR_INTERNAL, "invalid hash key (0xffffffff)" );
291 return ERROR;
292 }
293
294 pseudoKey += 1;
295 status = _InsertHash( hashTable, data, pseudoKey );
296 return status;
297 }
298
299 Error
DXInitGetNextHashElement(HashTable hashtab)300 DXInitGetNextHashElement( HashTable hashtab )
301 {
302 if ( hashtab == NULL )
303 return ERROR;
304
305 hashtab->getNextPage = 0;
306 hashtab->getNextElement = 0;
307
308 return OK;
309 }
310
311
312 Element
DXGetNextHashElement(HashTable hashtab)313 DXGetNextHashElement( HashTable hashtab )
314 {
315 PageTable * pagetab;
316 HashElement element, nextelt;
317 HashElement *pages;
318 int pageNum, eltNum;
319 int eltSize, eltsInPage;
320 int nPages;
321
322 if ( ! hashtab )
323 return ERROR;
324
325 pagetab = &hashtab->pageTable;
326
327 if ( ( pageNum = hashtab->getNextPage ) >= ( nPages = pagetab->nPages ) )
328 return NULL;
329
330 eltNum = hashtab->getNextElement;
331 pages = pagetab->pagePtrs;
332 eltSize = pagetab->eltSize;
333
334 if ( pageNum == nPages - 1 )
335 eltsInPage = pagetab->nextEltNum;
336 else
337 eltsInPage = ELTS_PER_PAGE;
338
339 nextelt = ( HashElement ) ( ( ( char * ) pages[ pageNum ] ) + eltNum * eltSize );
340
341 while ( pageNum < nPages ) {
342 element = nextelt;
343 eltNum ++;
344
345 if ( eltNum >= eltsInPage ) {
346 eltNum = 0;
347
348 if ( ++pageNum < nPages ) {
349 if ( pageNum == nPages - 1 )
350 eltsInPage = pagetab->nextEltNum;
351 else
352 eltsInPage = ELTS_PER_PAGE;
353
354 nextelt = pages[ pageNum ];
355 }
356 } else
357 nextelt = ( HashElement ) ( ( char * ) element + eltSize );
358
359 if ( element->u.pseudoKey ) {
360 hashtab->getNextPage = pageNum;
361 hashtab->getNextElement = eltNum;
362 return DATA_PTR( element );
363 }
364 }
365 return NULL;
366 }
367
368
369 static HashElement
_QueryHashElement(HashTable hashTable,Key key)370 _QueryHashElement( HashTable hashTable, Key key )
371 {
372 PseudoKey pseudoKey;
373 int bucketNum;
374 Leaf leaf;
375 int slot, start, found;
376 HashElement element;
377 PseudoKey ( *hash ) ();
378 int ( *cmp ) ();
379
380 cmp = hashTable->cmp;
381 hash = hashTable->hash;
382
383 if ( hash )
384 pseudoKey = ( *hash ) ( key );
385 else
386 pseudoKey = *( PseudoKey * ) key;
387
388 pseudoKey += 1;
389
390 bucketNum = ( pseudoKey >> LEAF_SHIFT ) & hashTable->directoryMask;
391 leaf = hashTable->directory.leaves[ bucketNum ];
392 start = LEAF_INDEX( pseudoKey );
393 found = 0; slot = start;
394
395 do {
396
397 if ( ( element = leaf->elements[ slot ] ) == NULL )
398 break;
399
400 if ( ( element->u.pseudoKey == pseudoKey )
401 && ( !cmp || !( *cmp ) ( key, DATA_PTR( element ) ) ) ) {
402 found = 1;
403 break;
404 }
405
406 #ifdef STATS
407 hashTable->nMismatches ++;
408 #endif
409 slot = LEAF_INCREMENT( slot );
410 }
411
412 while ( slot != start )
413 ;
414
415 if ( ! found )
416 return NULL;
417 else
418 return element;
419 }
420
421
422 static Error
_initPageTable(PageTable * pagetab,int dataSize)423 _initPageTable( PageTable *pagetab, int dataSize )
424 {
425 int eltSize;
426
427 eltSize = sizeof( struct hashElement ) + dataSize;
428 eltSize = ( eltSize + ( sizeof( long ) - 1 ) ) & ~( sizeof( long ) - 1 );
429
430 pagetab->nPages = 0;
431 pagetab->nPageSlots = 0;
432 pagetab->eltsPerPage = ELTS_PER_PAGE;
433 pagetab->nextEltNum = pagetab->eltsPerPage; /* force alloc of first page */
434 pagetab->pageSize = pagetab->eltsPerPage * eltSize;
435 pagetab->eltSize = eltSize;
436 pagetab->pagePtrs = NULL;
437 pagetab->freeList = NULL;
438
439 #ifdef STATS
440 pagetab->currElts = 0;
441 pagetab->maxElts = 0;
442 #endif
443
444 return OK;
445 }
446
447
448 static HashElement
_getFreeElement(PageTable * pagetab)449 _getFreeElement( PageTable *pagetab )
450 {
451 HashElement element;
452
453 if ( pagetab->freeList ) {
454 element = pagetab->freeList;
455 pagetab->freeList = pagetab->freeList->u.next;
456 } else {
457 if ( pagetab->nextEltNum == pagetab->eltsPerPage ) {
458 /*
459 * If no page table slot is available, must make room for more.
460 */
461
462 if ( pagetab->nPages == pagetab->nPageSlots || !pagetab->pagePtrs ) {
463 /*
464 * If this is the first, allocate pagePtrs table. Otherwise,
465 * increase the size
466 */
467
468 if ( ! pagetab->pagePtrs ) {
469 pagetab->nPageSlots = 1;
470 pagetab->pagePtrs = ( HashElement * ) DXAllocate
471 ( pagetab->nPageSlots * sizeof( HashElement ) );
472 } else {
473 pagetab->nPageSlots *= 2;
474 pagetab->pagePtrs = ( HashElement * ) DXReAllocate(
475 ( Pointer ) pagetab->pagePtrs,
476 pagetab->nPageSlots * sizeof( HashElement ) );
477 }
478
479 if ( pagetab->pagePtrs == NULL )
480 return NULL;
481 }
482
483 pagetab->pagePtrs[ pagetab->nPages ] =
484 ( HashElement ) DXAllocate( pagetab->pageSize );
485
486 if ( ! pagetab->pagePtrs[ pagetab->nPages ] )
487 return NULL;
488
489 pagetab->nextElt = pagetab->pagePtrs[ pagetab->nPages ];
490 pagetab->nextEltNum = 0;
491 pagetab->nPages++;
492
493 }
494
495 element = pagetab->nextElt;
496
497 pagetab->nextEltNum ++;
498 pagetab->nextElt = ( HashElement ) ( ( char * ) pagetab->nextElt
499 + pagetab->eltSize );
500 }
501
502 element->u.pseudoKey = 0;
503
504 #ifdef STATS
505
506 if ( ( ++( pagetab->currElts ) ) > pagetab->maxElts )
507 pagetab->maxElts = pagetab->currElts;
508
509 #endif
510
511 return element;
512 }
513
514
515 static void
_deletePageTable(PageTable * pagetab)516 _deletePageTable( PageTable *pagetab )
517 {
518 int i;
519
520 if ( pagetab->pagePtrs ) {
521 for ( i = 0; i < pagetab->nPages; i++ )
522 if ( pagetab->pagePtrs[ i ] ) {
523 DXFree( ( Pointer ) pagetab->pagePtrs[ i ] );
524 pagetab->pagePtrs[ i ] = NULL;
525 }
526
527 DXFree( ( Pointer ) pagetab->pagePtrs );
528 pagetab->pagePtrs = NULL;
529 }
530
531 #ifdef STATS
532 DXMessage( "elements: %d current, %d max",
533 pagetab->currElts, pagetab->maxElts );
534
535 #endif
536
537 }
538
539 static Error
_initDirectory(Directory * directory)540 _initDirectory( Directory *directory )
541 {
542 int nBuckets;
543
544 _initLeafCache( &( directory->leafCache ) );
545
546 nBuckets = 1;
547
548 directory->depth = 0;
549 directory->mask = maskBits[ 0 ];
550 directory->leaves = ( Leaf * ) DXAllocate( nBuckets * sizeof( Leaf ) );
551
552 if ( ! directory->leaves )
553 return ERROR;
554
555 directory->leaves[ 0 ] = _getFreeLeaf( &( directory->leafCache ) );
556 directory->leaves[ 0 ] ->depth = 0;
557 directory->leaves[ 0 ] ->reference = 1;
558
559 return OK;
560 }
561
562 static void
_deleteDirectory(Directory * directory)563 _deleteDirectory( Directory *directory )
564 {
565 _deleteLeafCache( &( directory->leafCache ) );
566
567 if ( directory->leaves )
568 DXFree( ( Pointer ) directory->leaves );
569
570 #ifdef STATS
571 DXMessage( "Directory length: %d", powers_of_2[ directory->depth ] );
572
573 #endif
574 }
575
576
577 static Error
_InsertHash(HashTable hashTable,void * data,PseudoKey pseudoKey)578 _InsertHash( HashTable hashTable, void *data, PseudoKey pseudoKey )
579 {
580 int bucketNum;
581 Leaf leaf;
582 int found;
583
584 bucketNum = ( pseudoKey >> LEAF_SHIFT ) & hashTable->directoryMask;
585 leaf = hashTable->directory.leaves[ bucketNum ];
586
587 found = _InsertHashLeaf( hashTable, pseudoKey, leaf, data );
588
589 if ( found == 1 ) {
590 return OK;
591 } else if ( found == 0 ) {
592 /*
593 * If leaf isn't shared, expand the directory.
594 */
595
596 if ( leaf->depth == hashTable->directory.depth )
597 if ( ! _expandHash( hashTable ) )
598 return ERROR;
599
600 /*
601 * Now expand the leaf
602 */
603 if ( ! _splitLeaf( hashTable, bucketNum, leaf ) )
604 return ERROR;
605
606 /*
607 * Now try insertion again recursively
608 */
609 return _InsertHash( hashTable, data, pseudoKey );
610 } else {
611 return ERROR;
612 }
613 }
614
615
616 static Error
_expandHash(HashTable hashTable)617 _expandHash( HashTable hashTable )
618 {
619 int oldNBuckets;
620 int oldLength;
621 int i;
622 Directory *dir;
623
624 dir = &hashTable->directory;
625
626 oldNBuckets = powers_of_2[ dir->depth ];
627 oldLength = oldNBuckets * sizeof( Leaf * );
628
629 for ( i = 0; i < oldNBuckets; i++ )
630 dir->leaves[ i ] ->reference ++;
631
632 dir->leaves = ( Leaf * ) DXReAllocate( ( Pointer ) dir->leaves, 2 * oldLength );
633
634 if ( ! dir->leaves )
635 return ERROR;
636
637 memcpy( ( char * ) dir->leaves + oldLength, ( char * ) dir->leaves, oldLength );
638
639 dir->depth ++;
640
641 hashTable->directoryMask = maskBits[ dir->depth ];
642 hashTable->directoryLength = powers_of_2[ dir->depth ];
643
644 return OK;
645 }
646
647
648 static int
_InsertHashLeaf(HashTable hashTable,PseudoKey pseudoKey,Leaf leaf,void * data)649 _InsertHashLeaf( HashTable hashTable, PseudoKey pseudoKey,
650 Leaf leaf, void *data )
651 {
652 int slot, start;
653 int found;
654 HashElement element;
655 int ( *cmp ) ();
656
657 cmp = hashTable->cmp;
658 start = LEAF_INDEX( pseudoKey );
659
660 /*
661 * Look for either an empty slot in the leaf or one that
662 * matches the key.
663 */
664 found = 0; slot = start;
665
666 do {
667
668 element = leaf->elements[ slot ];
669
670 if ( element == NULL || ! element->u.pseudoKey ) {
671 found = 1;
672 break;
673 }
674
675 if ( ( element->u.pseudoKey == pseudoKey )
676 && ( !cmp || !( *cmp ) ( ( Key ) data, DATA_PTR( element ) ) ) ) {
677 found = 1;
678 break;
679 }
680
681 #ifdef STATS
682 hashTable->nCollisions ++;
683 #endif
684 slot = LEAF_INCREMENT( slot );
685 }
686
687 while ( slot != start )
688 ;
689
690 if ( found ) {
691 if ( ! element ) {
692 element = _getFreeElement( &hashTable->pageTable );
693
694 if ( ! element )
695 return -1;
696 }
697
698 if ( ! element->u.pseudoKey )
699 element->u.pseudoKey = pseudoKey;
700
701 if ( hashTable->dataSize )
702 memcpy( DATA_PTR( element ), data, hashTable->dataSize );
703
704 leaf->elements[ slot ] = element;
705 }
706
707 return found;
708 }
709
710
711 static Error
_splitLeaf(HashTable hashTable,int bucketNum,Leaf leaf)712 _splitLeaf( HashTable hashTable, int bucketNum, Leaf leaf )
713 {
714 Leaf leaf0, leaf1;
715 int mask;
716 int i, count;
717 HashElement elt, elt0;
718 Leaf which;
719 int slot, start, bit;
720 int knt0, knt1;
721
722 elt0 = leaf->elements[ 0 ];
723
724 for ( i = 1; i < LEAF_LEN; i++ ) {
725 elt = leaf->elements[ i ];
726
727 if ( elt->u.pseudoKey != elt0->u.pseudoKey )
728 break;
729 }
730
731 if ( i == LEAF_LEN ) {
732 DXSetError( ERROR_INTERNAL, "excessive hash key collisions" );
733 return ERROR;
734 }
735
736 leaf0 = _getFreeLeaf( &( hashTable->directory.leafCache ) );
737
738 if ( ! leaf0 )
739 return ERROR;
740
741 leaf1 = _getFreeLeaf( &( hashTable->directory.leafCache ) );
742
743 if ( ! leaf1 )
744 return ERROR;
745
746 leaf0->depth = leaf1->depth = leaf->depth + 1;
747 mask = bucketNum & maskBits[ leaf->depth ];
748 count = powers_of_2[ hashTable->directory.depth - leaf->depth ];
749
750 for ( i = 0; i < count; i++ ) {
751 bucketNum = mask | i << leaf->depth;
752
753 if ( i & 0x01 ) {
754 hashTable->directory.leaves[ bucketNum ] = leaf1;
755 leaf1->reference ++;
756 } else {
757 hashTable->directory.leaves[ bucketNum ] = leaf0;
758 leaf0->reference ++;
759 }
760 }
761
762 bit = 1 << ( leaf->depth + LEAF_SHIFT );
763
764 knt0 = knt1 = 0;
765
766 for ( i = 0; i < LEAF_LEN; i++ ) {
767 elt = leaf->elements[ i ];
768
769 start = LEAF_INDEX( elt->u.pseudoKey );
770
771 if ( elt->u.pseudoKey & bit ) {
772 which = leaf1;
773 knt1++;
774 } else {
775 which = leaf0;
776 knt0++;
777 }
778
779 for ( slot = start; ; slot = LEAF_INCREMENT( slot ) )
780 if ( ! which->elements[ slot ] ) {
781 which->elements[ slot ] = elt;
782 break;
783 }
784 }
785
786 _freeLeaf( &( hashTable->directory.leafCache ), leaf );
787
788 return OK;
789 }
790
791
792 static void
_initLeafCache(LeafCache * lc)793 _initLeafCache( LeafCache *lc )
794 {
795 lc->blocks = NULL;
796 lc->nextInBlock = -1;
797 lc->freeList = NULL;
798
799 #ifdef STATS
800 lc->currLeaves = 0;
801 lc->maxLeaves = 0;
802 #endif
803 }
804
805
806 static void
_freeLeaf(LeafCache * lc,Leaf leaf)807 _freeLeaf( LeafCache *lc, Leaf leaf )
808 {
809 *( ( Leaf * ) leaf ) = lc->freeList;
810 lc->freeList = leaf;
811
812 #ifdef STATS
813 lc->currLeaves --;
814 #endif
815 }
816
817 static Leaf
_getFreeLeaf(LeafCache * lc)818 _getFreeLeaf( LeafCache *lc )
819 {
820 int i;
821 Leaf leaf;
822
823 if ( lc->freeList ) {
824 leaf = lc->freeList;
825 lc->freeList = *( ( Leaf * ) leaf );
826 } else {
827 if ( lc->blocks == NULL || lc->nextInBlock == LEAVES_PER_BLOCK ) {
828 LeafBlock * lb;
829
830 lb = ( LeafBlock * ) DXAllocate( sizeof( struct leafBlock ) );
831
832 if ( !lb )
833 return NULL;
834
835 lb->next = lc->blocks;
836 lc->blocks = lb;
837 lc->nextInBlock = 0;
838 }
839
840 leaf = lc->blocks->leaves + lc->nextInBlock++;
841 }
842
843 leaf->depth = -1;
844 leaf->reference = 0;
845
846 for ( i = 0; i < LEAF_LEN; i++ )
847 leaf->elements[ i ] = NULL;
848
849 #ifdef STATS
850 if ( ( ++( lc->currLeaves ) ) > lc->maxLeaves )
851 lc->maxLeaves = lc->currLeaves;
852
853 #endif
854
855 return leaf;
856 }
857
858
859 static void
_deleteLeafCache(LeafCache * lc)860 _deleteLeafCache( LeafCache *lc )
861 {
862 LeafBlock * this, *next;
863
864 this = lc->blocks;
865
866 while ( this != NULL ) {
867 next = this->next;
868 DXFree( ( Pointer ) this );
869 this = next;
870 }
871
872 #ifdef STATS
873 DXMessage( "leaves: %d current, %d max", lc->currLeaves, lc->maxLeaves );
874
875 #endif
876 }
877
878
879
880 #if 0
881 static void
882 _freeElement( PageTable *pagetab, HashElement elt )
883 {
884 elt->u.next = pagetab->freeList;
885 pagetab->freeList = elt;
886
887 #ifdef STATS
888 pagetab->currElts ++;
889 #endif
890 }
891
892 static Error
893 _hashCheck( HashTable hashTable )
894 {
895 int nBuckets;
896 int i, j;
897 Directory *dir;
898 Leaf leaf;
899
900 dir = &hashTable->directory;
901
902 nBuckets = powers_of_2[ dir->depth ];
903
904 for ( i = 0; i < nBuckets; i++ ) {
905 leaf = hashTable->directory.leaves[ i ];
906
907 for ( j = 0; j < LEAF_LEN; j++ )
908 if ( leaf->elements[ j ] != NULL
909 && ( ( ( ( int ) leaf->elements[ j ] ) < 0x00ffffff )
910 || ( ( ( int ) leaf->elements[ j ] ) > 0x30000000 ) ) )
911 return ERROR;
912 }
913
914 return OK;
915 }
916
917 #endif /* 0 */
918