1 /* =========================================================================
2 zhashx - extended generic hash container
3
4 Copyright (c) the Contributors as noted in the AUTHORS file.
5 This file is part of CZMQ, the high-level C binding for 0MQ:
6 http://czmq.zeromq.org.
7
8 This Source Code Form is subject to the terms of the Mozilla Public
9 License, v. 2.0. If a copy of the MPL was not distributed with this
10 file, You can obtain one at http://mozilla.org/MPL/2.0/.
11 =========================================================================
12 */
13
14 /*
15 @header
16 zhashx is an extended hash table container with more functionality than
17 zhash, its simpler cousin.
18 @discuss
19 The hash table always has a size that is prime and roughly doubles its
20 size when 75% full. In case of hash collisions items are chained in a
21 linked list. The hash table size is increased slightly (up to 5 times
22 before roughly doubling the size) when an overly long chain (between 1
23 and 63 items depending on table size) is detected.
24 @end
25 */
26
27 #include "czmq_classes.h"
28
29 // Hash table performance parameters
30
31 #define INITIAL_PRIME 0 // Initial size in items (index into primes)
32 #define GROWTH_FACTOR 5 // Increase after splitting (index into primes)
33 #define LOAD_FACTOR 75 // Percent loading before splitting
34 #define INITIAL_CHAIN 1 // Initial chaining limit
35 #define CHAIN_GROWS 1 // Increase after splitting (chaining limit)
36
37 #include "zhash_primes.inc"
38
39
40 // Hash item, used internally only
41
42 typedef struct _item_t {
43 void *value; // Opaque item value
44 struct _item_t *next; // Next item in the hash slot
45 size_t index; // Index of item in table
46 const void *key; // Item's original key
47 zhashx_free_fn *free_fn; // Value free function if any
48 } item_t;
49
50
51 // ---------------------------------------------------------------------
52 // Structure of our class
53
54 struct _zhashx_t {
55 size_t size; // Current size of hash table
56 uint prime_index; // Current prime number used as limit
57 uint chain_limit; // Current limit on chain length
58 item_t **items; // Array of items
59 size_t cached_index; // Avoids duplicate hash calculations
60 size_t cursor_index; // For first/next iteration
61 item_t *cursor_item; // For first/next iteration
62 const void *cursor_key; // After first/next call, points to key
63 zlistx_t *comments; // File comments, if any
64 time_t modified; // Set during zhashx_load
65 char *filename; // Set during zhashx_load
66 // Function callbacks for duplicating and destroying items, if any
67 zhashx_duplicator_fn *duplicator;
68 zhashx_destructor_fn *destructor;
69 // Function callbacks for duplicating and destroying keys, if any
70 zhashx_duplicator_fn *key_duplicator;
71 zhashx_destructor_fn *key_destructor;
72 zhashx_comparator_fn *key_comparator;
73 // Custom hash function
74 zhashx_hash_fn *hasher;
75 };
76
77 // Local helper functions
78 static item_t *s_item_lookup (zhashx_t *self, const void *key);
79 static item_t *s_item_insert (zhashx_t *self, const void *key, void *value);
80 static void s_item_destroy (zhashx_t *self, item_t *item, bool hard);
81
82
83 // --------------------------------------------------------------------------
84 // Modified Bernstein hashing function
85
86 static size_t
s_bernstein_hash(const void * key)87 s_bernstein_hash (const void *key)
88 {
89 const char *pointer = (const char *) key;
90 size_t key_hash = 0;
91 while (*pointer)
92 key_hash = 33 * key_hash ^ *pointer++;
93 return key_hash;
94 }
95
96
97 // --------------------------------------------------------------------------
98 // Hash table constructor
99
100 zhashx_t *
zhashx_new(void)101 zhashx_new (void)
102 {
103 zhashx_t *self = (zhashx_t *) zmalloc (sizeof (zhashx_t));
104 assert (self);
105 self->prime_index = INITIAL_PRIME;
106 self->chain_limit = INITIAL_CHAIN;
107 size_t limit = primes [self->prime_index];
108 self->items = (item_t **) zmalloc (sizeof (item_t *) * limit);
109 assert (self->items);
110 self->hasher = s_bernstein_hash;
111 self->key_destructor = (zhashx_destructor_fn *) zstr_free;
112 self->key_duplicator = (zhashx_duplicator_fn *) strdup;
113 self->key_comparator = (zhashx_comparator_fn *) strcmp;
114
115 return self;
116 }
117
118
119 // --------------------------------------------------------------------------
120 // Purge all items from a hash table
121
122 static void
s_purge(zhashx_t * self)123 s_purge (zhashx_t *self)
124 {
125 uint index;
126 size_t limit = primes [self->prime_index];
127
128 for (index = 0; index < limit; index++) {
129 // Destroy all items in this hash bucket
130 item_t *cur_item = self->items [index];
131 while (cur_item) {
132 item_t *next_item = cur_item->next;
133 s_item_destroy (self, cur_item, true);
134 cur_item = next_item;
135 }
136 self->items [index] = NULL;
137 }
138 }
139
140 // --------------------------------------------------------------------------
141 // Hash table destructor
142
143 void
zhashx_destroy(zhashx_t ** self_p)144 zhashx_destroy (zhashx_t **self_p)
145 {
146 assert (self_p);
147 if (*self_p) {
148 zhashx_t *self = *self_p;
149 if (self->items) {
150 s_purge (self);
151 freen (self->items);
152 }
153 zlistx_destroy (&self->comments);
154 freen (self->filename);
155 freen (self);
156 *self_p = NULL;
157 }
158 }
159
160
161 // --------------------------------------------------------------------------
162 // Local helper function
163 // Destroy item in hash table, item must exist in table
164
165 static void
s_item_destroy(zhashx_t * self,item_t * item,bool hard)166 s_item_destroy (zhashx_t *self, item_t *item, bool hard)
167 {
168 // Find previous item since it's a singly-linked list
169 item_t *cur_item = self->items [item->index];
170 item_t **prev_item = &(self->items [item->index]);
171 while (cur_item) {
172 if (cur_item == item)
173 break;
174 prev_item = &(cur_item->next);
175 cur_item = cur_item->next;
176 }
177 assert (cur_item);
178 *prev_item = item->next;
179 self->size--;
180 if (hard) {
181 if (self->destructor)
182 (self->destructor)(&item->value);
183 else
184 if (item->free_fn)
185 (item->free_fn)(item->value);
186
187 self->cursor_item = NULL;
188 self->cursor_key = NULL;
189
190 if (self->key_destructor)
191 (self->key_destructor)((void **) &item->key);
192 freen (item);
193 }
194 }
195
196
197 // --------------------------------------------------------------------------
198 // Rehash hash table with specified new prime index
199 // Returns 0 on success, or fails the assertions (e.g. insufficient memory)
200 // Note: Older code used to return -1 in case of errors - this is no longer so
201
202 static int
s_zhashx_rehash(zhashx_t * self,uint new_prime_index)203 s_zhashx_rehash (zhashx_t *self, uint new_prime_index)
204 {
205 assert (self);
206 assert (new_prime_index < sizeof (primes));
207
208 size_t limit = primes [self->prime_index];
209 size_t new_limit = primes [new_prime_index];
210 item_t **new_items = (item_t **) zmalloc (sizeof (item_t *) * new_limit);
211 assert (new_items);
212
213 // Move all items to the new hash table, rehashing to
214 // take into account new hash table limit
215 size_t index;
216 for (index = 0; index < limit; index++) {
217 item_t *cur_item = self->items [index];
218 while (cur_item) {
219 item_t *next_item = cur_item->next;
220 size_t new_index = self->hasher (cur_item->key);
221 new_index %= new_limit;
222 cur_item->index = new_index;
223 cur_item->next = new_items [new_index];
224 new_items [new_index] = cur_item;
225 cur_item = next_item;
226 }
227 }
228 // Destroy old hash table
229 freen (self->items);
230 self->items = new_items;
231 self->prime_index = new_prime_index;
232 return 0;
233 }
234
235
236 // --------------------------------------------------------------------------
237 // Insert item into hash table with specified key and item. Returns 0 on
238 // success. If the key is already present, returns -1 and leaves existing
239 // item unchanged. Sets the hash cursor to the item, if found. Dies with
240 // assertion if the process heap memory ran out. (Note: older code returned
241 // -1 in such cases; this is no longer so).
242
243 int
zhashx_insert(zhashx_t * self,const void * key,void * value)244 zhashx_insert (zhashx_t *self, const void *key, void *value)
245 {
246 assert (self);
247 assert (key);
248
249 // If we're exceeding the load factor of the hash table,
250 // resize it according to the growth factor
251 size_t limit = primes [self->prime_index];
252 if (self->size >= limit * LOAD_FACTOR / 100) {
253 // Create new hash table
254 uint new_prime_index = self->prime_index + GROWTH_FACTOR;
255 assert (s_zhashx_rehash (self, new_prime_index) == 0);
256 self->chain_limit += CHAIN_GROWS;
257 }
258 return s_item_insert (self, key, value)? 0: -1;
259 }
260
261
262 // --------------------------------------------------------------------------
263 // Local helper function
264 // Insert new item into hash table, returns item
265 // If item already existed, returns NULL
266 // Sets the hash cursor to the item, if found.
267
268 static item_t *
s_item_insert(zhashx_t * self,const void * key,void * value)269 s_item_insert (zhashx_t *self, const void *key, void *value)
270 {
271 // Check that item does not already exist in hash table
272 // Leaves self->cached_index with calculated hash item
273 item_t *item = s_item_lookup (self, key);
274 if (item == NULL) {
275 item = (item_t *) zmalloc (sizeof (item_t));
276 assert (item);
277
278 // If necessary, take duplicate of item key
279 if (self->key_duplicator)
280 item->key = (self->key_duplicator)((void *) key);
281 else
282 item->key = key;
283
284 // If necessary, take duplicate of item value
285 if (self->duplicator)
286 item->value = (self->duplicator)(value);
287 else
288 item->value = value;
289
290 item->index = self->cached_index;
291
292 // Insert into start of bucket list
293 item->next = self->items [self->cached_index];
294 self->items [self->cached_index] = item;
295 self->size++;
296 self->cursor_item = item;
297 self->cursor_key = item->key;
298 }
299 else
300 item = NULL; // Signal duplicate insertion
301
302 return item;
303 }
304
305
306 // --------------------------------------------------------------------------
307 // Local helper function
308 // Lookup item in hash table, returns item or NULL
309 // Dies with assertion if the process heap memory ran out (Note: older code
310 // returned NULL in such cases; this is no longer so).
311
312 static item_t *
s_item_lookup(zhashx_t * self,const void * key)313 s_item_lookup (zhashx_t *self, const void *key)
314 {
315 // Look in bucket list for item by key
316 size_t limit = primes [self->prime_index];
317 self->cached_index = self->hasher (key) % limit;
318 item_t *item = self->items [self->cached_index];
319 uint len = 0;
320 while (item) {
321 if ((self->key_comparator)(item->key, key) == 0)
322 break;
323 item = item->next;
324 ++len;
325 }
326 if (len > self->chain_limit) {
327 // Create new hash table
328 uint new_prime_index = self->prime_index + GROWTH_FACTOR;
329 assert (s_zhashx_rehash (self, new_prime_index) == 0);
330 limit = primes [self->prime_index];
331 self->cached_index = self->hasher (key) % limit;
332 }
333 return item;
334 }
335
336
337 // --------------------------------------------------------------------------
338 // Update or insert item into hash table with specified key and item. If the
339 // key is already present, destroys old item and inserts new one. If you set
340 // a container item destructor, this is called on the old value. If the key
341 // was not already present, inserts a new item. Sets the hash cursor to the
342 // new item.
343
344 void
zhashx_update(zhashx_t * self,const void * key,void * value)345 zhashx_update (zhashx_t *self, const void *key, void *value)
346 {
347 assert (self);
348 assert (key);
349
350 item_t *item = s_item_lookup (self, key);
351 if (item) {
352 if (self->destructor)
353 (self->destructor)(&item->value);
354 else
355 if (item->free_fn)
356 (item->free_fn)(item->value);
357
358 // If necessary, take duplicate of item value
359 if (self->duplicator)
360 item->value = (self->duplicator)(value);
361 else
362 item->value = value;
363 }
364 else
365 zhashx_insert (self, key, value);
366 }
367
368
369 // --------------------------------------------------------------------------
370 // Remove an item specified by key from the hash table. If there was no such
371 // item, this function does nothing.
372
373 void
zhashx_delete(zhashx_t * self,const void * key)374 zhashx_delete (zhashx_t *self, const void *key)
375 {
376 assert (self);
377 assert (key);
378
379 item_t *item = s_item_lookup (self, key);
380 if (item)
381 s_item_destroy (self, item, true);
382 }
383
384
385 // --------------------------------------------------------------------------
386 // Delete all items from the hash table. If the key destructor is
387 // set, calls it on every key. If the item destructor is set, calls
388 // it on every item.
389 void
zhashx_purge(zhashx_t * self)390 zhashx_purge (zhashx_t *self)
391 {
392 assert (self);
393 s_purge (self);
394
395 if (self->prime_index > INITIAL_PRIME) {
396 // Try to shrink hash table
397 size_t limit = primes [INITIAL_PRIME];
398 item_t **items = (item_t **) zmalloc (sizeof (item_t *) * limit);
399 assert (items);
400 freen (self->items);
401 self->prime_index = INITIAL_PRIME;
402 self->chain_limit = INITIAL_CHAIN;
403 self->items = items;
404 }
405 }
406
407
408 // --------------------------------------------------------------------------
409 // Look for item in hash table and return its item, or NULL. Sets the hash
410 // cursor to the item, if found.
411
412 void *
zhashx_lookup(zhashx_t * self,const void * key)413 zhashx_lookup (zhashx_t *self, const void *key)
414 {
415 assert (self);
416 assert (key);
417
418 item_t *item = s_item_lookup (self, key);
419 if (item) {
420 self->cursor_item = item;
421 self->cursor_key = item->key;
422 return item->value;
423 }
424 else
425 return NULL;
426 }
427
428
429 // --------------------------------------------------------------------------
430 // Reindexes an item from an old key to a new key. If there was no such
431 // item, does nothing. If the new key already exists, deletes old item.
432 // Sets the item cursor to the renamed item.
433
434 int
zhashx_rename(zhashx_t * self,const void * old_key,const void * new_key)435 zhashx_rename (zhashx_t *self, const void *old_key, const void *new_key)
436 {
437 item_t *old_item = s_item_lookup (self, old_key);
438 item_t *new_item = s_item_lookup (self, new_key);
439 if (old_item && !new_item) {
440 s_item_destroy (self, old_item, false);
441 if (self->key_destructor)
442 (self->key_destructor)((void **) &old_item->key);
443
444 if (self->key_duplicator)
445 old_item->key = (self->key_duplicator)(new_key);
446 else
447 old_item->key = new_key;
448
449 old_item->index = self->cached_index;
450 old_item->next = self->items [self->cached_index];
451 self->items [self->cached_index] = old_item;
452 self->size++;
453 self->cursor_item = old_item;
454 self->cursor_key = old_item->key;
455 return 0;
456 }
457 else
458 return -1;
459 }
460
461
462 // --------------------------------------------------------------------------
463 // Set a free function for the specified hash table item. When the item is
464 // destroyed, the free function, if any, is called on that item.
465 // Use this when hash items are dynamically allocated, to ensure that
466 // you don't have memory leaks. You can pass 'free' or NULL as a free_fn.
467 // Returns the item, or NULL if there is no such item.
468
469 void *
zhashx_freefn(zhashx_t * self,const void * key,zhashx_free_fn free_fn)470 zhashx_freefn (zhashx_t *self, const void *key, zhashx_free_fn free_fn)
471 {
472 assert (self);
473 assert (key);
474
475 item_t *item = s_item_lookup (self, key);
476 if (item) {
477 item->free_fn = free_fn;
478 return item->value;
479 }
480 else
481 return NULL;
482 }
483
484
485 // --------------------------------------------------------------------------
486 // Return size of hash table
487
488 size_t
zhashx_size(zhashx_t * self)489 zhashx_size (zhashx_t *self)
490 {
491 assert (self);
492 return self->size;
493 }
494
495
496 // --------------------------------------------------------------------------
497 // Return a zlistx_t containing the keys for the items in the
498 // table. Uses the key_duplicator to duplicate all keys and sets the
499 // key_destructor as destructor for the list.
500
501 zlistx_t *
zhashx_keys(zhashx_t * self)502 zhashx_keys (zhashx_t *self)
503 {
504 assert (self);
505 zlistx_t *keys = zlistx_new ();
506 if (!keys)
507 return NULL;
508 zlistx_set_destructor (keys, self->key_destructor);
509 zlistx_set_duplicator (keys, self->key_duplicator);
510
511 uint index;
512 size_t limit = primes [self->prime_index];
513 for (index = 0; index < limit; index++) {
514 item_t *item = self->items [index];
515 while (item) {
516 if (zlistx_add_end (keys, (void *) item->key) == NULL) {
517 zlistx_destroy (&keys);
518 return NULL;
519 }
520 item = item->next;
521 }
522 }
523 return keys;
524 }
525
526 // Return a zlistx_t containing the items in the table. If there exists
527 // a duplicator, then it is used to duplicate all items, and if there
528 // is a destructor then it set as the destructor for the list.
529
530 zlistx_t *
zhashx_values(zhashx_t * self)531 zhashx_values (zhashx_t *self)
532 {
533 assert (self);
534
535 zlistx_t *values = zlistx_new ();
536 if (!values)
537 return NULL;
538
539 zlistx_set_destructor (values, self->destructor);
540 zlistx_set_duplicator (values, self->duplicator);
541
542 uint index;
543 size_t limit = primes [self->prime_index];
544 for (index = 0; index < limit; index++) {
545 item_t *item = self->items [index];
546 while (item) {
547 if (zlistx_add_end (values, (void *) item->value) == NULL) {
548 zlistx_destroy (&values);
549 return NULL;
550 }
551 item = item->next;
552 }
553 }
554 return values;
555 }
556
557
558 // --------------------------------------------------------------------------
559 // Simple iterator; returns first item in hash table, in no given order,
560 // or NULL if the table is empty. This method is simpler to use than the
561 // foreach() method, which is deprecated. NOTE: do NOT modify the table
562 // while iterating.
563
564 void *
zhashx_first(zhashx_t * self)565 zhashx_first (zhashx_t *self)
566 {
567 assert (self);
568 // Point to before or at first item
569 self->cursor_index = 0;
570 self->cursor_item = self->items [self->cursor_index];
571 // Now scan forwards to find it, leave cursor after item
572 return zhashx_next (self);
573 }
574
575
576 // --------------------------------------------------------------------------
577 // Simple iterator; returns next item in hash table, in no given order,
578 // or NULL if the last item was already returned. Use this together with
579 // zhashx_first() to process all items in a hash table. If you need the
580 // items in sorted order, use zhashx_keys() and then zlistx_sort(). NOTE:
581 // do NOT modify the table while iterating.
582
583 void *
zhashx_next(zhashx_t * self)584 zhashx_next (zhashx_t *self)
585 {
586 assert (self);
587 // Scan forward from cursor until we find an item
588 size_t limit = primes [self->prime_index];
589 while (self->cursor_item == NULL) {
590 if (self->cursor_index < limit - 1)
591 self->cursor_index++;
592 else
593 return NULL; // At end of table
594
595 // Get first item in next bucket
596 self->cursor_item = self->items [self->cursor_index];
597 }
598 // We have an item, so return it, and bump past it
599 assert (self->cursor_item);
600 item_t *item = self->cursor_item;
601 self->cursor_key = item->key;
602 self->cursor_item = self->cursor_item->next;
603 return item->value;
604 }
605
606
607 // --------------------------------------------------------------------------
608 // After a successful insert, update, or first/next method, returns the key
609 // for the item that was returned. You may not modify or deallocate
610 // the key, and it lasts as long as the item in the hash.
611 // After an unsuccessful first/next, returns NULL.
612
613 const void *
zhashx_cursor(zhashx_t * self)614 zhashx_cursor (zhashx_t *self)
615 {
616 assert (self);
617 return self->cursor_key;
618 }
619
620
621 // --------------------------------------------------------------------------
622 // Add a comment to hash table before saving to disk. You can add as many
623 // comment lines as you like. These comment lines are discarded when loading
624 // the file. If you use a null format, all comments are deleted.
625 // FIXME: return 0 on success, -1 on error
626
627 void
zhashx_comment(zhashx_t * self,const char * format,...)628 zhashx_comment (zhashx_t *self, const char *format, ...)
629 {
630 if (format) {
631 if (!self->comments) {
632 self->comments = zlistx_new ();
633 if (!self->comments)
634 return;
635 zlistx_set_destructor (self->comments, (zhashx_destructor_fn *) zstr_free);
636 }
637 va_list argptr;
638 va_start (argptr, format);
639 char *string = zsys_vprintf (format, argptr);
640 va_end (argptr);
641 if (string)
642 zlistx_add_end (self->comments, string);
643 }
644 else
645 zlistx_destroy (&self->comments);
646 }
647
648
649 // --------------------------------------------------------------------------
650 // Save hash table to a text file in name=value format
651 // Hash values must be printable strings.
652 // Returns 0 if OK, else -1 if a file error occurred
653
654 int
zhashx_save(zhashx_t * self,const char * filename)655 zhashx_save (zhashx_t *self, const char *filename)
656 {
657 assert (self);
658
659 FILE *handle = fopen (filename, "w");
660 if (!handle)
661 return -1; // Failed to create file
662
663 if (self->comments) {
664 char *comment = (char *) zlistx_first (self->comments);
665 while (comment) {
666 fprintf (handle, "# %s\n", comment);
667 comment = (char *) zlistx_next (self->comments);
668 }
669 fprintf (handle, "\n");
670 }
671 uint index;
672 size_t limit = primes [self->prime_index];
673 for (index = 0; index < limit; index++) {
674 item_t *item = self->items [index];
675 while (item) {
676 fprintf (handle, "%s=%s\n", (char *) item->key, (char *) item->value);
677 item = item->next;
678 }
679 }
680 fclose (handle);
681 return 0;
682 }
683
684
685 // --------------------------------------------------------------------------
686 // Load hash table from a text file in name=value format; hash table must
687 // already exist. Hash values must printable strings.
688 // Returns 0 if OK, else -1 if a file was not readable.
689
690 int
zhashx_load(zhashx_t * self,const char * filename)691 zhashx_load (zhashx_t *self, const char *filename)
692 {
693 assert (self);
694 zhashx_set_destructor (self, (zhashx_destructor_fn *) zstr_free);
695 zhashx_set_duplicator (self, (zhashx_duplicator_fn *) strdup);
696
697 // Whether or not file exists, we'll track the filename and last
698 // modification date (0 for unknown files), so that zhashx_refresh ()
699 // will always work after zhashx_load (), to load a newly-created
700 // file.
701
702 // Take copy of filename in case self->filename is same string.
703 char *filename_copy = strdup (filename);
704 assert (filename_copy);
705 freen (self->filename);
706 self->filename = filename_copy;
707 self->modified = zsys_file_modified (self->filename);
708 FILE *handle = fopen (self->filename, "r");
709 if (handle) {
710 char *buffer = (char *) zmalloc (1024);
711 assert (buffer);
712 while (fgets (buffer, 1024, handle)) {
713 // Skip lines starting with "#" or that do not look like
714 // name=value data.
715 char *equals = strchr (buffer, '=');
716 if (buffer [0] == '#' || equals == buffer || !equals)
717 continue;
718
719 // Buffer may end in newline, which we don't want
720 if (buffer [strlen (buffer) - 1] == '\n')
721 buffer [strlen (buffer) - 1] = 0;
722 *equals++ = 0;
723 zhashx_update (self, buffer, equals);
724 }
725 freen (buffer);
726 fclose (handle);
727 }
728 else
729 return -1; // Failed to open file for reading
730
731 return 0;
732 }
733
734
735 // --------------------------------------------------------------------------
736 // When a hash table was loaded from a file by zhashx_load, this method will
737 // reload the file if it has been modified since, and is "stable", i.e. not
738 // still changing. Returns 0 if OK, -1 if there was an error reloading the
739 // file.
740
741 int
zhashx_refresh(zhashx_t * self)742 zhashx_refresh (zhashx_t *self)
743 {
744 assert (self);
745
746 if (self->filename) {
747 if (zsys_file_modified (self->filename) > self->modified
748 && zsys_file_stable (self->filename)) {
749 // Empty the hash table; code is copied from zhashx_destroy
750 uint index;
751 size_t limit = primes [self->prime_index];
752 for (index = 0; index < limit; index++) {
753 // Destroy all items in this hash bucket
754 item_t *cur_item = self->items [index];
755 while (cur_item) {
756 item_t *next_item = cur_item->next;
757 s_item_destroy (self, cur_item, true);
758 cur_item = next_item;
759 }
760 }
761 zhashx_load (self, self->filename);
762 }
763 }
764 return 0;
765 }
766
767
768 // --------------------------------------------------------------------------
769 // Same as pack but uses a user-defined serializer function to convert items
770 // into longstr.
771 // Caller owns return value and must destroy it when done.
772
773 zframe_t *
zhashx_pack_own(zhashx_t * self,zhashx_serializer_fn serializer)774 zhashx_pack_own (zhashx_t *self, zhashx_serializer_fn serializer)
775 {
776 assert (self);
777
778 // First, calculate packed data size
779 size_t frame_size = 4; // Dictionary size, number-4
780 uint index;
781 uint vindex = 0;
782 size_t limit = primes [self->prime_index];
783 char **values = (char **) zmalloc (self->size * sizeof (char*));
784 for (index = 0; index < limit; index++) {
785 item_t *item = self->items [index];
786 while (item) {
787 // We store key as short string
788 frame_size += 1 + strlen ((char *) item->key);
789 // We store value as long string
790 if (serializer != NULL)
791 values [vindex] = serializer (item->value);
792 else
793 values [vindex] = (char *) item->value;
794
795 frame_size += 4 + strlen ((char *) values [vindex]);
796 item = item->next;
797 vindex++;
798 }
799 }
800 // Now serialize items into the frame
801 zframe_t *frame = zframe_new (NULL, frame_size);
802 if (!frame) {
803 freen (values);
804 return NULL;
805 }
806
807 byte *needle = zframe_data (frame);
808 // Store size as number-4
809 *(uint32_t *) needle = htonl ((u_long) self->size);
810 needle += 4;
811 vindex = 0;
812 for (index = 0; index < limit; index++) {
813 item_t *item = self->items [index];
814 while (item) {
815 // Store key as string
816 size_t length = strlen ((char *) item->key);
817 *needle++ = (byte) length;
818 memcpy (needle, item->key, length);
819 needle += length;
820
821 // Store value as longstr
822 length = strlen (values [vindex]);
823 uint32_t serialize = htonl ((u_long) length);
824 memcpy (needle, &serialize, 4);
825 needle += 4;
826 memcpy (needle, values [vindex], length);
827 needle += length;
828 item = item->next;
829
830 // Destroy serialized value
831 if (serializer != NULL)
832 zstr_free (&values [vindex]);
833
834 vindex++;
835 }
836 }
837 freen (values);
838 return frame;
839 }
840
841
842 // --------------------------------------------------------------------------
843 // Serialize hash table to a binary frame that can be sent in a message.
844 // The packed format is compatible with the 'dictionary' type defined in
845 // http://rfc.zeromq.org/spec:35/FILEMQ, and implemented by zproto:
846 //
847 // ; A list of name/value pairs
848 // dictionary = dict-count *( dict-name dict-value )
849 // dict-count = number-4
850 // dict-value = longstr
851 // dict-name = string
852 //
853 // ; Strings are always length + text contents
854 // longstr = number-4 *VCHAR
855 // string = number-1 *VCHAR
856 //
857 // ; Numbers are unsigned integers in network byte order
858 // number-1 = 1OCTET
859 // number-4 = 4OCTET
860 //
861 // Comments are not included in the packed data. Item values MUST be
862 // strings.
863
864 zframe_t *
zhashx_pack(zhashx_t * self)865 zhashx_pack (zhashx_t *self)
866 {
867 return zhashx_pack_own (self, NULL);
868 }
869
870
871 // --------------------------------------------------------------------------
872 // Same as unpack but uses a user-defined deserializer function to convert
873 // a longstr back into item format.
874
875 zhashx_t *
zhashx_unpack_own(zframe_t * frame,zhashx_deserializer_fn deserializer)876 zhashx_unpack_own (zframe_t *frame, zhashx_deserializer_fn deserializer)
877 {
878 zhashx_t *self = zhashx_new ();
879 if (!self)
880 return NULL;
881
882 // Hash will free values in destructor
883 zhashx_set_destructor (self, (zhashx_destructor_fn *) zstr_free);
884
885 assert (frame);
886 if (zframe_size (frame) < 4)
887 return self; // Arguable...
888
889 byte *needle = zframe_data (frame);
890 byte *ceiling = needle + zframe_size (frame);
891 size_t nbr_items = ntohl (*(uint32_t *) needle);
892 needle += 4;
893 while (nbr_items && needle < ceiling) {
894 // Get key as string
895 size_t key_size = *needle++;
896 if (needle + key_size <= ceiling) {
897 char key [256];
898 memcpy (key, needle, key_size);
899 key [key_size] = 0;
900 needle += key_size;
901
902 // Get value as longstr
903 if (needle + 4 <= ceiling) {
904 size_t value_size = ntohl (*(uint32_t *) needle);
905 needle += 4;
906 // Be wary of malformed frames
907 if (needle + value_size <= ceiling) {
908 char *value = (char *) zmalloc (value_size + 1);
909 assert (value);
910 memcpy (value, needle, value_size);
911 value [value_size] = 0;
912 needle += value_size;
913
914 // Convert string to real value
915 void *real_value;
916 if (deserializer != NULL) {
917 real_value = deserializer (value);
918 zstr_free (&value);
919 }
920 else
921 real_value = value;
922
923 // Hash takes ownership of real_value
924 if (zhashx_insert (self, key, real_value)) {
925 zhashx_destroy (&self);
926 break;
927 }
928 }
929 }
930 }
931 }
932
933 if (self)
934 zhashx_set_duplicator (self, (zhashx_duplicator_fn *) strdup);
935
936 return self;
937 }
938
939
940 // --------------------------------------------------------------------------
941 // Unpack binary frame into a new hash table. Packed data must follow format
942 // defined by zhashx_pack. Hash table is set to autofree. An empty frame
943 // unpacks to an empty hash table.
944
945 zhashx_t *
zhashx_unpack(zframe_t * frame)946 zhashx_unpack (zframe_t *frame)
947 {
948 return zhashx_unpack_own (frame, NULL);
949 }
950
951
952 // --------------------------------------------------------------------------
953 // Make a copy of the list; items are duplicated if you set a duplicator
954 // for the list, otherwise not. Copying a null reference returns a null
955 // reference. Note that this method's behavior changed slightly for CZMQ
956 // v3.x, as it does not set nor respect autofree. It does however let you
957 // duplicate any hash table safely. The old behavior is in zhashx_dup_v2.
958
959 zhashx_t *
zhashx_dup(zhashx_t * self)960 zhashx_dup (zhashx_t *self)
961 {
962 if (!self)
963 return NULL;
964
965 zhashx_t *copy = zhashx_new ();
966 if (copy) {
967 copy->destructor = self->destructor;
968 copy->duplicator = self->duplicator;
969 copy->key_duplicator = self->key_duplicator;
970 copy->key_destructor = self->key_destructor;
971 copy->key_comparator = self->key_comparator;
972 copy->hasher = self->hasher;
973 uint index;
974 size_t limit = primes [self->prime_index];
975 for (index = 0; index < limit; index++) {
976 item_t *item = self->items [index];
977 while (item) {
978 if (zhashx_insert (copy, item->key, item->value)) {
979 zhashx_destroy (©);
980 break;
981 }
982 item = item->next;
983 }
984 }
985 }
986 return copy;
987 }
988
989
990 // --------------------------------------------------------------------------
991 // Set a user-defined deallocator for hash items; by default items are not
992 // freed when the hash is destroyed.
993
994 void
zhashx_set_destructor(zhashx_t * self,zhashx_destructor_fn destructor)995 zhashx_set_destructor (zhashx_t *self, zhashx_destructor_fn destructor)
996 {
997 assert (self);
998 self->destructor = destructor;
999 }
1000
1001
1002 // --------------------------------------------------------------------------
1003 // Set a user-defined duplicator for hash items; by default items are not
1004 // copied when the hash is duplicated.
1005
1006 void
zhashx_set_duplicator(zhashx_t * self,zhashx_duplicator_fn duplicator)1007 zhashx_set_duplicator (zhashx_t *self, zhashx_duplicator_fn duplicator)
1008 {
1009 assert (self);
1010 self->duplicator = duplicator;
1011 }
1012
1013
1014 // --------------------------------------------------------------------------
1015 // Set a user-defined deallocator for keys; by default keys are
1016 // freed when the hash is destroyed by calling free().
1017
1018 void
zhashx_set_key_destructor(zhashx_t * self,zhashx_destructor_fn destructor)1019 zhashx_set_key_destructor (zhashx_t *self, zhashx_destructor_fn destructor)
1020 {
1021 assert (self);
1022 self->key_destructor = destructor;
1023 }
1024
1025
1026 // --------------------------------------------------------------------------
1027 // Set a user-defined duplicator for keys; by default keys are
1028 // duplicated by calling strdup().
1029
1030 void
zhashx_set_key_duplicator(zhashx_t * self,zhashx_duplicator_fn duplicator)1031 zhashx_set_key_duplicator (zhashx_t *self, zhashx_duplicator_fn duplicator)
1032 {
1033 assert (self);
1034 self->key_duplicator = duplicator;
1035 }
1036
1037
1038 // --------------------------------------------------------------------------
1039 // Set a user-defined comparator for keys; by default keys are
1040 // compared using streq.
1041
1042 void
zhashx_set_key_comparator(zhashx_t * self,zhashx_comparator_fn comparator)1043 zhashx_set_key_comparator (zhashx_t *self, zhashx_comparator_fn comparator)
1044 {
1045 assert (self);
1046 assert (comparator != NULL);
1047 self->key_comparator = comparator;
1048 }
1049
1050
1051 // --------------------------------------------------------------------------
1052 // Set a user-defined hash function for keys; by default keys are
1053 // hashed by a modified Bernstein hashing function.
1054
1055 void
zhashx_set_key_hasher(zhashx_t * self,zhashx_hash_fn hasher)1056 zhashx_set_key_hasher (zhashx_t *self, zhashx_hash_fn hasher)
1057 {
1058 assert (self);
1059 self->hasher = hasher;
1060 }
1061
1062
1063 // --------------------------------------------------------------------------
1064 // DEPRECATED by zhashx_dup
1065 // Make copy of hash table; if supplied table is null, returns null.
1066 // Does not copy items themselves. Rebuilds new table so may be slow on
1067 // very large tables. NOTE: only works with item values that are strings
1068 // since there's no other way to know how to duplicate the item value.
1069
1070 zhashx_t *
zhashx_dup_v2(zhashx_t * self)1071 zhashx_dup_v2 (zhashx_t *self)
1072 {
1073 if (!self)
1074 return NULL;
1075
1076 zhashx_t *copy = zhashx_new ();
1077 if (copy) {
1078 zhashx_set_destructor (copy, (zhashx_destructor_fn *) zstr_free);
1079 zhashx_set_duplicator (copy, (zhashx_duplicator_fn *) strdup);
1080 uint index;
1081 size_t limit = primes [self->prime_index];
1082 for (index = 0; index < limit; index++) {
1083 item_t *item = self->items [index];
1084 while (item) {
1085 if (zhashx_insert (copy, item->key, item->value)) {
1086 zhashx_destroy (©);
1087 break;
1088 }
1089 item = item->next;
1090 }
1091 }
1092 }
1093 return copy;
1094 }
1095
1096
1097 // --------------------------------------------------------------------------
1098 // Runs selftest of class
1099 //
1100
1101 #ifdef CZMQ_BUILD_DRAFT_API
1102 static char *
s_test_serialize_int(const void * item)1103 s_test_serialize_int (const void *item)
1104 {
1105 int *int_item = (int *) item;
1106 char *str_item = (char *) zmalloc (sizeof (char) * 10);
1107 sprintf (str_item, "%d", *int_item);
1108 return str_item;
1109 }
1110
1111 static void *
s_test_deserialze_int(const char * str_item)1112 s_test_deserialze_int (const char *str_item)
1113 {
1114 int *int_item = (int *) zmalloc (sizeof (int));
1115 sscanf (str_item, "%d", int_item);
1116 return int_item;
1117 }
1118
1119 static void
s_test_destroy_int(void ** item)1120 s_test_destroy_int (void **item)
1121 {
1122 int *int_item = (int *) *item;
1123 freen (int_item);
1124 }
1125 #endif // CZMQ_BUILD_DRAFT_API
1126
1127 void
zhashx_test(bool verbose)1128 zhashx_test (bool verbose)
1129 {
1130 printf (" * zhashx: ");
1131
1132 // @selftest
1133 zhashx_t *hash = zhashx_new ();
1134 assert (hash);
1135 assert (zhashx_size (hash) == 0);
1136 assert (zhashx_first (hash) == NULL);
1137 assert (zhashx_cursor (hash) == NULL);
1138
1139 // Insert some items
1140 int rc;
1141 rc = zhashx_insert (hash, "DEADBEEF", "dead beef");
1142 char *item = (char *) zhashx_first (hash);
1143 assert (streq ((char *) zhashx_cursor (hash), "DEADBEEF"));
1144 assert (streq (item, "dead beef"));
1145 assert (rc == 0);
1146 rc = zhashx_insert (hash, "ABADCAFE", "a bad cafe");
1147 assert (rc == 0);
1148 rc = zhashx_insert (hash, "C0DEDBAD", "coded bad");
1149 assert (rc == 0);
1150 rc = zhashx_insert (hash, "DEADF00D", "dead food");
1151 assert (rc == 0);
1152 assert (zhashx_size (hash) == 4);
1153
1154 // Look for existing items
1155 item = (char *) zhashx_lookup (hash, "DEADBEEF");
1156 assert (streq (item, "dead beef"));
1157 item = (char *) zhashx_lookup (hash, "ABADCAFE");
1158 assert (streq (item, "a bad cafe"));
1159 item = (char *) zhashx_lookup (hash, "C0DEDBAD");
1160 assert (streq (item, "coded bad"));
1161 item = (char *) zhashx_lookup (hash, "DEADF00D");
1162 assert (streq (item, "dead food"));
1163
1164 // Look for non-existent items
1165 item = (char *) zhashx_lookup (hash, "foo");
1166 assert (item == NULL);
1167
1168 // Try to insert duplicate items
1169 rc = zhashx_insert (hash, "DEADBEEF", "foo");
1170 assert (rc == -1);
1171 item = (char *) zhashx_lookup (hash, "DEADBEEF");
1172 assert (streq (item, "dead beef"));
1173
1174 // Some rename tests
1175
1176 // Valid rename, key is now LIVEBEEF
1177 rc = zhashx_rename (hash, "DEADBEEF", "LIVEBEEF");
1178 assert (rc == 0);
1179 item = (char *) zhashx_lookup (hash, "LIVEBEEF");
1180 assert (streq (item, "dead beef"));
1181
1182 // Trying to rename an unknown item to a non-existent key
1183 rc = zhashx_rename (hash, "WHATBEEF", "NONESUCH");
1184 assert (rc == -1);
1185
1186 // Trying to rename an unknown item to an existing key
1187 rc = zhashx_rename (hash, "WHATBEEF", "LIVEBEEF");
1188 assert (rc == -1);
1189 item = (char *) zhashx_lookup (hash, "LIVEBEEF");
1190 assert (streq (item, "dead beef"));
1191
1192 // Trying to rename an existing item to another existing item
1193 rc = zhashx_rename (hash, "LIVEBEEF", "ABADCAFE");
1194 assert (rc == -1);
1195 item = (char *) zhashx_lookup (hash, "LIVEBEEF");
1196 assert (streq (item, "dead beef"));
1197 item = (char *) zhashx_lookup (hash, "ABADCAFE");
1198 assert (streq (item, "a bad cafe"));
1199
1200 // Test keys method
1201 zlistx_t *keys = zhashx_keys (hash);
1202 assert (zlistx_size (keys) == 4);
1203 zlistx_destroy (&keys);
1204
1205 zlistx_t *values = zhashx_values (hash);
1206 assert (zlistx_size (values) == 4);
1207 zlistx_destroy (&values);
1208
1209 // Test dup method
1210 zhashx_t *copy = zhashx_dup (hash);
1211 assert (zhashx_size (copy) == 4);
1212 item = (char *) zhashx_lookup (copy, "LIVEBEEF");
1213 assert (item);
1214 assert (streq (item, "dead beef"));
1215 zhashx_destroy (©);
1216
1217 // Test pack/unpack methods
1218 zframe_t *frame = zhashx_pack (hash);
1219 copy = zhashx_unpack (frame);
1220 zframe_destroy (&frame);
1221 assert (zhashx_size (copy) == 4);
1222 item = (char *) zhashx_lookup (copy, "LIVEBEEF");
1223 assert (item);
1224 assert (streq (item, "dead beef"));
1225 zhashx_destroy (©);
1226
1227 #ifdef CZMQ_BUILD_DRAFT_API
1228 // Test own pack/unpack methods
1229 zhashx_t *own_hash = zhashx_new ();
1230 zhashx_set_destructor (own_hash, s_test_destroy_int);
1231 assert (own_hash);
1232 int *val1 = (int *) zmalloc (sizeof (int));
1233 int *val2 = (int *) zmalloc (sizeof (int));
1234 *val1 = 25;
1235 *val2 = 100;
1236 zhashx_insert (own_hash, "val1", val1);
1237 zhashx_insert (own_hash, "val2", val2);
1238 frame = zhashx_pack_own (own_hash, s_test_serialize_int);
1239 copy = zhashx_unpack_own (frame, s_test_deserialze_int);
1240 zhashx_set_destructor (copy, s_test_destroy_int);
1241 zframe_destroy (&frame);
1242 assert (zhashx_size (copy) == 2);
1243 assert (*((int *) zhashx_lookup (copy, "val1")) == 25);
1244 assert (*((int *) zhashx_lookup (copy, "val2")) == 100);
1245 zhashx_destroy (©);
1246 zhashx_destroy (&own_hash);
1247 #endif // CZMQ_BUILD_DRAFT_API
1248
1249 // Test save and load
1250 zhashx_comment (hash, "This is a test file");
1251 zhashx_comment (hash, "Created by %s", "czmq_selftest");
1252 zhashx_save (hash, ".cache");
1253 copy = zhashx_new ();
1254 assert (copy);
1255 zhashx_load (copy, ".cache");
1256 item = (char *) zhashx_lookup (copy, "LIVEBEEF");
1257 assert (item);
1258 assert (streq (item, "dead beef"));
1259 zhashx_destroy (©);
1260 zsys_file_delete (".cache");
1261
1262 // Delete a item
1263 zhashx_delete (hash, "LIVEBEEF");
1264 item = (char *) zhashx_lookup (hash, "LIVEBEEF");
1265 assert (item == NULL);
1266 assert (zhashx_size (hash) == 3);
1267
1268 // Check that the queue is robust against random usage
1269 struct {
1270 char name [100];
1271 bool exists;
1272 } testset [200];
1273 memset (testset, 0, sizeof (testset));
1274 int testmax = 200, testnbr, iteration;
1275
1276 srandom ((unsigned) time (NULL));
1277 for (iteration = 0; iteration < 25000; iteration++) {
1278 testnbr = randof (testmax);
1279 assert (testnbr != testmax);
1280 assert (testnbr < testmax);
1281 if (testset [testnbr].exists) {
1282 item = (char *) zhashx_lookup (hash, testset [testnbr].name);
1283 assert (item);
1284 zhashx_delete (hash, testset [testnbr].name);
1285 testset [testnbr].exists = false;
1286 }
1287 else {
1288 sprintf (testset [testnbr].name, "%x-%x", rand (), rand ());
1289 if (zhashx_insert (hash, testset [testnbr].name, "") == 0)
1290 testset [testnbr].exists = true;
1291 }
1292 }
1293 // Test 10K lookups
1294 for (iteration = 0; iteration < 10000; iteration++)
1295 item = (char *) zhashx_lookup (hash, "DEADBEEFABADCAFE");
1296
1297 // Destructor should be safe to call twice
1298 zhashx_destroy (&hash);
1299 zhashx_destroy (&hash);
1300 assert (hash == NULL);
1301
1302 // Test randof() limits - should be within (0..testmax)
1303 // and randomness distribution - should not have (many) zero-counts
1304 // If there are - maybe the ZSYS_RANDOF_MAX is too big for this platform
1305 // Note: This test can take a while on systems with weak floating point HW
1306 testmax = 999;
1307 size_t rndcnt[999];
1308 assert ((sizeof (rndcnt)/sizeof(rndcnt[0])) == testmax);
1309 memset (rndcnt, 0, sizeof (rndcnt));
1310 for (iteration = 0; iteration < 10000000; iteration++) {
1311 testnbr = randof (testmax);
1312 assert (testnbr != testmax);
1313 assert (testnbr < testmax);
1314 assert (testnbr >= 0);
1315 rndcnt[testnbr]++;
1316 }
1317 int rndmisses = 0;
1318 for (iteration = 0; iteration < testmax; iteration++) {
1319 if (rndcnt[iteration] == 0) {
1320 zsys_warning("zhashx_test() : random distribution fault : got 0 hits for %d/%d",
1321 iteration, testmax);
1322 rndmisses++;
1323 }
1324 }
1325 // Too many misses are suspicious... we can lose half the entries
1326 // for each bit not used in the assumed ZSYS_RANDOF_MAX...
1327 assert ( (rndmisses < (testmax / 3 )) );
1328
1329 // Test destructor; automatically copies and frees string values
1330 hash = zhashx_new ();
1331 assert (hash);
1332 zhashx_set_destructor (hash, (zhashx_destructor_fn *) zstr_free);
1333 zhashx_set_duplicator (hash, (zhashx_duplicator_fn *) strdup);
1334 char value [255];
1335 strcpy (value, "This is a string");
1336 rc = zhashx_insert (hash, "key1", value);
1337 assert (rc == 0);
1338 strcpy (value, "Ring a ding ding");
1339 rc = zhashx_insert (hash, "key2", value);
1340 assert (rc == 0);
1341 assert (streq ((char *) zhashx_lookup (hash, "key1"), "This is a string"));
1342 assert (streq ((char *) zhashx_lookup (hash, "key2"), "Ring a ding ding"));
1343 zhashx_destroy (&hash);
1344
1345 // Test purger and shrinker: no data should end up unreferenced in valgrind
1346 hash = zhashx_new ();
1347 assert (hash);
1348 zhashx_set_destructor (hash, (zhashx_destructor_fn *) zstr_free);
1349 zhashx_set_duplicator (hash, (zhashx_duplicator_fn *) strdup);
1350 char valuep [255];
1351 strcpy (valuep, "This is a string");
1352 rc = zhashx_insert (hash, "key1", valuep);
1353 assert (rc == 0);
1354 strcpy (valuep, "Ring a ding ding");
1355 rc = zhashx_insert (hash, "key2", valuep);
1356 assert (rc == 0);
1357 strcpy (valuep, "Cartahena delenda est");
1358 rc = zhashx_insert (hash, "key3", valuep);
1359 assert (rc == 0);
1360 strcpy (valuep, "So say we all!");
1361 rc = zhashx_insert (hash, "key4", valuep);
1362 assert (rc == 0);
1363 assert (streq ((char *) zhashx_lookup (hash, "key1"), "This is a string"));
1364 assert (streq ((char *) zhashx_lookup (hash, "key2"), "Ring a ding ding"));
1365 assert (streq ((char *) zhashx_lookup (hash, "key3"), "Cartahena delenda est"));
1366 assert (streq ((char *) zhashx_lookup (hash, "key4"), "So say we all!"));
1367 zhashx_purge (hash);
1368 zhashx_destroy (&hash);
1369
1370 #if defined (__WINDOWS__)
1371 zsys_shutdown();
1372 #endif
1373 // @end
1374
1375 printf ("OK\n");
1376 }
1377