Changeset b9cb911 in mainline for kernel/generic/src/adt/cht.c


Ignore:
Timestamp:
2012-08-20T18:40:19Z (12 years ago)
Author:
Adam Hraska <adam.hraska+hos@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
7cfe5c0
Parents:
85d31de9
Message:

cht: API comments.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • kernel/generic/src/adt/cht.c

    r85d31de9 rb9cb911  
    6161typedef bool (*equal_pred_t)(void *arg, const cht_link_t *item);
    6262
     63/** The following mark items and bucket heads.
     64 *
     65 * They are stored in the two low order bits of the next item pointers.
     66 * Some marks may be combined. Some marks share the same binary value and
     67 * are distinguished only by context (eg bucket head vs an ordinary item),
     68 * in particular by walk_mode_t.
     69 */
    6370typedef enum mark {
     71        /** Normal non-deleted item or a valid bucket head. */
    6472        N_NORMAL = 0,
     73        /** Logically deleted item that might have already been unlinked.
     74         *
     75         * May be combined with N_JOIN and N_JOIN_FOLLOWS. Applicable only
     76         * to items; never to bucket heads.
     77         *
     78         * Once marked deleted an item remains marked deleted.   
     79         */
    6580        N_DELETED = 1,
     81        /** Immutable bucket head.
     82         *
     83         * The bucket is being moved or joined with another and its (old) head
     84         * must not be modified.
     85         *
     86         * May be combined with N_INVALID. Applicable only to old bucket heads,
     87         * ie cht_t.b and not cht_t.new_b.
     88         */
    6689        N_CONST = 1,
     90        /** Invalid bucket head. The bucket head must not be modified.
     91         *
     92         * Old bucket heads (ie cht_t.b) are marked invalid if they have
     93         * already been moved to cht_t.new_b or if the bucket had already
     94         * been merged with another when shrinking the table. New bucket
     95         * heads (ie cht_t.new_b) are marked invalid if the old bucket had
     96         * not yet been moved or if an old bucket had not yet been split
     97         * when growing the table.
     98         */
    6799        N_INVALID = 3,
     100        /** The item is a join node, ie joining two buckets
     101         *
     102         * A join node is either the first node of the second part of
     103         * a bucket to be split; or it is the first node of the bucket
     104         * to be merged into/appended to/joined with another bucket.
     105         *
     106         * May be combined with N_DELETED. Applicable only to items, never
     107         * to bucket heads.
     108         *
     109         * Join nodes are referred to from two different buckets and may,
     110         * therefore, not be safely/atomically unlinked from both buckets.
     111         * As a result join nodes are not unlinked but rather just marked
     112         * deleted. Once resize completes join nodes marked deleted are
     113         * garbage collected.
     114         */
    68115        N_JOIN = 2,
     116        /** The next node is a join node and will soon be marked so.
     117         *
     118         * A join-follows node is the last node of the first part of bucket
     119         * that is to be split, ie it is the last node that will remain
     120         * in the same bucket after splitting it.
     121         *
     122         * May be combined with N_DELETED. Applicable to items as well
     123         * as to bucket heads of the bucket to be split (but only in cht_t.new_b).
     124         */
    69125        N_JOIN_FOLLOWS = 2,
     126        /** Bit mask to filter out the address to the next item from the next ptr. */
    70127        N_MARK_MASK = 3
    71128} mark_t;
    72129
     130/** Determines */
    73131typedef enum walk_mode {
     132        /** The table is not resizing. */
    74133        WM_NORMAL = 4,
     134        /** The table is undergoing a resize. Join nodes may be encountered. */
    75135        WM_LEAVE_JOIN,
     136        /** The table is growing. A join-follows node may be encountered. */
    76137        WM_MOVE_JOIN_FOLLOWS
    77138} walk_mode_t;
    78139
     140/** Bucket position window. */
    79141typedef struct wnd {
     142        /** Pointer to cur's predecessor. */
    80143        marked_ptr_t *ppred;
     144        /** Current item. */
    81145        cht_link_t *cur;
     146        /** Last encountered item. Deleted or not. */
    82147        cht_link_t *last;
    83148} wnd_t;
     
    162227static void cas_order_barrier(void);
    163228
    164 
     229/** Creates a concurrent hash table.
     230 *
     231 * @param h         Valid pointer to a cht_t instance.
     232 * @param init_size The initial number of buckets the table should contain.
     233 *                  The table may be shrunk below this value if deemed necessary.
     234 *                  Uses the default value if 0.
     235 * @param min_size  Minimum number of buckets that the table should contain.
     236 *                  The number of buckets never drops below this value,
     237 *                  although it may be rounded up internally as appropriate.
     238 *                  Uses the default value if 0.
     239 * @param max_load  Maximum average number of items per bucket that allowed
     240 *                  before the table grows.
     241 * @param op        Item specific operations. All operations are compulsory.
     242 * @return True if successfully created the table. False otherwise.
     243 */
    165244bool cht_create(cht_t *h, size_t init_size, size_t min_size, size_t max_load,
    166245        cht_ops_t *op)
     
    202281}
    203282
     283/** Allocates and initializes 2^order buckets.
     284 *
     285 * All bucket heads are initialized to point to the sentinel node.
     286 *
     287 * @param order       The number of buckets to allocate is 2^order.
     288 * @param set_invalid Bucket heads are marked invalid if true; otherwise
     289 *                    they are marked N_NORMAL.
     290 * @return Newly allocated and initialized buckets or NULL if not enough memory.
     291 */
    204292static cht_buckets_t *alloc_buckets(size_t order, bool set_invalid)
    205293{
     
    225313}
    226314
     315/** Returns the smallest k such that bucket_cnt <= 2^k and min_order <= k.*/
    227316static size_t size_to_order(size_t bucket_cnt, size_t min_order)
    228317{
     
    240329}
    241330
    242 
     331/** Destroys a CHT successfully created via cht_create().
     332 *
     333 * Waits for all outstanding concurrent operations to complete and
     334 * frees internal allocated resources. The table is however not cleared
     335 * and items already present in the table (if any) are leaked.
     336 */
    243337void cht_destroy(cht_t *h)
    244338{
     
    253347        free(h->b);
    254348        h->b = 0;
    255 }
    256 
     349       
     350        /* You must clear the table of items. Otherwise cht_destroy will leak. */
     351        ASSERT(atomic_get(&h->item_cnt) == 0);
     352}
     353
     354/** Returns the first item equal to the search key or NULL if not found.
     355 *
     356 * The call must be enclosed in a rcu_read_lock() unlock() pair. The
     357 * returned item is guaranteed to be allocated until rcu_read_unlock()
     358 * although the item may be concurrently removed from the table by another
     359 * cpu.
     360 *
     361 * Further items matching the key may be retrieved via cht_find_next().
     362 *
     363 * cht_find() sees the effects of any completed cht_remove(), cht_insert().
     364 * If a concurrent remove or insert had not yet completed cht_find() may
     365 * or may not see the effects of it (eg it may find an item being removed).
     366 *
     367 * @param h   CHT to operate on.
     368 * @param key Search key as defined by cht_ops_t.key_equal() and .key_hash().
     369 * @return First item equal to the key or NULL if such an item does not exist.
     370 */
    257371cht_link_t *cht_find(cht_t *h, void *key)
    258372{
     
    262376}
    263377
     378/** Returns the first item equal to the search key or NULL if not found.
     379 *
     380 * Unlike cht_find(), cht_find_lazy() may not see the effects of
     381 * cht_remove() or cht_insert() even though they have already completed.
     382 * It may take a couple of milliseconds for those changes to propagate
     383 * and become visible to cht_find_lazy(). On the other hand, cht_find_lazy()
     384 * operates a bit faster than cht_find().
     385 *
     386 * See cht_find() for more details.
     387 */
    264388cht_link_t *cht_find_lazy(cht_t *h, void *key)
    265389{
     
    267391}
    268392
     393/** Finds the first item equal to the search key. */
    269394static inline cht_link_t *find_lazy(cht_t *h, void *key)
    270395{
    271396        ASSERT(h);
     397        /* See docs to cht_find() and cht_find_lazy(). */
    272398        ASSERT(rcu_read_locked());
    273399       
     
    282408        marked_ptr_t head = b->head[idx];
    283409       
     410        /* Undergoing a resize - take the slow path. */
    284411        if (N_INVALID == get_mark(head))
    285412                return find_resizing(h, key, hash, head, idx);
     
    288415}
    289416
     417/** Returns the next item matching \a item.
     418 *
     419 * Must be enclosed in a rcu_read_lock()/unlock() pair. Effects of
     420 * completed cht_remove(), cht_insert() are guaranteed to be visible
     421 * to cht_find_next().
     422 *
     423 * See cht_find() for more details. 
     424 */
    290425cht_link_t *cht_find_next(cht_t *h, const cht_link_t *item)
    291426{
     
    295430}
    296431
     432/** Returns the next item matching \a item.
     433 *
     434 * Must be enclosed in a rcu_read_lock()/unlock() pair. Effects of
     435 * completed cht_remove(), cht_insert() may or may not be visible
     436 * to cht_find_next_lazy().
     437 *
     438 * See cht_find_lazy() for more details. 
     439 */
    297440cht_link_t *cht_find_next_lazy(cht_t *h, const cht_link_t *item)
    298441{
     
    304447}
    305448
     449/** Searches the bucket at head for key using search_hash. */
    306450static inline cht_link_t *search_bucket(cht_t *h, marked_ptr_t head, void *key,
    307451        size_t search_hash)
     
    351495}
    352496
     497/** Searches for the key while the table is undergoing a resize. */
    353498static cht_link_t *find_resizing(cht_t *h, void *key, size_t hash,
    354499        marked_ptr_t old_head, size_t old_idx)
     
    487632}
    488633
    489 
     634/** Inserts an item. Succeeds even if an equal item is already present. */
    490635void cht_insert(cht_t *h, cht_link_t *item)
    491636{
     
    493638}
    494639
     640/** Inserts a unique item. Returns false if an equal item was already present.
     641 *
     642 * Use this function to atomically check if an equal/duplicate item had
     643 * not yet been inserted into the table and to insert this item into the
     644 * table.
     645 *
     646 * The following is NOT thread-safe, so do not use:
     647 * \code
     648 * if (!cht_find(h, key)) {
     649 *     // A concurrent insert here may go unnoticed by cht_find() above.
     650 *     item = malloc(..);
     651 *     cht_insert(h, item);
     652 *     // Now we may have two items with equal search keys.
     653 * }
     654 * \endcode
     655 *
     656 * Replace such code with:
     657 * \code
     658 * item = malloc(..);
     659 * if (!cht_insert_unique(h, item)) {
     660 *     // Whoops, someone beat us to it - an equal item had already been inserted.
     661 *     free(item);
     662 * } else {
     663 *     // Successfully inserted the item and we are guaranteed that
     664 *     // there are no other equal items.
     665 * }
     666 * \endcode
     667 *
     668 */
    495669bool cht_insert_unique(cht_t *h, cht_link_t *item)
    496670{
     
    498672}
    499673
     674/** Inserts the item into the table and checks for duplicates if unique is true.*/
    500675static bool insert_impl(cht_t *h, cht_link_t *item, bool unique)
    501676{
     
    547722}
    548723
     724/** Inserts item between wnd.ppred and wnd.cur.
     725 *
     726 * @param item      Item to link to wnd.ppred and wnd.cur.
     727 * @param wnd       The item will be inserted before wnd.cur. Wnd.ppred
     728 *                  must be N_NORMAL.
     729 * @param walk_mode
     730 * @param resizing  Set to true only if the table is undergoing resize
     731 *         and it was not expected (ie walk_mode == WM_NORMAL).
     732 * @return True if the item was successfully linked to wnd.ppred. False
     733 *         if whole insert operation must be retried because the predecessor
     734 *         of wnd.cur has changed.
     735 */
    549736inline static bool insert_at(cht_link_t *item, const wnd_t *wnd,
    550737        walk_mode_t walk_mode, bool *resizing)
     
    594781}
    595782
     783/** Returns true the chain starting at wnd hash an item equal to \a item.
     784 *
     785 * @param h    CHT to operate on.
     786 * @param item Item whose duplicates the function looks for.
     787 * @param hash Hash of \a item.
     788 * @param[in] wnd  wnd.cur is the first node with a hash greater to or equal
     789 *             to item's hash.
     790 * @return True if a non-deleted item equal to \a item exists in the table.
     791 */
    596792static inline bool has_duplicates(cht_t *h, const cht_link_t *item, size_t hash,
    597793        const wnd_t *wnd)
     
    614810}
    615811
     812/** Returns an item that is equal to \a item starting in a chain at \a start. */
    616813static cht_link_t *find_duplicate(cht_t *h, const cht_link_t *item, size_t hash,
    617814        cht_link_t *start)
     
    637834        }
    638835
     836        /* Skip logically deleted nodes with rcu_call() in progress. */
    639837        if (h->invalid_hash == node_hash(h, cur)) {
    640838                cur = get_next(cur->link);
     
    645843}
    646844
     845/** Removes all items matching the search key. Returns the number of items removed.*/
    647846size_t cht_remove_key(cht_t *h, void *key)
    648847{
     
    658857}
    659858
     859/** Removes a specific item from the table.
     860 *
     861 * The called must hold rcu read lock.
     862 *
     863 * @param item Item presumably present in the table and to be removed.
     864 * @return True if the item was removed successfully; or false if it had
     865 *     already been deleted.
     866 */
    660867bool cht_remove_item(cht_t *h, cht_link_t *item)
    661868{
    662869        ASSERT(h);
    663870        ASSERT(item);
     871        /* Otherwise a concurrent cht_remove_key might free the item. */
     872        ASSERT(rcu_read_locked());
    664873
    665874        /*
     
    672881}
    673882
    674 
     883/** Removes an item equal to pred_arg according to the predicate pred. */
    675884static bool remove_pred(cht_t *h, size_t hash, equal_pred_t pred, void *pred_arg)
    676885{
     
    739948}
    740949
    741 
     950/** Unlinks wnd.cur from wnd.ppred and schedules a deferred free for the item.
     951 *
     952 * Ignores nodes marked N_JOIN if walk mode is WM_LEAVE_JOIN.
     953 *
     954 * @param h   CHT to operate on.
     955 * @param wnd Points to the item to delete and its N_NORMAL predecessor.
     956 * @param walk_mode Bucket chaing walk mode.
     957 * @param deleted_but_gc Set to true if the item had been logically deleted,
     958 *         but a garbage collecting walk of the bucket is in order for
     959 *         it to be fully unlinked.         
     960 * @param resizing Set to true if the table is undergoing an unexpected
     961 *         resize (ie walk_mode == WM_NORMAL).
     962 * @return False if the wnd.ppred changed in the meantime and the whole
     963 *         delete operation must be retried.
     964 */
    742965static inline bool delete_at(cht_t *h, wnd_t *wnd, walk_mode_t walk_mode,
    743966        bool *deleted_but_gc, bool *resizing)
     
    769992}
    770993
     994/** Marks cur logically deleted. Returns false to request a retry. */
    771995static inline bool mark_deleted(cht_link_t *cur, walk_mode_t walk_mode,
    772996        bool *resizing)
     
    8051029}
    8061030
     1031/** Unlinks wnd.cur from wnd.ppred. Returns false if it should be retried. */
    8071032static inline bool unlink_from_pred(wnd_t *wnd, walk_mode_t walk_mode,
    8081033        bool *resizing)
     
    8491074}
    8501075
    851 
     1076/** Finds the first non-deleted item equal to \a pred_arg according to \a pred.
     1077 *
     1078 * The function returns the candidate item in \a wnd. Logically deleted
     1079 * nodes are garbage collected so the predecessor will most likely not
     1080 * be marked as deleted.
     1081 *
     1082 * Unlike find_wnd_and_gc(), this function never returns a node that
     1083 * is known to have already been marked N_DELETED.
     1084 *
     1085 * Any logically deleted nodes (ie those marked N_DELETED) are garbage
     1086 * collected, ie free in the background via rcu_call (except for join-nodes
     1087 * if walk_mode == WM_LEAVE_JOIN).
     1088 *
     1089 * @param h         CHT to operate on.
     1090 * @param hash      Hash the search for.
     1091 * @param walk_mode Bucket chain walk mode.
     1092 * @param pred      Predicate used to find an item equal to pred_arg.
     1093 * @param pred_arg  Argument to pass to the equality predicate \a pred.
     1094 * @param[in,out] wnd The search starts with wnd.cur. If the desired
     1095 *                  item is found wnd.cur will point to it.
     1096 * @param resizing  Set to true if the table is resizing but it was not
     1097 *                  expected (ie walk_mode == WM_NORMAL).
     1098 * @return False if the operation has to be retried. True otherwise
     1099 *        (even if an equal item had not been found).
     1100 */
    8521101static bool find_wnd_and_gc_pred(cht_t *h, size_t hash, walk_mode_t walk_mode,
    8531102        equal_pred_t pred, void *pred_arg, wnd_t *wnd, bool *resizing)
     
    8991148}
    9001149
    901 /* todo: comment different semantics (eg deleted JN first w/ specific hash) */
     1150/** Find the first item (deleted or not) with a hash greater or equal to \a hash.
     1151 *
     1152 * The function returns the first item with a hash that is greater or
     1153 * equal to \a hash in \a wnd. Moreover it garbage collects logically
     1154 * deleted node that have not yet been unlinked and freed. Therefore,
     1155 * the returned node's predecessor will most likely be N_NORMAL.
     1156 *
     1157 * Unlike find_wnd_and_gc_pred(), this function may return a node
     1158 * that is known to had been marked N_DELETED.
     1159 * 
     1160 * @param h         CHT to operate on.
     1161 * @param hash      Hash of the item to find.
     1162 * @param walk_mode Bucket chain walk mode.
     1163 * @param[in,out] wnd wnd.cur denotes the first node of the chain. If the
     1164 *                  the operation is successful, \a wnd points to the desired
     1165 *                  item.
     1166 * @param resizing  Set to true if a table resize was detected but walk_mode
     1167 *                  suggested the table was not undergoing a resize.
     1168 * @return False indicates the operation must be retried. True otherwise
     1169 *       (even if an item with exactly the same has was not found).
     1170 */
    9021171static bool find_wnd_and_gc(cht_t *h, size_t hash, walk_mode_t walk_mode,
    9031172        wnd_t *wnd, bool *resizing)
     
    9291198}
    9301199
     1200/** Garbage collects the N_DELETED node at \a wnd skipping join nodes. */
    9311201static bool gc_deleted_node(cht_t *h, walk_mode_t walk_mode, wnd_t *wnd,
    9321202        bool *resizing)
     
    9581228}
    9591229
     1230/** Returns true if a bucket join had already completed.
     1231 *
     1232 * May only be called if upd_resizing_head() indicates a bucket join
     1233 * may be in progress.
     1234 *
     1235 * If it returns false, the search must be retried in order to guarantee
     1236 * all item that should have been encountered have been seen.
     1237 */
    9601238static bool join_completed(cht_t *h, const wnd_t *wnd)
    9611239{
     
    10091287}
    10101288
     1289/** When resizing returns the bucket head to start the search with in \a phead.
     1290 *
     1291 * If a resize had been detected (eg cht_t.b.head[idx] is marked immutable).
     1292 * upd_resizing_head() moves the bucket for \a hash from the old head
     1293 * to the new head. Moreover, it splits or joins buckets as necessary.
     1294 *
     1295 * @param h     CHT to operate on.
     1296 * @param hash  Hash of an item whose chain we would like to traverse.
     1297 * @param[out] phead Head of the bucket to search for \a hash.
     1298 * @param[out] join_finishing Set to true if a bucket join might be
     1299 *              in progress and the bucket may have to traversed again
     1300 *              as indicated by join_completed().
     1301 * @param[out] walk_mode Specifies how to interpret node marks. 
     1302 */
    10111303static void upd_resizing_head(cht_t *h, size_t hash, marked_ptr_t **phead,
    10121304        bool *join_finishing,  walk_mode_t *walk_mode)
     
    11121404#endif
    11131405
     1406/** Moves an immutable head \a psrc_head of cht_t.b to \a pdest_head of cht_t.new_b.
     1407 *
     1408 * The function guarantees the move will be visible on this cpu once
     1409 * it completes. In particular, *pdest_head will not be N_INVALID.
     1410 *
     1411 * Unlike complete_head_move(), help_head_move() checks if the head had already
     1412 * been moved and tries to avoid moving the bucket heads if possible.
     1413 */
    11141414static inline void help_head_move(marked_ptr_t *psrc_head,
    11151415        marked_ptr_t *pdest_head)
     
    11321432}
    11331433
     1434/** Initiates the move of the old head \a psrc_head.
     1435 *
     1436 * The move may be completed with help_head_move().
     1437 */
    11341438static void start_head_move(marked_ptr_t *psrc_head)
    11351439{
     
    11381442}
    11391443
     1444/** Marks the head immutable. */
    11401445static void mark_const(marked_ptr_t *psrc_head)
    11411446{
     
    11521457}
    11531458
     1459/** Completes moving head psrc_head to pdest_head (started by start_head_move()).*/
    11541460static void complete_head_move(marked_ptr_t *psrc_head, marked_ptr_t *pdest_head)
    11551461{
     
    11691475}
    11701476
     1477/** Splits the bucket at psrc_head and links to the remainder from pdest_head.
     1478 *
     1479 * Items with hashes greater or equal to \a split_hash are moved to bucket
     1480 * with head at \a pdest_head.
     1481 *
     1482 * @param h           CHT to operate on.
     1483 * @param psrc_head   Head of the bucket to split (in cht_t.new_b).
     1484 * @param pdest_head  Head of the bucket that points to the second part
     1485 *                    of the split bucket in psrc_head. (in cht_t.new_b)
     1486 * @param split_hash  Hash of the first possible item in the remainder of
     1487 *                    psrc_head, ie the smallest hash pdest_head is allowed
     1488 *                    to point to..
     1489 */
    11711490static void split_bucket(cht_t *h, marked_ptr_t *psrc_head,
    11721491        marked_ptr_t *pdest_head, size_t split_hash)
     
    12511570}
    12521571
     1572/** Finds and marks the last node of psrc_head w/ hash less than split_hash.
     1573 *
     1574 * Finds a node in psrc_head with the greatest hash that is strictly less
     1575 * than split_hash and marks it with N_JOIN_FOLLOWS.
     1576 *
     1577 * Returns a window pointing to that node.
     1578 *
     1579 * Any logically deleted nodes along the way are
     1580 * garbage collected; therefore, the predecessor node (if any) will most
     1581 * likely not be marked N_DELETED.
     1582 *
     1583 * @param h          CHT to operate on.
     1584 * @param psrc_head  Bucket head.
     1585 * @param split_hash The smallest hash a join node (ie the node following
     1586 *                   the desired join-follows node) may have.
     1587 * @param[out] wnd   Points to the node marked with N_JOIN_FOLLOWS.
     1588 */
    12531589static void mark_join_follows(cht_t *h, marked_ptr_t *psrc_head,
    12541590        size_t split_hash, wnd_t *wnd)
     
    12881624}
    12891625
     1626/** Marks join_node with N_JOIN. */
    12901627static void mark_join_node(cht_link_t *join_node)
    12911628{
     
    13101647}
    13111648
    1312 
     1649/** Appends the bucket at psrc_head to the bucket at pdest_head.
     1650 *
     1651 * @param h          CHT to operate on.
     1652 * @param psrc_head  Bucket to merge with pdest_head.
     1653 * @param pdest_head Bucket to be joined by psrc_head.
     1654 * @param split_hash The smallest hash psrc_head may contain.
     1655 */
    13131656static void join_buckets(cht_t *h, marked_ptr_t *psrc_head,
    13141657        marked_ptr_t *pdest_head, size_t split_hash)
     
    14071750}
    14081751
     1752/** Links the tail of pdest_head to join_node.
     1753 *
     1754 * @param h          CHT to operate on.
     1755 * @param pdest_head Head of the bucket whose tail is to be linked to join_node.
     1756 * @param join_node  A node marked N_JOIN with a hash greater or equal to
     1757 *                   split_hash.
     1758 * @param split_hash The least hash that is greater than the hash of any items
     1759 *                   (originally) in pdest_head.
     1760 */
    14091761static void link_to_join_node(cht_t *h, marked_ptr_t *pdest_head,
    14101762        cht_link_t *join_node, size_t split_hash)
     
    14391791}
    14401792
     1793/** Instructs RCU to free the item once all preexisting references are dropped.
     1794 *
     1795 * The item is freed via op->remove_callback().
     1796 */
    14411797static void free_later(cht_t *h, cht_link_t *item)
    14421798{
     
    14521808}
    14531809
     1810/** Notes that an item had been unlinked from the table and shrinks it if needed.
     1811 *
     1812 * If the number of items in the table drops below 1/4 of the maximum
     1813 * allowed load the table is shrunk in the background.
     1814 */
    14541815static inline void item_removed(cht_t *h)
    14551816{
     
    14691830}
    14701831
     1832/** Notes an item had been inserted and grows the table if needed.
     1833 *
     1834 * The table is resized in the background.
     1835 */
    14711836static inline void item_inserted(cht_t *h)
    14721837{
     
    14861851}
    14871852
     1853/** Resize request handler. Invoked on the system work queue. */
    14881854static void resize_table(work_t *arg)
    14891855{
     
    15171883}
    15181884
     1885/** Increases the number of buckets two-fold. Blocks until done. */
    15191886static void grow_table(cht_t *h)
    15201887{
     
    16021969}
    16031970
     1971/** Halfs the number of buckets. Blocks until done. */
    16041972static void shrink_table(cht_t *h)
    16051973{
     
    17002068}
    17012069
     2070/** Finds and clears the N_JOIN mark from a node in new_head (if present). */
    17022071static void cleanup_join_node(cht_t *h, marked_ptr_t *new_head)
    17032072{
     
    17192088}
    17202089
     2090/** Clears the join_node's N_JOIN mark frees it if marked N_DELETED as well. */
    17212091static void clear_join_and_gc(cht_t *h, cht_link_t *join_node,
    17222092        marked_ptr_t *new_head)
     
    17662136}
    17672137
     2138/** Finds a non-deleted node with N_JOIN_FOLLOWS and clears the mark. */
    17682139static void cleanup_join_follows(cht_t *h, marked_ptr_t *new_head)
    17692140{
     
    18412212}
    18422213
    1843 
     2214/** Returns the first possible hash following a bucket split point.
     2215 *
     2216 * In other words the returned hash is the smallest possible hash
     2217 * the remainder of the split bucket may contain.
     2218 */
    18442219static inline size_t calc_split_hash(size_t split_idx, size_t order)
    18452220{
     
    18482223}
    18492224
     2225/** Returns the bucket head index given the table size order and item hash. */
    18502226static inline size_t calc_bucket_idx(size_t hash, size_t order)
    18512227{
     
    18542230}
    18552231
     2232/** Returns the bucket index of destination*/
    18562233static inline size_t grow_to_split_idx(size_t old_idx)
    18572234{
     
    18592236}
    18602237
     2238/** Returns the destination index of a bucket head when the table is growing. */
    18612239static inline size_t grow_idx(size_t idx)
    18622240{
     
    18642242}
    18652243
     2244/** Returns the destination index of a bucket head when the table is shrinking.*/
    18662245static inline size_t shrink_idx(size_t idx)
    18672246{
     
    18692248}
    18702249
     2250/** Returns a mixed hash of the search key.*/
    18712251static inline size_t calc_key_hash(cht_t *h, void *key)
    18722252{
     
    18752255}
    18762256
     2257/** Returns a memoized mixed hash of the item. */
    18772258static inline size_t node_hash(cht_t *h, const cht_link_t *item)
    18782259{
     
    18842265}
    18852266
     2267/** Calculates and mixed the hash of the item. */
    18862268static inline size_t calc_node_hash(cht_t *h, const cht_link_t *item)
    18872269{
     
    18942276}
    18952277
     2278/** Computes and memoizes the hash of the item. */
    18962279static inline void memoize_node_hash(cht_t *h, cht_link_t *item)
    18972280{
     
    18992282}
    19002283
     2284/** Packs the next pointer address and the mark into a single pointer. */
    19012285static inline marked_ptr_t make_link(const cht_link_t *next, mark_t mark)
    19022286{
     
    19092293}
    19102294
    1911 
     2295/** Strips any marks from the next item link and returns the next item's address.*/
    19122296static inline cht_link_t * get_next(marked_ptr_t link)
    19132297{
     
    19152299}
    19162300
    1917 
     2301/** Returns the current node's mark stored in the next item link. */
    19182302static inline mark_t get_mark(marked_ptr_t link)
    19192303{
     
    19212305}
    19222306
    1923 
     2307/** Moves the window by one item so that is points to the next item. */
    19242308static inline void next_wnd(wnd_t *wnd)
    19252309{
     
    19322316}
    19332317
    1934 
     2318/** Predicate that matches only exactly the same node. */
    19352319static bool same_node_pred(void *node, const cht_link_t *item2)
    19362320{
     
    19392323}
    19402324
     2325/** Compare-and-swaps a next item link. */
    19412326static inline marked_ptr_t cas_link(marked_ptr_t *link, const cht_link_t *cur_next,
    19422327        mark_t cur_mark, const cht_link_t *new_next, mark_t new_mark)
     
    19462331}
    19472332
     2333/** Compare-and-swaps a next item link. */
    19482334static inline marked_ptr_t _cas_link(marked_ptr_t *link, marked_ptr_t cur,
    19492335        marked_ptr_t new)
     
    19762362}
    19772363
     2364/** Orders compare-and-swaps to different memory locations. */
    19782365static inline void cas_order_barrier(void)
    19792366{
Note: See TracChangeset for help on using the changeset viewer.