1 /*
2  pblMap.c - C implementation of a Map similar
3  to the Java Map.
4 
5  Copyright (C) 2010   Peter Graf
6 
7  This file is part of PBL - The Program Base Library.
8  PBL is free software.
9 
10  This library is free software; you can redistribute it and/or
11  modify it under the terms of the GNU Lesser General Public
12  License as published by the Free Software Foundation; either
13  version 2.1 of the License, or (at your option) any later version.
14 
15  This library is distributed in the hope that it will be useful,
16  but WITHOUT ANY WARRANTY; without even the implied warranty of
17  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18  Lesser General Public License for more details.
19 
20  You should have received a copy of the GNU Lesser General Public
21  License along with this library; if not, write to the Free Software
22  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
23 
24  For more information on the Program Base Library or Peter Graf,
25  please see: http://www.mission-base.com/.
26 
27  $Log: pblMap.c,v $
28  Revision 1.7  2010/05/30 20:06:45  peter
29  Removed warnings found by 'Microsoft Visual C++ 2010'.
30 
31  Revision 1.6  2010/05/20 21:42:53  peter
32  Added pblSetReplace.
33 
34  Revision 1.5  2010/05/19 22:38:45  peter
35  Testing the map.
36 
37  Revision 1.4  2010/05/16 20:57:24  peter
38  Working on maps
39 
40  Revision 1.3  2010/05/16 01:06:45  peter
41  More work on maps.
42 
43  Revision 1.2  2010/05/15 16:33:43  peter
44  Some fixes.
45 
46  Revision 1.1  2010/05/15 16:26:10  peter
47  Exposing the map interface.
48 
49  */
50 
51 /*
52  * Make sure "strings <exe> | grep Id | sort -u" shows the source file versions
53  */
54 char* pblMap_c_id = "$Id: pblMap.c,v 1.7 2010/05/30 20:06:45 peter Exp $";
55 
56 #include <stdio.h>
57 #include <memory.h>
58 
59 #ifndef __APPLE__
60 #include <stdlib.h>
61 #endif
62 
63 #include <stdlib.h>
64 
65 #include "pbl.h"
66 
67 /*****************************************************************************/
68 /* #defines                                                                  */
69 /*****************************************************************************/
70 #define PBL_MAP_ENTRY_TAG               1
71 #define PBL_MAP_KEY_TAG                 2
72 
73 /*****************************************************************************/
74 /* Globals                                                                   */
75 /*****************************************************************************/
76 
77 /*****************************************************************************/
78 /* Function declarations                                                     */
79 /*****************************************************************************/
80 
81 /*****************************************************************************/
82 /* Functions                                                                 */
83 /*****************************************************************************/
84 
85 /*
86  * Hash value function used for map entries.
87  *
88  * @return int rc: The hash value of the entry that was passed.
89  */
pblMapEntryHashValue(const void * element)90 static int pblMapEntryHashValue( /*                                          */
91 const void *element /**                 Element to calculate hash value for  */
92 )
93 {
94     PblMapEntry * entry = (PblMapEntry*)element;
95 
96     if( !entry || 0 == entry->keyLength )
97     {
98         return 0;
99     }
100 
101     if( entry->tag == PBL_MAP_ENTRY_TAG )
102     {
103         return pblHtHashValue( (unsigned char *)entry->buffer, entry->keyLength );
104     }
105     else
106     {
107         PblMapKey * key = (PblMapKey*)element;
108         return pblHtHashValue( (unsigned char *)key->key, key->keyLength );
109     }
110 }
111 
112 /*
113  * Compares two map entries.
114  *
115  * Used as compare function for maps.
116  *
117  * @return int rc  < 0: left is smaller than right
118  * @return int rc == 0: left and right are equal
119  * @return int rc  > 0: left is greater than right
120  */
pblMapEntryCompareFunction(const void * left,const void * right)121 static int pblMapEntryCompareFunction( /*                                    */
122 const void * left, /*                     The left value for the comparison  */
123 const void * right /*                     The right value for the comparison */
124 )
125 {
126     PblMapEntry * leftEntry = *(PblMapEntry**)left;
127     PblMapEntry * rightEntry = *(PblMapEntry**)right;
128 
129     if( !leftEntry )
130     {
131         if( rightEntry )
132         {
133             return -1;
134         }
135         return 0;
136     }
137     if( !rightEntry )
138     {
139         return 1;
140     }
141     if( leftEntry->tag == PBL_MAP_ENTRY_TAG )
142     {
143         if( rightEntry->tag == PBL_MAP_ENTRY_TAG )
144         {
145             return pbl_memcmp( leftEntry->buffer, leftEntry->keyLength,
146                                rightEntry->buffer, rightEntry->keyLength );
147         }
148         else
149         {
150             PblMapKey * rightKey = *(PblMapKey**)right;
151 
152             return pbl_memcmp( leftEntry->buffer, leftEntry->keyLength,
153                                rightKey->key, rightKey->keyLength );
154         }
155     }
156     else
157     {
158         PblMapKey * leftKey = *(PblMapKey**)left;
159 
160         if( rightEntry->tag == PBL_MAP_ENTRY_TAG )
161         {
162             return pbl_memcmp( leftKey->key, leftKey->keyLength,
163                                rightEntry->buffer, rightEntry->keyLength );
164         }
165         else
166         {
167             PblMapKey * rightKey = *(PblMapKey**)right;
168 
169             return pbl_memcmp( leftKey->key, leftKey->keyLength, rightKey->key,
170                                rightKey->keyLength );
171         }
172     }
173 }
174 
175 /**
176  * Creates a new tree map.
177  *
178  * This method has a time complexity of O(1).
179  *
180  * @return pblMap * retPtr != NULL: A pointer to the new map.
181  * @return pblMap * retPtr == NULL: An error, see pbl_errno:
182  *
183  * <BR>PBL_ERROR_OUT_OF_MEMORY - Out of memory.
184  */
pblMapNewTreeMap(void)185 PblMap * pblMapNewTreeMap( void )
186 {
187     PblMap * pblMap = (PblMap *)pbl_malloc0( "pblMapNewTreeMap", sizeof(PblMap) );
188     if( !pblMap )
189     {
190         return NULL;
191     }
192 
193     pblMap->entrySet = pblSetNewTreeSet();
194     if( !pblMap->entrySet )
195     {
196         PBL_FREE( pblMap );
197         return NULL;
198     }
199 
200     pblSetSetCompareFunction( pblMap->entrySet, pblMapEntryCompareFunction );
201     pblSetSetHashValueFunction( pblMap->entrySet, pblMapEntryHashValue );
202 
203     return pblMap;
204 }
205 
206 /**
207  * Creates a new hash map.
208  *
209  * This method has a time complexity of O(1).
210  *
211  * @return PblMap * retPtr != NULL: A pointer to the new map.
212  * @return PblMap * retPtr == NULL: An error, see pbl_errno:
213  *
214  * <BR>PBL_ERROR_OUT_OF_MEMORY - Out of memory.
215  */
pblMapNewHashMap(void)216 PblMap * pblMapNewHashMap( void )
217 {
218     PblMap * pblMap = (PblMap *)pbl_malloc0( "pblMapNewHashMap", sizeof(PblMap) );
219     if( !pblMap )
220     {
221         return NULL;
222     }
223 
224     pblMap->entrySet = pblSetNewHashSet();
225     if( !pblMap->entrySet )
226     {
227         PBL_FREE( pblMap );
228         return NULL;
229     }
230 
231     pblSetSetCompareFunction( pblMap->entrySet, pblMapEntryCompareFunction );
232     pblSetSetHashValueFunction( pblMap->entrySet, pblMapEntryHashValue );
233 
234     return pblMap;
235 }
236 
237 /**
238  * Removes all of the mappings from this map. The map will be empty after this call returns.
239  *
240  * <B>Note:</B> The memory of the entries cleared is freed.
241  *
242  * For hash maps this method has a time complexity of O(N).
243  * For tree maps this method has a time complexity of O(N * Log N).
244  *
245  * @return void
246  */
pblMapClear(PblMap * map)247 void pblMapClear( /*                                               */
248 PblMap * map /**                                  The map to clear */
249 )
250 {
251     void * ptr;
252     while( pblSetSize( map->entrySet ) > 0 )
253     {
254         ptr = pblSetRemove( map->entrySet );
255         PBL_FREE(ptr);
256     }
257 }
258 
259 /**
260  * Removes all of the mappings from this map and frees the map's memory from heap.
261  *
262  * For hash maps this method has a time complexity of O(N).
263  * For tree maps this method has a time complexity of O(N * Log N).
264  *
265  * @return void
266  */
pblMapFree(PblMap * map)267 void pblMapFree( /*                                              */
268 PblMap * map /**                                 The map to free */
269 )
270 {
271     pblMapClear( map );
272     pblSetFree( map->entrySet );
273     PBL_FREE(map);
274 }
275 
276 /**
277  * Returns true if this map contains a mapping for the specified string key.
278  *
279  * More formally, returns true if and only if this map contains a mapping for a key k such that
280  * (key==null ? k==null : memcmp( key, k, keyLength ) == 0. (There can be at most one such mapping.)
281  *
282  * For hash maps his method has a time complexity of O(1).
283  * For tree maps this method has a time complexity of O(Log N).
284  *
285  * @return int rc >  0: The map contains a mapping for the specified key.
286  * @return int rc == 0: The map did not contain a mapping for the key.
287  */
pblMapContainsKeyStr(PblMap * map,char * key)288 int pblMapContainsKeyStr( /*                                                 */
289 PblMap * map, /**             The map to check                               */
290 char * key /**                Key whose presence in this map is to be tested */
291 )
292 {
293     return pblMapContainsKey( map, key, key ? 1 + strlen( key ) : 0 );
294 }
295 
296 /**
297  * Returns true if this map contains a mapping for the specified key.
298  *
299  * More formally, returns true if and only if this map contains a mapping for a key k such that
300  * (key==null ? k==null : memcmp( key, k, keyLength ) == 0. (There can be at most one such mapping.)
301  *
302  * For hash maps his method has a time complexity of O(1).
303  * For tree maps this method has a time complexity of O(Log N).
304  *
305  * @return int rc >  0: The map contains a mapping for the specified key.
306  * @return int rc == 0: The map did not contain a mapping for the key.
307  */
pblMapContainsKey(PblMap * map,void * key,size_t keyLength)308 int pblMapContainsKey( /*                                                    */
309 PblMap * map, /**             The map to check                               */
310 void * key, /**               Key whose presence in this map is to be tested */
311 size_t keyLength /**          Length of the key                              */
312 )
313 {
314     PblMapKey mapKey;
315 
316     mapKey.tag = PBL_MAP_KEY_TAG;
317     mapKey.keyLength = keyLength;
318     mapKey.key = key;
319 
320     return pblSetContains( map->entrySet, &mapKey );
321 }
322 
323 /**
324  * Returns true if this map contains a mapping for the specified string value.
325  *
326  * This method has a time complexity of O(N).
327  *
328  * @return int rc >  0: The map contains a mapping for the specified value.
329  * @return int rc == 0: The map did not contain a mapping for the value.
330  * @return int rc <  0:  An error, see pbl_errno:
331  *
332  * <BR>PBL_ERROR_CONCURRENT_MODIFICATION - The underlying collection was modified concurrently.
333  */
pblMapContainsValueStr(PblMap * map,char * value)334 int pblMapContainsValueStr( /*                                               */
335 PblMap * map, /**           The map to check                                 */
336 char * value /**            Value whose presence in this map is to be tested */
337 )
338 {
339     return pblMapContainsValue( map, value, value ? 1 + strlen( value ) : 0 );
340 }
341 
342 /**
343  * Returns true if this map contains a mapping for the specified value.
344  *
345  * This method has a time complexity of O(N).
346  *
347  * @return int rc >  0: The map contains a mapping for the specified value.
348  * @return int rc == 0: The map did not contain a mapping for the value.
349  * @return int rc <  0:  An error, see pbl_errno:
350  *
351  * <BR>PBL_ERROR_CONCURRENT_MODIFICATION - The underlying collection was modified concurrently.
352  */
pblMapContainsValue(PblMap * map,void * value,size_t valueLength)353 int pblMapContainsValue( /*                                                  */
354 PblMap * map, /**           The map to check                                 */
355 void * value, /**           Value whose presence in this map is to be tested */
356 size_t valueLength /**      Length of the value                              */
357 )
358 {
359     int hasNext;
360     void * element;
361     PblMapEntry * entry;
362 
363     PblIterator iterator;
364     pblIteratorInit( map->entrySet, &iterator );
365 
366     while( ( hasNext = pblIteratorHasNext( &iterator ) ) > 0 )
367     {
368         element = pblIteratorNext( &iterator );
369         if( element == (void*)-1 )
370         {
371             // Concurrent modification
372             //
373             return -1;
374         }
375 
376         entry = (PblMapEntry *)element;
377         if( !entry )
378         {
379             continue;
380         }
381 
382         if( entry->valueLength != valueLength )
383         {
384             continue;
385         }
386 
387         if( 0 == valueLength )
388         {
389             return 1;
390         }
391 
392         if( 0 == memcmp( value, entry->buffer + entry->keyLength, valueLength ) )
393         {
394             return 1;
395         }
396     }
397 
398     return 0;
399 }
400 
401 /**
402  * Returns the value to which the specified string key is mapped,
403  * or null if this map contains no mapping for the key.
404  *
405  * More formally, if this map contains a mapping from a key k to a value v such that
406  * (key==null ? k==null : memcmp( key, k, keyLength ) == 0,
407  * then this method returns v; otherwise it returns null.
408  * (There can be at most one such mapping.)
409  *
410  * For hash maps this method has a time complexity of O(1).
411  * For tree maps this method has a time complexity of O(Log N).
412  *
413  * @return void * retptr != NULL: The associated value.
414  * @return void * retptr == NULL: There is no associated value.
415  */
pblMapGetStr(PblMap * map,char * key,size_t * valueLengthPtr)416 void * pblMapGetStr( /*                                                   */
417 PblMap * map, /**            The map to check                             */
418 char * key, /**              Key whose associated value is to be returned */
419 size_t * valueLengthPtr /**  Out: Length of the value returned            */
420 )
421 {
422     return pblMapGet( map, key, key ? 1 + strlen( key ) : 0, valueLengthPtr );
423 }
424 
425 /**
426  * Returns the value to which the specified key is mapped,
427  * or null if this map contains no mapping for the key.
428  *
429  * More formally, if this map contains a mapping from a key k to a value v such that
430  * (key==null ? k==null : memcmp( key, k, keyLength ) == 0,
431  * then this method returns v; otherwise it returns null.
432  * (There can be at most one such mapping.)
433  *
434  * For hash maps this method has a time complexity of O(1).
435  * For tree maps this method has a time complexity of O(Log N).
436  *
437  * @return void * retptr != NULL: The associated value.
438  * @return void * retptr == NULL: There is no associated value.
439  */
pblMapGet(PblMap * map,void * key,size_t keyLength,size_t * valueLengthPtr)440 void * pblMapGet( /*                                                      */
441 PblMap * map, /**            The map to check                             */
442 void * key, /**              Key whose associated value is to be returned */
443 size_t keyLength, /**        Length of the key                            */
444 size_t * valueLengthPtr /**  Out: Length of the value returned            */
445 )
446 {
447     PblMapEntry * mapEntry;
448     PblMapKey mapKey;
449 
450     mapKey.tag = PBL_MAP_KEY_TAG;
451     mapKey.keyLength = keyLength;
452     mapKey.key = key;
453 
454     mapEntry = (PblMapEntry *)pblSetGetElement( map->entrySet, &mapKey );
455     if( !mapEntry )
456     {
457         if( valueLengthPtr )
458         {
459             *valueLengthPtr = 0;
460         }
461         return NULL;
462     }
463 
464     if( valueLengthPtr )
465     {
466         *valueLengthPtr = mapEntry->valueLength;
467     }
468 
469     return mapEntry->buffer + mapEntry->keyLength;
470 }
471 
472 /**
473  * Associates the specified string value with the specified string key in this map.
474  *
475  * If the map previously contained a mapping for the key, the old value is replaced by the specified value.
476  * (A map m is said to contain a mapping for a key k if and only if pblMapContainsKey(k) would return true.)
477  *
478  * For hash maps this method has a time complexity of O(1).
479  * For tree maps this method has a time complexity of O(Log N).
480  *
481  * @return int rc >  0: The map did not already contain a mapping for the key.
482  * @return int rc == 0: The map did already contain a mapping for the key.
483  * @return int rc <  0: An error, see pbl_errno:
484  *
485  * <BR>PBL_ERROR_OUT_OF_MEMORY - Out of memory.
486  * <BR>PBL_ERROR_OUT_OF_BOUNDS - Maximum capacity of the hash set exceeded.
487  */
pblMapAddStrStr(PblMap * map,char * key,char * value)488 int pblMapAddStrStr( /*                                       */
489 PblMap * map, /**                   The map to add to         */
490 char * key, /**                     Key to add a mapping for  */
491 char * value /**                    Value of the new mapping  */
492 )
493 {
494     return pblMapAdd( map, key, key ? 1 + strlen( key ) : 0, value, value ? 1
495             + strlen( value ) : 0 );
496 }
497 
498 /*
499  * Creates a new map entry
500  *
501  * @return void * retptr != NULL: The new entry.
502  * @return void * retptr == NULL: An error, see pbl_errno:
503  *
504  * <BR>PBL_ERROR_OUT_OF_MEMORY - Out of memory.
505  */
pblMapEntryNew(void * key,size_t keyLength,void * value,size_t valueLength)506 static PblMapEntry * pblMapEntryNew( void * key, /**                     Key to add a mapping for  */
507 size_t keyLength, /**               Length of the key         */
508 void * value, /**                   Value of the new mapping  */
509 size_t valueLength /**              Length of the value       */
510 )
511 {
512     PblMapEntry * newEntry = (PblMapEntry *)pbl_malloc( "pblMapEntryNew", sizeof(PblMapEntry)
513             + keyLength + valueLength );
514     if( !newEntry )
515     {
516         return NULL;
517     }
518 
519     newEntry->tag = PBL_MAP_ENTRY_TAG;
520     newEntry->keyLength = keyLength;
521     if( keyLength > 0 )
522     {
523         memcpy( newEntry->buffer, key, keyLength);
524     }
525     newEntry->valueLength = valueLength;
526     if( valueLength > 0 )
527     {
528         memcpy( newEntry->buffer + keyLength, value, valueLength );
529     }
530     return newEntry;
531 }
532 
533 /**
534  * Associates the specified value with the specified key in this map.
535  *
536  * If the map previously contained a mapping for the key, the old value is replaced by the specified value.
537  * (A map m is said to contain a mapping for a key k if and only if pblMapContainsKey(k) would return true.)
538  *
539  * For hash maps this method has a time complexity of O(1).
540  * For tree maps this method has a time complexity of O(Log N).
541  *
542  * @return int rc >  0: The map did not already contain a mapping for the key.
543  * @return int rc == 0: The map did already contain a mapping for the key.
544  * @return int rc <  0: An error, see pbl_errno:
545  *
546  * <BR>PBL_ERROR_OUT_OF_MEMORY - Out of memory.
547  * <BR>PBL_ERROR_OUT_OF_BOUNDS - Maximum capacity of the hash set exceeded.
548  */
pblMapAdd(PblMap * map,void * key,size_t keyLength,void * value,size_t valueLength)549 int pblMapAdd( /*                                             */
550 PblMap * map, /**                   The map to add to         */
551 void * key, /**                     Key to add a mapping for  */
552 size_t keyLength, /**               Length of the key         */
553 void * value, /**                   Value of the new mapping  */
554 size_t valueLength /**              Length of the value       */
555 )
556 {
557     int rc;
558     PblMapEntry * mapEntry;
559     PblMapEntry * newEntry =
560             pblMapEntryNew( key, keyLength, value, valueLength );
561     if( !newEntry )
562     {
563         return -1;
564     }
565 
566     mapEntry = (PblMapEntry *)pblSetReplaceElement( map->entrySet, newEntry );
567     if( mapEntry )
568     {
569         PBL_FREE( mapEntry );
570         return 0;
571     }
572 
573     rc = pblSetAdd( map->entrySet, newEntry );
574     if( rc < 0 )
575     {
576         PBL_FREE(newEntry);
577         return -1;
578     }
579 
580     return 1;
581 }
582 
583 /**
584  * Associates the specified string value with the specified string key in this map.
585  *
586  * If the map previously contained a mapping for the key, the old value is replaced by the specified value.
587  * (A map m is said to contain a mapping for a key k if and only if pblMapContainsKey(k) would return true.)
588  *
589  * Returns the previous value associated with key, NULL if there was no mapping for key
590  * or (void*)-1 in case of an error.
591  *
592  * Note: If a valid pointer to a value is returned, the value returned is
593  * malloced on the heap. It is the caller's responsibility to free that memory
594  * once it is no longer needed.
595  *
596  * For hash maps this method has a time complexity of O(1).
597  * For tree maps this method has a time complexity of O(Log N).
598  *
599  * @return void * retptr != (void*)-1: The previously associated value.
600  * @return void * retptr == (void*)-1: An error, see pbl_errno:
601  *
602  * <BR>PBL_ERROR_OUT_OF_MEMORY - Out of memory.
603  * <BR>PBL_ERROR_OUT_OF_BOUNDS - Maximum capacity of the hash set exceeded.
604  */
pblMapPutStrStr(PblMap * map,char * key,char * value,size_t * valueLengthPtr)605 void * pblMapPutStrStr( /*                                             */
606 PblMap * map, /**                                    The map to add to */
607 char * key, /**                               Key to add a mapping for */
608 char * value, /**                             Value of the new mapping */
609 size_t * valueLengthPtr /**          Out: Length of the value returned */
610 )
611 {
612     return pblMapPut( map, key, key ? 1 + strlen( key ) : 0, value, value ? 1
613             + strlen( value ) : 0, valueLengthPtr );
614 }
615 
616 /**
617  * Associates the specified value with the specified key in this map.
618  *
619  * If the map previously contained a mapping for the key, the old value is replaced by the specified value.
620  * (A map m is said to contain a mapping for a key k if and only if pblMapContainsKey(k) would return true.)
621  *
622  * Returns the previous value associated with key, NULL if there was no mapping for key
623  * or (void*)-1 in case of an error.
624  *
625  * Note: If a valid pointer to a value is returned, the value returned is
626  * malloced on the heap. It is the caller's responsibility to free that memory
627  * once it is no longer needed.
628  *
629  * For hash maps this method has a time complexity of O(1).
630  * For tree maps this method has a time complexity of O(Log N).
631  *
632  * @return void * retptr != (void*)-1: The previously associated value.
633  * @return void * retptr == NULL: There was no previously associated value.
634  * @return void * retptr == (void*)-1: An error, see pbl_errno:
635  *
636  * <BR>PBL_ERROR_OUT_OF_MEMORY - Out of memory.
637  * <BR>PBL_ERROR_OUT_OF_BOUNDS - Maximum capacity of the hash set exceeded.
638  */
pblMapPut(PblMap * map,void * key,size_t keyLength,void * value,size_t valueLength,size_t * valueLengthPtr)639 void * pblMapPut( /*                                                   */
640 PblMap * map, /**                                    The map to add to */
641 void * key, /**                               Key to add a mapping for */
642 size_t keyLength, /**                                Length of the key */
643 void * value, /**                             Value of the new mapping */
644 size_t valueLength, /**                            Length of the value */
645 size_t * valueLengthPtr /**          Out: Length of the value returned */
646 )
647 {
648     int rc;
649     PblMapEntry * mapEntry;
650     PblMapEntry * newEntry =
651             pblMapEntryNew( key, keyLength, value, valueLength );
652     if( !newEntry )
653     {
654         return (void*)-1;
655     }
656 
657     mapEntry = (PblMapEntry *)pblSetReplaceElement( map->entrySet, newEntry );
658     if( mapEntry )
659     {
660         void * retptr;
661 
662         if( mapEntry->valueLength > 0 )
663         {
664             retptr = pbl_memdup( "pblMapPut", mapEntry->buffer
665                     + mapEntry->keyLength, mapEntry->valueLength );
666         }
667         else
668         {
669             retptr = pbl_malloc0( "pblMapPut0", 1 );
670         }
671         if( !retptr )
672         {
673             if( valueLengthPtr )
674             {
675                 *valueLengthPtr = 0;
676             }
677             pblSetReplaceElement( map->entrySet, mapEntry );
678             PBL_FREE( newEntry );
679             return (void*)-1;
680         }
681 
682         if( valueLengthPtr )
683         {
684             *valueLengthPtr = mapEntry->valueLength;
685         }
686         PBL_FREE( mapEntry );
687         return retptr;
688     }
689 
690     if( valueLengthPtr )
691     {
692         *valueLengthPtr = 0;
693     }
694 
695     rc = pblSetAdd( map->entrySet, newEntry );
696     if( rc < 0 )
697     {
698         PBL_FREE(newEntry);
699         return (void*)-1;
700     }
701 
702     return NULL;
703 }
704 
705 /**
706  * Copies all of the mappings from the specified source map to this map.
707  * These mappings will replace any mappings that this map had for any
708  * of the keys currently in the specified map.
709  *
710  * For hash maps this method has a time complexity of O(M).
711  * For tree maps this method has a time complexity of O(M * Log N).
712  * With M being the number of elements in the source map and
713  * N being the number of elements in the target map.
714  *
715  * @return int rc == 0: Ok.
716  * @return int rc <  0:  An error, see pbl_errno:
717  *
718  * <BR>PBL_ERROR_CONCURRENT_MODIFICATION - The source map was modified concurrently.
719  * <BR>PBL_ERROR_OUT_OF_MEMORY - Out of memory.
720  */
pblMapPutAll(PblMap * map,PblMap * sourceMap)721 int pblMapPutAll( /*                                            */
722 PblMap * map, /**                The map to copy the entries to */
723 PblMap * sourceMap /**         The map to copy the entries from */
724 )
725 {
726     int hasNext;
727     void * element;
728     PblMapEntry * entry;
729 
730     PblIterator iterator;
731     pblIteratorInit( sourceMap->entrySet, &iterator );
732 
733     while( ( hasNext = pblIteratorHasNext( &iterator ) ) > 0 )
734     {
735         element = pblIteratorNext( &iterator );
736         if( element == (void*)-1 )
737         {
738             // Concurrent modification
739             //
740             return -1;
741         }
742 
743         entry = (PblMapEntry *)element;
744         if( !entry )
745         {
746             continue;
747         }
748 
749         if( pblMapAdd( map, entry->buffer, entry->keyLength, entry->buffer
750                 + entry->keyLength, entry->valueLength ) < 0 )
751         {
752             return -1;
753         }
754     }
755 
756     return 0;
757 }
758 
759 /**
760  * Removes the mapping for this string key from this map if it is present.
761  *
762  * More formally, if this map contains a mapping from a key k to a value v such that
763  * (key==null ? k==null : memcmp( key, k, keyLength ) == 0,
764  * that mapping is removed.
765  * (The map can contain at most one such mapping.)
766  *
767  * Returns the previous value associated with key,
768  * NULL if there was no mapping for key
769  * or (void*)-1 in case of an error.
770  *
771  * Note: If a valid pointer to a value is returned, the value returned is
772  * malloced on the heap. It is the caller's responsibility to free that memory
773  * once it is no longer needed.
774  *
775  * For hash maps this method has a time complexity of O(1).
776  * For tree maps this method has a time complexity of O(Log N).
777  *
778  * @return void * retptr != (void*)-1: The previously associated value.
779  * @return void * retptr == (void*)-1: An error, see pbl_errno:
780  *
781  * <BR>PBL_ERROR_OUT_OF_MEMORY - Out of memory.
782  */
pblMapRemoveStr(PblMap * map,char * key,size_t * valueLengthPtr)783 void * pblMapRemoveStr( /*                                          */
784 PblMap * map, /**                            The map to remove from */
785 char * key, /**                    Key whose association is removed */
786 size_t * valueLengthPtr /**       Out: Length of the value returned */
787 )
788 {
789     return pblMapRemove( map, key, key ? 1 + strlen( key ) : 0, valueLengthPtr );
790 }
791 
792 /**
793  * Removes the mapping for this key from this map if it is present.
794  *
795  * More formally, if this map contains a mapping from a key k to a value v such that
796  * (key==null ? k==null : memcmp( key, k, keyLength ) == 0,
797  * that mapping is removed.
798  * (The map can contain at most one such mapping.)
799  *
800  * Returns the previous value associated with key,
801  * NULL if there was no mapping for key
802  * or (void*)-1 in case of an error.
803  *
804  * Note: If a valid pointer to a value is returned, the value returned is
805  * malloced on the heap. It is the caller's responsibility to free that memory
806  * once it is no longer needed.
807  *
808  * For hash maps this method has a time complexity of O(1).
809  * For tree maps this method has a time complexity of O(Log N).
810  *
811  * @return void * retptr != (void*)-1: The previously associated value.
812  * @return void * retptr == (void*)-1: An error, see pbl_errno:
813  *
814  * <BR>PBL_ERROR_OUT_OF_MEMORY - Out of memory.
815  */
pblMapRemove(PblMap * map,void * key,size_t keyLength,size_t * valueLengthPtr)816 void * pblMapRemove( /*                                             */
817 PblMap * map, /**                            The map to remove from */
818 void * key, /**                    Key whose association is removed */
819 size_t keyLength, /**                             Length of the key */
820 size_t * valueLengthPtr /**       Out: Length of the value returned */
821 )
822 {
823     PblMapEntry * mapEntry;
824     void * retptr = NULL;
825     PblMapKey mapKey;
826 
827     mapKey.tag = PBL_MAP_KEY_TAG;
828     mapKey.keyLength = keyLength;
829     mapKey.key = key;
830 
831     mapEntry = (PblMapEntry *)pblSetGetElement( map->entrySet, &mapKey );
832     if( !mapEntry )
833     {
834         if( valueLengthPtr )
835         {
836             *valueLengthPtr = 0;
837         }
838         return NULL;
839     }
840 
841     if( mapEntry->valueLength > 0 )
842     {
843         retptr = pbl_memdup( "pblMapRemove", mapEntry->buffer
844                 + mapEntry->keyLength, mapEntry->valueLength );
845     }
846     else
847     {
848         retptr = pbl_malloc0( "pblMapRemove0", 1 );
849     }
850     if( !retptr )
851     {
852         if( valueLengthPtr )
853         {
854             *valueLengthPtr = 0;
855         }
856         return (void*)-1;
857     }
858 
859     if( valueLengthPtr )
860     {
861         *valueLengthPtr = mapEntry->valueLength;
862     }
863 
864     pblSetRemoveElement( map->entrySet, mapEntry );
865 
866     PBL_FREE( mapEntry );
867 
868     return retptr;
869 }
870 
871 /**
872  * Tests if this map has no elements.
873  *
874  * This method has a time complexity of O(1).
875  *
876  * @return int rc != 0: This map has no elements.
877  * @return int rc == 0: This map has elements.
878  */
pblMapIsEmpty(PblMap * map)879 int pblMapIsEmpty( /*                               */
880 PblMap * map /**                    The map to test */
881 )
882 {
883     return 0 == map->entrySet->size;
884 }
885 
886 /**
887  * Returns the number of entries in this map.
888  *
889  * This method has a time complexity of O(1).
890  *
891  * @return int rc: The number of entries in this map.
892  */
pblMapSize(PblMap * map)893 int pblMapSize( /*                              */
894 PblMap * map /**                 The map to use */
895 )
896 {
897     return map->entrySet->size;
898 }
899 
900 /**
901  * Returns an iterator over the map entries in this map in proper sequence.
902  *
903  * The iterator starts the iteration at the beginning of the map.
904  *
905  * The elements returned by the pblIteratorNext() and pblIteratorPrevious() calls to
906  * this iterator are of type 'PblMapEntry *'. Use the methods pblMapEntryKeyLength(),
907  * pblMapEntryKey(), pblMapEntryValueLength() and pblMapEntryValue() to retrieve
908  * the attributes of the map entries.
909  *
910  * <B>Note</B>: The memory allocated by this method for the iterator returned needs to be released
911  *              by calling pblIteratorFree() once the iterator is no longer needed.
912  *
913  * The iterators returned by the this method are fail-fast:
914  * if the map is structurally modified at any time after the iterator is created,
915  * in any way, the iterator will return a PBL_ERROR_CONCURRENT_MODIFICATION error.
916  *
917  * Thus, in the face of concurrent modification,
918  * the iterator fails quickly and cleanly,
919  * rather than risking arbitrary, non-deterministic
920  * behavior at an undetermined time in the future.
921  *
922  * This method has a time complexity of O(1).
923  *
924  * @return void * retptr != NULL: The iterator.
925  * @return void * retptr == NULL: An error, see pbl_errno:
926  *
927  * <BR>PBL_ERROR_OUT_OF_MEMORY       - Out of memory.
928  * <BR>PBL_ERROR_PARAM_COLLECTION    - The map cannot be iterated.
929  */
pblMapIteratorNew(PblMap * map)930 PblIterator * pblMapIteratorNew( /*                 */
931 PblMap * map /** The map to create the iterator for */
932 )
933 {
934     return pblIteratorNew( map->entrySet );
935 }
936 
937 /**
938  * Returns a reverse iterator over the elements in this map in proper sequence.
939  *
940  * The reverse iterator starts the iteration at the end of the map.
941  *
942  * The elements returned by the pblIteratorNext() and pblIteratorPrevious() calls to
943  * this iterator are of type 'PblMapEntry *'. Use the methods pblMapEntryKeyLength(),
944  * pblMapEntryKey(), pblMapEntryValueLength() and pblMapEntryValue() to retrieve
945  * the attributes of the map entries.
946  *
947  * <B>Note</B>: The memory allocated by this method for the iterator returned needs to be released
948  *              by calling pblIteratorFree() once the iterator is no longer needed.
949  *
950  * The iterators returned by the this method are fail-fast:
951  * if the map is structurally modified at any time after the iterator is created,
952  * in any way, the iterator will return a PBL_ERROR_CONCURRENT_MODIFICATION error.
953  *
954  * Thus, in the face of concurrent modification,
955  * the iterator fails quickly and cleanly,
956  * rather than risking arbitrary, non-deterministic
957  * behavior at an undetermined time in the future.
958  *
959  * This method has a time complexity of O(1).
960  *
961  * @return void * retptr != NULL: The iterator.
962  * @return void * retptr == NULL: An error, see pbl_errno:
963  *
964  * <BR>PBL_ERROR_OUT_OF_MEMORY       - Out of memory.
965  * <BR>PBL_ERROR_PARAM_COLLECTION    - The map cannot be iterated.
966  */
pblMapIteratorReverseNew(PblMap * map)967 PblIterator * pblMapIteratorReverseNew( /*          */
968 PblMap * map /** The map to create the iterator for */
969 )
970 {
971     return pblIteratorReverseNew( map->entrySet );
972 }
973 
974 /**
975  * Returns the key length of the map entry passed.
976  *
977  * This method has a time complexity of O(1).
978  *
979  * @return size_t length: The key length of the map entry.
980  */
pblMapEntryKeyLength(PblMapEntry * entry)981 size_t pblMapEntryKeyLength( /*                   */
982 PblMapEntry * entry /**                 The entry */
983 )
984 {
985     return entry->keyLength;
986 }
987 
988 /**
989  * Returns the value length of the map entry passed.
990  *
991  * This method has a time complexity of O(1).
992  *
993  * @return size_t length: The value length of the map entry.
994  */
pblMapEntryValueLength(PblMapEntry * entry)995 size_t pblMapEntryValueLength( /*                   */
996 PblMapEntry * entry /**                   The entry */
997 )
998 {
999     return entry->valueLength;
1000 }
1001 
1002 /**
1003  * Returns a pointer to the key of the map entry passed.
1004  *
1005  * This method has a time complexity of O(1).
1006  *
1007  * @return void * ptr: The key of the map entry.
1008  */
pblMapEntryKey(PblMapEntry * entry)1009 void * pblMapEntryKey( /*                         */
1010 PblMapEntry * entry /**                 The entry */
1011 )
1012 {
1013     return entry->buffer;
1014 }
1015 
1016 /**
1017  * Returns a pointer to the value of the map entry passed.
1018  *
1019  * This method has a time complexity of O(1).
1020  *
1021  * @return void * ptr: The value of the map entry.
1022  */
pblMapEntryValue(PblMapEntry * entry)1023 void * pblMapEntryValue( /*                       */
1024 PblMapEntry * entry /**                 The entry */
1025 )
1026 {
1027     return entry->buffer + entry->keyLength;
1028 }
1029 
1030