1
/* A fast (Inline) map/hash table implementation for NSObjects
2
* Copyright (C) 1998,1999 Free Software Foundation, Inc.
4
* Author: Richard Frith-Macdonald <richard@brainstorm.co.uk>
5
* Created: Thu Oct 1 09:30:00 GMT 1998
7
* Based on original o_map code by Albin L. Jones <Albin.L.Jones@Dartmouth.EDU>
9
* This file is part of the GNUstep Base Library.
11
* This library is free software; you can redistribute it and/or
12
* modify it under the terms of the GNU Library General Public
13
* License as published by the Free Software Foundation; either
14
* version 2 of the License, or (at your option) any later version.
16
* This library is distributed in the hope that it will be useful,
17
* but WITHOUT ANY WARRANTY; without even the implied warranty of
18
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19
* Library General Public License for more details.
21
* You should have received a copy of the GNU Library General Public
22
* License along with this library; if not, write to the Free
23
* Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA. */
25
#include <Foundation/NSObject.h>
26
#include <Foundation/NSZone.h>
28
/* To easily un-inline functions for debugging */
34
* This file should be INCLUDED in files wanting to use the GSIMap
35
* functions - these are all declared inline for maximum performance.
37
* The file including this one may predefine some macros to alter
41
* If defined as 0, then this becomes a hash table rather than
44
* GSI_MAP_RETAIN_KEY()
45
* Macro to retain the key item in a map or hash table.
47
* GSI_MAP_RETAIN_VAL()
48
* Macro to retain the value item in a map table.
50
* GSI_MAP_RELEASE_KEY()
51
* Macro to release the key item in a map or hash table.
53
* GSI_MAP_RELEASE_VAL()
54
* Macro to release the value item in a map table.
57
* Macro to get the hash of a key item.
60
* Macro to compare two key items for equality - produces zero
61
* if the items are not equal.
64
* If this value is defined, there is an 'extra' field in each
65
* map table whose type is that specified by the value of the
66
* preprocessor constant. This field can be used
67
* to store additional information for the map.
70
* Define this to a non-zero integer value if the map keys and
71
* values do not need to be released when the map is emptied.
72
* This permits some optimisation.
76
#ifndef GSI_MAP_HAS_VALUE
77
#define GSI_MAP_HAS_VALUE 1
80
#ifndef GSI_MAP_RETAIN_KEY
81
#define GSI_MAP_RETAIN_KEY(M, X) [(X).obj retain]
83
#ifndef GSI_MAP_RELEASE_KEY
84
#define GSI_MAP_RELEASE_KEY(M, X) [(X).obj release]
86
#ifndef GSI_MAP_RETAIN_VAL
87
#define GSI_MAP_RETAIN_VAL(M, X) [(X).obj retain]
89
#ifndef GSI_MAP_RELEASE_VAL
90
#define GSI_MAP_RELEASE_VAL(M, X) [(X).obj release]
93
#define GSI_MAP_HASH(M, X) [(X).obj hash]
96
#define GSI_MAP_EQUAL(M, X, Y) [(X).obj isEqual: (Y).obj]
100
* If there is no bitmask defined to supply the types that
101
* may be used as keys in the map, default to permitting all types.
103
#ifndef GSI_MAP_KTYPES
104
#define GSI_MAP_KTYPES GSUNION_ALL
108
* Set up the name of the union to store keys.
113
#define GSUNION GSIMapKey
116
* Set up the types that will be storable in the union.
117
* See 'GSUnion.h' for further information.
122
#define GSUNION_TYPES GSI_MAP_KTYPES
126
#ifdef GSI_MAP_KEXTRA
127
#define GSUNION_EXTRA GSI_MAP_KEXTRA
131
* Generate the union typedef
133
#include <GNUstepBase/GSUnion.h>
136
#if (GSI_MAP_KTYPES) & GSUNION_OBJ
137
#define GSI_MAP_CLEAR_KEY(node) node->key.obj = nil
138
#elif (GSI_MAP_KTYPES) & GSUNION_PTR
139
#define GSI_MAP_CLEAR_KEY(node) node->key.ptr = 0
141
#define GSI_MAP_CLEAR_KEY(node)
145
* If there is no bitmask defined to supply the types that
146
* may be used as values in the map, default to permitting all types.
148
#ifndef GSI_MAP_VTYPES
149
#define GSI_MAP_VTYPES GSUNION_ALL
153
* Set up the name of the union to store map values.
158
#define GSUNION GSIMapVal
161
* Set up the types that will be storable in the union.
162
* See 'GSUnion.h' for further information.
167
#define GSUNION_TYPES GSI_MAP_VTYPES
171
#ifdef GSI_MAP_VEXTRA
172
#define GSUNION_EXTRA GSI_MAP_VEXTRA
175
#ifndef GSI_MAP_SIMPLE
176
#define GSI_MAP_SIMPLE 0
180
* Generate the union typedef
182
#include <GNUstepBase/GSUnion.h>
184
#if (GSI_MAP_VTYPES) & GSUNION_OBJ
185
#define GSI_MAP_CLEAR_VAL(node) node->value.obj = nil
186
#elif (GSI_MAP_VTYPES) & GSUNION_PTR
187
#define GSI_MAP_CLEAR_VAL(node) node->value.ptr = 0
189
#define GSI_MAP_CLEAR_VAL(node)
193
* Description of the datastructure
194
* --------------------------------
195
* The complete GSIMap implementation can be viewed in two different ways,
197
* (1) viewed as a structure to add and retrieve elements
198
* (2) viewed as a memory management structure to facilitate (1)
200
* The first view is best described as follows:
202
* _GSIMapTable -----> C-array of buckets
204
* Where each bucket contains a count (nodeCount), describing the number
205
* of nodes in the bucket and a pointer (firstNode) to a single linked
208
* The second view is slightly more complicated.
209
* The individual nodes are allocated and deallocated in chunks.
210
* In order to keep track of this we have:
212
* _GSIMapTable -----> C-array of chunks
214
* Where each chunk points to a C-array of nodes.
215
* Also the _GSIMapTable contains a pointer to the free nodes
217
* _GSIMapTable -----> single linked list of free nodes
219
* Consequence of this is that EVERY node is part of a single linked list.
220
* Either it is in use and reachable from a bucket, or it is part of the
221
* freeNodes linked list.
222
* Also EVERY node is part of chunk, due to the way the nodes are allocated.
224
* A rough picture is include below:
227
* This is the map C - array of the buckets
228
* +---------------+ +---------------+
229
* | _GSIMapTable | /----->| nodeCount |
230
* |---------------| / | firstNode ----+--\
231
* | buckets ---+----/ | .......... | |
232
* | bucketCount =| size of --> | nodeCount | |
233
* | nodeChunks ---+--\ | firstNode | |
234
* | chunkCount =-+\ | | . | |
235
* | .... || | | . | |
236
* +---------------+| | | nodeCount | |
238
* / | +---------------+ |
240
* / +----------+ +---------------------------+
241
* | | * ------+----->| Node1 | Node2 | Node3 ... | a chunk
242
* chunkCount | * ------+--\ +---------------------------+
243
* is size of = | . | \ +-------------------------------+
244
* | . | ->| Node n | Node n + 1 | ... | another
245
* +----------+ +-------------------------------+
250
* NOTES on the way chunks are allocated
251
* -------------------------------------
252
* Chunks are allocated when needed, that is a new chunk is allocated
253
* whenever the freeNodes list is empty and a new node is required.
254
* In gnustep-base-1.9.0 the size of the new chunk is calculated as
255
* roughly 3/4 of the number of nodes in use.
256
* The problem with this approach is that it can lead to unnecessary
257
* address space fragmentation. So in this version the algorithm we
258
* will use the 3/4 rule until the nodeCount reaches the "increment"
260
* If nodeCount is bigger than the "increment" it will allocate chunks
261
* of size "increment".
264
typedef struct _GSIMapTable GSIMapTable_t;
265
typedef struct _GSIMapBucket GSIMapBucket_t;
266
typedef struct _GSIMapNode GSIMapNode_t;
268
typedef GSIMapTable_t *GSIMapTable;
269
typedef GSIMapBucket_t *GSIMapBucket;
270
typedef GSIMapNode_t *GSIMapNode;
273
GSIMapNode nextInBucket; /* Linked list of bucket. */
275
#if GSI_MAP_HAS_VALUE
280
struct _GSIMapBucket {
281
size_t nodeCount; /* Number of nodes in bucket. */
282
GSIMapNode firstNode; /* The linked list of nodes. */
285
struct _GSIMapTable {
287
size_t nodeCount; /* Number of used nodes in map. */
288
size_t bucketCount; /* Number of buckets in map. */
289
GSIMapBucket buckets; /* Array of buckets. */
290
GSIMapNode freeNodes; /* List of unused nodes. */
291
size_t chunkCount; /* Number of chunks in array. */
292
GSIMapNode *nodeChunks; /* Chunks of allocated memory. */
299
typedef struct _GSIMapEnumerator {
300
GSIMapTable map; /* the map being enumerated. */
301
GSIMapNode node; /* The next node to use. */
302
size_t bucket; /* The next bucket to use. */
305
#ifdef GSI_MAP_ENUMERATOR
306
typedef GSI_MAP_ENUMERATOR GSIMapEnumerator_t;
308
typedef struct _GSIMapEnumerator GSIMapEnumerator_t;
310
typedef GSIMapEnumerator_t *GSIMapEnumerator;
312
static INLINE GSIMapBucket
313
GSIMapPickBucket(unsigned hash, GSIMapBucket buckets, size_t bucketCount)
315
return buckets + hash % bucketCount;
318
static INLINE GSIMapBucket
319
GSIMapBucketForKey(GSIMapTable map, GSIMapKey key)
321
return GSIMapPickBucket(GSI_MAP_HASH(map, key),
322
map->buckets, map->bucketCount);
326
GSIMapLinkNodeIntoBucket(GSIMapBucket bucket, GSIMapNode node)
328
node->nextInBucket = bucket->firstNode;
329
bucket->firstNode = node;
333
GSIMapUnlinkNodeFromBucket(GSIMapBucket bucket, GSIMapNode node)
335
if (node == bucket->firstNode)
337
bucket->firstNode = node->nextInBucket;
341
GSIMapNode tmp = bucket->firstNode;
343
while (tmp->nextInBucket != node)
345
tmp = tmp->nextInBucket;
347
tmp->nextInBucket = node->nextInBucket;
349
node->nextInBucket = 0;
353
GSIMapAddNodeToBucket(GSIMapBucket bucket, GSIMapNode node)
355
GSIMapLinkNodeIntoBucket(bucket, node);
356
bucket->nodeCount += 1;
360
GSIMapAddNodeToMap(GSIMapTable map, GSIMapNode node)
364
bucket = GSIMapBucketForKey(map, node->key);
365
GSIMapAddNodeToBucket(bucket, node);
370
GSIMapRemoveNodeFromBucket(GSIMapBucket bucket, GSIMapNode node)
373
GSIMapUnlinkNodeFromBucket(bucket, node);
377
GSIMapRemoveNodeFromMap(GSIMapTable map, GSIMapBucket bkt, GSIMapNode node)
380
GSIMapRemoveNodeFromBucket(bkt, node);
384
GSIMapRemangleBuckets(GSIMapTable map,
385
GSIMapBucket old_buckets, size_t old_bucketCount,
386
GSIMapBucket new_buckets, size_t new_bucketCount)
388
while (old_bucketCount-- > 0)
392
while ((node = old_buckets->firstNode) != 0)
396
GSIMapRemoveNodeFromBucket(old_buckets, node);
397
bkt = GSIMapPickBucket(GSI_MAP_HASH(map, node->key),
398
new_buckets, new_bucketCount);
399
GSIMapAddNodeToBucket(bkt, node);
406
GSIMapMoreNodes(GSIMapTable map, unsigned required)
408
GSIMapNode *newArray;
409
size_t arraySize = (map->chunkCount+1)*sizeof(GSIMapNode);
413
* Our nodes may be allocated from the atomic zone - but we don't want
414
* them freed - so we must keep the array of pointers to memory chunks in
417
if (map->zone == GSAtomicMallocZone())
419
newArray = (GSIMapNode*)NSZoneMalloc(NSDefaultMallocZone(), arraySize);
423
newArray = (GSIMapNode*)NSZoneMalloc(map->zone, arraySize);
430
memcpy(newArray, map->nodeChunks, (map->chunkCount)*sizeof(GSIMapNode));
431
if (map->nodeChunks != 0)
433
NSZoneFree(map->zone, map->nodeChunks);
435
map->nodeChunks = newArray;
439
if (map->chunkCount == 0)
441
chunkCount = map->bucketCount > 1 ? map->bucketCount : 2;
445
chunkCount = ((map->nodeCount>>2)+1)<<1;
450
chunkCount = required;
452
chunkSize = chunkCount * sizeof(GSIMapNode_t);
453
newNodes = (GSIMapNode)NSZoneMalloc(map->zone, chunkSize);
456
map->nodeChunks[map->chunkCount++] = newNodes;
457
newNodes[--chunkCount].nextInBucket = map->freeNodes;
460
newNodes[chunkCount].nextInBucket = &newNodes[chunkCount+1];
462
map->freeNodes = newNodes;
467
#if GSI_MAP_HAS_VALUE
468
static INLINE GSIMapNode
469
GSIMapNewNode(GSIMapTable map, GSIMapKey key, GSIMapVal value)
471
GSIMapNode node = map->freeNodes;
475
GSIMapMoreNodes(map, map->nodeCount < map->increment ? 0: map->increment);
476
node = map->freeNodes;
483
map->freeNodes = node->nextInBucket;
486
node->nextInBucket = 0;
491
static INLINE GSIMapNode
492
GSIMapNewNode(GSIMapTable map, GSIMapKey key)
494
GSIMapNode node = map->freeNodes;
498
GSIMapMoreNodes(map, map->nodeCount < map->increment ? 0: map->increment);
499
node = map->freeNodes;
506
map->freeNodes = node->nextInBucket;
508
node->nextInBucket = 0;
514
GSIMapFreeNode(GSIMapTable map, GSIMapNode node)
516
GSI_MAP_RELEASE_KEY(map, node->key);
517
GSI_MAP_CLEAR_KEY(node);
518
#if GSI_MAP_HAS_VALUE
519
GSI_MAP_RELEASE_VAL(map, node->value);
520
GSI_MAP_CLEAR_VAL(node);
523
node->nextInBucket = map->freeNodes;
524
map->freeNodes = node;
527
static INLINE GSIMapNode
528
GSIMapNodeForKeyInBucket(GSIMapTable map, GSIMapBucket bucket, GSIMapKey key)
530
GSIMapNode node = bucket->firstNode;
532
while ((node != 0) && GSI_MAP_EQUAL(map, node->key, key) == NO)
534
node = node->nextInBucket;
539
static INLINE GSIMapNode
540
GSIMapNodeForKey(GSIMapTable map, GSIMapKey key)
545
if (map->nodeCount == 0)
549
bucket = GSIMapBucketForKey(map, key);
550
node = GSIMapNodeForKeyInBucket(map, bucket, key);
554
#if (GSI_MAP_KTYPES & GSUNION_INT)
556
* Specialized lookup for the case where keys are known to be simple integer
557
* or pointer values that are their own hash values and con be compared with
558
* a test for integer equality.
560
static INLINE GSIMapNode
561
GSIMapNodeForSimpleKey(GSIMapTable map, GSIMapKey key)
566
if (map->nodeCount == 0)
570
bucket = map->buckets + key.uint % map->bucketCount;
571
node = bucket->firstNode;
572
while ((node != 0) && node->key.uint != key.uint)
574
node = node->nextInBucket;
581
GSIMapResize(GSIMapTable map, size_t new_capacity)
583
GSIMapBucket new_buckets;
588
* Find next size up in the fibonacci series
590
while (size < new_capacity)
598
* Avoid even numbers - since hash functions frequently generate uneven
599
* distributions around powers of two -
600
* we don't want lots of keys falling into a single bucket.
608
* Make a new set of buckets for this map
610
new_buckets = (GSIMapBucket)NSZoneCalloc(map->zone, size,
611
sizeof(GSIMapBucket_t));
612
if (new_buckets != 0)
614
GSIMapRemangleBuckets(map, map->buckets, map->bucketCount, new_buckets,
617
if (map->buckets != 0)
619
NSZoneFree(map->zone, map->buckets);
621
map->buckets = new_buckets;
622
map->bucketCount = size;
627
GSIMapRightSizeMap(GSIMapTable map, size_t capacity)
629
/* FIXME: Now, this is a guess, based solely on my intuition. If anyone
630
* knows of a better ratio (or other test, for that matter) and can
631
* provide evidence of its goodness, please get in touch with me, Albin
632
* L. Jones <Albin.L.Jones@Dartmouth.EDU>. */
634
if (3 * capacity >= 4 * map->bucketCount)
636
GSIMapResize(map, (3 * capacity)/4 + 1);
642
/* IMPORTANT WARNING: Enumerators have a wonderous property.
643
* Once a node has been returned by `GSIMapEnumeratorNextNode()', it may be
644
* removed from the map without effecting the rest of the current
647
/* EXTREMELY IMPORTANT WARNING: The purpose of this warning is point
648
* out that, various (i.e., many) functions currently depend on
649
* the behaviour outlined above. So be prepared for some serious
650
* breakage when you go fudging around with these things. */
653
* Create an return an enumerator for the specified map.<br />
654
* You must call GSIMapEndEnumerator() when you have finished
655
* with the enumerator.<br />
656
* <strong>WARNING</strong> You should not alter a map while an enumeration
657
* is in progress. The results of doing so are reasonably unpredictable.
658
* <br />Remember, DON'T MESS WITH A MAP WHILE YOU'RE ENUMERATING IT.
660
static INLINE GSIMapEnumerator_t
661
GSIMapEnumeratorForMap(GSIMapTable map)
663
GSIMapEnumerator_t enumerator;
665
enumerator.map = map;
667
enumerator.bucket = 0;
669
* Locate next bucket and node to be returned.
671
while (enumerator.bucket < map->bucketCount)
673
enumerator.node = map->buckets[enumerator.bucket].firstNode;
674
if (enumerator.node != 0)
676
break; // Got first node, and recorded its bucket.
685
* Tidies up after map enumeration ... effectively destroys the enumerator.
688
GSIMapEndEnumerator(GSIMapEnumerator enumerator)
690
((_GSIE)enumerator)->map = 0;
691
((_GSIE)enumerator)->node = 0;
692
((_GSIE)enumerator)->bucket = 0;
696
* Returns the bucket from which the next node in the enumeration will
697
* come. Once the next node has been enumerated, you can use the
698
* bucket and node to remove the node from the map using the
699
* GSIMapRemoveNodeFromMap() function.
701
static INLINE GSIMapBucket
702
GSIMapEnumeratorBucket(GSIMapEnumerator enumerator)
704
if (((_GSIE)enumerator)->node != 0)
706
GSIMapTable map = ((_GSIE)enumerator)->map;
708
return &((map->buckets)[((_GSIE)enumerator)->bucket]);
714
* Returns the next node in the map, or a nul pointer if at the end.
716
static INLINE GSIMapNode
717
GSIMapEnumeratorNextNode(GSIMapEnumerator enumerator)
719
GSIMapNode node = ((_GSIE)enumerator)->node;
723
GSIMapNode next = node->nextInBucket;
727
GSIMapTable map = ((_GSIE)enumerator)->map;
728
size_t bucketCount = map->bucketCount;
729
size_t bucket = ((_GSIE)enumerator)->bucket;
731
while (next == 0 && ++bucket < bucketCount)
733
next = (map->buckets[bucket]).firstNode;
735
((_GSIE)enumerator)->bucket = bucket;
737
((_GSIE)enumerator)->node = next;
742
#if GSI_MAP_HAS_VALUE
743
static INLINE GSIMapNode
744
GSIMapAddPairNoRetain(GSIMapTable map, GSIMapKey key, GSIMapVal value)
748
node = GSIMapNewNode(map, key, value);
752
GSIMapRightSizeMap(map, map->nodeCount);
753
GSIMapAddNodeToMap(map, node);
758
static INLINE GSIMapNode
759
GSIMapAddPair(GSIMapTable map, GSIMapKey key, GSIMapVal value)
763
GSI_MAP_RETAIN_KEY(map, key);
764
GSI_MAP_RETAIN_VAL(map, value);
765
node = GSIMapNewNode(map, key, value);
769
GSIMapRightSizeMap(map, map->nodeCount);
770
GSIMapAddNodeToMap(map, node);
775
static INLINE GSIMapNode
776
GSIMapAddKeyNoRetain(GSIMapTable map, GSIMapKey key)
780
node = GSIMapNewNode(map, key);
784
GSIMapRightSizeMap(map, map->nodeCount);
785
GSIMapAddNodeToMap(map, node);
790
static INLINE GSIMapNode
791
GSIMapAddKey(GSIMapTable map, GSIMapKey key)
795
GSI_MAP_RETAIN_KEY(map, key);
796
node = GSIMapNewNode(map, key);
800
GSIMapRightSizeMap(map, map->nodeCount);
801
GSIMapAddNodeToMap(map, node);
808
GSIMapRemoveKey(GSIMapTable map, GSIMapKey key)
810
GSIMapBucket bucket = GSIMapBucketForKey(map, key);
813
node = GSIMapNodeForKeyInBucket(map, bucket, key);
816
GSIMapRemoveNodeFromMap(map, bucket, node);
817
GSIMapFreeNode(map, node);
822
GSIMapCleanMap(GSIMapTable map)
824
if (map->nodeCount > 0)
826
GSIMapBucket bucket = map->buckets;
828
GSIMapNode startNode = 0;
829
GSIMapNode prevNode = 0;
833
for (i = 0; i < map->bucketCount; i++)
835
node = bucket->firstNode;
838
prevNode->nextInBucket = node;
846
GSI_MAP_RELEASE_KEY(map, node->key);
848
#if GSI_MAP_HAS_VALUE
849
GSI_MAP_RELEASE_VAL(map, node->value);
852
node = node->nextInBucket;
854
bucket->nodeCount = 0;
855
bucket->firstNode = 0;
859
prevNode->nextInBucket = map->freeNodes;
860
map->freeNodes = startNode;
865
GSIMapEmptyMap(GSIMapTable map)
869
#ifdef GSI_MAP_NOCLEAN
881
if (map->buckets != 0)
883
NSZoneFree(map->zone, map->buckets);
885
map->bucketCount = 0;
887
if (map->nodeChunks != 0)
889
for (i = 0; i < map->chunkCount; i++)
891
NSZoneFree(map->zone, map->nodeChunks[i]);
894
NSZoneFree(map->zone, map->nodeChunks);
902
GSIMapInitWithZoneAndCapacity(GSIMapTable map, NSZone *zone, size_t capacity)
906
map->bucketCount = 0;
911
map->increment = 300000; // choosen so the chunksize will be less than 4Mb
912
GSIMapRightSizeMap(map, capacity);
913
GSIMapMoreNodes(map, capacity);
added
removed
Headers/Additions/GNUstepBase/GSIMap.h
