Fork us on GitHub Follow us on Facebook Follow us on Twitter

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


Ignore:
Timestamp:
2012-08-03T16:08:39Z (9 years ago)
Author:
Adam Hraska <adam.hraska+hos@…>
Branches:
lfn, master
Children:
5e5cef3
Parents:
fbe17545
Message:

cht: Slightly changed CHT interface. It now allows to specify the maximum desired load of the table before it resizes.

File:
1 edited

Legend:

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

    rfbe17545 r0b7bcb8  
    4949
    5050
    51 /* Logarithm of the min bucket count. 2^6 == 64 buckets. */
     51/* Logarithm of the min bucket count. Must be at least 3. 2^6 == 64 buckets. */
    5252#define CHT_MIN_ORDER 6
    5353/* Logarithm of the max bucket count. */
     
    5555/* Minimum number of hash table buckets. */
    5656#define CHT_MIN_BUCKET_CNT (1 << CHT_MIN_ORDER)
    57 /* Must be a power of 2. */
     57/* Does not have to be a power of 2. */
    5858#define CHT_MAX_LOAD 2
    5959
     
    8383} wnd_t;
    8484
    85 /* Fwd decl. */
     85
    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);
     
    153153
    154154
    155 bool cht_create(cht_t *h, size_t init_size, size_t min_size, cht_ops_t *op)
     155bool cht_create(cht_t *h, size_t init_size, size_t min_size, size_t max_load,
     156        cht_ops_t *op)
    156157{
    157158        ASSERT(h);
     
    170171                return false;
    171172       
     173        h->max_load = (max_load == 0) ? CHT_MAX_LOAD : max_load;
    172174        h->min_order = min_order;
    173175        h->new_b = 0;
     
    13601362        size_t bucket_cnt = (1 << h->b->order);
    13611363       
    1362         bool need_shrink = (items == CHT_MAX_LOAD * bucket_cnt / 4);
    1363         bool missed_shrink = (items == CHT_MAX_LOAD * bucket_cnt / 8);
     1364        bool need_shrink = (items == h->max_load * bucket_cnt / 4);
     1365        bool missed_shrink = (items == h->max_load * bucket_cnt / 8);
    13641366       
    13651367        if ((need_shrink || missed_shrink) && h->b->order > h->min_order) {
     
    13771379        size_t bucket_cnt = (1 << h->b->order);
    13781380       
    1379         bool need_grow = (items == CHT_MAX_LOAD * bucket_cnt);
    1380         bool missed_grow = (items == 2 * CHT_MAX_LOAD * bucket_cnt);
     1381        bool need_grow = (items == h->max_load * bucket_cnt);
     1382        bool missed_grow = (items == 2 * h->max_load * bucket_cnt);
    13811383       
    13821384        if ((need_grow || missed_grow) && h->b->order < CHT_MAX_ORDER) {
     
    14061408                size_t cur_items = (size_t) atomic_get(&h->item_cnt);
    14071409                size_t bucket_cnt = (1 << h->b->order);
    1408                 size_t max_items = CHT_MAX_LOAD * bucket_cnt;
     1410                size_t max_items = h->max_load * bucket_cnt;
    14091411
    14101412                if (cur_items >= max_items && h->b->order < CHT_MAX_ORDER) {
Note: See TracChangeset for help on using the changeset viewer.