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

Changeset 0b7bcb8 in mainline


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.

Location:
kernel
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • kernel/generic/include/adt/cht.h

    rfbe17545 r0b7bcb8  
    7575        cht_buckets_t *new_b;
    7676
     77        size_t max_load;
    7778        work_t resize_work;
    7879        atomic_t resize_reqs;
     
    8889#define cht_read_unlock()   rcu_read_unlock()
    8990
    90 extern bool cht_create(cht_t *h, size_t init_size, size_t min_size, cht_ops_t *op);
     91extern bool cht_create(cht_t *h, size_t init_size, size_t min_size,
     92        size_t max_load, cht_ops_t *op);
    9193extern void cht_destroy(cht_t *h);
    9294
  • 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) {
  • kernel/test/cht/cht1.c

    rfbe17545 r0b7bcb8  
    235235{
    236236        cht_t h;
    237         if (!cht_create(&h, 5, 0, &val_ops))
     237        if (!cht_create(&h, 5, 0, 0, &val_ops))
    238238                return "Could not create the table.";
    239239       
     
    445445        cht_t h;
    446446       
    447         if (!cht_create(&h, 0, 0, &stress_ops)) {
     447        if (!cht_create(&h, 0, 0, 0, &stress_ops)) {
    448448                TPRINTF("Failed to create the table\n");
    449449                return false;
Note: See TracChangeset for help on using the changeset viewer.