Deleted Added
sdiff udiff text old ( 302408 ) new ( 356345 )
full compact
lruhash.c (302408) lruhash.c (356345)
1/*
2 * util/storage/lruhash.c - hashtable, hash function, LRU keeping.
3 *
4 * Copyright (c) 2007, NLnet Labs. All rights reserved.
5 *
6 * This software is open source.
7 *
8 * Redistribution and use in source and binary forms, with or without

--- 45 unchanged lines hidden (view full) ---

54 for(i=0; i<size; i++) {
55 lock_quick_init(&array[i].lock);
56 lock_protect(&array[i].lock, &array[i],
57 sizeof(struct lruhash_bin));
58 }
59}
60
61struct lruhash*
1/*
2 * util/storage/lruhash.c - hashtable, hash function, LRU keeping.
3 *
4 * Copyright (c) 2007, NLnet Labs. All rights reserved.
5 *
6 * This software is open source.
7 *
8 * Redistribution and use in source and binary forms, with or without

--- 45 unchanged lines hidden (view full) ---

54 for(i=0; i<size; i++) {
55 lock_quick_init(&array[i].lock);
56 lock_protect(&array[i].lock, &array[i],
57 sizeof(struct lruhash_bin));
58 }
59}
60
61struct lruhash*
62lruhash_create(size_t start_size, size_t maxmem, lruhash_sizefunc_t sizefunc,
63 lruhash_compfunc_t compfunc, lruhash_delkeyfunc_t delkeyfunc,
64 lruhash_deldatafunc_t deldatafunc, void* arg)
62lruhash_create(size_t start_size, size_t maxmem,
63 lruhash_sizefunc_type sizefunc, lruhash_compfunc_type compfunc,
64 lruhash_delkeyfunc_type delkeyfunc,
65 lruhash_deldatafunc_type deldatafunc, void* arg)
65{
66 struct lruhash* table = (struct lruhash*)calloc(1,
67 sizeof(struct lruhash));
68 if(!table)
69 return NULL;
70 lock_quick_init(&table->lock);
71 table->sizefunc = sizefunc;
72 table->compfunc = compfunc;

--- 137 unchanged lines hidden (view full) ---

210 (*table->markdelfunc)(d->key);
211 lock_rw_unlock(&d->lock);
212 lock_quick_unlock(&bin->lock);
213 }
214}
215
216struct lruhash_entry*
217bin_find_entry(struct lruhash* table,
66{
67 struct lruhash* table = (struct lruhash*)calloc(1,
68 sizeof(struct lruhash));
69 if(!table)
70 return NULL;
71 lock_quick_init(&table->lock);
72 table->sizefunc = sizefunc;
73 table->compfunc = compfunc;

--- 137 unchanged lines hidden (view full) ---

211 (*table->markdelfunc)(d->key);
212 lock_rw_unlock(&d->lock);
213 lock_quick_unlock(&bin->lock);
214 }
215}
216
217struct lruhash_entry*
218bin_find_entry(struct lruhash* table,
218 struct lruhash_bin* bin, hashvalue_t hash, void* key)
219 struct lruhash_bin* bin, hashvalue_type hash, void* key)
219{
220 struct lruhash_entry* p = bin->overflow_list;
221 while(p) {
222 if(p->hash == hash && table->compfunc(p->key, key) == 0)
223 return p;
224 p = p->overflow_next;
225 }
226 return NULL;

--- 64 unchanged lines hidden (view full) ---

291 return; /* nothing to do */
292 /* remove from current lru position */
293 lru_remove(table, entry);
294 /* add at front */
295 lru_front(table, entry);
296}
297
298void
220{
221 struct lruhash_entry* p = bin->overflow_list;
222 while(p) {
223 if(p->hash == hash && table->compfunc(p->key, key) == 0)
224 return p;
225 p = p->overflow_next;
226 }
227 return NULL;

--- 64 unchanged lines hidden (view full) ---

292 return; /* nothing to do */
293 /* remove from current lru position */
294 lru_remove(table, entry);
295 /* add at front */
296 lru_front(table, entry);
297}
298
299void
299lruhash_insert(struct lruhash* table, hashvalue_t hash,
300lruhash_insert(struct lruhash* table, hashvalue_type hash,
300 struct lruhash_entry* entry, void* data, void* cb_arg)
301{
302 struct lruhash_bin* bin;
303 struct lruhash_entry* found, *reclaimlist=NULL;
304 size_t need_size;
305 fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
306 fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
307 fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));

--- 39 unchanged lines hidden (view full) ---

347 void* d = reclaimlist->data;
348 (*table->delkeyfunc)(reclaimlist->key, cb_arg);
349 (*table->deldatafunc)(d, cb_arg);
350 reclaimlist = n;
351 }
352}
353
354struct lruhash_entry*
301 struct lruhash_entry* entry, void* data, void* cb_arg)
302{
303 struct lruhash_bin* bin;
304 struct lruhash_entry* found, *reclaimlist=NULL;
305 size_t need_size;
306 fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
307 fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
308 fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));

--- 39 unchanged lines hidden (view full) ---

348 void* d = reclaimlist->data;
349 (*table->delkeyfunc)(reclaimlist->key, cb_arg);
350 (*table->deldatafunc)(d, cb_arg);
351 reclaimlist = n;
352 }
353}
354
355struct lruhash_entry*
355lruhash_lookup(struct lruhash* table, hashvalue_t hash, void* key, int wr)
356lruhash_lookup(struct lruhash* table, hashvalue_type hash, void* key, int wr)
356{
357 struct lruhash_entry* entry;
358 struct lruhash_bin* bin;
359 fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));
360
361 lock_quick_lock(&table->lock);
362 bin = &table->array[hash & table->size_mask];
363 lock_quick_lock(&bin->lock);

