Changeset 04d66804 in mainline


Ignore:
Timestamp:
2012-11-20T17:35:55Z (11 years ago)
Author:
Adam Hraska <adam.hraska+hos@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
669f3d32
Parents:
0adfc9d
Message:

cht: Expanded cht_insert_unique() to return a duplicate if found.

Location:
kernel
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • kernel/generic/include/adt/cht.h

    r0adfc9d r04d66804  
    142142
    143143extern void cht_insert(cht_t *h, cht_link_t *item);
    144 extern bool cht_insert_unique(cht_t *h, cht_link_t *item);
     144extern bool cht_insert_unique(cht_t *h, cht_link_t *item, cht_link_t **dup_item);
    145145extern size_t cht_remove_key(cht_t *h, void *key);
    146146extern bool cht_remove_item(cht_t *h, cht_link_t *item);

  • kernel/generic/src/adt/cht.c

    r0adfc9d r04d66804  
    414414static cht_link_t *find_resizing(cht_t *h, void *key, size_t hash,
    415415        marked_ptr_t old_head, size_t old_idx);
    416 static bool insert_impl(cht_t *h, cht_link_t *item, bool unique);
     416static bool insert_impl(cht_t *h, cht_link_t *item, cht_link_t **dup_item);
    417417static bool insert_at(cht_link_t *item, const wnd_t *wnd, walk_mode_t walk_mode,
    418418        bool *resizing);
    419 static bool has_duplicates(cht_t *h, const cht_link_t *item, size_t hash,
    420         const wnd_t *cwnd);
     419static bool has_duplicate(cht_t *h, const cht_link_t *item, size_t hash,
     420        cht_link_t *cur, cht_link_t **dup_item);
    421421static cht_link_t *find_duplicate(cht_t *h, const cht_link_t *item, size_t hash,
    422422        cht_link_t *start);
    … …  
    886886void cht_insert(cht_t *h, cht_link_t *item)
    887887{
    888         insert_impl(h, item, false);
     888        insert_impl(h, item, NULL);
    889889}
    890890
    … …  
    908908 * @code
    909909 * item = malloc(..);
    910  * if (!cht_insert_unique(h, item)) {
    911  *     // Whoops, someone beat us to it - an equal item had already been inserted.
     910 * if (!cht_insert_unique(h, item, &dup_item)) {
     911 *     // Whoops, someone beat us to it - an equal item 'dup_item'
     912 *     // had already been inserted.
    912913 *     free(item);
    913914 * } else {
    … …  
    918919 *
    919920 */
    920 bool cht_insert_unique(cht_t *h, cht_link_t *item)
    921 {
    922         return insert_impl(h, item, true);
    923 }
    924 
    925 /** Inserts the item into the table and checks for duplicates if unique is true.*/
    926 static bool insert_impl(cht_t *h, cht_link_t *item, bool unique)
     921bool cht_insert_unique(cht_t *h, cht_link_t *item, cht_link_t **dup_item)
     922{
     923        ASSERT(rcu_read_locked());
     924        ASSERT(dup_item);
     925        return insert_impl(h, item, dup_item);
     926}
     927
     928/** Inserts the item into the table and checks for duplicates if dup_item. */
     929static bool insert_impl(cht_t *h, cht_link_t *item, cht_link_t **dup_item)
    927930{
    928931        rcu_read_lock();
    … …  
    959962                }
    960963               
    961                 if (unique && has_duplicates(h, item, hash, &wnd)) {
     964                if (dup_item && has_duplicate(h, item, hash, wnd.cur, dup_item)) {
    962965                        rcu_read_unlock();
    963966                        return false;
    … …  
    10321035}
    10331036
    1034 /** Returns true the chain starting at wnd hash an item equal to \a item.
     1037/** Returns true if the chain starting at cur has an item equal to \a item.
    10351038 *
    10361039 * @param h    CHT to operate on.
    10371040 * @param item Item whose duplicates the function looks for.
    10381041 * @param hash Hash of \a item.
    1039  * @param[in] wnd  wnd.cur is the first node with a hash greater to or equal
    1040  *             to item's hash.
     1042 * @param[in] cur  The first node with a hash greater to or equal to item's hash.
     1043 * @param[out] dup_item The first duplicate item encountered.
    10411044 * @return True if a non-deleted item equal to \a item exists in the table.
    10421045 */
    1043 static inline bool has_duplicates(cht_t *h, const cht_link_t *item, size_t hash,
    1044         const wnd_t *wnd)
    1045 {
    1046         ASSERT(wnd->cur);
    1047         ASSERT(wnd->cur == &sentinel || hash <= node_hash(h, wnd->cur)
    1048                 || node_hash(h, wnd->cur) == h->invalid_hash);
    1049        
    1050         /* hash < node_hash(h, wnd->cur) */
    1051         if (hash != node_hash(h, wnd->cur) && h->invalid_hash != node_hash(h, wnd->cur))
     1046static inline bool has_duplicate(cht_t *h, const cht_link_t *item, size_t hash,
     1047        cht_link_t *cur, cht_link_t **dup_item)
     1048{
     1049        ASSERT(cur);
     1050        ASSERT(cur == &sentinel || hash <= node_hash(h, cur)
     1051                || node_hash(h, cur) == h->invalid_hash);
     1052       
     1053        /* hash < node_hash(h, cur) */
     1054        if (hash != node_hash(h, cur) && h->invalid_hash != node_hash(h, cur))
    10521055                return false;
    10531056
    … …  
    10581061         */
    10591062        read_barrier();
    1060         return NULL != find_duplicate(h, item, hash, wnd->cur);
     1063       
     1064        *dup_item = find_duplicate(h, item, hash, cur);
     1065        return NULL != *dup_item;
    10611066}
    10621067

  • kernel/test/cht/cht1.c

    r0adfc9d r04d66804  
    124124        set_val(v[4], 2, key[4]);
    125125        set_val(v[5], 3, key[5]);
     126       
     127        cht_link_t *dup;
    126128                       
    127         if (!cht_insert_unique(h, &v[0]->link))
     129        if (!cht_insert_unique(h, &v[0]->link, &dup))
    128130                return "Duplicates in empty";
    129131
    130         if (cht_insert_unique(h, &v[1]->link))
     132        if (cht_insert_unique(h, &v[1]->link, &dup))
    131133                return "Inserted a duplicate";
    132 
    133         if (!cht_insert_unique(h, &v[3]->link))
     134       
     135        if (dup != &v[0]->link)
     136                return "Returned wrong duplicate";
     137
     138        if (!cht_insert_unique(h, &v[3]->link, &dup))
    134139                return "Refused non-equal item but with a hash in table.";
    135140       
    … …  
    138143       
    139144        bool ok = true;
    140         ok = ok && cht_insert_unique(h, &v[4]->link);
    141         ok = ok && cht_insert_unique(h, &v[5]->link);
     145        ok = ok && cht_insert_unique(h, &v[4]->link, &dup);
     146        ok = ok && cht_insert_unique(h, &v[5]->link, &dup);
    142147       
    143148        if (!ok)
    … …  
    398403                               
    399404                                if (item_op) {
    400                                         if (!cht_insert_unique(work->h, &work->elem[elem_idx].link)) {
     405                                        rcu_read_lock();
     406                                        cht_link_t *dup;
     407                                        if (!cht_insert_unique(work->h, &work->elem[elem_idx].link,
     408                                                &dup)) {
    401409                                                TPRINTF("Err: already inserted\n");
    402410                                                work->failed = true;
    403411                                        }
     412                                        rcu_read_unlock();
    404413                                } else {
    405414                                        cht_insert(work->h, &work->elem[elem_idx].link);
Note: See TracChangeset for help on using the changeset viewer.