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