--- 5 unchanged lines hidden (view full) ---

369 if(wr) { lock_rw_wrlock(&entry->lock); }
370 else { lock_rw_rdlock(&entry->lock); }
371 }
372 lock_quick_unlock(&bin->lock);
373 return entry;
374}
375
376void
357{
358 struct lruhash_entry* entry;
359 struct lruhash_bin* bin;
360 fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));
361
362 lock_quick_lock(&table->lock);
363 bin = &table->array[hash & table->size_mask];
364 lock_quick_lock(&bin->lock);

--- 5 unchanged lines hidden (view full) ---

370 if(wr) { lock_rw_wrlock(&entry->lock); }
371 else { lock_rw_rdlock(&entry->lock); }
372 }
373 lock_quick_unlock(&bin->lock);
374 return entry;
375}
376
377void
377lruhash_remove(struct lruhash* table, hashvalue_t hash, void* key)
378lruhash_remove(struct lruhash* table, hashvalue_type hash, void* key)
378{
379 struct lruhash_entry* entry;
380 struct lruhash_bin* bin;
381 void *d;
382 fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
383 fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
384 fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
385 fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));

--- 121 unchanged lines hidden (view full) ---

507 lock_get_mem(&table->array[0].lock));
508#endif
509 lock_quick_unlock(&table->lock);
510 s += lock_get_mem(&table->lock);
511 return s;
512}
513
514void
379{
380 struct lruhash_entry* entry;
381 struct lruhash_bin* bin;
382 void *d;
383 fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
384 fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
385 fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
386 fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));

--- 121 unchanged lines hidden (view full) ---

508 lock_get_mem(&table->array[0].lock));
509#endif
510 lock_quick_unlock(&table->lock);
511 s += lock_get_mem(&table->lock);
512 return s;
513}
514
515void
515lruhash_setmarkdel(struct lruhash* table, lruhash_markdelfunc_t md)
516lruhash_setmarkdel(struct lruhash* table, lruhash_markdelfunc_type md)
516{
517 lock_quick_lock(&table->lock);
518 table->markdelfunc = md;
519 lock_quick_unlock(&table->lock);
520}
521
522void
523lruhash_traverse(struct lruhash* h, int wr,

--- 13 unchanged lines hidden (view full) ---

537 }
538 (*func)(e, arg);
539 lock_rw_unlock(&e->lock);
540 }
541 lock_quick_unlock(&h->array[i].lock);
542 }
543 lock_quick_unlock(&h->lock);
544}
517{
518 lock_quick_lock(&table->lock);
519 table->markdelfunc = md;
520 lock_quick_unlock(&table->lock);
521}
522
523void
524lruhash_traverse(struct lruhash* h, int wr,

--- 13 unchanged lines hidden (view full) ---

538 }
539 (*func)(e, arg);
540 lock_rw_unlock(&e->lock);
541 }
542 lock_quick_unlock(&h->array[i].lock);
543 }
544 lock_quick_unlock(&h->lock);
545}
546
547/*
548 * Demote: the opposite of touch, move an entry to the bottom
549 * of the LRU pile.
550 */
551
552void
553lru_demote(struct lruhash* table, struct lruhash_entry* entry)
554{
555 log_assert(table && entry);
556 if (entry == table->lru_end)
557 return; /* nothing to do */
558 /* remove from current lru position */
559 lru_remove(table, entry);
560 /* add at end */
561 entry->lru_next = NULL;
562 entry->lru_prev = table->lru_end;
563
564 if (table->lru_end == NULL)
565 {
566 table->lru_start = entry;
567 }
568 else
569 {
570 table->lru_end->lru_next = entry;
571 }
572 table->lru_end = entry;
573}
574
575struct lruhash_entry*
576lruhash_insert_or_retrieve(struct lruhash* table, hashvalue_type hash,
577 struct lruhash_entry* entry, void* data, void* cb_arg)
578{
579 struct lruhash_bin* bin;
580 struct lruhash_entry* found, *reclaimlist = NULL;
581 size_t need_size;
582 fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
583 fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
584 fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
585 fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));
586 fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc));
587 need_size = table->sizefunc(entry->key, data);
588 if (cb_arg == NULL) cb_arg = table->cb_arg;
589
590 /* find bin */
591 lock_quick_lock(&table->lock);
592 bin = &table->array[hash & table->size_mask];
593 lock_quick_lock(&bin->lock);
594
595 /* see if entry exists already */
596 if ((found = bin_find_entry(table, bin, hash, entry->key)) != NULL) {
597 /* if so: keep the existing data - acquire a writelock */
598 lock_rw_wrlock(&found->lock);
599 }
600 else
601 {
602 /* if not: add to bin */
603 entry->overflow_next = bin->overflow_list;
604 bin->overflow_list = entry;
605 lru_front(table, entry);
606 table->num++;
607 table->space_used += need_size;
608 /* return the entry that was presented, and lock it */
609 found = entry;
610 lock_rw_wrlock(&found->lock);
611 }
612 lock_quick_unlock(&bin->lock);
613 if (table->space_used > table->space_max)
614 reclaim_space(table, &reclaimlist);
615 if (table->num >= table->size)
616 table_grow(table);
617 lock_quick_unlock(&table->lock);
618
619 /* finish reclaim if any (outside of critical region) */
620 while (reclaimlist) {
621 struct lruhash_entry* n = reclaimlist->overflow_next;
622 void* d = reclaimlist->data;
623 (*table->delkeyfunc)(reclaimlist->key, cb_arg);
624 (*table->deldatafunc)(d, cb_arg);
625 reclaimlist = n;
626 }
627
628 /* return the entry that was selected */
629 return found;
630}
631