Index: kernel/generic/src/adt/avl.c =================================================================== --- kernel/generic/src/adt/avl.c (revision 1b20da07baaa3e3c424f62c927274e676e4295cd) +++ kernel/generic/src/adt/avl.c (revision 0aa06cbe8a6965cc7f1ebfa7236bcd8d5316da16) @@ -66,5 +66,5 @@ { avltree_node_t *p; - + /* * Iteratively descend to the leaf that can contain the searched key. @@ -92,5 +92,5 @@ { avltree_node_t *p = t->root; - + /* * Check whether the tree is empty. @@ -98,5 +98,5 @@ if (!p) return NULL; - + /* * Iteratively descend to the leftmost leaf in the tree. @@ -104,5 +104,5 @@ while (p->lft != NULL) p = p->lft; - + return p; } @@ -151,5 +151,5 @@ #define REBALANCE_INSERT_LR() REBALANCE_INSERT_XY(lft, rgt, 1) #define REBALANCE_INSERT_RL() REBALANCE_INSERT_XY(rgt, lft, -1) - + /** Insert new node into AVL tree. * @@ -172,5 +172,5 @@ */ key = newnode->key + t->base; - + /* * Iteratively descend to the leaf that can contain the new node. @@ -244,5 +244,5 @@ } } - + /* * To balance the tree, we must check and balance top node. @@ -260,5 +260,5 @@ */ assert(par->balance == 1); - + REBALANCE_INSERT_LR(); } @@ -275,5 +275,5 @@ */ assert(par->balance == -1); - + REBALANCE_INSERT_RL(); } @@ -375,5 +375,5 @@ assert(t); assert(node); - + if (node->lft == NULL) { if (node->rgt) { @@ -451,5 +451,5 @@ cur->par = node->par; } - + /* * Repair the parent node's pointer which pointed previously to the @@ -457,5 +457,5 @@ */ (void) repair(t, node, node, cur, NULL, false); - + /* * Repair cycle which repairs balances of nodes on the way from from the @@ -484,5 +484,5 @@ * RL rotation. */ - + cur = par->lft; par->lft = cur->rgt; @@ -490,5 +490,5 @@ gpa->rgt = cur->lft; cur->lft = gpa; - + /* * Repair balances and paternity of @@ -497,5 +497,5 @@ */ REBALANCE_DELETE_RL(); - + /* * Repair paternity. @@ -513,10 +513,10 @@ * RR rotation. */ - + gpa->rgt = par->lft; if (par->lft) par->lft->par = gpa; par->lft = gpa; - + /* * Repair paternity. @@ -524,5 +524,5 @@ par->par = gpa->par; gpa->par = par; - + if (par->balance == 0) { /* @@ -575,10 +575,10 @@ */ par = gpa->lft; - + if (par->balance == 1) { /* * LR rotation. */ - + cur = par->rgt; par->rgt = cur->lft; @@ -586,5 +586,5 @@ gpa->lft = cur->rgt; cur->rgt = gpa; - + /* * Repair balances and paternity of @@ -619,5 +619,5 @@ par->par = gpa->par; gpa->par = par; - + if (par->balance == 0) { /* @@ -630,5 +630,5 @@ par->balance = 1; gpa->balance = -1; - + (void) repair(t, par, gpa, par, NULL, false); @@ -637,5 +637,5 @@ par->balance = 0; gpa->balance = 0; - + if (!repair(t, par, gpa, par, &dir, false)) @@ -667,5 +667,5 @@ { avltree_node_t *node; - + /* * Start searching for the smallest key in the tree starting in the root @@ -673,12 +673,12 @@ * must have the smallest key). */ - + node = t->root; if (!node) return false; - + while (node->lft != NULL) node = node->lft; - + avltree_delete(t, node); Index: kernel/generic/src/adt/bitmap.c =================================================================== --- kernel/generic/src/adt/bitmap.c (revision 1b20da07baaa3e3c424f62c927274e676e4295cd) +++ kernel/generic/src/adt/bitmap.c (revision 0aa06cbe8a6965cc7f1ebfa7236bcd8d5316da16) @@ -62,5 +62,5 @@ size_t byte = element / BITMAP_ELEMENT; uint8_t mask = 1 << (element & BITMAP_REMAINER); - + return !!((bitmap->bits)[byte] & mask); } @@ -78,8 +78,8 @@ { size_t size = elements / BITMAP_ELEMENT; - + if ((elements % BITMAP_ELEMENT) != 0) size++; - + return size; } @@ -113,20 +113,20 @@ { assert(start + count <= bitmap->elements); - + if (count == 0) return; - + size_t start_byte = start / BITMAP_ELEMENT; size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT); - + /* Leading unaligned bits */ size_t lub = min(aligned_start - start, count); - + /* Aligned middle bits */ size_t amb = (count > lub) ? (count - lub) : 0; - + /* Trailing aligned bits */ size_t tab = amb % BITMAP_ELEMENT; - + if (start + count < aligned_start) { /* Set bits in the middle of byte. */ @@ -135,5 +135,5 @@ return; } - + if (lub) { /* Make sure to set any leading unaligned bits. */ @@ -141,7 +141,7 @@ ~((1 << (BITMAP_ELEMENT - lub)) - 1); } - + size_t i; - + for (i = 0; i < amb / BITMAP_ELEMENT; i++) { /* The middle bits can be set byte by byte. */ @@ -149,5 +149,5 @@ ALL_ONES; } - + if (tab) { /* Make sure to set any trailing aligned bits. */ @@ -167,20 +167,20 @@ { assert(start + count <= bitmap->elements); - + if (count == 0) return; - + size_t start_byte = start / BITMAP_ELEMENT; size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT); - + /* Leading unaligned bits */ size_t lub = min(aligned_start - start, count); - + /* Aligned middle bits */ size_t amb = (count > lub) ? (count - lub) : 0; - + /* Trailing aligned bits */ size_t tab = amb % BITMAP_ELEMENT; - + if (start + count < aligned_start) { /* Set bits in the middle of byte */ @@ -189,5 +189,5 @@ return; } - + if (lub) { /* Make sure to clear any leading unaligned bits. */ @@ -195,7 +195,7 @@ (1 << (BITMAP_ELEMENT - lub)) - 1; } - + size_t i; - + for (i = 0; i < amb / BITMAP_ELEMENT; i++) { /* The middle bits can be cleared byte by byte. */ @@ -203,5 +203,5 @@ ALL_ZEROES; } - + if (tab) { /* Make sure to clear any trailing aligned bits. */ @@ -209,5 +209,5 @@ ~((1 << tab) - 1); } - + bitmap->next_fit = start_byte; } @@ -224,10 +224,10 @@ assert(count <= dst->elements); assert(count <= src->elements); - + size_t i; - + for (i = 0; i < count / BITMAP_ELEMENT; i++) dst->bits[i] = src->bits[i]; - + if (count % BITMAP_ELEMENT) { bitmap_clear_range(dst, i * BITMAP_ELEMENT, @@ -274,8 +274,8 @@ if (count == 0) return false; - + size_t size = bitmap_size(bitmap->elements); size_t next_fit = bitmap->next_fit; - + /* * Adjust the next-fit value according to the address @@ -284,30 +284,30 @@ if ((prefered > base) && (prefered < base + bitmap->elements)) { size_t prefered_fit = (prefered - base) / BITMAP_ELEMENT; - + if (prefered_fit > next_fit) next_fit = prefered_fit; } - + for (size_t pos = 0; pos < size; pos++) { size_t byte = (next_fit + pos) % size; - + /* Skip if the current byte has all bits set */ if (bitmap->bits[byte] == ALL_ONES) continue; - + size_t byte_bit = byte * BITMAP_ELEMENT; - + for (size_t bit = 0; bit < BITMAP_ELEMENT; bit++) { size_t i = byte_bit + bit; - + if (i >= bitmap->elements) break; - + if (!constraint_satisfy(i, base, constraint)) continue; - + if (!bitmap_get_fast(bitmap, i)) { size_t continuous = 1; - + for (size_t j = 1; j < count; j++) { if ((i + j < bitmap->elements) && @@ -317,5 +317,5 @@ break; } - + if (continuous == count) { if (index != NULL) { @@ -324,5 +324,5 @@ *index = i; } - + return true; } else @@ -331,5 +331,5 @@ } } - + return false; } Index: kernel/generic/src/adt/btree.c =================================================================== --- kernel/generic/src/adt/btree.c (revision 1b20da07baaa3e3c424f62c927274e676e4295cd) +++ kernel/generic/src/adt/btree.c (revision 0aa06cbe8a6965cc7f1ebfa7236bcd8d5316da16) @@ -83,7 +83,7 @@ { unsigned int i; - + node->keys = 0; - + /* Clean also space for the extra key. */ for (i = 0; i < BTREE_MAX_KEYS + 1; i++) { @@ -92,8 +92,8 @@ node->subtree[i] = NULL; } - + node->subtree[i] = NULL; node->parent = NULL; - + link_initialize(&node->leaf_link); link_initialize(&node->bfs_link); @@ -122,5 +122,5 @@ { size_t i; - + if (root->keys) { for (i = 0; i < root->keys + 1; i++) { @@ -129,5 +129,5 @@ } } - + slab_free(btree_node_cache, root); } @@ -156,9 +156,9 @@ { size_t i; - + for (i = 0; i < node->keys; i++) { if (key < node->key[i]) { size_t j; - + for (j = node->keys; j > i; j--) { node->key[j] = node->key[j - 1]; @@ -166,9 +166,9 @@ node->subtree[j + 1] = node->subtree[j]; } - + break; } } - + node->key[i] = key; node->value[i] = value; @@ -191,10 +191,10 @@ { size_t i; - + for (i = 0; i < node->keys + 1; i++) { if (subtree == node->subtree[i]) return i - (int) (right != false); } - + panic("Node %p does not contain subtree %p.", node, subtree); } @@ -215,5 +215,5 @@ size_t i; size_t j; - + for (i = 0; i < node->keys; i++) { if (key == node->key[i]) { @@ -223,12 +223,12 @@ node->subtree[j - 1] = node->subtree[j]; } - + node->subtree[j - 1] = node->subtree[j]; node->keys--; - + return; } } - + panic("Node %p does not contain key %" PRIu64 ".", node, key); } @@ -248,5 +248,5 @@ { size_t i, j; - + for (i = 0; i < node->keys; i++) { if (key == node->key[i]) { @@ -256,10 +256,10 @@ node->subtree[j] = node->subtree[j + 1]; } - + node->keys--; return; } } - + panic("Node %p does not contain key %" PRIu64 ".", node, key); } @@ -280,9 +280,9 @@ { size_t i; - + for (i = 0; i < node->keys; i++) { if (key < node->key[i]) { size_t j; - + for (j = node->keys; j > i; j--) { node->key[j] = node->key[j - 1]; @@ -290,14 +290,14 @@ node->subtree[j + 1] = node->subtree[j]; } - + node->subtree[j + 1] = node->subtree[j]; break; } } - + node->key[i] = key; node->value[i] = value; node->subtree[i] = lsubtree; - + node->keys++; } @@ -320,8 +320,8 @@ { btree_key_t key = lnode->key[lnode->keys - 1]; - + if (LEAF_NODE(lnode)) { void *value = lnode->value[lnode->keys - 1]; - + node_remove_key_and_rsubtree(lnode, key); node_insert_key_and_lsubtree(rnode, key, value, NULL); @@ -329,9 +329,9 @@ } else { btree_node_t *rsubtree = lnode->subtree[lnode->keys]; - + node_remove_key_and_rsubtree(lnode, key); node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree); lnode->parent->key[idx] = key; - + /* Fix parent link of the reconnected right subtree. */ rsubtree->parent = rnode; @@ -356,8 +356,8 @@ { btree_key_t key = rnode->key[0]; - + if (LEAF_NODE(rnode)) { void *value = rnode->value[0]; - + node_remove_key_and_lsubtree(rnode, key); node_insert_key_and_rsubtree(lnode, key, value, NULL); @@ -365,9 +365,9 @@ } else { btree_node_t *lsubtree = rnode->subtree[0]; - + node_remove_key_and_lsubtree(rnode, key); node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree); rnode->parent->key[idx] = key; - + /* Fix parent link of the reconnected left subtree. */ lsubtree->parent = lnode; @@ -395,5 +395,5 @@ size_t idx; btree_node_t *lnode; - + /* * If this is root node, the rotation can not be done. @@ -401,5 +401,5 @@ if (ROOT_NODE(node)) return false; - + idx = find_key_by_subtree(node->parent, node, true); if ((int) idx == -1) { @@ -410,5 +410,5 @@ return false; } - + lnode = node->parent->subtree[idx]; if (lnode->keys < BTREE_MAX_KEYS) { @@ -420,5 +420,5 @@ return true; } - + return false; } @@ -444,5 +444,5 @@ size_t idx; btree_node_t *rnode; - + /* * If this is root node, the rotation can not be done. @@ -450,5 +450,5 @@ if (ROOT_NODE(node)) return false; - + idx = find_key_by_subtree(node->parent, node, false); if (idx == node->parent->keys) { @@ -459,5 +459,5 @@ return false; } - + rnode = node->parent->subtree[idx + 1]; if (rnode->keys < BTREE_MAX_KEYS) { @@ -469,5 +469,5 @@ return true; } - + return false; } @@ -499,18 +499,18 @@ size_t i; size_t j; - + assert(median); assert(node->keys == BTREE_MAX_KEYS); - + /* * Use the extra space to store the extra node. */ node_insert_key_and_rsubtree(node, key, value, rsubtree); - + /* * Compute median of keys. */ *median = MEDIAN_HIGH(node); - + /* * Allocate and initialize new right sibling. @@ -520,5 +520,5 @@ rnode->parent = node->parent; rnode->depth = node->depth; - + /* * Copy big keys, values and subtree pointers to the new right sibling. @@ -530,5 +530,5 @@ rnode->value[j] = node->value[i]; rnode->subtree[j] = node->subtree[i]; - + /* * Fix parent links in subtrees. @@ -537,12 +537,12 @@ rnode->subtree[j]->parent = rnode; } - + rnode->subtree[j] = node->subtree[i]; if (rnode->subtree[j]) rnode->subtree[j]->parent = rnode; - + rnode->keys = j; /* Set number of keys of the new node. */ node->keys /= 2; /* Shrink the old node. */ - + return rnode; } @@ -578,5 +578,5 @@ btree_node_t *rnode; btree_key_t median; - + /* * Node is full and both siblings (if both exist) are full too. @@ -584,11 +584,11 @@ * bigger keys (i.e. the new node) into its parent. */ - + rnode = node_split(node, key, value, rsubtree, &median); - + if (LEAF_NODE(node)) { list_insert_after(&rnode->leaf_link, &node->leaf_link); } - + if (ROOT_NODE(node)) { /* @@ -599,5 +599,5 @@ rnode->parent = t->root; node_initialize(t->root); - + /* * Left-hand side subtree will be the old root (i.e. node). @@ -605,5 +605,5 @@ */ t->root->subtree[0] = node; - + t->root->depth = node->depth + 1; } @@ -624,7 +624,7 @@ { btree_node_t *lnode; - + assert(value); - + lnode = leaf_node; if (!lnode) { @@ -632,5 +632,5 @@ panic("B-tree %p already contains key %" PRIu64 ".", t, key); } - + _btree_insert(t, key, value, NULL, lnode); } @@ -648,5 +648,5 @@ size_t idx; btree_node_t *lnode; - + /* * If this is root node, the rotation can not be done. @@ -654,5 +654,5 @@ if (ROOT_NODE(rnode)) return false; - + idx = find_key_by_subtree(rnode->parent, rnode, true); if ((int) idx == -1) { @@ -663,5 +663,5 @@ return false; } - + lnode = rnode->parent->subtree[idx]; if (lnode->keys > FILL_FACTOR) { @@ -669,5 +669,5 @@ return true; } - + return false; } @@ -685,5 +685,5 @@ size_t idx; btree_node_t *rnode; - + /* * If this is root node, the rotation can not be done. @@ -691,5 +691,5 @@ if (ROOT_NODE(lnode)) return false; - + idx = find_key_by_subtree(lnode->parent, lnode, false); if (idx == lnode->parent->keys) { @@ -700,5 +700,5 @@ return false; } - + rnode = lnode->parent->subtree[idx + 1]; if (rnode->keys > FILL_FACTOR) { @@ -706,5 +706,5 @@ return true; } - + return false; } @@ -724,7 +724,7 @@ btree_node_t *rnode; size_t i; - + assert(!ROOT_NODE(node)); - + idx = find_key_by_subtree(node->parent, node, false); if (idx == node->parent->keys) { @@ -737,14 +737,14 @@ } else rnode = node->parent->subtree[idx + 1]; - + /* Index nodes need to insert parent node key in between left and right node. */ if (INDEX_NODE(node)) node->key[node->keys++] = node->parent->key[idx]; - + /* Copy the key-value-subtree triplets from the right node. */ for (i = 0; i < rnode->keys; i++) { node->key[node->keys + i] = rnode->key[i]; node->value[node->keys + i] = rnode->value[i]; - + if (INDEX_NODE(node)) { node->subtree[node->keys + i] = rnode->subtree[i]; @@ -752,10 +752,10 @@ } } - + if (INDEX_NODE(node)) { node->subtree[node->keys + i] = rnode->subtree[i]; rnode->subtree[i]->parent = node; } - + node->keys += rnode->keys; return rnode; @@ -789,8 +789,8 @@ node_remove_key_and_rsubtree(node, key); } - + return; } - + if (node->keys <= FILL_FACTOR) { /* @@ -801,8 +801,8 @@ try_rotation_from_right(node); } - + if (node->keys > FILL_FACTOR) { size_t i; - + /* * The key can be immediately removed. @@ -813,5 +813,5 @@ */ node_remove_key_and_rsubtree(node, key); - + for (i = 0; i < node->parent->keys; i++) { if (node->parent->key[i] == key) @@ -822,5 +822,5 @@ btree_node_t *rnode; btree_node_t *parent; - + /* * The node is below the fill factor as well as its left and right sibling. @@ -832,8 +832,8 @@ node_remove_key_and_rsubtree(node, key); rnode = node_combine(node); - + if (LEAF_NODE(rnode)) list_remove(&rnode->leaf_link); - + idx = find_key_by_subtree(parent, rnode, true); assert((int) idx != -1); @@ -855,5 +855,5 @@ { btree_node_t *lnode; - + lnode = leaf_node; if (!lnode) { @@ -861,5 +861,5 @@ panic("B-tree %p does not contain key %" PRIu64 ".", t, key); } - + _btree_remove(t, key, lnode); } @@ -877,5 +877,5 @@ { btree_node_t *cur, *next; - + /* * Iteratively descend to the leaf that can contain the searched key. @@ -887,5 +887,5 @@ */ *leaf_node = cur; - + if (cur->keys == 0) return NULL; @@ -901,5 +901,5 @@ void *val; size_t i; - + /* * Now if the key is smaller than cur->key[i] @@ -911,12 +911,12 @@ next = cur->subtree[i]; val = cur->value[i - 1]; - + if (LEAF_NODE(cur)) return key == cur->key[i - 1] ? val : NULL; - + goto descend; } } - + /* * Last possibility is that the key is @@ -925,5 +925,5 @@ next = cur->subtree[i]; val = cur->value[i - 1]; - + if (LEAF_NODE(cur)) return key == cur->key[i - 1] ? val : NULL; @@ -932,5 +932,5 @@ ; } - + /* * The key was not found in the *leaf_node and @@ -952,5 +952,5 @@ { assert(LEAF_NODE(node)); - + if (node->leaf_link.prev != &t->leaf_list.head) return list_get_instance(node->leaf_link.prev, btree_node_t, leaf_link); @@ -971,5 +971,5 @@ { assert(LEAF_NODE(node)); - + if (node->leaf_link.next != &t->leaf_list.head) return list_get_instance(node->leaf_link.next, btree_node_t, leaf_link); @@ -988,9 +988,9 @@ int depth = t->root->depth; list_t list; - + printf("Printing B-tree:\n"); list_initialize(&list); list_append(&t->root->bfs_link, &list); - + /* * Use BFS search to print out the tree. @@ -1000,19 +1000,19 @@ link_t *hlp; btree_node_t *node; - + hlp = list_first(&list); assert(hlp != NULL); node = list_get_instance(hlp, btree_node_t, bfs_link); list_remove(hlp); - + assert(node); - + if (node->depth != depth) { printf("\n"); depth = node->depth; } - + printf("("); - + for (i = 0; i < node->keys; i++) { printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : ""); @@ -1021,25 +1021,25 @@ } } - + if (node->depth && node->subtree[i]) list_append(&node->subtree[i]->bfs_link, &list); - + printf(")"); } - + printf("\n"); - + printf("Printing list of leaves:\n"); list_foreach(t->leaf_list, leaf_link, btree_node_t, node) { assert(node); - + printf("("); - + for (i = 0; i < node->keys; i++) printf("%" PRIu64 "%s", node->key[i], i < node->keys - 1 ? "," : ""); - + printf(")"); } - + printf("\n"); } Index: kernel/generic/src/adt/cht.c =================================================================== --- kernel/generic/src/adt/cht.c (revision 1b20da07baaa3e3c424f62c927274e676e4295cd) +++ kernel/generic/src/adt/cht.c (revision 0aa06cbe8a6965cc7f1ebfa7236bcd8d5316da16) @@ -531,13 +531,13 @@ if (!op || !op->hash || !op->key_hash || !op->equal || !op->key_equal) return false; - + size_t min_order = size_to_order(min_size, CHT_MIN_ORDER); size_t order = size_to_order(init_size, min_order); - + h->b = alloc_buckets(order, false, can_block); - + if (!h->b) return false; - + h->max_load = (max_load == 0) ? CHT_MAX_LOAD : max_load; h->min_order = min_order; @@ -546,9 +546,9 @@ atomic_set(&h->item_cnt, 0); atomic_set(&h->resize_reqs, 0); - + if (NULL == op->remove_callback) { h->op->remove_callback = dummy_remove_callback; } - + /* * Cached item hashes are stored in item->rcu_link.func. Once the item @@ -556,8 +556,8 @@ */ h->invalid_hash = (uintptr_t)h->op->remove_callback; - + /* Ensure the initialization takes place before we start using the table. */ write_barrier(); - + return true; } @@ -581,18 +581,18 @@ sizeof(cht_buckets_t) + (bucket_cnt - 1) * sizeof(marked_ptr_t); cht_buckets_t *b = malloc(bytes, can_block ? 0 : FRAME_ATOMIC); - + if (!b) return NULL; - + b->order = order; - + marked_ptr_t head_link = set_invalid ? make_link(&sentinel, N_INVALID) : make_link(&sentinel, N_NORMAL); - + for (size_t i = 0; i < bucket_cnt; ++i) { b->head[i] = head_link; } - + return b; } @@ -607,8 +607,8 @@ if (bucket_cnt <= ((size_t)1 << order)) return order; - + ++order; } while (order < CHT_MAX_ORDER); - + return order; } @@ -623,5 +623,5 @@ { cht_destroy_unsafe(h); - + /* You must clear the table of items. Otherwise cht_destroy will leak. */ assert(atomic_get(&h->item_cnt) == 0); @@ -635,8 +635,8 @@ rcu_barrier(); } - + /* Wait for all remove_callback()s to complete. */ rcu_barrier(); - + free(h->b); h->b = NULL; @@ -688,7 +688,7 @@ /* See docs to cht_find() and cht_find_lazy(). */ assert(rcu_read_locked()); - + size_t hash = calc_key_hash(h, key); - + cht_buckets_t *b = rcu_access(h->b); size_t idx = calc_bucket_idx(hash, b->order); @@ -698,9 +698,9 @@ */ marked_ptr_t head = b->head[idx]; - + /* Undergoing a resize - take the slow path. */ if (N_INVALID == get_mark(head)) return find_resizing(h, key, hash, head, idx); - + return search_bucket(h, head, key, hash); } @@ -734,5 +734,5 @@ assert(rcu_read_locked()); assert(item); - + return find_duplicate(h, item, calc_node_hash(h, item), get_next(item->link)); } @@ -758,5 +758,5 @@ prev = cur->link; } while (node_hash(h, cur) < search_hash); - + /* * Only search for an item with an equal key if cur is not the sentinel @@ -768,9 +768,9 @@ return cur; } - + cur = get_next(cur->link); assert(cur); } - + /* * In the unlikely case that we have encountered a node whose cached @@ -782,5 +782,5 @@ goto try_again; } - + return NULL; } @@ -792,9 +792,9 @@ assert(N_INVALID == get_mark(old_head)); assert(h->new_b); - + size_t new_idx = calc_bucket_idx(hash, h->new_b->order); marked_ptr_t new_head = h->new_b->head[new_idx]; marked_ptr_t search_head = new_head; - + /* Growing. */ if (h->b->order < h->new_b->order) { @@ -818,7 +818,7 @@ new_head = h->new_b->head[grow_idx(old_idx)]; } - + /* new_head is now the moved bucket, either valid or invalid. */ - + /* * The old bucket was definitely moved to new_head but the @@ -845,13 +845,13 @@ } } - + return search_bucket(h, search_head, key, hash); } else if (h->b->order > h->new_b->order) { /* Shrinking. */ - + /* Index of the bucket in the old table that was moved. */ size_t move_src_idx = grow_idx(new_idx); marked_ptr_t moved_old_head = h->b->head[move_src_idx]; - + /* * h->b->head[move_src_idx] had already been moved to new_head @@ -883,7 +883,7 @@ search_head = moved_old_head; } - + cht_link_t *ret = search_bucket(h, search_head, key, hash); - + if (ret) return ret; @@ -906,5 +906,5 @@ return search_bucket(h, old_head, key, hash); } - + return NULL; } else { @@ -979,16 +979,16 @@ bool resizing = false; bool inserted = false; - + do { walk_mode_t walk_mode = WM_NORMAL; bool join_finishing; - + resizing = resizing || (N_NORMAL != get_mark(*phead)); - + /* The table is resizing. Get the correct bucket head. */ if (resizing) { upd_resizing_head(h, hash, &phead, &join_finishing, &walk_mode); } - + wnd_t wnd = { .ppred = phead, @@ -996,18 +996,18 @@ .last = NULL }; - + if (!find_wnd_and_gc(h, hash, walk_mode, &wnd, &resizing)) { /* Could not GC a node; or detected an unexpected resize. */ continue; } - + if (dup_item && has_duplicate(h, item, hash, wnd.cur, dup_item)) { rcu_read_unlock(); return false; } - + inserted = insert_at(item, &wnd, walk_mode, &resizing); } while (!inserted); - + rcu_read_unlock(); @@ -1032,13 +1032,13 @@ { marked_ptr_t ret; - + if (walk_mode == WM_NORMAL) { item->link = make_link(wnd->cur, N_NORMAL); /* Initialize the item before adding it to a bucket. */ memory_barrier(); - + /* Link a clean/normal predecessor to the item. */ ret = cas_link(wnd->ppred, wnd->cur, N_NORMAL, item, N_NORMAL); - + if (ret == make_link(wnd->cur, N_NORMAL)) { return true; @@ -1054,8 +1054,8 @@ /* Initialize the item before adding it to a bucket. */ memory_barrier(); - + /* Link the not-deleted predecessor to the item. Move its JF mark. */ ret = cas_link(wnd->ppred, wnd->cur, jf_mark, item, N_NORMAL); - + return ret == make_link(wnd->cur, jf_mark); } else { @@ -1065,5 +1065,5 @@ /* Initialize the item before adding it to a bucket. */ memory_barrier(); - + mark_t pred_mark = get_mark(*wnd->ppred); /* If the predecessor is a join node it may be marked deleted.*/ @@ -1090,5 +1090,5 @@ assert(cur == &sentinel || hash <= node_hash(h, cur) || node_hash(h, cur) == h->invalid_hash); - + /* hash < node_hash(h, cur) */ if (hash != node_hash(h, cur) && h->invalid_hash != node_hash(h, cur)) @@ -1101,5 +1101,5 @@ */ read_barrier(); - + *dup_item = find_duplicate(h, item, hash, cur); return NULL != *dup_item; @@ -1113,5 +1113,5 @@ cht_link_t *cur = start; - + try_again: assert(cur); @@ -1119,11 +1119,11 @@ while (node_hash(h, cur) == hash) { assert(cur != &sentinel); - + bool deleted = (N_DELETED & get_mark(cur->link)); - + /* Skip logically deleted nodes. */ if (!deleted && h->op->equal(item, cur)) return cur; - + cur = get_next(cur->link); assert(cur); @@ -1135,5 +1135,5 @@ goto try_again; } - + return NULL; } @@ -1143,11 +1143,11 @@ { assert(h); - + size_t hash = calc_key_hash(h, key); size_t removed = 0; - + while (remove_pred(h, hash, h->op->key_equal, key)) ++removed; - + return removed; } @@ -1181,24 +1181,24 @@ { rcu_read_lock(); - + bool resizing = false; bool deleted = false; bool deleted_but_gc = false; - + cht_buckets_t *b = rcu_access(h->b); size_t idx = calc_bucket_idx(hash, b->order); marked_ptr_t *phead = &b->head[idx]; - + do { walk_mode_t walk_mode = WM_NORMAL; bool join_finishing = false; - + resizing = resizing || (N_NORMAL != get_mark(*phead)); - + /* The table is resizing. Get the correct bucket head. */ if (resizing) { upd_resizing_head(h, hash, &phead, &join_finishing, &walk_mode); } - + wnd_t wnd = { .ppred = phead, @@ -1206,5 +1206,5 @@ .last = NULL }; - + if (!find_wnd_and_gc_pred( h, hash, walk_mode, pred, pred_arg, &wnd, &resizing)) { @@ -1212,5 +1212,5 @@ continue; } - + /* * The item lookup is affected by a bucket join but effects of @@ -1225,19 +1225,19 @@ continue; } - + /* Already deleted, but delete_at() requested one GC pass. */ if (deleted_but_gc) break; - + bool found = (wnd.cur != &sentinel && pred(pred_arg, wnd.cur)); - + if (!found) { rcu_read_unlock(); return false; } - + deleted = delete_at(h, &wnd, walk_mode, &deleted_but_gc, &resizing); } while (!deleted || deleted_but_gc); - + rcu_read_unlock(); return true; @@ -1263,20 +1263,20 @@ { assert(wnd->cur && wnd->cur != &sentinel); - + *deleted_but_gc = false; - + if (!mark_deleted(wnd->cur, walk_mode, resizing)) { /* Already deleted, or unexpectedly marked as JOIN/JOIN_FOLLOWS. */ return false; } - + /* Marked deleted. Unlink from the bucket. */ - + /* Never unlink join nodes. */ if (walk_mode == WM_LEAVE_JOIN && (N_JOIN & get_mark(wnd->cur->link))) return true; - + cas_order_barrier(); - + if (unlink_from_pred(wnd, walk_mode, resizing)) { free_later(h, wnd->cur); @@ -1284,5 +1284,5 @@ *deleted_but_gc = true; } - + return true; } @@ -1293,16 +1293,16 @@ { assert(cur && cur != &sentinel); - + /* * Btw, we could loop here if the cas fails but let's not complicate * things and let's retry from the head of the bucket. */ - + cht_link_t *next = get_next(cur->link); - + if (walk_mode == WM_NORMAL) { /* Only mark clean/normal nodes - JF/JN is used only during resize. */ marked_ptr_t ret = cas_link(&cur->link, next, N_NORMAL, next, N_DELETED); - + if (ret != make_link(next, N_NORMAL)) { *resizing = (N_JOIN | N_JOIN_FOLLOWS) & get_mark(ret); @@ -1311,15 +1311,15 @@ } else { static_assert(N_JOIN == N_JOIN_FOLLOWS, ""); - + /* Keep the N_JOIN/N_JOIN_FOLLOWS mark but strip N_DELETED. */ mark_t cur_mark = get_mark(cur->link) & N_JOIN_FOLLOWS; - + marked_ptr_t ret = cas_link(&cur->link, next, cur_mark, next, cur_mark | N_DELETED); - + if (ret != make_link(next, cur_mark)) return false; } - + return true; } @@ -1331,7 +1331,7 @@ assert(wnd->cur != &sentinel); assert(wnd->cur && (N_DELETED & get_mark(wnd->cur->link))); - + cht_link_t *next = get_next(wnd->cur->link); - + if (walk_mode == WM_LEAVE_JOIN) { /* Never try to unlink join nodes. */ @@ -1341,8 +1341,8 @@ /* Succeed only if the predecessor is clean/normal or a join node. */ mark_t exp_pred_mark = (N_JOIN & pred_mark) ? pred_mark : N_NORMAL; - + marked_ptr_t pred_link = make_link(wnd->cur, exp_pred_mark); marked_ptr_t next_link = make_link(next, exp_pred_mark); - + if (pred_link != _cas_link(wnd->ppred, pred_link, next_link)) return false; @@ -1351,12 +1351,12 @@ /* Move the JF mark if set. Clear DEL mark. */ mark_t cur_mark = N_JOIN_FOLLOWS & get_mark(wnd->cur->link); - + /* The predecessor must be clean/normal. */ marked_ptr_t pred_link = make_link(wnd->cur, N_NORMAL); /* Link to cur's successor keeping/copying cur's JF mark. */ marked_ptr_t next_link = make_link(next, cur_mark); - + marked_ptr_t ret = _cas_link(wnd->ppred, pred_link, next_link); - + if (pred_link != ret) { /* If we're not resizing the table there are no JF/JN nodes. */ @@ -1366,5 +1366,5 @@ } } - + return true; } @@ -1399,8 +1399,8 @@ { assert(wnd->cur); - + if (wnd->cur == &sentinel) return true; - + /* * A read barrier is not needed here to bring up the most recent @@ -1408,13 +1408,13 @@ * an already deleted node; fail in delete_at(); and retry. */ - + size_t cur_hash; try_again: cur_hash = node_hash(h, wnd->cur); - + while (cur_hash <= hash) { assert(wnd->cur && wnd->cur != &sentinel); - + /* GC any deleted nodes on the way. */ if (N_DELETED & get_mark(wnd->cur->link)) { @@ -1427,11 +1427,11 @@ if (cur_hash == hash && pred(pred_arg, wnd->cur)) return true; - + next_wnd(wnd); } - + cur_hash = node_hash(h, wnd->cur); } - + if (cur_hash == h->invalid_hash) { next_wnd(wnd); @@ -1439,5 +1439,5 @@ goto try_again; } - + /* The searched for node is not in the current bucket. */ return true; @@ -1481,8 +1481,8 @@ next_wnd(wnd); } - + assert(wnd->cur); } - + if (node_hash(h, wnd->cur) == h->invalid_hash) { next_wnd(wnd); @@ -1520,5 +1520,5 @@ wnd->cur = get_next(wnd->cur->link); } - + return true; } @@ -1539,5 +1539,5 @@ * is visible and if not, make it visible to this cpu. */ - + /* * Resizer ensures h->b->order stays the same for the duration of this @@ -1548,21 +1548,21 @@ assert(h->b->order > h->new_b->order); assert(wnd->cur); - + /* Either we did not need the joining link or we have already followed it.*/ if (wnd->cur != &sentinel) return true; - + /* We have reached the end of a bucket. */ - + if (wnd->last != &sentinel) { size_t last_seen_hash = node_hash(h, wnd->last); - + if (last_seen_hash == h->invalid_hash) { last_seen_hash = calc_node_hash(h, wnd->last); } - + size_t last_old_idx = calc_bucket_idx(last_seen_hash, h->b->order); size_t move_src_idx = grow_idx(shrink_idx(last_old_idx)); - + /* * Last node seen was in the joining bucket - if the searched @@ -1572,5 +1572,5 @@ return true; } - + /* * Reached the end of the bucket but no nodes from the joining bucket @@ -1603,8 +1603,8 @@ size_t old_idx = calc_bucket_idx(hash, b->order); size_t new_idx = calc_bucket_idx(hash, h->new_b->order); - + marked_ptr_t *pold_head = &b->head[old_idx]; marked_ptr_t *pnew_head = &h->new_b->head[new_idx]; - + /* In any case, use the bucket in the new table. */ *phead = pnew_head; @@ -1614,8 +1614,8 @@ size_t move_dest_idx = grow_idx(old_idx); marked_ptr_t *pmoved_head = &h->new_b->head[move_dest_idx]; - + /* Complete moving the bucket from the old to the new table. */ help_head_move(pold_head, pmoved_head); - + /* The hash belongs to the moved bucket. */ if (move_dest_idx == new_idx) { @@ -1634,5 +1634,5 @@ * half of the split/old/moved bucket. */ - + /* The moved bucket has not yet been split. */ if (N_NORMAL != get_mark(*pnew_head)) { @@ -1645,12 +1645,12 @@ assert(N_NORMAL == get_mark(*pnew_head)); } - + *walk_mode = WM_LEAVE_JOIN; } } else if (h->new_b->order < b->order ) { /* Shrinking the table. */ - + size_t move_src_idx = grow_idx(new_idx); - + /* * Complete moving the bucket from the old to the new table. @@ -1658,5 +1658,5 @@ */ help_head_move(&b->head[move_src_idx], pnew_head); - + /* Hash belongs to the bucket to be joined with the moved bucket. */ if (move_src_idx != old_idx) { @@ -1666,5 +1666,5 @@ join_buckets(h, pold_head, pnew_head, split_hash); } - + /* * The resizer sets pold_head to &sentinel when all cpus are @@ -1673,5 +1673,5 @@ *join_finishing = (&sentinel != get_next(*pold_head)); } - + /* move_head() or join_buckets() makes it so or makes the mark visible.*/ assert(N_INVALID == get_mark(*pold_head)); @@ -1713,5 +1713,5 @@ /* Head move has to in progress already when calling this func. */ assert(N_CONST & get_mark(*psrc_head)); - + /* Head already moved. */ if (N_INVALID == get_mark(*psrc_head)) { @@ -1724,5 +1724,5 @@ complete_head_move(psrc_head, pdest_head); } - + assert(!(N_CONST & get_mark(*pdest_head))); } @@ -1742,10 +1742,10 @@ { marked_ptr_t ret, src_link; - + /* Mark src head immutable. */ do { cht_link_t *next = get_next(*psrc_head); src_link = make_link(next, N_NORMAL); - + /* Mark the normal/clean src link immutable/const. */ ret = cas_link(psrc_head, next, N_NORMAL, next, N_CONST); @@ -1758,5 +1758,5 @@ assert(N_JOIN_FOLLOWS != get_mark(*psrc_head)); assert(N_CONST & get_mark(*psrc_head)); - + cht_link_t *next = get_next(*psrc_head); @@ -1765,5 +1765,5 @@ assert(ret == make_link(&sentinel, N_INVALID) || (N_NORMAL == get_mark(ret))); cas_order_barrier(); - + DBG(ret = ) cas_link(psrc_head, next, N_CONST, next, N_INVALID); @@ -1791,5 +1791,5 @@ if (N_NORMAL == get_mark(*pdest_head)) return; - + /* * L == Last node of the first part of the split bucket. That part @@ -1836,11 +1836,11 @@ */ wnd_t wnd; - + rcu_read_lock(); - + /* Mark the last node of the first part of the split bucket as JF. */ mark_join_follows(h, psrc_head, split_hash, &wnd); cas_order_barrier(); - + /* There are nodes in the dest bucket, ie the second part of the split. */ if (wnd.cur != &sentinel) { @@ -1857,5 +1857,5 @@ */ } - + /* Link the dest head to the second part of the split. */ DBG(marked_ptr_t ret = ) @@ -1863,5 +1863,5 @@ assert(ret == make_link(&sentinel, N_INVALID) || (N_NORMAL == get_mark(ret))); cas_order_barrier(); - + rcu_read_unlock(); } @@ -1888,5 +1888,5 @@ { /* See comment in split_bucket(). */ - + bool done = false; @@ -1895,5 +1895,5 @@ wnd->ppred = psrc_head; wnd->cur = get_next(*psrc_head); - + /* * Find the split window, ie the last node of the first part of @@ -1903,5 +1903,5 @@ if (!find_wnd_and_gc(h, split_hash, WM_MOVE_JOIN_FOLLOWS, wnd, &resizing)) continue; - + /* Must not report that the table is resizing if WM_MOVE_JOIN_FOLLOWS.*/ assert(!resizing); @@ -1926,10 +1926,10 @@ { /* See comment in split_bucket(). */ - + bool done; do { cht_link_t *next = get_next(join_node->link); mark_t mark = get_mark(join_node->link); - + /* * May already be marked as deleted, but it won't be unlinked @@ -1938,5 +1938,5 @@ marked_ptr_t ret = cas_link(&join_node->link, next, mark, next, mark | N_JOIN); - + /* Successfully marked or already marked as a join node. */ done = (ret == make_link(next, mark)) @@ -2023,11 +2023,11 @@ * [src_head | Inv]-----------> [JN] -> .. */ - + rcu_read_lock(); - + /* Mark src_head immutable - signals updaters that bucket join started. */ mark_const(psrc_head); cas_order_barrier(); - + cht_link_t *join_node = get_next(*psrc_head); @@ -2035,14 +2035,14 @@ mark_join_node(join_node); cas_order_barrier(); - + link_to_join_node(h, pdest_head, join_node, split_hash); cas_order_barrier(); } - + DBG(marked_ptr_t ret = ) cas_link(psrc_head, join_node, N_CONST, join_node, N_INVALID); assert(ret == make_link(join_node, N_CONST) || (N_INVALID == get_mark(ret))); cas_order_barrier(); - + rcu_read_unlock(); } @@ -2067,12 +2067,12 @@ .cur = get_next(*pdest_head) }; - + bool resizing = false; - + if (!find_wnd_and_gc(h, split_hash, WM_LEAVE_JOIN, &wnd, &resizing)) continue; assert(!resizing); - + if (wnd.cur != &sentinel) { /* Must be from the new appended bucket. */ @@ -2081,9 +2081,9 @@ return; } - + /* Reached the tail of pdest_head - link it to the join node. */ marked_ptr_t ret = cas_link(wnd.ppred, &sentinel, N_NORMAL, join_node, N_NORMAL); - + done = (ret == make_link(&sentinel, N_NORMAL)); } while (!done); @@ -2097,5 +2097,5 @@ { assert(item != &sentinel); - + /* * remove_callback only works as rcu_func_t because rcu_link is the first @@ -2103,5 +2103,5 @@ */ rcu_call(&item->rcu_link, (rcu_func_t)h->op->remove_callback); - + item_removed(h); } @@ -2116,8 +2116,8 @@ size_t items = (size_t) atomic_predec(&h->item_cnt); size_t bucket_cnt = (1 << h->b->order); - + bool need_shrink = (items == h->max_load * bucket_cnt / 4); bool missed_shrink = (items == h->max_load * bucket_cnt / 8); - + if ((need_shrink || missed_shrink) && h->b->order > h->min_order) { atomic_count_t resize_reqs = atomic_preinc(&h->resize_reqs); @@ -2137,8 +2137,8 @@ size_t items = (size_t) atomic_preinc(&h->item_cnt); size_t bucket_cnt = (1 << h->b->order); - + bool need_grow = (items == h->max_load * bucket_cnt); bool missed_grow = (items == 2 * h->max_load * bucket_cnt); - + if ((need_grow || missed_grow) && h->b->order < CHT_MAX_ORDER) { atomic_count_t resize_reqs = atomic_preinc(&h->resize_reqs); @@ -2154,5 +2154,5 @@ { cht_t *h = member_to_inst(arg, cht_t, resize_work); - + #ifdef CONFIG_DEBUG assert(h->b); @@ -2188,5 +2188,5 @@ if (h->b->order >= CHT_MAX_ORDER) return; - + h->new_b = alloc_buckets(h->b->order + 1, true, false); @@ -2198,5 +2198,5 @@ rcu_synchronize(); size_t old_bucket_cnt = (1 << h->b->order); - + /* * Give updaters a chance to help out with the resize. Do the minimum @@ -2206,8 +2206,8 @@ start_head_move(&h->b->head[idx]); } - + /* Order start_head_move() wrt complete_head_move(). */ cas_order_barrier(); - + /* Complete moving heads and split any buckets not yet split by updaters. */ for (size_t old_idx = 0; old_idx < old_bucket_cnt; ++old_idx) { @@ -2226,5 +2226,5 @@ split_bucket(h, move_dest_head, split_dest_head, split_hash); } - + /* * Wait for all updaters to notice the new heads. Once everyone sees @@ -2233,9 +2233,9 @@ */ rcu_synchronize(); - + /* Clear the JOIN_FOLLOWS mark and remove the link between the split buckets.*/ for (size_t old_idx = 0; old_idx < old_bucket_cnt; ++old_idx) { size_t new_idx = grow_idx(old_idx); - + cleanup_join_follows(h, &h->new_b->head[new_idx]); } @@ -2246,9 +2246,9 @@ */ rcu_synchronize(); - + /* Clear the JOIN mark and GC any deleted join nodes. */ for (size_t old_idx = 0; old_idx < old_bucket_cnt; ++old_idx) { size_t new_idx = grow_to_split_idx(old_idx); - + cleanup_join_node(h, &h->new_b->head[new_idx]); } @@ -2256,5 +2256,5 @@ /* Wait for everyone to see that the table is clear of any resize marks. */ rcu_synchronize(); - + cht_buckets_t *old_b = h->b; rcu_assign(h->b, h->new_b); @@ -2262,7 +2262,7 @@ /* Wait for everyone to start using the new table. */ rcu_synchronize(); - + free(old_b); - + /* Not needed; just for increased readability. */ h->new_b = NULL; @@ -2274,5 +2274,5 @@ if (h->b->order <= h->min_order) return; - + h->new_b = alloc_buckets(h->b->order - 1, true, false); @@ -2283,7 +2283,7 @@ /* Wait for all readers and updaters to see the initialized new table. */ rcu_synchronize(); - + size_t old_bucket_cnt = (1 << h->b->order); - + /* * Give updaters a chance to help out with the resize. Do the minimum @@ -2292,5 +2292,5 @@ for (size_t old_idx = 0; old_idx < old_bucket_cnt; ++old_idx) { size_t new_idx = shrink_idx(old_idx); - + /* This bucket should be moved. */ if (grow_idx(new_idx) == old_idx) { @@ -2300,13 +2300,13 @@ } } - + /* Order start_head_move() wrt to complete_head_move(). */ cas_order_barrier(); - + /* Complete moving heads and join buckets with the moved buckets. */ for (size_t old_idx = 0; old_idx < old_bucket_cnt; ++old_idx) { size_t new_idx = shrink_idx(old_idx); size_t move_src_idx = grow_idx(new_idx); - + /* This bucket should be moved. */ if (move_src_idx == old_idx) { @@ -2322,5 +2322,5 @@ } } - + /* * Wait for all updaters to notice the new heads. Once everyone sees @@ -2329,23 +2329,23 @@ */ rcu_synchronize(); - + /* Let everyone know joins are complete and fully visible. */ for (size_t old_idx = 0; old_idx < old_bucket_cnt; ++old_idx) { size_t move_src_idx = grow_idx(shrink_idx(old_idx)); - + /* Set the invalid joinee head to NULL. */ if (old_idx != move_src_idx) { assert(N_INVALID == get_mark(h->b->head[old_idx])); - + if (&sentinel != get_next(h->b->head[old_idx])) h->b->head[old_idx] = make_link(&sentinel, N_INVALID); } } - + /* todo comment join node vs reset joinee head*/ rcu_synchronize(); size_t new_bucket_cnt = (1 << h->new_b->order); - + /* Clear the JOIN mark and GC any deleted join nodes. */ for (size_t new_idx = 0; new_idx < new_bucket_cnt; ++new_idx) { @@ -2355,13 +2355,13 @@ /* Wait for everyone to see that the table is clear of any resize marks. */ rcu_synchronize(); - + cht_buckets_t *old_b = h->b; rcu_assign(h->b, h->new_b); - + /* Wait for everyone to start using the new table. */ rcu_synchronize(); - + free(old_b); - + /* Not needed; just for increased readability. */ h->new_b = NULL; @@ -2374,5 +2374,5 @@ cht_link_t *cur = get_next(*new_head); - + while (cur != &sentinel) { /* Clear the join node's JN mark - even if it is marked as deleted. */ @@ -2381,8 +2381,8 @@ break; } - + cur = get_next(cur->link); } - + rcu_read_unlock(); } @@ -2394,7 +2394,7 @@ assert(join_node != &sentinel); assert(join_node && (N_JOIN & get_mark(join_node->link))); - + bool done; - + /* Clear the JN mark. */ do { @@ -2411,5 +2411,5 @@ assert(ret == jn_link || (get_mark(ret) & N_JOIN)); } while (!done); - + if (!(N_DELETED & get_mark(join_node->link))) return; @@ -2419,17 +2419,17 @@ /* Clear the JOIN mark before trying to unlink the deleted join node.*/ cas_order_barrier(); - + size_t jn_hash = node_hash(h, join_node); do { bool resizing = false; - + wnd_t wnd = { .ppred = new_head, .cur = get_next(*new_head) }; - + done = find_wnd_and_gc_pred(h, jn_hash, WM_NORMAL, same_node_pred, join_node, &wnd, &resizing); - + assert(!resizing); } while (!done); @@ -2440,5 +2440,5 @@ { assert(new_head); - + rcu_read_lock(); @@ -2448,5 +2448,5 @@ }; marked_ptr_t *cur_link = new_head; - + /* * Find the non-deleted node with a JF mark and clear the JF mark. @@ -2461,5 +2461,5 @@ while (true) { bool is_jf_node = N_JOIN_FOLLOWS & get_mark(*cur_link); - + /* GC any deleted nodes on the way - even deleted JOIN_FOLLOWS. */ if (N_DELETED & get_mark(*cur_link)) { @@ -2483,5 +2483,5 @@ marked_ptr_t ret = cas_link(cur_link, next, N_JOIN_FOLLOWS, &sentinel, N_NORMAL); - + assert(next == &sentinel || ((N_JOIN | N_JOIN_FOLLOWS) & get_mark(ret))); @@ -2508,5 +2508,5 @@ cur_link = &wnd.cur->link; } - + rcu_read_unlock(); } @@ -2561,5 +2561,5 @@ || item->hash == sentinel.hash || item->hash == calc_node_hash(h, item)); - + return item->hash; } @@ -2586,8 +2586,8 @@ { marked_ptr_t ptr = (marked_ptr_t) next; - + assert(!(ptr & N_MARK_MASK)); assert(!((unsigned)mark & ~N_MARK_MASK)); - + return ptr | mark; } @@ -2690,5 +2690,5 @@ */ void *expected = (void*)cur; - + /* * Use the acquire-release model, although we could probably @@ -2698,5 +2698,5 @@ __atomic_compare_exchange_n((void**)link, &expected, (void *)new, false, __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE); - + return (marked_ptr_t) expected; } Index: kernel/generic/src/adt/hash_table.c =================================================================== --- kernel/generic/src/adt/hash_table.c (revision 1b20da07baaa3e3c424f62c927274e676e4295cd) +++ kernel/generic/src/adt/hash_table.c (revision 0aa06cbe8a6965cc7f1ebfa7236bcd8d5316da16) @@ -96,14 +96,14 @@ assert(h); assert(op && op->hash && op->key_hash && op->key_equal); - + /* Check for compulsory ops. */ if (!op || !op->hash || !op->key_hash || !op->key_equal) return false; - + h->bucket_cnt = round_up_size(init_size); - + if (!alloc_table(h->bucket_cnt, &h->bucket)) return false; - + h->max_load = (max_load == 0) ? HT_MAX_LOAD : max_load; h->item_cnt = 0; @@ -115,5 +115,5 @@ h->op->remove_callback = nop_remove_callback; } - + return true; } @@ -128,7 +128,7 @@ assert(h && h->bucket); assert(!h->apply_ongoing); - + clear_items(h); - + free(h->bucket); @@ -159,7 +159,7 @@ assert(h && h->bucket); assert(!h->apply_ongoing); - + clear_items(h); - + /* Shrink the table to its minimum size if possible. */ if (HT_MIN_BUCKETS < h->bucket_cnt) { @@ -173,15 +173,15 @@ if (h->item_cnt == 0) return; - + for (size_t idx = 0; idx < h->bucket_cnt; ++idx) { list_foreach_safe(h->bucket[idx], cur, next) { assert(cur); ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); - + list_remove(cur); h->op->remove_callback(cur_link); } } - + h->item_cnt = 0; } @@ -197,7 +197,7 @@ assert(h && h->bucket); assert(!h->apply_ongoing); - + size_t idx = h->op->hash(item) % h->bucket_cnt; - + list_append(&item->link, &h->bucket[idx]); ++h->item_cnt; @@ -220,7 +220,7 @@ assert(h->op && h->op->hash && h->op->equal); assert(!h->apply_ongoing); - + size_t idx = h->op->hash(item) % h->bucket_cnt; - + /* Check for duplicates. */ list_foreach(h->bucket[idx], link, ht_link_t, cur_link) { @@ -232,9 +232,9 @@ return false; } - + list_append(&item->link, &h->bucket[idx]); ++h->item_cnt; grow_if_needed(h); - + return true; } @@ -251,5 +251,5 @@ { assert(h && h->bucket); - + size_t idx = h->op->key_hash(key) % h->bucket_cnt; @@ -264,5 +264,5 @@ } } - + return NULL; } @@ -305,12 +305,12 @@ assert(h && h->bucket); assert(!h->apply_ongoing); - + size_t idx = h->op->key_hash(key) % h->bucket_cnt; size_t removed = 0; - + list_foreach_safe(h->bucket[idx], cur, next) { ht_link_t *cur_link = member_to_inst(cur, ht_link_t, link); - + if (h->op->key_equal(key, cur_link)) { ++removed; @@ -322,5 +322,5 @@ h->item_cnt -= removed; shrink_if_needed(h); - + return removed; } @@ -352,10 +352,10 @@ assert(f); assert(h && h->bucket); - + if (h->item_cnt == 0) return; - + h->apply_ongoing = true; - + for (size_t idx = 0; idx < h->bucket_cnt; ++idx) { list_foreach_safe(h->bucket[idx], cur, next) { @@ -371,5 +371,5 @@ out: h->apply_ongoing = false; - + shrink_if_needed(h); grow_if_needed(h); @@ -380,9 +380,9 @@ { size_t rounded_size = HT_MIN_BUCKETS; - + while (rounded_size < size) { rounded_size = 2 * rounded_size + 1; } - + return rounded_size; } @@ -392,9 +392,9 @@ { assert(pbuckets && HT_MIN_BUCKETS <= bucket_cnt); - + list_t *buckets = malloc(bucket_cnt * sizeof(list_t), FRAME_ATOMIC); if (!buckets) return false; - + for (size_t i = 0; i < bucket_cnt; i++) list_initialize(&buckets[i]); @@ -434,9 +434,9 @@ assert(h && h->bucket); assert(HT_MIN_BUCKETS <= new_bucket_cnt); - + /* We are traversing the table and resizing would mess up the buckets. */ if (h->apply_ongoing) return; - + list_t *new_buckets; @@ -444,5 +444,5 @@ if (!alloc_table(new_bucket_cnt, &new_buckets)) return; - + if (0 < h->item_cnt) { /* Rehash all the items to the new table. */ @@ -457,5 +457,5 @@ } } - + free(h->bucket); h->bucket = new_buckets; Index: kernel/generic/src/adt/list.c =================================================================== --- kernel/generic/src/adt/list.c (revision 1b20da07baaa3e3c424f62c927274e676e4295cd) +++ kernel/generic/src/adt/list.c (revision 0aa06cbe8a6965cc7f1ebfa7236bcd8d5316da16) @@ -56,5 +56,5 @@ bool found = false; link_t *hlp = list->head.next; - + while (hlp != &list->head) { if (hlp == link) { @@ -64,5 +64,5 @@ hlp = hlp->next; } - + return found; } @@ -80,13 +80,13 @@ if (list_empty(list)) return; - + /* Attach list to destination. */ list->head.next->prev = pos; list->head.prev->next = pos->next; - + /* Link destination list to the added list. */ pos->next->prev = list->head.prev; pos->next = list->head.next; - + list_initialize(list); } @@ -102,5 +102,5 @@ { unsigned long count = 0; - + link_t *link = list_first(list); while (link != NULL) { @@ -108,5 +108,5 @@ link = list_next(link, list); } - + return count; }