1 /* A fast (Inline) map/hash table implementation for NSObjects
2 * Copyright (C) 1998,1999 Free Software Foundation, Inc.
3 *
4 * Author: Richard Frith-Macdonald <richard@brainstorm.co.uk>
5 * Created: Thu Oct 1 09:30:00 GMT 1998
6 *
7 * Based on original o_map code by Albin L. Jones <Albin.L.Jones@Dartmouth.EDU>
8 *
9 * This file is part of the GNUstep Base Library.
10 *
11 * This library is free software; you can redistribute it and/or
12 * modify it under the terms of the GNU Lesser 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.
15 *
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.
20 *
21 * You should have received a copy of the GNU Lesser General Public
22 * License along with this library; if not, write to the Free
23 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
24 * Boston, MA 02111 USA. */
25
26 #import <GNUstepBase/GSVersionMacros.h>
27
28 #if OS_API_VERSION(GS_API_NONE,GS_API_LATEST)
29
30 #if defined(GNUSTEP_BASE_INTERNAL)
31 #import "Foundation/NSObject.h"
32 #import "Foundation/NSEnumerator.h"
33 #import "Foundation/NSException.h"
34 #import "Foundation/NSGarbageCollector.h"
35 #import "Foundation/NSZone.h"
36 #else
37 #import <Foundation/NSObject.h>
38 #import <Foundation/NSEnumerator.h>
39 #import <Foundation/NSException.h>
40 #import <Foundation/NSGarbageCollector.h>
41 #import <Foundation/NSZone.h>
42 #endif
43
44 #if defined(__cplusplus)
45 extern "C" {
46 #endif
47
48 /* To easily un-inline functions for debugging */
49 #ifndef GS_STATIC_INLINE
50 #define GS_STATIC_INLINE static inline
51 #endif
52
53
54 /*
55 * NB. This file is intended for internal use by the GNUstep libraries
56 * and may change siugnificantly between releases.
57 * While it is unlikley to be removed from the distributiuon any time
58 * soon, its use by other software is not officially supported.
59 *
60 * This file should be INCLUDED in files wanting to use the GSIMap
61 * functions - these are all declared inline for maximum performance.
62 *
63 * The file including this one may predefine some macros to alter
64 * the behaviour
65 *
66 * GSI_MAP_HAS_VALUE
67 * If defined as 0, then this becomes a hash table rather than
68 * a map table.
69 *
70 * GSI_MAP_RETAIN_KEY()
71 * Macro to retain the key item in a map or hash table.
72 *
73 * GSI_MAP_RETAIN_VAL()
74 * Macro to retain the value item in a map table.
75 *
76 * GSI_MAP_RELEASE_KEY()
77 * Macro to release the key item in a map or hash table.
78 *
79 * GSI_MAP_RELEASE_VAL()
80 * Macro to release the value item in a map table.
81 *
82 * GSI_MAP_WRITE_KEY()
83 * Macro defining the write barrier for a key.
84 *
85 * GSI_MAP_WRITE_VAL()
86 * Macro defining the write barrier for a value.
87 *
88 * GSI_MAP_READ_KEY()
89 * Macro defining the read barrier for a key.
90 *
91 * GSI_MAP_HASH()
92 * Macro to get the hash of a key item.
93 *
94 * GSI_MAP_EQUAL()
95 * Macro to compare two key items for equality - produces zero
96 * if the items are not equal.
97 *
98 * GSI_MAP_EXTRA
99 * If this value is defined, there is an 'extra' field in each
100 * map table whose type is that specified by the value of the
101 * preprocessor constant. This field can be used
102 * to store additional information for the map.
103 *
104 * GSI_MAP_NOCLEAN
105 * Define this to a non-zero integer value if the map keys and
106 * values do not need to be released when the map is emptied.
107 * This permits some optimisation.
108 *
109 * GSI_MAP_NODES()
110 * Define this macro to allocate nodes for the map using typed
111 * memory when working with garbage collection.
112 *
113 * GSI_MAP_ZEROED()
114 * Define this macro to check whether a map uses keys which may
115 * be zeroed weak pointers.
116 */
117
118 #ifndef GSI_MAP_HAS_VALUE
119 #define GSI_MAP_HAS_VALUE 1
120 #endif
121
122 #ifndef GSI_MAP_RETAIN_KEY
123 #define GSI_MAP_RETAIN_KEY(M, X) [(X).obj retain]
124 #endif
125 #ifndef GSI_MAP_RELEASE_KEY
126 #define GSI_MAP_RELEASE_KEY(M, X) [(X).obj release]
127 #endif
128 #ifndef GSI_MAP_RETAIN_VAL
129 #define GSI_MAP_RETAIN_VAL(M, X) [(X).obj retain]
130 #endif
131 #ifndef GSI_MAP_RELEASE_VAL
132 #define GSI_MAP_RELEASE_VAL(M, X) [(X).obj release]
133 #endif
134 #ifndef GSI_MAP_HASH
135 #define GSI_MAP_HASH(M, X) [(X).obj hash]
136 #endif
137 #ifndef GSI_MAP_EQUAL
138 #define GSI_MAP_EQUAL(M, X, Y) [(X).obj isEqual: (Y).obj]
139 #endif
140 #ifndef GSI_MAP_NODES
141 #define GSI_MAP_NODES(M, X) \
142 (GSIMapNode)NSAllocateCollectable(X*sizeof(GSIMapNode_t), NSScannedOption)
143 #endif
144 #ifndef GSI_MAP_ZEROED
145 #define GSI_MAP_ZEROED(M) 0
146 #endif
147 #ifndef GSI_MAP_READ_KEY
148 # define GSI_MAP_READ_KEY(M, x) (*(x))
149 #endif
150 #ifndef GSI_MAP_READ_VALUE
151 # define GSI_MAP_READ_VALUE(M, x) (*(x))
152 #endif
153 #ifndef GSI_MAP_WRITE_KEY
154 # define GSI_MAP_WRITE_KEY(M, addr, obj) (*(addr) = obj)
155 #endif
156 #ifndef GSI_MAP_WRITE_VAL
157 # define GSI_MAP_WRITE_VAL(M, addr, obj) (*(addr) = obj)
158 #endif
159 #if GSI_MAP_HAS_VALUE
160 #define GSI_MAP_NODE_IS_EMPTY(M, node) \
161 (((GSI_MAP_READ_KEY(M, &node->key).addr) == 0) \
162 || ((GSI_MAP_READ_VALUE(M, &node->value).addr == 0)))
163 #else
164 #define GSI_MAP_NODE_IS_EMPTY(M, node) \
165 (((GSI_MAP_READ_KEY(M, &node->key).addr) == 0))
166 #endif
167
168 /*
169 * If there is no bitmask defined to supply the types that
170 * may be used as keys in the map, default to none.
171 */
172 #ifndef GSI_MAP_KTYPES
173 #define GSI_MAP_KTYPES 0
174 #endif
175
176 /*
177 * Set up the name of the union to store keys.
178 */
179 #ifdef GSUNION
180 #undef GSUNION
181 #endif
182 #define GSUNION GSIMapKey
183
184 /*
185 * Set up the types that will be storable in the union.
186 * See 'GSUnion.h' for further information.
187 */
188 #ifdef GSUNION_TYPES
189 #undef GSUNION_TYPES
190 #endif
191 #define GSUNION_TYPES GSI_MAP_KTYPES
192 #ifdef GSUNION_EXTRA
193 #undef GSUNION_EXTRA
194 #endif
195 #ifdef GSI_MAP_KEXTRA
196 #define GSUNION_EXTRA GSI_MAP_KEXTRA
197 #endif
198
199 /*
200 * Generate the union typedef
201 */
202 #if defined(GNUSTEP_BASE_INTERNAL)
203 #include "GNUstepBase/GSUnion.h"
204 #else
205 #include <GNUstepBase/GSUnion.h>
206 #endif
207
208
209 #if (GSI_MAP_KTYPES) & GSUNION_OBJ
210 #define GSI_MAP_CLEAR_KEY(node) GSI_MAP_WRITE_KEY(map, &node->key, (GSIMapKey)(id)nil)
211 #elif (GSI_MAP_KTYPES) & GSUNION_PTR
212 #define GSI_MAP_CLEAR_KEY(node) GSI_MAP_WRITE_KEY(map, &node->key, (GSIMapKey)(void *)NULL)
213 #else
214 #define GSI_MAP_CLEAR_KEY(node)
215 #endif
216
217 /*
218 * If there is no bitmask defined to supply the types that
219 * may be used as values in the map, default to none.
220 */
221 #ifndef GSI_MAP_VTYPES
222 #define GSI_MAP_VTYPES 0
223 #endif
224
225 /*
226 * Set up the name of the union to store map values.
227 */
228 #ifdef GSUNION
229 #undef GSUNION
230 #endif
231 #define GSUNION GSIMapVal
232
233 /*
234 * Set up the types that will be storable in the union.
235 * See 'GSUnion.h' for further information.
236 */
237 #ifdef GSUNION_TYPES
238 #undef GSUNION_TYPES
239 #endif
240 #define GSUNION_TYPES GSI_MAP_VTYPES
241 #ifdef GSUNION_EXTRA
242 #undef GSUNION_EXTRA
243 #endif
244 #ifdef GSI_MAP_VEXTRA
245 #define GSUNION_EXTRA GSI_MAP_VEXTRA
246 #endif
247
248 #ifndef GSI_MAP_SIMPLE
249 #define GSI_MAP_SIMPLE 0
250 #endif
251
252 /*
253 * Generate the union typedef
254 */
255 #if defined(GNUSTEP_BASE_INTERNAL)
256 #include "GNUstepBase/GSUnion.h"
257 #else
258 #include <GNUstepBase/GSUnion.h>
259 #endif
260
261 #if (GSI_MAP_VTYPES) & GSUNION_OBJ
262 #define GSI_MAP_CLEAR_VAL(node) GSI_MAP_WRITE_VAL(map, &node->value, (GSIMapVal)(id)nil)
263 #elif (GSI_MAP_VTYPES) & GSUNION_PTR
264 #define GSI_MAP_CLEAR_VAL(node) GSI_MAP_WRITE_VAL(map, &node->value, (GSIMapVal)(void *)NULL)
265 #else
266 #define GSI_MAP_CLEAR_VAL(node)
267 #endif
268
269 /*
270 * Description of the datastructure
271 * --------------------------------
272 * The complete GSIMap implementation can be viewed in two different ways,
273 *
274 * (1) viewed as a structure to add and retrieve elements
275 * (2) viewed as a memory management structure to facilitate (1)
276 *
277 * The first view is best described as follows:
278 *
279 * _GSIMapTable -----> C-array of buckets
280 *
281 * Where each bucket contains a count (nodeCount), describing the number
282 * of nodes in the bucket and a pointer (firstNode) to a single linked
283 * list of nodes.
284 *
285 * The second view is slightly more complicated.
286 * The individual nodes are allocated and deallocated in chunks.
287 * In order to keep track of this we have:
288 *
289 * _GSIMapTable -----> C-array of chunks
290 *
291 * Where each chunk points to a C-array of nodes.
292 * Also the _GSIMapTable contains a pointer to the free nodes
293 *
294 * _GSIMapTable -----> single linked list of free nodes
295 *
296 * Consequence of this is that EVERY node is part of a single linked list.
297 * Either it is in use and reachable from a bucket, or it is part of the
298 * freeNodes linked list.
299 * Also EVERY node is part of chunk, due to the way the nodes are allocated.
300 *
301 * A rough picture is include below:
302 *
303 *
304 * This is the map C - array of the buckets
305 * +---------------+ +---------------+
306 * | _GSIMapTable | /----->| nodeCount |
307 * |---------------| / | firstNode ----+--\
308 * | buckets ---+----/ | .......... | |
309 * | bucketCount =| size of --> | nodeCount | |
310 * | nodeChunks ---+--\ | firstNode | |
311 * | chunkCount =-+\ | | . | |
312 * | .... || | | . | |
313 * +---------------+| | | nodeCount | |
314 * | | | fistNode | |
315 * / | +---------------+ |
316 * ---------- v v
317 * / +----------+ +---------------------------+
318 * | | * ------+----->| Node1 | Node2 | Node3 ... | a chunk
319 * chunkCount | * ------+--\ +---------------------------+
320 * is size of = | . | \ +-------------------------------+
321 * | . | ->| Node n | Node n + 1 | ... | another
322 * +----------+ +-------------------------------+
323 * array pointing
324 * to the chunks
325 *
326 *
327 * NOTES on the way chunks are allocated
328 * -------------------------------------
329 * Chunks are allocated when needed, that is a new chunk is allocated
330 * whenever the freeNodes list is empty and a new node is required.
331 * In gnustep-base-1.9.0 the size of the new chunk is calculated as
332 * roughly 3/4 of the number of nodes in use.
333 * The problem with this approach is that it can lead to unnecessary
334 * address space fragmentation. So in this version the algorithm we
335 * will use the 3/4 rule until the nodeCount reaches the "increment"
336 * member variable.
337 * If nodeCount is bigger than the "increment" it will allocate chunks
338 * of size "increment".
339 */
340
341 #if !defined(GSI_MAP_TABLE_T)
342 typedef struct _GSIMapBucket GSIMapBucket_t;
343 typedef struct _GSIMapNode GSIMapNode_t;
344
345 typedef GSIMapBucket_t *GSIMapBucket;
346 typedef GSIMapNode_t *GSIMapNode;
347 #endif
348
349 struct _GSIMapNode {
350 GSIMapNode nextInBucket; /* Linked list of bucket. */
351 GSIMapKey key;
352 #if GSI_MAP_HAS_VALUE
353 GSIMapVal value;
354 #endif
355 };
356
357 struct _GSIMapBucket {
358 uintptr_t nodeCount; /* Number of nodes in bucket. */
359 GSIMapNode firstNode; /* The linked list of nodes. */
360 };
361
362 #if defined(GSI_MAP_TABLE_T)
363 typedef GSI_MAP_TABLE_T *GSIMapTable;
364 #else
365 typedef struct _GSIMapTable GSIMapTable_t;
366 typedef GSIMapTable_t *GSIMapTable;
367
368 struct _GSIMapTable {
369 NSZone *zone;
370 uintptr_t nodeCount; /* Number of used nodes in map. */
371 uintptr_t bucketCount; /* Number of buckets in map. */
372 GSIMapBucket buckets; /* Array of buckets. */
373 GSIMapNode freeNodes; /* List of unused nodes. */
374 uintptr_t chunkCount; /* Number of chunks in array. */
375 GSIMapNode *nodeChunks; /* Chunks of allocated memory. */
376 uintptr_t increment;
377 #ifdef GSI_MAP_EXTRA
378 GSI_MAP_EXTRA extra;
379 #endif
380 };
381 #define GSI_MAP_TABLE_T GSIMapTable_t
382 #endif
383
384 #ifndef GSI_MAP_TABLE_S
385 #define GSI_MAP_TABLE_S sizeof(GSI_MAP_TABLE_T)
386 #endif
387
388 typedef struct _GSIMapEnumerator {
389 GSIMapTable map; /* the map being enumerated. */
390 GSIMapNode node; /* The next node to use. */
391 uintptr_t bucket; /* The next bucket to use. */
392 } *_GSIE;
393
394 #ifdef GSI_MAP_ENUMERATOR
395 typedef GSI_MAP_ENUMERATOR GSIMapEnumerator_t;
396 #else
397 typedef struct _GSIMapEnumerator GSIMapEnumerator_t;
398 #endif
399 typedef GSIMapEnumerator_t *GSIMapEnumerator;
400
401 GS_STATIC_INLINE GSIMapBucket
GSIMapPickBucket(unsigned hash,GSIMapBucket buckets,uintptr_t bucketCount)402 GSIMapPickBucket(unsigned hash, GSIMapBucket buckets, uintptr_t bucketCount)
403 {
404 return buckets + hash % bucketCount;
405 }
406
407 GS_STATIC_INLINE GSIMapBucket
GSIMapBucketForKey(GSIMapTable map,GSIMapKey key)408 GSIMapBucketForKey(GSIMapTable map, GSIMapKey key)
409 {
410 return GSIMapPickBucket(GSI_MAP_HASH(map, key),
411 map->buckets, map->bucketCount);
412 }
413
414 GS_STATIC_INLINE void
GSIMapLinkNodeIntoBucket(GSIMapBucket bucket,GSIMapNode node)415 GSIMapLinkNodeIntoBucket(GSIMapBucket bucket, GSIMapNode node)
416 {
417 node->nextInBucket = bucket->firstNode;
418 bucket->firstNode = node;
419 }
420
421 GS_STATIC_INLINE void
GSIMapUnlinkNodeFromBucket(GSIMapBucket bucket,GSIMapNode node)422 GSIMapUnlinkNodeFromBucket(GSIMapBucket bucket, GSIMapNode node)
423 {
424 if (node == bucket->firstNode)
425 {
426 bucket->firstNode = node->nextInBucket;
427 }
428 else
429 {
430 GSIMapNode tmp = bucket->firstNode;
431
432 while (tmp->nextInBucket != node)
433 {
434 tmp = tmp->nextInBucket;
435 }
436 tmp->nextInBucket = node->nextInBucket;
437 }
438 node->nextInBucket = 0;
439 }
440
441 GS_STATIC_INLINE void
GSIMapAddNodeToBucket(GSIMapBucket bucket,GSIMapNode node)442 GSIMapAddNodeToBucket(GSIMapBucket bucket, GSIMapNode node)
443 {
444 GSIMapLinkNodeIntoBucket(bucket, node);
445 bucket->nodeCount += 1;
446 }
447
448 GS_STATIC_INLINE void
GSIMapAddNodeToMap(GSIMapTable map,GSIMapNode node)449 GSIMapAddNodeToMap(GSIMapTable map, GSIMapNode node)
450 {
451 GSIMapBucket bucket;
452
453 bucket = GSIMapBucketForKey(map, GSI_MAP_READ_KEY(map, &node->key));
454 GSIMapAddNodeToBucket(bucket, node);
455 map->nodeCount++;
456 }
457
458 GS_STATIC_INLINE void
GSIMapRemoveNodeFromBucket(GSIMapBucket bucket,GSIMapNode node)459 GSIMapRemoveNodeFromBucket(GSIMapBucket bucket, GSIMapNode node)
460 {
461 bucket->nodeCount--;
462 GSIMapUnlinkNodeFromBucket(bucket, node);
463 }
464
465 GS_STATIC_INLINE void
GSIMapRemoveNodeFromMap(GSIMapTable map,GSIMapBucket bkt,GSIMapNode node)466 GSIMapRemoveNodeFromMap(GSIMapTable map, GSIMapBucket bkt, GSIMapNode node)
467 {
468 map->nodeCount--;
469 GSIMapRemoveNodeFromBucket(bkt, node);
470 }
471
472 GS_STATIC_INLINE void
GSIMapFreeNode(GSIMapTable map,GSIMapNode node)473 GSIMapFreeNode(GSIMapTable map, GSIMapNode node)
474 {
475 GSI_MAP_RELEASE_KEY(map, node->key);
476 GSI_MAP_CLEAR_KEY(node);
477 #if GSI_MAP_HAS_VALUE
478 GSI_MAP_RELEASE_VAL(map, node->value);
479 GSI_MAP_CLEAR_VAL(node);
480 #endif
481
482 node->nextInBucket = map->freeNodes;
483 map->freeNodes = node;
484 }
485
486 GS_STATIC_INLINE GSIMapNode
GSIMapRemoveAndFreeNode(GSIMapTable map,uintptr_t bkt,GSIMapNode node)487 GSIMapRemoveAndFreeNode(GSIMapTable map, uintptr_t bkt, GSIMapNode node)
488 {
489 GSIMapNode next = node->nextInBucket;
490 GSIMapRemoveNodeFromMap(map, &(map->buckets[bkt]), node);
491 GSIMapFreeNode(map, node);
492 return next;
493 }
494
495 GS_STATIC_INLINE void
GSIMapRemoveWeak(GSIMapTable map)496 GSIMapRemoveWeak(GSIMapTable map)
497 {
498 if (GSI_MAP_ZEROED(map))
499 {
500 uintptr_t bucketCount = map->bucketCount;
501 GSIMapBucket bucket = map->buckets;
502
503 while (bucketCount-- > 0)
504 {
505 GSIMapNode node = bucket->firstNode;
506
507 while (node != 0)
508 {
509 GSIMapNode next = node->nextInBucket;
510 if (GSI_MAP_NODE_IS_EMPTY(map, node))
511 {
512 GSIMapRemoveNodeFromMap(map, bucket, node);
513 GSIMapFreeNode(map, node);
514 }
515 node = next;
516 }
517 bucket++;
518 }
519 return;
520 }
521 }
522
523 GS_STATIC_INLINE void
GSIMapRemangleBuckets(GSIMapTable map,GSIMapBucket old_buckets,uintptr_t old_bucketCount,GSIMapBucket new_buckets,uintptr_t new_bucketCount)524 GSIMapRemangleBuckets(GSIMapTable map,
525 GSIMapBucket old_buckets, uintptr_t old_bucketCount,
526 GSIMapBucket new_buckets, uintptr_t new_bucketCount)
527 {
528 if (GSI_MAP_ZEROED(map))
529 {
530 while (old_bucketCount-- > 0)
531 {
532 GSIMapNode node;
533
534 while ((node = old_buckets->firstNode) != 0)
535 {
536 if (GSI_MAP_NODE_IS_EMPTY(map, node))
537 {
538 GSIMapRemoveNodeFromMap(map, old_buckets, node);
539 GSIMapFreeNode(map, node);
540 }
541 else
542 {
543 GSIMapBucket bkt;
544
545 GSIMapRemoveNodeFromBucket(old_buckets, node);
546 bkt = GSIMapPickBucket(GSI_MAP_HASH(map,
547 GSI_MAP_READ_KEY(map, &node->key)),
548 new_buckets, new_bucketCount);
549 GSIMapAddNodeToBucket(bkt, node);
550 }
551 }
552 old_buckets++;
553 }
554 return;
555 }
556 while (old_bucketCount-- > 0)
557 {
558 GSIMapNode node;
559
560 while ((node = old_buckets->firstNode) != 0)
561 {
562 GSIMapBucket bkt;
563
564 GSIMapRemoveNodeFromBucket(old_buckets, node);
565 bkt = GSIMapPickBucket(GSI_MAP_HASH(map,
566 GSI_MAP_READ_KEY(map, &node->key)),
567 new_buckets, new_bucketCount);
568 GSIMapAddNodeToBucket(bkt, node);
569 }
570 old_buckets++;
571 }
572 }
573
574 GS_STATIC_INLINE void
GSIMapMoreNodes(GSIMapTable map,unsigned required)575 GSIMapMoreNodes(GSIMapTable map, unsigned required)
576 {
577 GSIMapNode *newArray;
578
579 newArray = (GSIMapNode*)NSZoneCalloc(map->zone,
580 (map->chunkCount+1), sizeof(GSIMapNode));
581 if (newArray)
582 {
583 GSIMapNode newNodes;
584 uintptr_t chunkCount;
585
586 if (map->nodeChunks != 0)
587 {
588 memcpy(newArray, map->nodeChunks,
589 (map->chunkCount)*sizeof(GSIMapNode));
590 NSZoneFree(map->zone, map->nodeChunks);
591 }
592 map->nodeChunks = newArray;
593
594 if (required == 0)
595 {
596 if (map->chunkCount == 0)
597 {
598 chunkCount = map->bucketCount > 1 ? map->bucketCount : 2;
599 }
600 else
601 {
602 chunkCount = ((map->nodeCount>>2)+1)<<1;
603 }
604 }
605 else
606 {
607 chunkCount = required;
608 }
609 newNodes
610 = (GSIMapNode)NSZoneCalloc(map->zone, chunkCount, sizeof(GSIMapNode_t));
611 if (newNodes)
612 {
613 map->nodeChunks[map->chunkCount++] = newNodes;
614 newNodes[--chunkCount].nextInBucket = map->freeNodes;
615 while (chunkCount--)
616 {
617 newNodes[chunkCount].nextInBucket = &newNodes[chunkCount+1];
618 }
619 map->freeNodes = newNodes;
620 }
621 else
622 {
623 [NSException raise: NSMallocException format: @"No memory for nodes"];
624 }
625 }
626 else
627 {
628 [NSException raise: NSMallocException format: @"No memory for chunks"];
629 }
630 }
631
632 GS_STATIC_INLINE GSIMapNode
GSIMapNodeForKeyInBucket(GSIMapTable map,GSIMapBucket bucket,GSIMapKey key)633 GSIMapNodeForKeyInBucket(GSIMapTable map, GSIMapBucket bucket, GSIMapKey key)
634 {
635 GSIMapNode node = bucket->firstNode;
636
637 if (GSI_MAP_ZEROED(map))
638 {
639 while ((node != 0)
640 && GSI_MAP_EQUAL(map, GSI_MAP_READ_KEY(map, &node->key), key) == NO)
641 {
642 GSIMapNode tmp = node->nextInBucket;
643
644 if (GSI_MAP_NODE_IS_EMPTY(map, node))
645 {
646 GSIMapRemoveNodeFromMap(map, bucket, node);
647 GSIMapFreeNode(map, node);
648 }
649 node = tmp;
650 }
651 return node;
652 }
653 while ((node != 0)
654 && GSI_MAP_EQUAL(map, GSI_MAP_READ_KEY(map, &node->key), key) == NO)
655 {
656 node = node->nextInBucket;
657 }
658 return node;
659 }
660
661 GS_STATIC_INLINE GSIMapNode
GSIMapNodeForKey(GSIMapTable map,GSIMapKey key)662 GSIMapNodeForKey(GSIMapTable map, GSIMapKey key)
663 {
664 GSIMapBucket bucket;
665 GSIMapNode node;
666
667 if (map->nodeCount == 0)
668 {
669 return 0;
670 }
671 bucket = GSIMapBucketForKey(map, key);
672 node = GSIMapNodeForKeyInBucket(map, bucket, key);
673 return node;
674 }
675
676 GS_STATIC_INLINE GSIMapNode
GSIMapFirstNode(GSIMapTable map)677 GSIMapFirstNode(GSIMapTable map)
678 {
679 if (map->nodeCount > 0)
680 {
681 uintptr_t count = map->bucketCount;
682 uintptr_t bucket = 0;
683 GSIMapNode node = 0;
684
685 if (GSI_MAP_ZEROED(map))
686 {
687 while (bucket < count)
688 {
689 node = map->buckets[bucket].firstNode;
690 while (node != 0 && GSI_MAP_NODE_IS_EMPTY(map, node))
691 {
692 node = GSIMapRemoveAndFreeNode(map, bucket, node);
693 }
694 if (node != 0)
695 {
696 break;
697 }
698 bucket++;
699 }
700 return node;
701 }
702 while (bucket < count)
703 {
704 node = map->buckets[bucket].firstNode;
705 if (node != 0)
706 {
707 break;
708 }
709 bucket++;
710 }
711 return node;
712 }
713 else
714 {
715 return 0;
716 }
717 }
718
719 #if (GSI_MAP_KTYPES & GSUNION_INT)
720 /*
721 * Specialized lookup for the case where keys are known to be simple integer
722 * or pointer values that are their own hash values (when converted to unsigned
723 * integers) and can be compared with a test for integer equality.
724 */
725 GS_STATIC_INLINE GSIMapNode
GSIMapNodeForSimpleKey(GSIMapTable map,GSIMapKey key)726 GSIMapNodeForSimpleKey(GSIMapTable map, GSIMapKey key)
727 {
728 GSIMapBucket bucket;
729 GSIMapNode node;
730
731 if (map->nodeCount == 0)
732 {
733 return 0;
734 }
735 bucket = map->buckets + ((unsigned)key.addr) % map->bucketCount;
736 node = bucket->firstNode;
737 if (GSI_MAP_ZEROED(map))
738 {
739 while ((node != 0) && GSI_MAP_READ_KEY(map, &node->key).addr != key.addr)
740 {
741 GSIMapNode tmp = node->nextInBucket;
742
743 if (GSI_MAP_NODE_IS_EMPTY(map, node))
744 {
745 GSIMapRemoveNodeFromMap(map, bucket, node);
746 GSIMapFreeNode(map, node);
747 }
748 node = tmp;
749 }
750 return node;
751 }
752 while ((node != 0) && GSI_MAP_READ_KEY(map, &node->key).addr != key.addr)
753 {
754 node = node->nextInBucket;
755 }
756 return node;
757 }
758 #endif
759
760 GS_STATIC_INLINE void
GSIMapResize(GSIMapTable map,uintptr_t new_capacity)761 GSIMapResize(GSIMapTable map, uintptr_t new_capacity)
762 {
763 GSIMapBucket new_buckets;
764 uintptr_t size = 1;
765 uintptr_t old = 1;
766
767 /*
768 * Find next size up in the fibonacci series
769 */
770 while (size < new_capacity)
771 {
772 uintptr_t tmp = old;
773
774 old = size;
775 size += tmp;
776 }
777 /*
778 * Avoid even numbers - since hash functions frequently generate uneven
779 * distributions around powers of two -
780 * we don't want lots of keys falling into a single bucket.
781 */
782 if (size % 2 == 0)
783 {
784 size++;
785 }
786
787 /* Use the zone specified for this map.
788 */
789 new_buckets = (GSIMapBucket)NSZoneCalloc(map->zone, size,
790 sizeof(GSIMapBucket_t));
791
792 if (new_buckets != 0)
793 {
794 GSIMapRemangleBuckets(map, map->buckets, map->bucketCount, new_buckets,
795 size);
796 if (map->buckets != 0)
797 {
798 NSZoneFree(map->zone, map->buckets);
799 }
800 map->buckets = new_buckets;
801 map->bucketCount = size;
802 }
803 }
804
805 GS_STATIC_INLINE void
GSIMapRightSizeMap(GSIMapTable map,uintptr_t capacity)806 GSIMapRightSizeMap(GSIMapTable map, uintptr_t capacity)
807 {
808 /* FIXME: Now, this is a guess, based solely on my intuition. If anyone
809 * knows of a better ratio (or other test, for that matter) and can
810 * provide evidence of its goodness, please get in touch with me, Albin
811 * L. Jones <Albin.L.Jones@Dartmouth.EDU>. */
812
813 if (3 * capacity >= 4 * map->bucketCount)
814 {
815 GSIMapResize(map, (3 * capacity)/4 + 1);
816 }
817 }
818
819 /** Enumerating **/
820
821 /* IMPORTANT WARNING: Enumerators have a wonderous property.
822 * Once a node has been returned by `GSIMapEnumeratorNextNode()', it may be
823 * removed from the map without effecting the rest of the current
824 * enumeration. */
825
826 /* EXTREMELY IMPORTANT WARNING: The purpose of this warning is point
827 * out that, various (i.e., many) functions currently depend on
828 * the behaviour outlined above. So be prepared for some serious
829 * breakage when you go fudging around with these things. */
830
831 /**
832 * Create an return an enumerator for the specified map.<br />
833 * You must call GSIMapEndEnumerator() when you have finished
834 * with the enumerator.<br />
835 * <strong>WARNING</strong> You should not alter a map while an enumeration
836 * is in progress. The results of doing so are reasonably unpredictable.
837 * <br />Remember, DON'T MESS WITH A MAP WHILE YOU'RE ENUMERATING IT.
838 */
839 GS_STATIC_INLINE GSIMapEnumerator_t
GSIMapEnumeratorForMap(GSIMapTable map)840 GSIMapEnumeratorForMap(GSIMapTable map)
841 {
842 GSIMapEnumerator_t enumerator;
843
844 enumerator.map = map;
845 enumerator.node = 0;
846 enumerator.bucket = 0;
847 /*
848 * Locate next bucket and node to be returned.
849 */
850 if (GSI_MAP_ZEROED(map))
851 {
852 while (enumerator.bucket < map->bucketCount)
853 {
854 GSIMapNode node = map->buckets[enumerator.bucket].firstNode;
855
856 while (node != 0 && GSI_MAP_READ_KEY(map, &node->key).addr == 0)
857 {
858 node = GSIMapRemoveAndFreeNode(map, enumerator.bucket, node);
859 }
860 if ((enumerator.node = node) != 0)
861 {
862 return enumerator;
863 }
864 enumerator.bucket++;
865 }
866 }
867 while (enumerator.bucket < map->bucketCount)
868 {
869 enumerator.node = map->buckets[enumerator.bucket].firstNode;
870 if (enumerator.node != 0)
871 {
872 return enumerator; // Got first node, and recorded its bucket.
873 }
874 enumerator.bucket++;
875 }
876
877 return enumerator;
878 }
879
880 /**
881 * Tidies up after map enumeration ... effectively destroys the enumerator.
882 */
883 GS_STATIC_INLINE void
GSIMapEndEnumerator(GSIMapEnumerator enumerator)884 GSIMapEndEnumerator(GSIMapEnumerator enumerator)
885 {
886 ((_GSIE)enumerator)->map = 0;
887 ((_GSIE)enumerator)->node = 0;
888 ((_GSIE)enumerator)->bucket = 0;
889 }
890
891 /**
892 * Returns the bucket from which the next node in the enumeration will
893 * come. Once the next node has been enumerated, you can use the
894 * bucket and node to remove the node from the map using the
895 * GSIMapRemoveNodeFromMap() function.
896 */
897 GS_STATIC_INLINE GSIMapBucket
GSIMapEnumeratorBucket(GSIMapEnumerator enumerator)898 GSIMapEnumeratorBucket(GSIMapEnumerator enumerator)
899 {
900 if (((_GSIE)enumerator)->node != 0)
901 {
902 GSIMapTable map = ((_GSIE)enumerator)->map;
903
904 return &((map->buckets)[((_GSIE)enumerator)->bucket]);
905 }
906 return 0;
907 }
908
909 /**
910 * Returns the next node in the map, or a nul pointer if at the end.
911 */
912 GS_STATIC_INLINE GSIMapNode
GSIMapEnumeratorNextNode(GSIMapEnumerator enumerator)913 GSIMapEnumeratorNextNode(GSIMapEnumerator enumerator)
914 {
915 GSIMapNode node = ((_GSIE)enumerator)->node;
916 GSIMapTable map = ((_GSIE)enumerator)->map;
917
918 /* Find the frst available non-zeroed node.
919 */
920 if (node != 0 && GSI_MAP_ZEROED(map)
921 && GSI_MAP_READ_KEY(map, &node->key).addr == 0)
922 {
923 uintptr_t bucketCount = map->bucketCount;
924 uintptr_t bucket = ((_GSIE)enumerator)->bucket;
925
926 while (node != 0 && GSI_MAP_READ_KEY(map, &node->key).addr == 0)
927 {
928 node = GSIMapRemoveAndFreeNode(map, bucket, node);
929 while (node == 0 && ++bucket < bucketCount)
930 {
931 node = (map->buckets[bucket]).firstNode;
932 while (node != 0 && GSI_MAP_READ_KEY(map, &node->key).addr == 0)
933 {
934 node = GSIMapRemoveAndFreeNode(map, bucket, node);
935 }
936 }
937 ((_GSIE)enumerator)->bucket = bucket;
938 ((_GSIE)enumerator)->node = node;
939 }
940 }
941
942 if (node != 0)
943 {
944 GSIMapNode next = node->nextInBucket;
945
946 if (GSI_MAP_ZEROED(map))
947 {
948 uintptr_t bucket = ((_GSIE)enumerator)->bucket;
949
950 while (next != 0 && GSI_MAP_NODE_IS_EMPTY(map, next))
951 {
952 next = GSIMapRemoveAndFreeNode(map, bucket, next);
953 }
954 }
955
956 if (next == 0)
957 {
958 uintptr_t bucketCount = map->bucketCount;
959 uintptr_t bucket = ((_GSIE)enumerator)->bucket;
960
961 if (GSI_MAP_ZEROED(map))
962 {
963 while (next == 0 && ++bucket < bucketCount)
964 {
965 next = (map->buckets[bucket]).firstNode;
966 while (next != 0 && GSI_MAP_NODE_IS_EMPTY(map, next))
967 {
968 next = GSIMapRemoveAndFreeNode(map, bucket, next);
969 }
970 }
971 ((_GSIE)enumerator)->bucket = bucket;
972 ((_GSIE)enumerator)->node = next;
973 return node;
974 }
975 while (next == 0 && ++bucket < bucketCount)
976 {
977 next = (map->buckets[bucket]).firstNode;
978 }
979 ((_GSIE)enumerator)->bucket = bucket;
980 }
981 ((_GSIE)enumerator)->node = next;
982 }
983 return node;
984 }
985
986 /**
987 * Used to implement fast enumeration methods in classes that use GSIMap for
988 * their data storage.
989 */
990 GS_STATIC_INLINE NSUInteger
GSIMapCountByEnumeratingWithStateObjectsCount(GSIMapTable map,NSFastEnumerationState * state,id * stackbuf,NSUInteger len)991 GSIMapCountByEnumeratingWithStateObjectsCount(GSIMapTable map,
992 NSFastEnumerationState *state, id *stackbuf, NSUInteger len)
993 {
994 NSInteger count;
995 NSInteger i;
996
997 /* We can store a GSIMapEnumerator inside the extra buffer in state on all
998 * platforms that don't suck beyond belief (i.e. everything except win64),
999 * but we can't on anything where long is 32 bits and pointers are 64 bits,
1000 * so we have to construct it here to avoid breaking on that platform.
1001 */
1002 struct GSPartMapEnumerator
1003 {
1004 GSIMapNode node;
1005 uintptr_t bucket;
1006 };
1007 GSIMapEnumerator_t enumerator;
1008
1009 count = MIN(len, map->nodeCount - state->state);
1010
1011 /* Construct the real enumerator */
1012 if (0 == state->state)
1013 {
1014 enumerator = GSIMapEnumeratorForMap(map);
1015 }
1016 else
1017 {
1018 enumerator.map = map;
1019 enumerator.node = ((struct GSPartMapEnumerator*)(state->extra))->node;
1020 enumerator.bucket = ((struct GSPartMapEnumerator*)(state->extra))->bucket;
1021 }
1022 /* Get the next count objects and put them in the stack buffer. */
1023 for (i = 0; i < count; i++)
1024 {
1025 GSIMapNode node = GSIMapEnumeratorNextNode(&enumerator);
1026 if (0 != node)
1027 {
1028 /* UGLY HACK: Lets this compile with any key type. Fast enumeration
1029 * will only work with things that are id-sized, however, so don't
1030 * try using it with non-object collections.
1031 */
1032 stackbuf[i] = (id)GSI_MAP_READ_KEY(map, &node->key).addr;
1033 }
1034 }
1035 /* Store the important bits of the enumerator in the caller. */
1036 ((struct GSPartMapEnumerator*)(state->extra))->node = enumerator.node;
1037 ((struct GSPartMapEnumerator*)(state->extra))->bucket = enumerator.bucket;
1038 /* Update the rest of the state. */
1039 state->state += count;
1040 state->itemsPtr = stackbuf;
1041 return count;
1042 }
1043
1044 #if GSI_MAP_HAS_VALUE
1045 GS_STATIC_INLINE GSIMapNode
GSIMapAddPairNoRetain(GSIMapTable map,GSIMapKey key,GSIMapVal value)1046 GSIMapAddPairNoRetain(GSIMapTable map, GSIMapKey key, GSIMapVal value)
1047 {
1048 GSIMapNode node = map->freeNodes;
1049
1050 if (node == 0)
1051 {
1052 GSIMapMoreNodes(map, map->nodeCount < map->increment ? 0: map->increment);
1053 node = map->freeNodes;
1054 }
1055 map->freeNodes = node->nextInBucket;
1056 GSI_MAP_WRITE_KEY(map, &node->key, key);
1057 GSI_MAP_WRITE_VAL(map, &node->value, value);
1058 node->nextInBucket = 0;
1059 GSIMapRightSizeMap(map, map->nodeCount);
1060 GSIMapAddNodeToMap(map, node);
1061 return node;
1062 }
1063
1064 GS_STATIC_INLINE GSIMapNode
GSIMapAddPair(GSIMapTable map,GSIMapKey key,GSIMapVal value)1065 GSIMapAddPair(GSIMapTable map, GSIMapKey key, GSIMapVal value)
1066 {
1067 GSIMapNode node = map->freeNodes;
1068
1069 if (node == 0)
1070 {
1071 GSIMapMoreNodes(map, map->nodeCount < map->increment ? 0: map->increment);
1072 node = map->freeNodes;
1073 }
1074 map->freeNodes = node->nextInBucket;
1075 GSI_MAP_WRITE_KEY(map, &node->key, key);
1076 GSI_MAP_RETAIN_KEY(map, node->key);
1077 GSI_MAP_WRITE_VAL(map, &node->value, value);
1078 GSI_MAP_RETAIN_VAL(map, node->value);
1079 node->nextInBucket = 0;
1080 GSIMapRightSizeMap(map, map->nodeCount);
1081 GSIMapAddNodeToMap(map, node);
1082 return node;
1083 }
1084 #else
1085 GS_STATIC_INLINE GSIMapNode
GSIMapAddKeyNoRetain(GSIMapTable map,GSIMapKey key)1086 GSIMapAddKeyNoRetain(GSIMapTable map, GSIMapKey key)
1087 {
1088 GSIMapNode node = map->freeNodes;
1089
1090 if (node == 0)
1091 {
1092 GSIMapMoreNodes(map, map->nodeCount < map->increment ? 0: map->increment);
1093 node = map->freeNodes;
1094 }
1095 map->freeNodes = node->nextInBucket;
1096 GSI_MAP_WRITE_KEY(map, &node->key, key);
1097 node->nextInBucket = 0;
1098 GSIMapRightSizeMap(map, map->nodeCount);
1099 GSIMapAddNodeToMap(map, node);
1100 return node;
1101 }
1102
1103 GS_STATIC_INLINE GSIMapNode
GSIMapAddKey(GSIMapTable map,GSIMapKey key)1104 GSIMapAddKey(GSIMapTable map, GSIMapKey key)
1105 {
1106 GSIMapNode node = map->freeNodes;
1107
1108 if (node == 0)
1109 {
1110 GSIMapMoreNodes(map, map->nodeCount < map->increment ? 0: map->increment);
1111 node = map->freeNodes;
1112 }
1113 map->freeNodes = node->nextInBucket;
1114 GSI_MAP_WRITE_KEY(map, &node->key, key);
1115 GSI_MAP_RETAIN_KEY(map, node->key);
1116 node->nextInBucket = 0;
1117 GSIMapRightSizeMap(map, map->nodeCount);
1118 GSIMapAddNodeToMap(map, node);
1119 return node;
1120 }
1121 #endif
1122
1123 /**
1124 * Removes the item for the specified key from the map.
1125 * If the key was present, returns YES, otherwise returns NO.
1126 */
1127 GS_STATIC_INLINE BOOL
GSIMapRemoveKey(GSIMapTable map,GSIMapKey key)1128 GSIMapRemoveKey(GSIMapTable map, GSIMapKey key)
1129 {
1130 GSIMapBucket bucket = GSIMapBucketForKey(map, key);
1131 GSIMapNode node;
1132
1133 node = GSIMapNodeForKeyInBucket(map, bucket, key);
1134 if (node != 0)
1135 {
1136 GSIMapRemoveNodeFromMap(map, bucket, node);
1137 GSIMapFreeNode(map, node);
1138 return YES;
1139 }
1140 return NO;
1141 }
1142
1143 GS_STATIC_INLINE void
GSIMapCleanMap(GSIMapTable map)1144 GSIMapCleanMap(GSIMapTable map)
1145 {
1146 if (map->nodeCount > 0)
1147 {
1148 GSIMapBucket bucket = map->buckets;
1149 unsigned int i;
1150 GSIMapNode startNode = 0;
1151 GSIMapNode prevNode = 0;
1152 GSIMapNode node;
1153
1154 map->nodeCount = 0;
1155 for (i = 0; i < map->bucketCount; i++)
1156 {
1157 node = bucket->firstNode;
1158 if (prevNode != 0)
1159 {
1160 prevNode->nextInBucket = node;
1161 }
1162 else
1163 {
1164 startNode = node;
1165 }
1166 while(node != 0)
1167 {
1168 GSI_MAP_RELEASE_KEY(map, node->key);
1169 GSI_MAP_CLEAR_KEY(node);
1170
1171 #if GSI_MAP_HAS_VALUE
1172 GSI_MAP_RELEASE_VAL(map, node->value);
1173 GSI_MAP_CLEAR_VAL(node);
1174 #endif
1175 prevNode = node;
1176 node = node->nextInBucket;
1177 }
1178 bucket->nodeCount = 0;
1179 bucket->firstNode = 0;
1180 bucket++;
1181 }
1182 if (prevNode != 0)
1183 {
1184 prevNode->nextInBucket = map->freeNodes;
1185 }
1186 map->freeNodes = startNode;
1187 }
1188 }
1189
1190 GS_STATIC_INLINE void
GSIMapEmptyMap(GSIMapTable map)1191 GSIMapEmptyMap(GSIMapTable map)
1192 {
1193 #ifdef GSI_MAP_NOCLEAN
1194 if (GSI_MAP_NOCLEAN)
1195 {
1196 map->nodeCount = 0;
1197 }
1198 else
1199 {
1200 GSIMapCleanMap(map);
1201 }
1202 #else
1203 GSIMapCleanMap(map);
1204 #endif
1205 if (map->buckets != 0)
1206 {
1207 NSZoneFree(map->zone, map->buckets);
1208 map->buckets = 0;
1209 map->bucketCount = 0;
1210 }
1211 if (map->nodeChunks != 0)
1212 {
1213 unsigned int i;
1214
1215 for (i = 0; i < map->chunkCount; i++)
1216 {
1217 NSZoneFree(map->zone, map->nodeChunks[i]);
1218 }
1219 NSZoneFree(map->zone, map->nodeChunks);
1220 map->chunkCount = 0;
1221 map->nodeChunks = 0;
1222 }
1223 map->freeNodes = 0;
1224 map->zone = 0;
1225 }
1226
1227 GS_STATIC_INLINE void
GSIMapInitWithZoneAndCapacity(GSIMapTable map,NSZone * zone,uintptr_t capacity)1228 GSIMapInitWithZoneAndCapacity(GSIMapTable map, NSZone *zone, uintptr_t capacity)
1229 {
1230 map->zone = zone;
1231 map->nodeCount = 0;
1232 map->bucketCount = 0;
1233 map->buckets = 0;
1234 map->nodeChunks = 0;
1235 map->freeNodes = 0;
1236 map->chunkCount = 0;
1237 map->increment = 300000; // choosen so the chunksize will be less than 4Mb
1238 GSIMapRightSizeMap(map, capacity);
1239 GSIMapMoreNodes(map, capacity);
1240 }
1241
1242 GS_STATIC_INLINE NSUInteger
GSIMapSize(GSIMapTable map)1243 GSIMapSize(GSIMapTable map)
1244 {
1245 NSUInteger index;
1246 NSUInteger size;
1247 GSIMapNode node;
1248
1249 /* Map table plus arrays of pointers to chunks
1250 */
1251 size = GSI_MAP_TABLE_S + map->chunkCount * sizeof(void*);
1252
1253 /* Add the array of buckets.
1254 */
1255 size += map->bucketCount * sizeof(GSIMapBucket_t);
1256
1257 /* Add the free nodes.
1258 */
1259 for (node = map->freeNodes; 0 != node; node = node->nextInBucket)
1260 {
1261 size += sizeof(GSIMapNode_t);
1262 }
1263
1264 /* Add the used nodes (in the buckets).
1265 */
1266 for (index = 0; index < map->bucketCount; index++)
1267 {
1268 size += sizeof(GSIMapNode_t) * map->buckets[index].nodeCount;
1269 }
1270 return size;
1271 }
1272
1273 #if defined(__cplusplus)
1274 }
1275 #endif
1276
1277 #endif /* OS_API_VERSION(GS_API_NONE,GS_API_NONE) */
1278
1279