00001
00002
00003
00004 #include <stdlib.h>
00005 #include <unistd.h>
00006 #include <string.h>
00007 #include <stdio.h>
00008
00009 #include <toolbox/memory.h>
00010 #include <toolbox/carpal.h>
00011 #include <toolbox/hmap.h>
00012 #include <toolbox/queue.h>
00013 #include <toolbox/str.h>
00014 #include <toolbox/misc.h>
00015
00016
00017 #define U_HMAP_MAX_SIZE 512
00018 #define U_HMAP_MAX_ELEMS U_HMAP_MAX_SIZE
00019 #define U_HMAP_RATE_FULL 0.75
00020 #define U_HMAP_RATE_RESIZE 3
00021
00022
00023 enum {
00024 U_HMAP_PCY_OP_PUT = 0x1,
00025 U_HMAP_PCY_OP_GET = 0x2
00026 };
00027
00028
00029 struct u_hmap_q_s
00030 {
00031 u_hmap_o_t *ho;
00032 void *data;
00034 TAILQ_ENTRY(u_hmap_q_s) next;
00035 };
00036 typedef struct u_hmap_q_s u_hmap_q_t;
00037
00038
00039 struct u_hmap_pcy_s
00040 {
00041 int (*pop)(u_hmap_t *hmap, u_hmap_o_t **obj);
00042 int (*push)(u_hmap_t *hmap, u_hmap_o_t *obj,
00043 u_hmap_q_t **data);
00044 int ops;
00045
00046 TAILQ_HEAD(u_hmap_q_h_s, u_hmap_q_s) queue;
00047 };
00048 typedef struct u_hmap_q_h_s u_hmap_q_h_t;
00049
00050
00051 struct u_hmap_o_s
00052 {
00053 void *key;
00054 void *val;
00055
00056 LIST_ENTRY(u_hmap_o_s) next;
00057
00058 u_hmap_q_t *pqe;
00059
00060 u_hmap_t *hmap;
00061 };
00062
00063
00064 struct u_hmap_opts_s
00065 {
00066 size_t size,
00067 max;
00070 u_hmap_type_t type;
00072 u_hmap_pcy_type_t policy;
00074 int options;
00076 u_hmap_options_datatype_t key_type;
00077 u_hmap_options_datatype_t val_type;
00079 size_t key_sz;
00080 size_t val_sz;
00081
00083 size_t (*f_hash)(const void *key, size_t buckets);
00085 int (*f_comp)(const void *k1, const void *k2);
00087 void (*f_free)(u_hmap_o_t *obj);
00089 void (*f_key_free)(const void *key);
00091 void (*f_val_free)(void *val);
00093 u_string_t *(*f_str)(u_hmap_o_t *obj);
00095 int (*f_pcy_cmp)(void *o1, void *o2);
00096
00097 unsigned char easy;
00099 unsigned char val_free_set;
00102 };
00103
00104
00105 struct u_hmap_s
00106 {
00107 u_hmap_opts_t *opts;
00108
00109 size_t sz,
00110 size,
00111 threshold,
00112 px;
00113
00114 u_hmap_pcy_t pcy;
00115
00116 LIST_HEAD(u_hmap_e_s, u_hmap_o_s) *hmap;
00117 };
00118 typedef struct u_hmap_e_s u_hmap_e_t;
00119
00120 static int __get (u_hmap_t *hmap, const void *key, u_hmap_o_t **o);
00121
00122 static int __opts_check (u_hmap_opts_t *opts);
00123 static int __pcy_setup (u_hmap_t *hmap);
00124 static const char *__pcy2str(u_hmap_pcy_type_t policy);
00125
00126 static void __o_free (u_hmap_t *hmap, u_hmap_o_t *obj);
00127 static int __o_overwrite (u_hmap_t *hmap, u_hmap_o_t *o, u_hmap_o_t *obj,
00128 u_hmap_o_t **old);
00129
00130 static u_hmap_q_t *__q_o_new (u_hmap_o_t *ho);
00131 static void __q_o_free (u_hmap_q_t *s);
00132
00133 static size_t __f_hash (const void *key, size_t size);
00134 static int __f_comp (const void *k1, const void *k2);
00135 static u_string_t *__f_str (u_hmap_o_t *obj);
00136
00137 static int __queue_push (u_hmap_t *hmap, u_hmap_o_t *obj, u_hmap_q_t **data);
00138 static int __queue_push_count (u_hmap_t *hmap, u_hmap_o_t *obj,
00139 u_hmap_q_t **counts);
00140 static int __queue_push_cmp (u_hmap_t *hmap, u_hmap_o_t *obj,
00141 u_hmap_q_t **counts);
00142 static int __queue_pop_front (u_hmap_t *hmap, u_hmap_o_t **obj);
00143 static int __queue_pop_back (u_hmap_t *hmap, u_hmap_o_t **obj);
00144 static int __queue_del (u_hmap_t *hmap, u_hmap_o_t *obj);
00145
00146 static int __resize(u_hmap_t *hmap);
00147 static int __next_prime(size_t *prime, size_t sz, size_t *idx);
00148
00149 static const char *__datatype2str(u_hmap_options_datatype_t datatype);
00150
00274 int u_hmap_easy_new (u_hmap_opts_t *opts, u_hmap_t **phmap)
00275 {
00276 u_hmap_opts_t newopts;
00277
00278 dbg_err_if (opts == NULL);
00279 dbg_err_if (phmap == NULL);
00280
00281 u_hmap_opts_init(&newopts);
00282
00283 dbg_err_if (u_hmap_opts_copy(&newopts, opts));
00284
00285
00286 newopts.easy = 1;
00287
00288 dbg_err_if (u_hmap_new(&newopts, phmap));
00289
00290 return U_HMAP_ERR_NONE;
00291 err:
00292 return U_HMAP_ERR_FAIL;
00293 }
00294
00302 void u_hmap_easy_clear (u_hmap_t *hmap)
00303 {
00304 dbg_ifb (hmap == NULL) return;
00305
00306 u_hmap_clear(hmap);
00307 }
00308
00318 void u_hmap_easy_free (u_hmap_t *hmap)
00319 {
00320 dbg_return_if (hmap == NULL, );
00321
00322 u_hmap_free(hmap);
00323
00324 return;
00325 }
00326
00353 int u_hmap_easy_put (u_hmap_t *hmap, const char *key, const void *val)
00354 {
00355 int rc = U_HMAP_ERR_NONE;
00356 u_hmap_o_t *obj = NULL;
00357
00358 dbg_err_if ((obj = u_hmap_o_new(hmap, key, val)) == NULL);
00359 dbg_err_if ((rc = u_hmap_put(hmap, obj, NULL)));
00360
00361 return rc;
00362 err:
00363
00364 return (rc ? rc : U_HMAP_ERR_FAIL);
00365 }
00366
00378 void *u_hmap_easy_get (u_hmap_t *hmap, const char *key)
00379 {
00380 u_hmap_o_t *obj = NULL;
00381
00382 nop_return_if (u_hmap_get(hmap, key, &obj), NULL);
00383
00384 return obj->val;
00385 }
00386
00398 int u_hmap_easy_del (u_hmap_t *hmap, const char *key)
00399 {
00400 return (u_hmap_del(hmap, key, NULL));
00401 }
00402
00407
00408 static size_t __f_hash (const void *key, size_t size)
00409 {
00410 size_t h = 0;
00411 const unsigned char *k = (const unsigned char *) key;
00412
00413 dbg_ifb (key == NULL) return -1;
00414
00415 while (*k)
00416 {
00417 h += *k++;
00418 h += (h << 10);
00419 h ^= (h >> 6);
00420 }
00421
00422 h += (h << 3);
00423 h ^= (h >> 11);
00424
00425 return (h + (h << 15)) % size;
00426 }
00427
00428
00429 static int __f_comp (const void *k1, const void *k2)
00430 {
00431 dbg_ifb (k1 == NULL) return -1;
00432 dbg_ifb (k2 == NULL) return -1;
00433
00434 return strcmp((const char *)k1, (const char *)k2);
00435 }
00436
00437
00438 static u_string_t *__f_str (u_hmap_o_t *obj)
00439 {
00440 enum { MAX_OBJ_STR = 256 };
00441 char buf[MAX_OBJ_STR];
00442 u_string_t *s = NULL;
00443 const char *key, *val;
00444
00445 dbg_err_if (obj == NULL);
00446
00447 key = (obj->hmap->opts->key_type == U_HMAP_OPTS_DATATYPE_STRING) ?
00448 (const char *) obj->key : "";
00449 val = (obj->hmap->opts->val_type == U_HMAP_OPTS_DATATYPE_STRING) ?
00450 (const char *) obj->val : "";
00451
00452 dbg_err_if (u_snprintf(buf, MAX_OBJ_STR, "[%s:%s]", key, val));
00453 dbg_err_if (u_string_create(buf, strlen(buf)+1, &s));
00454
00455 return s;
00456
00457 err:
00458 U_FREE(s);
00459 return NULL;
00460 }
00461
00462
00463 static int __opts_check (u_hmap_opts_t *opts)
00464 {
00465 dbg_err_if (opts == NULL);
00466
00467 dbg_err_if (opts->size == 0);
00468 dbg_err_if (opts->max == 0);
00469 dbg_err_if (opts->type != U_HMAP_TYPE_CHAIN &&
00470 opts->type != U_HMAP_TYPE_LINEAR);
00471 dbg_err_if (!U_HMAP_IS_PCY(opts->policy));
00472 dbg_err_if (opts->f_hash == NULL);
00473 dbg_err_if (opts->f_comp == NULL);
00474
00475
00476
00477
00478
00479 dbg_err_ifm (opts->easy &&
00480 opts->val_type == U_HMAP_OPTS_DATATYPE_POINTER &&
00481 !opts->val_free_set,
00482 "value free function must be set for pointers!");
00483
00484 dbg_err_ifm (opts->policy == U_HMAP_PCY_CUSTOM &&
00485 opts->f_pcy_cmp == NULL,
00486 "comparison function must be set for custom policy!");
00487
00488 return U_HMAP_ERR_NONE;
00489 err:
00490 return U_HMAP_ERR_FAIL;
00491 }
00492
00493
00494 static int __pcy_setup (u_hmap_t *hmap)
00495 {
00496 dbg_return_if (hmap == NULL, ~0);
00497
00498 switch (hmap->opts->policy)
00499 {
00500 case U_HMAP_PCY_NONE:
00501 hmap->pcy.push = NULL;
00502 hmap->pcy.pop = NULL;
00503 hmap->pcy.ops = 0;
00504 break;
00505 case U_HMAP_PCY_FIFO:
00506 hmap->pcy.push = __queue_push;
00507 hmap->pcy.pop = __queue_pop_back;
00508 hmap->pcy.ops = U_HMAP_PCY_OP_PUT;
00509 break;
00510 case U_HMAP_PCY_LRU:
00511 hmap->pcy.push = __queue_push;
00512 hmap->pcy.pop = __queue_pop_back;
00513 hmap->pcy.ops = U_HMAP_PCY_OP_PUT | U_HMAP_PCY_OP_GET;
00514 break;
00515 case U_HMAP_PCY_LFU:
00516 hmap->pcy.push = __queue_push_count;
00517 hmap->pcy.pop = __queue_pop_front;
00518 hmap->pcy.ops = U_HMAP_PCY_OP_PUT | U_HMAP_PCY_OP_GET;
00519 break;
00520 case U_HMAP_PCY_CUSTOM:
00521 hmap->pcy.push = __queue_push_cmp;
00522 hmap->pcy.pop = __queue_pop_back;
00523 hmap->pcy.ops = U_HMAP_PCY_OP_PUT;
00524 break;
00525 default:
00526 u_dbg("Invalid policy: %d", hmap->opts->policy);
00527 return U_HMAP_ERR_FAIL;
00528 }
00529
00530 return U_HMAP_ERR_NONE;
00531 }
00532
00551 int u_hmap_new (u_hmap_opts_t *opts, u_hmap_t **phmap)
00552 {
00553 size_t i;
00554 u_hmap_t *c = NULL;
00555
00556
00557 dbg_return_if (phmap == NULL, U_HMAP_ERR_FAIL);
00558
00559 dbg_return_sif ((c = (u_hmap_t *) u_zalloc(sizeof(u_hmap_t))) == NULL,
00560 U_HMAP_ERR_FAIL);
00561
00562 dbg_err_if (u_hmap_opts_new(&c->opts));
00563 if (opts)
00564 dbg_err_if (u_hmap_opts_copy(c->opts, opts));
00565
00566
00567 if (c->opts->f_str == NULL &&
00568 (c->opts->key_type == U_HMAP_OPTS_DATATYPE_STRING ||
00569 c->opts->val_type == U_HMAP_OPTS_DATATYPE_STRING))
00570 c->opts->f_str = &__f_str;
00571
00572 dbg_err_if (__opts_check(c->opts));
00573 u_hmap_opts_dbg(c->opts);
00574 dbg_err_if (__pcy_setup(c));
00575
00576 c->size = c->opts->size;
00577 dbg_err_if (__next_prime(&c->size, c->size, &c->px));
00578 c->threshold = (size_t) (U_HMAP_RATE_FULL * c->size);
00579
00580 dbg_err_sif ((c->hmap = (u_hmap_e_t *)
00581 u_zalloc(sizeof(u_hmap_e_t) *
00582 c->size)) == NULL);
00583
00584
00585 for (i = 0; i < c->size; ++i)
00586 LIST_INIT(&c->hmap[i]);
00587
00588 TAILQ_INIT(&c->pcy.queue);
00589
00590 u_dbg("[hmap]");
00591 u_dbg("threshold: %u", c->threshold);
00592
00593 *phmap = c;
00594
00595 return U_HMAP_ERR_NONE;
00596
00597 err:
00598 u_free(c);
00599 *phmap = NULL;
00600 return U_HMAP_ERR_FAIL;
00601 }
00602
00611 void u_hmap_clear (u_hmap_t *hmap)
00612 {
00613 u_hmap_o_t *obj;
00614 u_hmap_q_t *data;
00615 size_t i;
00616
00617 dbg_ifb (hmap == NULL) return;
00618
00619
00620 for (i = 0; i < hmap->size; ++i)
00621 {
00622 while ((obj = LIST_FIRST(&hmap->hmap[i])) != NULL)
00623 {
00624 LIST_REMOVE(obj, next);
00625 __o_free(hmap, obj);
00626 }
00627 }
00628
00629
00630 while ((data = TAILQ_FIRST(&hmap->pcy.queue)) != NULL)
00631 {
00632 TAILQ_REMOVE(&hmap->pcy.queue, data, next);
00633 __q_o_free(data);
00634 }
00635 }
00636
00646 void u_hmap_free (u_hmap_t *hmap)
00647 {
00648 dbg_ifb (hmap == NULL) return;
00649
00650 u_hmap_clear(hmap);
00651 u_free(hmap->hmap);
00652 u_hmap_opts_free(hmap->opts);
00653 u_free(hmap);
00654 }
00655
00673 int u_hmap_put (u_hmap_t *hmap, u_hmap_o_t *obj, u_hmap_o_t **old)
00674 {
00675 u_hmap_o_t *o;
00676 u_hmap_e_t *x;
00677 int comp;
00678 int rc;
00679 size_t hash;
00680 size_t last;
00681
00682 dbg_err_if (hmap == NULL);
00683 dbg_err_if (obj == NULL);
00684
00685 if (old)
00686 *old = NULL;
00687
00688 if (hmap->sz >= hmap->threshold &&
00689 hmap->opts->policy == U_HMAP_PCY_NONE)
00690 dbg_err_if (__resize(hmap));
00691
00692 hash = hmap->opts->f_hash(obj->key, hmap->size);
00693
00694
00695 if (hmap->opts->f_hash != &__f_hash &&
00696 !(hmap->opts->options & U_HMAP_OPTS_HASH_STRONG))
00697 {
00698 enum { MAX_INT = 20 };
00699 char h[MAX_INT];
00700
00701 u_snprintf(h, MAX_INT, "%u", hash);
00702 hash = __f_hash(h, hmap->size);
00703 }
00704
00705 x = &hmap->hmap[hash];
00706
00707 switch (hmap->opts->type)
00708 {
00709 case U_HMAP_TYPE_CHAIN:
00710
00711 if (LIST_EMPTY(x))
00712 {
00713 LIST_INSERT_HEAD(x, obj, next);
00714 goto end;
00715 }
00716
00717 LIST_FOREACH(o, x, next)
00718 {
00719
00720 if ((comp = hmap->opts->f_comp(obj->key, o->key)) == 0)
00721 {
00722 rc = __o_overwrite(hmap, o, obj, old);
00723 dbg_err_if (rc && rc != U_HMAP_ERR_EXISTS);
00724 return rc;
00725 }
00726 else
00727 {
00728 if (comp < 0)
00729 {
00730 LIST_INSERT_BEFORE(o, obj, next);
00731 goto end;
00732 }
00733 else if (!LIST_NEXT(o, next))
00734 {
00735 LIST_INSERT_AFTER(o, obj, next);
00736 goto end;
00737 }
00738 }
00739 }
00740 break;
00741
00742 case U_HMAP_TYPE_LINEAR:
00743
00744 last = ((hash + hmap->size-1) % hmap->size);
00745
00746 for (; hash != last; hash = ((hash+1) % hmap->size),
00747 x = &hmap->hmap[hash])
00748 {
00749 if (LIST_EMPTY(x))
00750 {
00751 LIST_INSERT_HEAD(x, obj, next);
00752 goto end;
00753 }
00754
00755
00756 o = LIST_FIRST(x);
00757
00758
00759 if (hmap->opts->f_comp(o->key, obj->key) == 0)
00760 {
00761 rc = __o_overwrite(hmap, o, obj, old);
00762 dbg_err_if (rc && rc != U_HMAP_ERR_EXISTS);
00763 return rc;
00764 }
00765 }
00766 break;
00767 }
00768
00769 err:
00770 return U_HMAP_ERR_FAIL;
00771
00772 end:
00773
00774 if (hmap->sz >= hmap->opts->max &&
00775 hmap->opts->policy != U_HMAP_PCY_NONE)
00776 {
00777 u_dbg("Cache full - freeing according to policy '%s'",
00778 __pcy2str(hmap->opts->policy));
00779 dbg_err_if (hmap->pcy.pop(hmap, old));
00780 }
00781
00782 if (hmap->pcy.ops & U_HMAP_PCY_OP_PUT)
00783 dbg_err_if (hmap->pcy.push(hmap, obj, &obj->pqe));
00784 hmap->sz++;
00785
00786 return U_HMAP_ERR_NONE;
00787 }
00788
00803 int u_hmap_get (u_hmap_t *hmap, const void *key, u_hmap_o_t **obj)
00804 {
00805 dbg_err_if (hmap == NULL);
00806 dbg_err_if (key == NULL);
00807 dbg_err_if (obj == NULL);
00808
00809 if (__get(hmap, key, obj))
00810 {
00811 *obj = NULL;
00812 return U_HMAP_ERR_FAIL;
00813 }
00814 dbg_err_if (obj == NULL);
00815
00816 if (hmap->pcy.ops & U_HMAP_PCY_OP_GET)
00817 dbg_err_if (hmap->pcy.push(hmap, *obj, &(*obj)->pqe));
00818
00819 return U_HMAP_ERR_NONE;
00820
00821 err:
00822 return U_HMAP_ERR_FAIL;
00823 }
00824
00838 int u_hmap_del (u_hmap_t *hmap, const void *key, u_hmap_o_t **obj)
00839 {
00840 u_hmap_o_t *o = NULL;
00841
00842 dbg_err_if (hmap == NULL);
00843 dbg_err_if (key == NULL);
00844
00845 if (obj)
00846 *obj = NULL;
00847
00848 if (__get(hmap, key, &o))
00849 return U_HMAP_ERR_FAIL;
00850
00851 dbg_err_if (o == NULL);
00852 LIST_REMOVE(o, next);
00853
00854 if (hmap->opts->options & U_HMAP_OPTS_OWNSDATA)
00855 __o_free(hmap, o);
00856 else
00857 if (obj)
00858 *obj = o;
00859
00860 hmap->sz--;
00861
00862 return U_HMAP_ERR_NONE;
00863
00864 err:
00865 return U_HMAP_ERR_FAIL;
00866 }
00867
00881 u_hmap_o_t *u_hmap_o_new (u_hmap_t *hmap, const void *key, const void *val)
00882 {
00883 u_hmap_o_t *obj = NULL;
00884
00885 dbg_return_if (hmap == NULL, NULL);
00886 dbg_return_if (key == NULL, NULL);
00887 dbg_return_if (val == NULL, NULL);
00888
00889 dbg_err_sif ((obj = (u_hmap_o_t *) u_zalloc(sizeof(u_hmap_o_t))) == NULL);
00890 obj->hmap = hmap;
00891
00892 if (hmap->opts->options & U_HMAP_OPTS_OWNSDATA)
00893 {
00894
00895 switch (hmap->opts->key_type)
00896 {
00897 case U_HMAP_OPTS_DATATYPE_POINTER:
00898 memcpy(&obj->key, &key, sizeof(void **));
00899 break;
00900 case U_HMAP_OPTS_DATATYPE_STRING:
00901 dbg_err_if ((obj->key = u_strdup((const char *) key)) == NULL);
00902 break;
00903 case U_HMAP_OPTS_DATATYPE_OPAQUE:
00904 dbg_err_if ((obj->key = u_zalloc(hmap->opts->key_sz)) == NULL);
00905 memcpy(obj->key, key, hmap->opts->key_sz);
00906 break;
00907 }
00908
00909
00910 switch (hmap->opts->val_type)
00911 {
00912 case U_HMAP_OPTS_DATATYPE_POINTER:
00913 memcpy(&obj->val, &val, sizeof(void **));
00914 break;
00915 case U_HMAP_OPTS_DATATYPE_STRING:
00916 dbg_err_if ((obj->val = u_strdup((const char *) val)) == NULL);
00917 break;
00918 case U_HMAP_OPTS_DATATYPE_OPAQUE:
00919 dbg_err_if ((obj->val = u_zalloc(hmap->opts->val_sz)) == NULL);
00920 memcpy(obj->val, val, hmap->opts->val_sz);
00921 break;
00922 }
00923 }
00924 else
00925 {
00926 memcpy(&obj->key, &key, sizeof(void **));
00927 memcpy(&obj->val, &val, sizeof(void **));
00928 }
00929
00930 obj->pqe = NULL;
00931
00932 return obj;
00933
00934 err:
00935 U_FREEF(obj, u_hmap_o_free);
00936
00937 return NULL;
00938 }
00939
00951 void u_hmap_o_free (u_hmap_o_t *obj)
00952 {
00953 dbg_ifb (obj == NULL) return;
00954
00955 u_free(obj);
00956 }
00957
00959 void *u_hmap_o_get_key (u_hmap_o_t *obj)
00960 {
00961 return obj->key;
00962 }
00963
00965 void *u_hmap_o_get_val (u_hmap_o_t *obj)
00966 {
00967 return obj->val;
00968 }
00969
00970
00971 static void __o_free (u_hmap_t *hmap, u_hmap_o_t *obj)
00972 {
00973 dbg_ifb (hmap == NULL) return;
00974 dbg_ifb (obj == NULL) return;
00975
00976 if (hmap->opts->f_free)
00977 {
00978 hmap->opts->f_free(obj);
00979 }
00980 else
00981 {
00982 switch (hmap->opts->key_type)
00983 {
00984 case U_HMAP_OPTS_DATATYPE_POINTER:
00985 if (hmap->opts->f_key_free)
00986 hmap->opts->f_key_free(obj->key);
00987 break;
00988 case U_HMAP_OPTS_DATATYPE_STRING:
00989 case U_HMAP_OPTS_DATATYPE_OPAQUE:
00990 u_free(obj->key);
00991 break;
00992 }
00993 switch (hmap->opts->val_type)
00994 {
00995 case U_HMAP_OPTS_DATATYPE_POINTER:
00996 if (hmap->opts->f_val_free)
00997 hmap->opts->f_val_free(obj->val);
00998 break;
00999 case U_HMAP_OPTS_DATATYPE_STRING:
01000 case U_HMAP_OPTS_DATATYPE_OPAQUE:
01001 u_free(obj->val);
01002 break;
01003 }
01004 }
01005
01006 u_hmap_o_free(obj);
01007 }
01008
01009 static int __o_overwrite (u_hmap_t *hmap, u_hmap_o_t *o, u_hmap_o_t *obj,
01010 u_hmap_o_t **old)
01011 {
01012
01013 if (!(hmap->opts->options &
01014 U_HMAP_OPTS_NO_OVERWRITE))
01015 {
01016 if (hmap->pcy.ops & U_HMAP_PCY_OP_PUT)
01017 {
01018
01019 dbg_err_if (__queue_del(hmap, o));
01020 dbg_err_if (hmap->pcy.push(hmap, obj, &obj->pqe));
01021 }
01022
01023
01024 LIST_INSERT_AFTER(o, obj, next);
01025 LIST_REMOVE(o, next);
01026
01027 if (hmap->opts->options & U_HMAP_OPTS_OWNSDATA)
01028 __o_free(hmap, o);
01029 else
01030 if (old)
01031 *old = o;
01032
01033 return U_HMAP_ERR_NONE;
01034 }
01035 else
01036 {
01037 if (hmap->opts->options & U_HMAP_OPTS_OWNSDATA)
01038 __o_free(hmap, obj);
01039 else
01040 if (old)
01041 *old = o;
01042
01043 return U_HMAP_ERR_EXISTS;
01044 }
01045 err:
01046 return U_HMAP_ERR_FAIL;
01047 }
01048
01059 ssize_t u_hmap_count (u_hmap_t *hmap)
01060 {
01061 dbg_return_if (hmap == NULL, -1);
01062 return hmap->sz;
01063 }
01064
01086 int u_hmap_opts_new (u_hmap_opts_t **opts)
01087 {
01088 u_hmap_opts_t *o;
01089
01090 dbg_err_if (opts == NULL);
01091
01092 dbg_err_sif ((o = (u_hmap_opts_t *) u_zalloc(sizeof(u_hmap_opts_t)))
01093 == NULL);
01094
01095 u_hmap_opts_init(o);
01096
01097 *opts = o;
01098
01099 return U_HMAP_ERR_NONE;
01100 err:
01101 *opts = NULL;
01102 return U_HMAP_ERR_FAIL;
01103 }
01104
01112 void u_hmap_opts_free (u_hmap_opts_t *opts)
01113 {
01114 dbg_ifb (opts == NULL) return;
01115
01116 u_free(opts);
01117 }
01118
01126 void u_hmap_opts_init (u_hmap_opts_t *opts)
01127 {
01128 dbg_ifb (opts == NULL) return;
01129
01130 opts->size = U_HMAP_MAX_SIZE;
01131 opts->type = U_HMAP_TYPE_CHAIN;
01132 opts->max = U_HMAP_MAX_ELEMS;
01133 opts->policy = U_HMAP_PCY_NONE;
01134 opts->options = U_HMAP_OPTS_NO_OVERWRITE | U_HMAP_OPTS_OWNSDATA;
01135 opts->f_hash = &__f_hash;
01136 opts->f_comp = &__f_comp;
01137 opts->f_free = NULL;
01138 opts->key_type = U_HMAP_OPTS_DATATYPE_STRING;
01139 opts->val_type = U_HMAP_OPTS_DATATYPE_POINTER;
01140 opts->f_key_free = NULL;
01141 opts->f_val_free = NULL;
01142 opts->val_free_set = 0;
01143 opts->f_str = NULL;
01144 opts->key_sz = sizeof(void *);
01145 opts->val_sz = sizeof(void *);
01146 opts->easy = 0;
01147
01148 return;
01149 }
01150
01162 int u_hmap_opts_copy (u_hmap_opts_t *to, u_hmap_opts_t *from)
01163 {
01164 dbg_err_if (to == NULL);
01165 dbg_err_if (from == NULL);
01166
01167 memcpy(to, from, sizeof(u_hmap_opts_t));
01168
01169 return U_HMAP_ERR_NONE;
01170 err:
01171 return U_HMAP_ERR_FAIL;
01172 }
01173
01181 void u_hmap_opts_dbg (u_hmap_opts_t *opts)
01182 {
01183 dbg_return_if (opts == NULL, );
01184
01185 u_dbg("<hmap_options>");
01186 u_dbg(" easy: %s", opts->easy ? "yes" : "no");
01187 u_dbg(" discard policy: %s", __pcy2str(opts->policy));
01188 u_dbg(" buckets: %u (max: %u -- if discard policy != none)",
01189 opts->size, opts->max);
01190 u_dbg(" owns data: %s",
01191 (opts->options & U_HMAP_OPTS_OWNSDATA) ? "yes" : "no");
01192 u_dbg(" objects dtor: %s", opts->f_free ? "set" : "not set");
01193 u_dbg(" keys dtor: %s", opts->f_key_free ? "set" : "not set");
01194 u_dbg(" values dtor: %s", opts->f_val_free ? "set" : "not set");
01195 u_dbg(" object serializer: %s", opts->f_str ? "set" : "not set");
01196 u_dbg(" overwrite equal keys: %s",
01197 (opts->options & U_HMAP_OPTS_NO_OVERWRITE) ? "no" : "yes");
01198 u_dbg(" key type: %s", __datatype2str(opts->key_type));
01199 u_dbg(" value type: %s", __datatype2str(opts->val_type));
01200 u_dbg("</hmap_options>");
01201
01202 return;
01203 }
01204
01206 int u_hmap_opts_set_size (u_hmap_opts_t *opts, int sz)
01207 {
01208 dbg_err_if (opts == NULL || sz <= 0);
01209
01210 opts->size = sz;
01211
01212 return U_HMAP_ERR_NONE;
01213 err:
01214 return U_HMAP_ERR_FAIL;
01215 }
01216
01222 int u_hmap_opts_set_max (u_hmap_opts_t *opts, int max)
01223 {
01224 dbg_err_if (opts == NULL || max <= 0);
01225
01226 opts->max = max;
01227
01228 return U_HMAP_ERR_NONE;
01229 err:
01230 return U_HMAP_ERR_FAIL;
01231 }
01232
01234 int u_hmap_opts_set_type (u_hmap_opts_t *opts, u_hmap_type_t type)
01235 {
01236 dbg_err_if (opts == NULL);
01237 dbg_err_if (!U_HMAP_IS_TYPE(type));
01238
01239 opts->type = type;
01240
01241 return U_HMAP_ERR_NONE;
01242 err:
01243 return U_HMAP_ERR_FAIL;
01244 }
01245
01248 int u_hmap_opts_set_option (u_hmap_opts_t *opts, int option)
01249 {
01250 dbg_err_if (opts == NULL);
01251
01252 dbg_err_if ((option != U_HMAP_OPTS_OWNSDATA &&
01253 option != U_HMAP_OPTS_NO_OVERWRITE &&
01254 option != U_HMAP_OPTS_HASH_STRONG));
01255
01256 dbg_err_if (opts->easy &&
01257 option == U_HMAP_OPTS_OWNSDATA);
01258
01259 opts->options |= option;
01260
01261 return U_HMAP_ERR_NONE;
01262 err:
01263 return U_HMAP_ERR_FAIL;
01264 }
01265
01268 int u_hmap_opts_unset_option (u_hmap_opts_t *opts, int option)
01269 {
01270 dbg_err_if (opts == NULL);
01271
01272 dbg_err_if ((option != U_HMAP_OPTS_OWNSDATA &&
01273 option != U_HMAP_OPTS_NO_OVERWRITE &&
01274 option != U_HMAP_OPTS_HASH_STRONG));
01275
01276 dbg_err_if (opts->easy &&
01277 option == U_HMAP_OPTS_OWNSDATA);
01278
01279 opts->options &= ~option;
01280
01281 return U_HMAP_ERR_NONE;
01282 err:
01283 return U_HMAP_ERR_FAIL;
01284 }
01285
01287 int u_hmap_opts_set_hashfunc (u_hmap_opts_t *opts,
01288 size_t (*f_hash)(const void *key, size_t buckets))
01289 {
01290 dbg_err_if (opts == NULL || f_hash == NULL);
01291
01292 opts->f_hash = f_hash;
01293
01294 return U_HMAP_ERR_NONE;
01295 err:
01296 return U_HMAP_ERR_FAIL;
01297 }
01298
01300 int u_hmap_opts_set_compfunc (u_hmap_opts_t *opts,
01301 int (*f_comp)(const void *k1, const void *k2))
01302 {
01303 dbg_err_if (opts == NULL || f_comp == NULL);
01304
01305 opts->f_comp = f_comp;
01306
01307 return U_HMAP_ERR_NONE;
01308 err:
01309 return U_HMAP_ERR_FAIL;
01310 }
01311
01314 int u_hmap_opts_set_freefunc (u_hmap_opts_t *opts,
01315 void (*f_free)(u_hmap_o_t *obj))
01316 {
01317 dbg_err_if (opts == NULL || opts->easy);
01318
01319 opts->f_free = f_free;
01320
01321 return U_HMAP_ERR_NONE;
01322 err:
01323 return U_HMAP_ERR_FAIL;
01324 }
01325
01327 int u_hmap_opts_set_strfunc (u_hmap_opts_t *opts,
01328 u_string_t *(*f_str)(u_hmap_o_t *obj))
01329 {
01330 dbg_err_if (opts == NULL);
01331
01332 opts->f_str = f_str;
01333
01334 return U_HMAP_ERR_NONE;
01335 err:
01336 return U_HMAP_ERR_FAIL;
01337 }
01338
01341 int u_hmap_opts_set_key_type (u_hmap_opts_t *opts,
01342 u_hmap_options_datatype_t type)
01343 {
01344 dbg_err_if (opts == NULL);
01345 dbg_err_if (!U_HMAP_IS_DATATYPE(type));
01346
01347
01348 dbg_err_ifm (opts->easy,
01349 "cannot set data type when \"easy\" interface is in use");
01350
01351 opts->key_type = type;
01352
01353 return U_HMAP_ERR_NONE;
01354 err:
01355 return U_HMAP_ERR_FAIL;
01356 }
01357
01360 int u_hmap_opts_set_key_sz (u_hmap_opts_t *opts, size_t sz)
01361 {
01362 dbg_err_if (opts == NULL || sz == 0);
01363
01364 dbg_err_if (opts->easy);
01365 dbg_err_if (opts->key_type != U_HMAP_OPTS_DATATYPE_OPAQUE);
01366
01367 opts->key_sz = sz;
01368
01369 return U_HMAP_ERR_NONE;
01370 err:
01371 return U_HMAP_ERR_FAIL;
01372 }
01373
01376 int u_hmap_opts_set_key_freefunc (u_hmap_opts_t *opts,
01377 void (*f_free)(const void *key))
01378 {
01379 dbg_err_if (opts == NULL);
01380
01381 dbg_err_if (opts->easy);
01382
01383 opts->f_key_free = f_free;
01384
01385 return U_HMAP_ERR_NONE;
01386 err:
01387 return U_HMAP_ERR_FAIL;
01388 }
01389
01391 int u_hmap_opts_set_val_type (u_hmap_opts_t *opts,
01392 u_hmap_options_datatype_t type)
01393 {
01394 dbg_err_if (opts == NULL);
01395 dbg_err_if (!U_HMAP_IS_DATATYPE(type));
01396
01397 opts->val_type = type;
01398
01399 return U_HMAP_ERR_NONE;
01400 err:
01401 return U_HMAP_ERR_FAIL;
01402 }
01403
01406 int u_hmap_opts_set_val_sz (u_hmap_opts_t *opts, size_t sz)
01407 {
01408 dbg_err_if (opts == NULL || sz == 0);
01409
01410 dbg_err_if (opts->val_type != U_HMAP_OPTS_DATATYPE_OPAQUE);
01411
01412 opts->val_sz = sz;
01413
01414 return U_HMAP_ERR_NONE;
01415 err:
01416 return U_HMAP_ERR_FAIL;
01417 }
01418
01420 int u_hmap_opts_set_val_freefunc (u_hmap_opts_t *opts,
01421 void (*f_free)(void *val))
01422 {
01423 dbg_err_if (opts == NULL);
01424
01425 opts->f_val_free = f_free;
01426 opts->val_free_set = 1;
01427
01428 return U_HMAP_ERR_NONE;
01429 err:
01430 return U_HMAP_ERR_FAIL;
01431 }
01432
01443 int u_hmap_opts_set_policy (u_hmap_opts_t *opts, u_hmap_pcy_type_t policy)
01444 {
01445 dbg_err_if (opts == NULL);
01446 dbg_err_if (!U_HMAP_IS_PCY(policy));
01447
01448 opts->policy = policy;
01449
01450 return U_HMAP_ERR_NONE;
01451 err:
01452 return U_HMAP_ERR_FAIL;
01453 }
01454
01461 int u_hmap_opts_set_policy_cmp (u_hmap_opts_t *opts,
01462 int (*f_pcy_cmp)(void *o1, void *o2))
01463 {
01464 dbg_err_if (opts == NULL || f_pcy_cmp == NULL);
01465 dbg_err_if (opts->policy != U_HMAP_PCY_CUSTOM);
01466
01467 opts->f_pcy_cmp = f_pcy_cmp;
01468
01469 return U_HMAP_ERR_NONE;
01470 err:
01471 return U_HMAP_ERR_FAIL;
01472 }
01473
01490 const char *u_hmap_strerror (u_hmap_ret_t rc)
01491 {
01492 switch (rc)
01493 {
01494 case U_HMAP_ERR_NONE:
01495 return "success";
01496 case U_HMAP_ERR_FAIL:
01497 return "general failure";
01498 case U_HMAP_ERR_EXISTS:
01499 return "element already exists in table";
01500 }
01501 return NULL;
01502 }
01503
01516 int u_hmap_copy (u_hmap_t *to, u_hmap_t *from)
01517 {
01518 u_hmap_o_t *obj;
01519 size_t i;
01520
01521 dbg_err_if (to == NULL);
01522 dbg_err_if (from == NULL);
01523
01524 for (i = 0; i < from->size; ++i)
01525 {
01526 while ((obj = LIST_FIRST(&from->hmap[i])) != NULL)
01527 {
01528 LIST_REMOVE(obj, next);
01529 dbg_err_if (u_hmap_put(to, obj, NULL));
01530 }
01531 }
01532
01533 return U_HMAP_ERR_NONE;
01534
01535 err:
01536 return U_HMAP_ERR_FAIL;
01537 }
01538
01539
01540 static int __get (u_hmap_t *hmap, const void *key, u_hmap_o_t **o)
01541 {
01542 u_hmap_o_t *obj;
01543 u_hmap_e_t *x;
01544 int comp;
01545 size_t hash;
01546 size_t last;
01547
01548 dbg_err_if (hmap == NULL);
01549 dbg_err_if (key == NULL);
01550 dbg_err_if (o == NULL);
01551
01552 hash = hmap->opts->f_hash(key, hmap->size);
01553
01554 if (hmap->opts->f_hash != &__f_hash &&
01555 !(hmap->opts->options & U_HMAP_OPTS_HASH_STRONG))
01556 {
01557 enum { MAX_INT = 20 };
01558 char h[MAX_INT];
01559
01560 u_snprintf(h, MAX_INT, "%u", hash);
01561 hash = __f_hash(h, hmap->size);
01562 }
01563
01564 x = &hmap->hmap[hash];
01565
01566 switch (hmap->opts->type)
01567 {
01568 case U_HMAP_TYPE_CHAIN:
01569
01570 LIST_FOREACH(obj, x, next)
01571 {
01572 if ((comp = hmap->opts->f_comp(key, obj->key)) == 0)
01573 {
01574 *o = obj;
01575 return U_HMAP_ERR_NONE;
01576 }
01577 else if (comp < 0)
01578 {
01579 *o = NULL;
01580 break;
01581 }
01582 }
01583 break;
01584
01585 case U_HMAP_TYPE_LINEAR:
01586
01587 last = ((hash + hmap->size -1) % hmap->size);
01588
01589 for (; hash != last; hash = ((hash +1) % hmap->size),
01590 x = &hmap->hmap[hash])
01591 {
01592 if (!LIST_EMPTY(x))
01593 {
01594 obj = LIST_FIRST(x);
01595
01596 if ((hmap->opts->f_comp(key, obj->key)) == 0)
01597 {
01598 *o = obj;
01599 return U_HMAP_ERR_NONE;
01600 }
01601 }
01602 }
01603 break;
01604 }
01605
01606 err:
01607 return U_HMAP_ERR_FAIL;
01608 }
01609
01610
01611 static int __queue_pop_front (u_hmap_t *hmap, u_hmap_o_t **obj)
01612 {
01613 u_hmap_q_t *first;
01614
01615 dbg_err_if (hmap == NULL);
01616
01617 dbg_err_if ((first = TAILQ_FIRST(&hmap->pcy.queue)) == NULL);
01618 dbg_err_if (u_hmap_del(hmap, first->ho->key, obj));
01619 TAILQ_REMOVE(&hmap->pcy.queue, first, next);
01620 __q_o_free(first);
01621
01622 return U_HMAP_ERR_NONE;
01623 err:
01624 return U_HMAP_ERR_FAIL;
01625 }
01626
01627
01628 static int __queue_pop_back (u_hmap_t *hmap, u_hmap_o_t **obj)
01629 {
01630 u_hmap_q_t *last;
01631
01632 dbg_err_if (hmap == NULL);
01633
01634 dbg_err_if ((last = TAILQ_LAST(&hmap->pcy.queue, u_hmap_q_h_s))
01635 == NULL);
01636 dbg_err_if (u_hmap_del(hmap, last->ho->key, obj));
01637 TAILQ_REMOVE(&hmap->pcy.queue, last, next);
01638 __q_o_free(last);
01639
01640 return U_HMAP_ERR_NONE;
01641
01642 err:
01643 return U_HMAP_ERR_FAIL;
01644 }
01645
01646
01647 static int __queue_push (u_hmap_t *hmap, u_hmap_o_t *obj,
01648 u_hmap_q_t **data)
01649 {
01650 u_hmap_q_t *new;
01651
01652 dbg_err_if (hmap == NULL);
01653 dbg_err_if (obj == NULL);
01654 dbg_err_if (data == NULL);
01655
01656 if (*data == NULL)
01657 {
01658
01659 dbg_err_if ((new = __q_o_new(obj)) == NULL);
01660 TAILQ_INSERT_HEAD(&hmap->pcy.queue, new, next);
01661 *data = new;
01662 } else {
01663
01664
01665 TAILQ_REMOVE(&hmap->pcy.queue, *data, next);
01666 TAILQ_INSERT_HEAD(&hmap->pcy.queue, *data, next);
01667 }
01668
01669 return U_HMAP_ERR_NONE;
01670 err:
01671 return U_HMAP_ERR_FAIL;
01672 }
01673
01674
01675 static int __queue_push_count (u_hmap_t *hmap, u_hmap_o_t *obj,
01676 u_hmap_q_t **counts)
01677 {
01678 u_hmap_q_t *new, *q;
01679 int *count;
01680
01681 dbg_err_if (hmap == NULL);
01682 dbg_err_if (obj == NULL);
01683 dbg_err_if (counts == NULL);
01684
01685 if (*counts == NULL)
01686 {
01687
01688 dbg_err_if ((new = __q_o_new(obj)) == NULL);
01689 TAILQ_INSERT_HEAD(&hmap->pcy.queue, new, next);
01690 dbg_err_sif ((count = (int *) u_zalloc(sizeof(int))) == NULL);
01691 new->data = (void *) count;
01692 *counts = new;
01693
01694
01695
01696 }
01697 else
01698 {
01699
01700
01701 count = (int *) (*counts)->data;
01702 *count = *count + 1;
01703
01704
01705
01706
01707
01708
01709 for (q = TAILQ_NEXT(*counts, next);
01710 q && ((*count) >= *((int *) q->data));
01711 q = TAILQ_NEXT(q, next))
01712 ;
01713 TAILQ_REMOVE(&hmap->pcy.queue, *counts, next);
01714 if (q)
01715 TAILQ_INSERT_BEFORE(q, *counts, next);
01716 else
01717 TAILQ_INSERT_TAIL(&hmap->pcy.queue, *counts, next);
01718 }
01719
01720 return U_HMAP_ERR_NONE;
01721 err:
01722 return U_HMAP_ERR_FAIL;
01723 }
01724
01725
01726 static int __queue_push_cmp (u_hmap_t *hmap, u_hmap_o_t *obj,
01727 u_hmap_q_t **data)
01728 {
01729 u_hmap_q_t *new, *q;
01730
01731 dbg_err_if (hmap == NULL);
01732 dbg_err_if (obj == NULL);
01733 dbg_err_if (data == NULL);
01734
01735
01736 dbg_err_if (*data != NULL);
01737
01738 dbg_err_if ((new = __q_o_new(obj)) == NULL);
01739
01740 if (TAILQ_EMPTY(&hmap->pcy.queue))
01741 {
01742 TAILQ_INSERT_HEAD(&hmap->pcy.queue, new, next);
01743 }
01744 else
01745 {
01746 TAILQ_FOREACH(q, &hmap->pcy.queue, next)
01747 {
01748
01749 if (hmap->opts->f_pcy_cmp(obj->val, q->ho->val) >= 0)
01750 {
01751 TAILQ_INSERT_BEFORE(q, new, next);
01752 break;
01753 }
01754 }
01755 if (q == NULL)
01756 TAILQ_INSERT_TAIL(&hmap->pcy.queue, new, next);
01757 }
01758
01759 *data = new;
01760
01761 return U_HMAP_ERR_NONE;
01762 err:
01763 return U_HMAP_ERR_FAIL;
01764 }
01765
01766
01767 static int __queue_del (u_hmap_t *hmap, u_hmap_o_t *obj)
01768 {
01769 dbg_err_if (hmap == NULL);
01770 dbg_err_if (obj == NULL);
01771
01772 TAILQ_REMOVE(&hmap->pcy.queue, obj->pqe, next);
01773 __q_o_free(obj->pqe);
01774 obj->pqe = NULL;
01775
01776 return U_HMAP_ERR_NONE;
01777 err:
01778 return U_HMAP_ERR_FAIL;
01779 }
01780
01793 int u_hmap_foreach (u_hmap_t *hmap, int f(const void *val))
01794 {
01795 u_hmap_o_t *obj;
01796 size_t i;
01797
01798 dbg_err_if (hmap == NULL);
01799 dbg_err_if (f == NULL);
01800
01801 for (i = 0; i < hmap->size; ++i)
01802 {
01803 LIST_FOREACH(obj, &hmap->hmap[i], next)
01804 dbg_err_if (f(obj->val));
01805 }
01806
01807 return U_HMAP_ERR_NONE;
01808 err:
01809 return U_HMAP_ERR_FAIL;
01810 }
01811
01826 int u_hmap_foreach_arg (u_hmap_t *hmap,
01827 int f(const void *val, const void *arg), void *arg)
01828 {
01829 size_t i;
01830 u_hmap_o_t *obj;
01831
01832 dbg_err_if (hmap == NULL);
01833 dbg_err_if (f == NULL);
01834
01835 for (i = 0; i < hmap->size; ++i)
01836 {
01837 LIST_FOREACH(obj, &hmap->hmap[i], next)
01838 dbg_err_if (f(obj->val, arg));
01839 }
01840
01841 return U_HMAP_ERR_NONE;
01842 err:
01843 return U_HMAP_ERR_FAIL;
01844 }
01845
01858 int u_hmap_foreach_keyval(u_hmap_t *hmap,
01859 int f(const void *key, const void *val))
01860 {
01861 struct u_hmap_o_s *obj;
01862 size_t i;
01863
01864 dbg_err_if (hmap == NULL);
01865 dbg_err_if (f == NULL);
01866
01867 for (i = 0; i < hmap->size; ++i)
01868 {
01869 LIST_FOREACH(obj, &hmap->hmap[i], next)
01870 dbg_err_if (f(obj->key, obj->val));
01871 }
01872
01873 return U_HMAP_ERR_NONE;
01874 err:
01875 return U_HMAP_ERR_FAIL;
01876 }
01877
01885 void u_hmap_dbg (u_hmap_t *hmap)
01886 {
01887 enum { MAX_LINE = 255 };
01888 u_string_t *s = NULL, *st = NULL;
01889 u_hmap_o_t *obj;
01890 size_t i;
01891
01892 dbg_ifb (hmap == NULL) return;
01893
01894 for (i = 0; i < hmap->size; ++i)
01895 {
01896 if (LIST_FIRST(&hmap->hmap[i]) == NULL)
01897 continue;
01898
01899 dbg_ifb (u_string_create("", 1, &s)) return;
01900 dbg_err_if (u_string_clear(s));
01901 dbg_err_if (u_string_aprintf(s, "%5d ", i));
01902
01903 LIST_FOREACH(obj, &hmap->hmap[i], next)
01904 {
01905 if (hmap->opts->f_str == NULL)
01906 {
01907 dbg_err_if (u_string_cat(s, "[]"));
01908 }
01909 else
01910 {
01911 st = hmap->opts->f_str(obj);
01912 dbg_err_if (u_string_append(s, u_string_c(st),
01913 u_string_len(st)-1));
01914 u_string_free(st);
01915 }
01916 }
01917 u_dbg(u_string_c(s));
01918 u_string_free(s);
01919 }
01920
01921 return;
01922 err:
01923 U_FREEF(st, u_string_free);
01924 U_FREEF(s, u_string_free);
01925 return;
01926 }
01927
01935 void u_hmap_pcy_dbg (u_hmap_t *hmap)
01936 {
01937 u_hmap_q_t *q;
01938 u_string_t *s = NULL, *s2 = NULL;
01939
01940 dbg_ifb (hmap == NULL) return;
01941
01942 dbg_ifb (u_string_create("", 1, &s)) return;
01943 dbg_err_if (u_string_clear(s));
01944 dbg_err_if (u_string_cat(s, "Policy: "));
01945
01946 TAILQ_FOREACH(q, &hmap->pcy.queue, next)
01947 {
01948 s2 = hmap->opts->f_str(q->ho);
01949 dbg_err_if (u_string_cat(s, u_string_c(s2)));
01950 if (hmap->opts->policy == U_HMAP_PCY_LFU)
01951 dbg_err_if (u_string_aprintf(s, "-%d", *((int *)q->data)));
01952 u_string_free(s2);
01953 }
01954
01955 u_dbg(u_string_c(s));
01956 u_string_free(s);
01957
01958 return;
01959 err:
01960 U_FREEF(s, u_string_free);
01961 U_FREEF(s2, u_string_free);
01962 return;
01963 }
01964
01965
01966 static u_hmap_q_t *__q_o_new (u_hmap_o_t *ho)
01967 {
01968 u_hmap_q_t *qo = NULL;
01969
01970 dbg_return_if (ho == NULL, NULL);
01971
01972 dbg_err_sif ((qo = (u_hmap_q_t *)
01973 u_zalloc(sizeof(u_hmap_q_t))) == NULL);
01974
01975 qo->ho = ho;
01976 qo->data = NULL;
01977
01978 return qo;
01979 err:
01980 u_free(qo);
01981 return NULL;
01982 }
01983
01984
01985 static void __q_o_free (u_hmap_q_t *qo)
01986 {
01987 dbg_ifb (qo == NULL) return;
01988
01989 if (qo->data)
01990 u_free(qo->data);
01991 u_free(qo);
01992 }
01993
01994
01995 static const char *__pcy2str (u_hmap_pcy_type_t policy)
01996 {
01997 switch (policy)
01998 {
01999 case U_HMAP_PCY_NONE:
02000 return "none";
02001 case U_HMAP_PCY_FIFO:
02002 return "fifo";
02003 case U_HMAP_PCY_LRU:
02004 return "lru";
02005 case U_HMAP_PCY_LFU:
02006 return "lfu";
02007 case U_HMAP_PCY_CUSTOM:
02008 return "custom";
02009 }
02010 return NULL;
02011 }
02012
02013
02014 static const char *__datatype2str(u_hmap_options_datatype_t datatype)
02015 {
02016 switch (datatype)
02017 {
02018 case U_HMAP_OPTS_DATATYPE_POINTER:
02019 return "pointer";
02020 case U_HMAP_OPTS_DATATYPE_STRING:
02021 return "string";
02022 case U_HMAP_OPTS_DATATYPE_OPAQUE:
02023 return "opaque";
02024 }
02025
02026 return NULL;
02027 }
02028
02029 static int __next_prime(size_t *prime, size_t sz, size_t *idx)
02030 {
02031 static size_t primes[] = {
02032 13, 19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031,
02033 1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783, 19219,
02034 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941, 204047,
02035 265271, 344857, 448321, 582821, 757693, 985003, 1280519, 1664681,
02036 2164111, 2813353, 3657361, 4754591, 6180989, 8035301, 10445899,
02037 13579681, 17653589, 22949669, 29834603, 38784989, 50420551, 65546729,
02038 85210757, 110774011, 144006217, 187208107, 243370577, 316381771,
02039 411296309, 534685237, 695090819, 903618083, 1174703521, 1527114613,
02040 1837299131, 2147483647
02041 };
02042
02043 size_t i;
02044
02045 dbg_err_if (prime == NULL);
02046 dbg_err_if (sz == 0);
02047 dbg_err_if (idx == NULL);
02048
02049 for (i = *idx; i < sizeof(primes)/sizeof(size_t); ++i)
02050 {
02051 if (primes[i] >= sz)
02052 {
02053 *idx = i;
02054 *prime = primes[i];
02055 goto ok;
02056 }
02057 }
02058 dbg_err_ifm (1, "hmap size limit exceeded");
02059
02060 ok:
02061 return 0;
02062
02063 err:
02064 return ~0;
02065 }
02066
02067 static int __resize(u_hmap_t *hmap)
02068 {
02069 u_hmap_opts_t *newopts = NULL;
02070 u_hmap_t *newmap = NULL;
02071
02072 dbg_err_if (hmap == NULL);
02073
02074 if (hmap->opts->policy != U_HMAP_PCY_NONE)
02075 return 0;
02076
02077 u_dbg("resize from: %u", hmap->size);
02078
02079
02080 dbg_err_if (u_hmap_opts_new(&newopts));
02081 dbg_err_if (u_hmap_opts_copy(newopts, hmap->opts));
02082
02083
02084 dbg_err_if (__next_prime(&newopts->size,
02085 U_HMAP_RATE_RESIZE * newopts->size,
02086 &hmap->px));
02087 dbg_err_if (u_hmap_new(newopts, &newmap));
02088 u_hmap_opts_free(newopts);
02089
02090
02091 hmap->opts->options &= !U_HMAP_OPTS_OWNSDATA;
02092
02093
02094 dbg_err_if (u_hmap_copy(newmap, hmap));
02095
02096
02097 u_hmap_opts_free(hmap->opts);
02098 u_free(hmap->hmap);
02099
02100
02101 memcpy(hmap, newmap, sizeof(u_hmap_t));
02102 u_free(newmap);
02103
02104 u_dbg("resized to: %u", hmap->size);
02105
02106 return 0;
02107 err:
02108 return ~0;
02109 }
02110