diff options
Diffstat (limited to 'src/map.c')
| -rw-r--r-- | src/map.c | 192 |
1 files changed, 97 insertions, 95 deletions
@@ -21,6 +21,8 @@ #include <libHX/string.h> #include "internal.h" #include "map_int.h" +#define N_LEFT sub[RBT_LEFT] +#define N_RIGHT sub[RBT_RIGHT] typedef void *(*clonefunc_t)(const void *, size_t); @@ -51,9 +53,9 @@ EXPORT_SYMBOL const unsigned int HXhash_primes[] = { }; #endif -static void HXhmap_free(struct HXhmap *hmap) +static void HXumap_free(struct HXumap *hmap) { - struct HXhmap_node *drop, *dnext; + struct HXumap_node *drop, *dnext; unsigned int i; for (i = 0; i < HXhash_primes[hmap->power]; ++i) { @@ -72,7 +74,7 @@ static void HXhmap_free(struct HXhmap *hmap) } static void HXrbtree_free_dive(const struct HXrbtree *btree, - struct HXrbtree_node *node) + struct HXrbnode *node) { /* * Recursively dives into the tree and destroys elements. Note that you @@ -80,10 +82,10 @@ static void HXrbtree_free_dive(const struct HXrbtree *btree, * deletion with HXrbtree_del(). Since this functions is meant to free * it all, it does not need to care about rebalancing. */ - if (node->sub[RBT_LEFT] != NULL) - HXrbtree_free_dive(btree, node->sub[RBT_LEFT]); - if (node->sub[RBT_RIGHT] != NULL) - HXrbtree_free_dive(btree, node->sub[RBT_RIGHT]); + if (node->N_LEFT != NULL) + HXrbtree_free_dive(btree, node->N_LEFT); + if (node->N_RIGHT != NULL) + HXrbtree_free_dive(btree, node->N_RIGHT); if (btree->super.ops.k_free != NULL) btree->super.ops.k_free(node->key); if (btree->super.ops.d_free != NULL) @@ -105,7 +107,7 @@ EXPORT_SYMBOL void HXmap_free(struct HXmap *xmap) switch (map->type) { case HXMAPT_HASH: - return HXhmap_free(vmap); + return HXumap_free(vmap); case HXMAPT_RBTREE: return HXrbtree_free(vmap); default: @@ -277,15 +279,15 @@ x_frac(unsigned int n, unsigned int d, unsigned int v) } /** - * HXhmap_move - move elements from one map to another + * HXumap_move - move elements from one map to another * @bk_array: target bucket array * @bk_number: number of buckets * @hmap: old hash table */ -static void HXhmap_move(struct HXlist_head *bk_array, unsigned int bk_number, - struct HXhmap *hmap) +static void HXumap_move(struct HXlist_head *bk_array, unsigned int bk_number, + struct HXumap *hmap) { - struct HXhmap_node *drop, *dnext; + struct HXumap_node *drop, *dnext; unsigned int bk_idx, i; #ifdef NONPRIME_HASH @@ -307,11 +309,11 @@ static void HXhmap_move(struct HXlist_head *bk_array, unsigned int bk_number, } /** - * HXhmap_layout - resize and rehash table + * HXumap_layout - resize and rehash table * @hmap: hash map * @prime_idx: requested new table size (prime power thereof) */ -static int HXhmap_layout(struct HXhmap *hmap, unsigned int power) +static int HXumap_layout(struct HXumap *hmap, unsigned int power) { const unsigned int bk_number = HXhash_primes[power]; struct HXlist_head *bk_array, *old_array = NULL; @@ -323,7 +325,7 @@ static int HXhmap_layout(struct HXhmap *hmap, unsigned int power) for (i = 0; i < bk_number; ++i) HXlist_init(&bk_array[i]); if (hmap->bk_array != NULL) { - HXhmap_move(bk_array, bk_number, hmap); + HXumap_move(bk_array, bk_number, hmap); old_array = hmap->bk_array; /* * It is ok to increment the TID this late. @map->bk_array is @@ -344,7 +346,7 @@ static struct HXmap *HXhashmap_init4(unsigned int flags, const struct HXmap_ops *ops, size_t key_size, size_t data_size) { struct HXmap_private *super; - struct HXhmap *hmap; + struct HXumap *hmap; int saved_errno; if ((hmap = calloc(1, sizeof(*hmap))) == NULL) @@ -358,7 +360,7 @@ static struct HXmap *HXhashmap_init4(unsigned int flags, super->data_size = data_size; HXmap_ops_setup(super, ops); hmap->tid = 1; - errno = HXhmap_layout(hmap, 0); + errno = HXumap_layout(hmap, 0); if (hmap->bk_array == NULL) goto out; @@ -367,7 +369,7 @@ static struct HXmap *HXhashmap_init4(unsigned int flags, out: saved_errno = errno; - HXhmap_free(hmap); + HXumap_free(hmap); errno = saved_errno; return NULL; } @@ -379,7 +381,7 @@ static struct HXmap *HXrbtree_init4(unsigned int flags, struct HXrbtree *btree; BUILD_BUG_ON(offsetof(struct HXrbtree, root) + - offsetof(struct HXrbtree_node, sub[0]) != + offsetof(struct HXrbnode, sub[0]) != offsetof(struct HXrbtree, root)); if ((btree = calloc(1, sizeof(*btree))) == NULL) @@ -447,10 +449,10 @@ EXPORT_SYMBOL struct HXmap *HXmap_init(enum HXmap_type type, return HXmap_init5(type, flags, NULL, 0, 0); } -static struct HXhmap_node *HXhmap_find(const struct HXhmap *hmap, +static struct HXumap_node *HXumap_find(const struct HXumap *hmap, const void *key) { - struct HXhmap_node *drop; + struct HXumap_node *drop; unsigned int bk_idx; #ifdef NONPRIME_HASH @@ -470,7 +472,7 @@ static struct HXhmap_node *HXhmap_find(const struct HXhmap *hmap, static const struct HXmap_node *HXrbtree_find(const struct HXrbtree *btree, const void *key) { - struct HXrbtree_node *node = btree->root; + struct HXrbnode *node = btree->root; int res; while (node != NULL) { @@ -491,7 +493,7 @@ HXmap_find(const struct HXmap *xmap, const void *key) switch (map->type) { case HXMAPT_HASH: { - const struct HXhmap_node *node = HXhmap_find(vmap, key); + const struct HXumap_node *node = HXumap_find(vmap, key); if (node == NULL) return NULL; return static_cast(const void *, &node->key); @@ -517,9 +519,9 @@ EXPORT_SYMBOL void *HXmap_get(const struct HXmap *map, const void *key) } /** - * HXhmap_replace - replace value in a drop + * HXumap_replace - replace value in a drop */ -static int HXhmap_replace(const struct HXhmap *hmap, struct HXhmap_node *drop, +static int HXumap_replace(const struct HXumap *hmap, struct HXumap_node *drop, const void *value) { void *old_value, *new_value; @@ -537,21 +539,21 @@ static int HXhmap_replace(const struct HXhmap *hmap, struct HXhmap_node *drop, return 1; } -static int HXhmap_add(struct HXhmap *hmap, const void *key, const void *value) +static int HXumap_add(struct HXumap *hmap, const void *key, const void *value) { - struct HXhmap_node *drop; + struct HXumap_node *drop; unsigned int bk_idx; int ret, saved_errno; - if ((drop = HXhmap_find(hmap, key)) != NULL) - return HXhmap_replace(hmap, drop, value); + if ((drop = HXumap_find(hmap, key)) != NULL) + return HXumap_replace(hmap, drop, value); if (hmap->super.items >= hmap->max_load && hmap->power < ARRAY_SIZE(HXhash_primes) - 1) { - if ((ret = HXhmap_layout(hmap, hmap->power + 1)) <= 0) + if ((ret = HXumap_layout(hmap, hmap->power + 1)) <= 0) return ret; } else if (hmap->super.items < hmap->min_load && hmap->power > 0) { - if ((ret = HXhmap_layout(hmap, hmap->power - 1)) <= 0) + if ((ret = HXumap_layout(hmap, hmap->power - 1)) <= 0) return ret; } @@ -592,10 +594,10 @@ static int HXhmap_add(struct HXhmap *hmap, const void *key, const void *value) * @depth: current index in @path and @dir * @tid: pointer to transaction ID which may need updating */ -static void HXrbtree_amov(struct HXrbtree_node **path, +static void HXrbtree_amov(struct HXrbnode **path, const unsigned char *dir, unsigned int depth, unsigned int *tid) { - struct HXrbtree_node *uncle, *parent, *grandp, *newnode; + struct HXrbnode *uncle, *parent, *grandp, *newnode; /* * The newly inserted node (or the last rebalanced node) at @@ -657,7 +659,7 @@ static void HXrbtree_amov(struct HXrbtree_node **path, } static int HXrbtree_replace(const struct HXrbtree *btree, - struct HXrbtree_node *node, const void *value) + struct HXrbnode *node, const void *value) { void *old_value, *new_value; @@ -677,18 +679,18 @@ static int HXrbtree_replace(const struct HXrbtree *btree, static int HXrbtree_add(struct HXrbtree *btree, const void *key, const void *value) { - struct HXrbtree_node *node, *path[RBT_MAXDEP]; + struct HXrbnode *node, *path[RBT_MAXDEP]; unsigned char dir[RBT_MAXDEP]; unsigned int depth = 0; int saved_errno; /* - * Since our struct HXrbtree_node runs without a ->parent pointer, + * Since our struct HXrbnode runs without a ->parent pointer, * the path "upwards" from @node needs to be recorded somehow, * here with @path. Another array, @dir is used to speedup direction * decisions. (WP's "n->parent == grandparent(n)->left" is just slow.) */ - path[depth] = reinterpret_cast(struct HXrbtree_node *, &btree->root); + path[depth] = reinterpret_cast(struct HXrbnode *, &btree->root); dir[depth++] = 0; node = btree->root; @@ -708,7 +710,7 @@ static int HXrbtree_add(struct HXrbtree *btree, node = node->sub[res]; } - if ((node = malloc(sizeof(struct HXrbtree_node))) == NULL) + if ((node = malloc(sizeof(struct HXrbnode))) == NULL) return -errno; /* New node, push data into it */ @@ -724,7 +726,7 @@ static int HXrbtree_add(struct HXrbtree *btree, * (each simple path has the same number of black nodes), it is colored * red so that below we only need to check for rule 1 violations. */ - node->sub[RBT_LEFT] = node->sub[RBT_RIGHT] = NULL; + node->N_LEFT = node->N_RIGHT = NULL; node->color = RBT_RED; path[depth-1]->sub[dir[depth-1]] = node; ++btree->super.items; @@ -765,7 +767,7 @@ EXPORT_SYMBOL int HXmap_add(struct HXmap *xmap, switch (map->type) { case HXMAPT_HASH: - return HXhmap_add(vmap, key, value); + return HXumap_add(vmap, key, value); case HXMAPT_RBTREE: return HXrbtree_add(vmap, key, value); default: @@ -773,12 +775,12 @@ EXPORT_SYMBOL int HXmap_add(struct HXmap *xmap, } } -static void *HXhmap_del(struct HXhmap *hmap, const void *key) +static void *HXumap_del(struct HXumap *hmap, const void *key) { - struct HXhmap_node *drop; + struct HXumap_node *drop; void *value; - if ((drop = HXhmap_find(hmap, key)) == NULL) { + if ((drop = HXumap_find(hmap, key)) == NULL) { errno = ENOENT; return NULL; } @@ -791,7 +793,7 @@ static void *HXhmap_del(struct HXhmap *hmap, const void *key) * Ignore return value. If it failed, it will continue to use * the current bk_array. */ - HXhmap_layout(hmap, hmap->power - 1); + HXumap_layout(hmap, hmap->power - 1); value = drop->data; if (hmap->super.ops.k_free != NULL) @@ -803,20 +805,20 @@ static void *HXhmap_del(struct HXhmap *hmap, const void *key) return value; } -static unsigned int HXrbtree_del_mm(struct HXrbtree_node **path, +static unsigned int HXrbtree_del_mm(struct HXrbnode **path, unsigned char *dir, unsigned int depth) { /* Both subtrees exist */ - struct HXrbtree_node *io_node, *io_parent, *orig_node = path[depth]; + struct HXrbnode *io_node, *io_parent, *orig_node = path[depth]; unsigned char color; unsigned int spos; - io_node = orig_node->sub[RBT_RIGHT]; + io_node = orig_node->N_RIGHT; dir[depth] = RBT_RIGHT; - if (io_node->sub[RBT_LEFT] == NULL) { + if (io_node->N_LEFT == NULL) { /* Right subtree node is direct inorder */ - io_node->sub[RBT_LEFT] = orig_node->sub[RBT_LEFT]; + io_node->N_LEFT = orig_node->N_LEFT; color = io_node->color; io_node->color = orig_node->color; orig_node->color = color; @@ -836,14 +838,14 @@ static unsigned int HXrbtree_del_mm(struct HXrbtree_node **path, io_parent = io_node; path[depth] = io_parent; dir[depth++] = RBT_LEFT; - io_node = io_parent->sub[RBT_LEFT]; - } while (io_node->sub[RBT_LEFT] != NULL); + io_node = io_parent->N_LEFT; + } while (io_node->N_LEFT != NULL); /* move node up */ path[spos-1]->sub[dir[spos-1]] = path[spos] = io_node; - io_parent->sub[RBT_LEFT] = io_node->sub[RBT_RIGHT]; - io_node->sub[RBT_LEFT] = orig_node->sub[RBT_LEFT]; - io_node->sub[RBT_RIGHT] = orig_node->sub[RBT_RIGHT]; + io_parent->N_LEFT = io_node->N_RIGHT; + io_node->N_LEFT = orig_node->N_LEFT; + io_node->N_RIGHT = orig_node->N_RIGHT; color = io_node->color; io_node->color = orig_node->color; @@ -858,10 +860,10 @@ static unsigned int HXrbtree_del_mm(struct HXrbtree_node **path, return depth; } -static void HXrbtree_dmov(struct HXrbtree_node **path, unsigned char *dir, +static void HXrbtree_dmov(struct HXrbnode **path, unsigned char *dir, unsigned int depth) { - struct HXrbtree_node *w, *x; + struct HXrbnode *w, *x; while (true) { unsigned char LR = dir[depth - 1]; @@ -906,7 +908,7 @@ static void HXrbtree_dmov(struct HXrbtree_node **path, unsigned char *dir, if (w->sub[!LR] == NULL || w->sub[!LR]->color == RBT_BLACK) { /* Case 5 */ - struct HXrbtree_node *y = w->sub[LR]; + struct HXrbnode *y = w->sub[LR]; y->color = RBT_BLACK; w->color = RBT_RED; w->sub[LR] = y->sub[!LR]; @@ -927,7 +929,7 @@ static void HXrbtree_dmov(struct HXrbtree_node **path, unsigned char *dir, static void *HXrbtree_del(struct HXrbtree *btree, const void *key) { - struct HXrbtree_node *path[RBT_MAXDEP], *node; + struct HXrbnode *path[RBT_MAXDEP], *node; unsigned char dir[RBT_MAXDEP]; unsigned int depth = 0; void *itemptr; @@ -935,7 +937,7 @@ static void *HXrbtree_del(struct HXrbtree *btree, const void *key) if (btree->root == NULL) return NULL; - path[depth] = reinterpret_cast(struct HXrbtree_node *, &btree->root); + path[depth] = reinterpret_cast(struct HXrbnode *, &btree->root); dir[depth++] = 0; node = btree->root; @@ -966,12 +968,12 @@ static void *HXrbtree_del(struct HXrbtree *btree, const void *key) ++btree->tid; path[depth] = node; - if (node->sub[RBT_RIGHT] == NULL) + if (node->N_RIGHT == NULL) /* Simple case: No right subtree, replace by left subtree. */ - path[depth-1]->sub[dir[depth-1]] = node->sub[RBT_LEFT]; - else if (node->sub[RBT_LEFT] == NULL) + path[depth-1]->sub[dir[depth-1]] = node->N_LEFT; + else if (node->N_LEFT == NULL) /* Simple case: No left subtree, replace by right subtree. */ - path[depth-1]->sub[dir[depth-1]] = node->sub[RBT_RIGHT]; + path[depth-1]->sub[dir[depth-1]] = node->N_RIGHT; else /* * Find minimum/maximum element in right/left subtree and @@ -1006,7 +1008,7 @@ EXPORT_SYMBOL void *HXmap_del(struct HXmap *xmap, const void *key) switch (map->type) { case HXMAPT_HASH: - return HXhmap_del(vmap, key); + return HXumap_del(vmap, key); case HXMAPT_RBTREE: return HXrbtree_del(vmap, key); default: @@ -1015,10 +1017,10 @@ EXPORT_SYMBOL void *HXmap_del(struct HXmap *xmap, const void *key) } } -static void HXhmap_keysvalues(const struct HXhmap *hmap, +static void HXumap_keysvalues(const struct HXumap *hmap, struct HXmap_node *array) { - const struct HXhmap_node *node; + const struct HXumap_node *node; unsigned int i; for (i = 0; i < HXhash_primes[hmap->power]; ++i) @@ -1029,7 +1031,7 @@ static void HXhmap_keysvalues(const struct HXhmap *hmap, } } -static struct HXmap_node *HXrbtree_keysvalues(const struct HXrbtree_node *node, +static struct HXmap_node *HXrbtree_keysvalues(const struct HXrbnode *node, struct HXmap_node *array) { if (node->sub[0] != NULL) @@ -1062,7 +1064,7 @@ EXPORT_SYMBOL struct HXmap_node *HXmap_keysvalues(const struct HXmap *xmap) switch (map->type) { case HXMAPT_HASH: - HXhmap_keysvalues(vmap, array); + HXumap_keysvalues(vmap, array); break; case HXMAPT_RBTREE: HXrbtree_keysvalues( @@ -1073,9 +1075,9 @@ EXPORT_SYMBOL struct HXmap_node *HXmap_keysvalues(const struct HXmap *xmap) return array; } -static void *HXhmap_travinit(const struct HXhmap *hmap, unsigned int flags) +static void *HXumap_travinit(const struct HXumap *hmap, unsigned int flags) { - struct HXhmap_trav *trav; + struct HXumap_trav *trav; if ((trav = malloc(sizeof(*trav))) == NULL) return NULL; @@ -1109,7 +1111,7 @@ EXPORT_SYMBOL struct HXmap_trav *HXmap_travinit(const struct HXmap *xmap, switch (map->type) { case HXMAPT_HASH: - return HXhmap_travinit(vmap, flags); + return HXumap_travinit(vmap, flags); case HXMAPT_RBTREE: return HXrbtrav_init(vmap, flags); default: @@ -1118,10 +1120,10 @@ EXPORT_SYMBOL struct HXmap_trav *HXmap_travinit(const struct HXmap *xmap, } } -static const struct HXmap_node *HXhmap_traverse(struct HXhmap_trav *trav) +static const struct HXmap_node *HXumap_traverse(struct HXumap_trav *trav) { - const struct HXhmap *hmap = trav->hmap; - const struct HXhmap_node *drop; + const struct HXumap *hmap = trav->hmap; + const struct HXumap_node *drop; if (trav->head == NULL) { trav->head = hmap->bk_array[trav->bk_current].next; @@ -1145,12 +1147,12 @@ static const struct HXmap_node *HXhmap_traverse(struct HXhmap_trav *trav) trav->head = hmap->bk_array[trav->bk_current].next; } - drop = HXlist_entry(trav->head, struct HXhmap_node, anchor); + drop = HXlist_entry(trav->head, struct HXumap_node, anchor); return static_cast(const void *, &drop->key); } static void HXrbtrav_checkpoint(struct HXrbtrav *trav, - const struct HXrbtree_node *node) + const struct HXrbnode *node) { const struct HXrbtree *tree = trav->tree; @@ -1166,19 +1168,19 @@ static void HXrbtrav_checkpoint(struct HXrbtrav *trav, } } -static struct HXrbtree_node *HXrbtrav_next(struct HXrbtrav *trav) +static struct HXrbnode *HXrbtrav_next(struct HXrbtrav *trav) { - if (trav->current->sub[RBT_RIGHT] != NULL) { + if (trav->current->N_RIGHT != NULL) { /* Got a right child */ - struct HXrbtree_node *node; + struct HXrbnode *node; trav->dir[trav->depth++] = RBT_RIGHT; - node = trav->current->sub[RBT_RIGHT]; + node = trav->current->N_RIGHT; /* Which might have left childs (our inorder successors!) */ while (node != NULL) { trav->path[trav->depth] = node; - node = node->sub[RBT_LEFT]; + node = node->N_LEFT; trav->dir[trav->depth++] = RBT_LEFT; } trav->current = trav->path[--trav->depth]; @@ -1210,7 +1212,7 @@ static struct HXrbtree_node *HXrbtrav_next(struct HXrbtrav *trav) return trav->current; } -static struct HXrbtree_node *HXrbtrav_rewalk(struct HXrbtrav *trav) +static struct HXrbnode *HXrbtrav_rewalk(struct HXrbtrav *trav) { /* * When the binary tree has been distorted (or the traverser is @@ -1219,7 +1221,7 @@ static struct HXrbtree_node *HXrbtrav_rewalk(struct HXrbtrav *trav) * find the node we were last at. */ const struct HXrbtree *btree = trav->tree; - struct HXrbtree_node *node = btree->root; + struct HXrbnode *node = btree->root; bool go_next = false; trav->depth = 0; @@ -1228,12 +1230,12 @@ static struct HXrbtree_node *HXrbtrav_rewalk(struct HXrbtrav *trav) /* Walk down the tree to the smallest element */ while (node != NULL) { trav->path[trav->depth] = node; - node = node->sub[RBT_LEFT]; + node = node->N_LEFT; trav->dir[trav->depth++] = RBT_LEFT; } } else { /* Search for the specific node to rebegin traversal at. */ - const struct HXrbtree_node *newpath[RBT_MAXDEP]; + const struct HXrbnode *newpath[RBT_MAXDEP]; unsigned char newdir[RBT_MAXDEP]; int newdepth = 0, res; bool found = false; @@ -1312,7 +1314,7 @@ static struct HXrbtree_node *HXrbtrav_rewalk(struct HXrbtrav *trav) static const struct HXmap_node *HXrbtree_traverse(struct HXrbtrav *trav) { - const struct HXrbtree_node *node; + const struct HXrbnode *node; if (trav->tid != trav->tree->tid || trav->current == NULL) /* @@ -1335,7 +1337,7 @@ EXPORT_SYMBOL const struct HXmap_node *HXmap_traverse(struct HXmap_trav *trav) switch (trav->type) { case HXMAPT_HASH: - return HXhmap_traverse(xtrav); + return HXumap_traverse(xtrav); case HXMAPT_RBTREE: return HXrbtree_traverse(xtrav); default: @@ -1369,9 +1371,9 @@ EXPORT_SYMBOL void HXmap_travfree(struct HXmap_trav *trav) } } -static void HXhmap_qfe(const struct HXhmap *hmap, qfe_fn_t fn, void *arg) +static void HXumap_qfe(const struct HXumap *hmap, qfe_fn_t fn, void *arg) { - const struct HXhmap_node *hnode; + const struct HXumap_node *hnode; unsigned int i; for (i = 0; i < HXhash_primes[hmap->power]; ++i) @@ -1380,15 +1382,15 @@ static void HXhmap_qfe(const struct HXhmap *hmap, qfe_fn_t fn, void *arg) return; } -static void HXrbtree_qfe(const struct HXrbtree_node *node, +static void HXrbtree_qfe(const struct HXrbnode *node, qfe_fn_t fn, void *arg) { - if (node->sub[RBT_LEFT] != NULL) - HXrbtree_qfe(node->sub[RBT_LEFT], fn, arg); + if (node->N_LEFT != NULL) + HXrbtree_qfe(node->N_LEFT, fn, arg); if (!(*fn)(static_cast(const void *, &node->key), arg)) return; - if (node->sub[RBT_RIGHT] != NULL) - HXrbtree_qfe(node->sub[RBT_RIGHT], fn, arg); + if (node->N_RIGHT != NULL) + HXrbtree_qfe(node->N_RIGHT, fn, arg); } EXPORT_SYMBOL void HXmap_qfe(const struct HXmap *xmap, qfe_fn_t fn, void *arg) @@ -1398,7 +1400,7 @@ EXPORT_SYMBOL void HXmap_qfe(const struct HXmap *xmap, qfe_fn_t fn, void *arg) switch (map->type) { case HXMAPT_HASH: - HXhmap_qfe(vmap, fn, arg); + HXumap_qfe(vmap, fn, arg); errno = 0; break; case HXMAPT_RBTREE: { |