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


Ignore:
Timestamp:
2012-08-03T16:17:16Z (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:
26d8df3
Parents:
0b7bcb8
Message:

cht: Reduced lookup overhead.

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r0b7bcb8 r5e5cef3  
    8686static size_t size_to_order(size_t bucket_cnt, size_t min_order);
    8787static cht_buckets_t *alloc_buckets(size_t order, bool set_invalid);
     88static inline cht_link_t *find_lazy(cht_t *h, void *key);
    8889static cht_link_t *search_bucket(cht_t *h, marked_ptr_t head, void *key,
    8990        size_t search_hash);
    … …  
    242243}
    243244
    244 
    245245cht_link_t *cht_find_lazy(cht_t *h, void *key)
     246{
     247        return find_lazy(h, key);
     248}
     249
     250static inline cht_link_t *find_lazy(cht_t *h, void *key)
    246251{
    247252        ASSERT(h);
    … …  
    280285}
    281286
    282 static cht_link_t *search_bucket(cht_t *h, marked_ptr_t head, void *key,
     287static inline cht_link_t *search_bucket(cht_t *h, marked_ptr_t head, void *key,
    283288        size_t search_hash)
    284289{
    … …  
    291296                 * may find by following the next pointers is allocated.
    292297                 */
    293                 size_t cur_hash = node_hash(h, cur);
    294 
    295                 if (cur_hash >= search_hash) {
    296                         if (cur_hash != search_hash)
    297                                 return 0;
    298 
    299                         int present = !(N_DELETED & get_mark(cur->link));
    300                         if (present && h->op->key_equal(key, cur))
     298                if (h->op->key_equal(key, cur)) {
     299                        if (!(N_DELETED & get_mark(cur->link)))
    301300                                return cur;
    302301                }
    … …  
    465464
    466465        bool resizing = false;
    467         bool inserted;
     466        bool inserted = false;
    468467       
    469468        do {
    … …  
    503502}
    504503
    505 static bool insert_at(cht_link_t *item, const wnd_t *wnd, walk_mode_t walk_mode,
    506         bool *resizing)
     504inline static bool insert_at(cht_link_t *item, const wnd_t *wnd,
     505        walk_mode_t walk_mode, bool *resizing)
    507506{
    508507        marked_ptr_t ret;
    … …  
    550549}
    551550
    552 static bool has_duplicates(cht_t *h, const cht_link_t *item, size_t hash,
     551static inline bool has_duplicates(cht_t *h, const cht_link_t *item, size_t hash,
    553552        const wnd_t *wnd)
    554553{
    … …  
    682681
    683682
    684 static bool delete_at(cht_t *h, wnd_t *wnd, walk_mode_t walk_mode,
     683static inline bool delete_at(cht_t *h, wnd_t *wnd, walk_mode_t walk_mode,
    685684        bool *deleted_but_gc, bool *resizing)
    686685{
    … …  
    711710}
    712711
    713 static bool mark_deleted(cht_link_t *cur, walk_mode_t walk_mode, bool *resizing)
     712static inline bool mark_deleted(cht_link_t *cur, walk_mode_t walk_mode,
     713        bool *resizing)
    714714{
    715715        ASSERT(cur);
    … …  
    746746}
    747747
    748 static bool unlink_from_pred(wnd_t *wnd, walk_mode_t walk_mode, bool *resizing)
     748static inline bool unlink_from_pred(wnd_t *wnd, walk_mode_t walk_mode,
     749        bool *resizing)
    749750{
    750751        ASSERT(wnd->cur && (N_DELETED & get_mark(wnd->cur->link)));
    … …  
    10231024#endif
    10241025
    1025 static void help_head_move(marked_ptr_t *psrc_head, marked_ptr_t *pdest_head)
     1026static inline void help_head_move(marked_ptr_t *psrc_head,
     1027        marked_ptr_t *pdest_head)
    10261028{
    10271029        /* Head move has to in progress already when calling this func. */
    … …  
    13571359}
    13581360
    1359 static void item_removed(cht_t *h)
     1361static inline void item_removed(cht_t *h)
    13601362{
    13611363        size_t items = (size_t) atomic_predec(&h->item_cnt);
    … …  
    13741376}
    13751377
    1376 static void item_inserted(cht_t *h)
     1378static inline void item_inserted(cht_t *h)
    13771379{
    13781380        size_t items = (size_t) atomic_preinc(&h->item_cnt);
    … …  
    17451747
    17461748
    1747 static size_t calc_split_hash(size_t split_idx, size_t order)
     1749static inline size_t calc_split_hash(size_t split_idx, size_t order)
    17481750{
    17491751        ASSERT(1 <= order && order <= 8 * sizeof(size_t));
    … …  
    17511753}
    17521754
    1753 static size_t calc_bucket_idx(size_t hash, size_t order)
     1755static inline size_t calc_bucket_idx(size_t hash, size_t order)
    17541756{
    17551757        ASSERT(1 <= order && order <= 8 * sizeof(size_t));
    … …  
    17571759}
    17581760
    1759 static size_t grow_to_split_idx(size_t old_idx)
     1761static inline size_t grow_to_split_idx(size_t old_idx)
    17601762{
    17611763        return grow_idx(old_idx) | 1;
    17621764}
    17631765
    1764 static size_t grow_idx(size_t idx)
     1766static inline size_t grow_idx(size_t idx)
    17651767{
    17661768        return idx << 1;
    17671769}
    17681770
    1769 static size_t shrink_idx(size_t idx)
     1771static inline size_t shrink_idx(size_t idx)
    17701772{
    17711773        return idx >> 1;
    … …  
    17731775
    17741776
    1775 static size_t key_hash(cht_t *h, void *key)
     1777static inline size_t key_hash(cht_t *h, void *key)
    17761778{
    17771779        return hash_mix(h->op->key_hash(key));
    17781780}
    17791781
    1780 static size_t node_hash(cht_t *h, const cht_link_t *item)
     1782static inline size_t node_hash(cht_t *h, const cht_link_t *item)
    17811783{
    17821784        return hash_mix(h->op->hash(item));
    … …  
    17841786
    17851787
    1786 static marked_ptr_t make_link(const cht_link_t *next, mark_t mark)
     1788static inline marked_ptr_t make_link(const cht_link_t *next, mark_t mark)
    17871789{
    17881790        marked_ptr_t ptr = (marked_ptr_t) next;
    … …  
    17951797
    17961798
    1797 static cht_link_t * get_next(marked_ptr_t link)
     1799static inline cht_link_t * get_next(marked_ptr_t link)
    17981800{
    17991801        return (cht_link_t*)(link & ~N_MARK_MASK);
    … …  
    18011803
    18021804
    1803 static mark_t get_mark(marked_ptr_t link)
     1805static inline mark_t get_mark(marked_ptr_t link)
    18041806{
    18051807        return (mark_t)(link & N_MARK_MASK);
    … …  
    18071809
    18081810
    1809 static void next_wnd(wnd_t *wnd)
     1811static inline void next_wnd(wnd_t *wnd)
    18101812{
    18111813        ASSERT(wnd);
    … …  
    18241826}
    18251827
    1826 static marked_ptr_t cas_link(marked_ptr_t *link, const cht_link_t *cur_next,
     1828static inline marked_ptr_t cas_link(marked_ptr_t *link, const cht_link_t *cur_next,
    18271829        mark_t cur_mark, const cht_link_t *new_next, mark_t new_mark)
    18281830{
    … …  
    18311833}
    18321834
    1833 static marked_ptr_t _cas_link(marked_ptr_t *link, marked_ptr_t cur,
     1835static inline marked_ptr_t _cas_link(marked_ptr_t *link, marked_ptr_t cur,
    18341836        marked_ptr_t new)
    18351837{
    … …  
    18601862}
    18611863
    1862 static void cas_order_barrier(void)
     1864static inline void cas_order_barrier(void)
    18631865{
    18641866        /* Make sure CAS to different memory locations are ordered. */
Note: See TracChangeset for help on using the changeset viewer.