Lines Matching full:table
67 struct lruhash* table = (struct lruhash*)calloc(1,
69 if(!table)
71 lock_quick_init(&table->lock);
72 table->sizefunc = sizefunc;
73 table->compfunc = compfunc;
74 table->delkeyfunc = delkeyfunc;
75 table->deldatafunc = deldatafunc;
76 table->cb_arg = arg;
77 table->size = start_size;
78 table->size_mask = (int)(start_size-1);
79 table->lru_start = NULL;
80 table->lru_end = NULL;
81 table->num = 0;
82 table->space_used = 0;
83 table->space_max = maxmem;
84 table->max_collisions = 0;
85 table->array = calloc(table->size, sizeof(struct lruhash_bin));
86 if(!table->array) {
87 lock_quick_destroy(&table->lock);
88 free(table);
91 bin_init(table->array, table->size);
92 lock_protect(&table->lock, table, sizeof(*table));
93 lock_protect(&table->lock, table->array,
94 table->size*sizeof(struct lruhash_bin));
95 return table;
99 bin_delete(struct lruhash* table, struct lruhash_bin* bin)
111 (*table->delkeyfunc)(p->key, table->cb_arg);
112 (*table->deldatafunc)(d, table->cb_arg);
118 bin_split(struct lruhash* table, struct lruhash_bin* newa,
124 /* move entries to new table. Notice that since hash x is mapped to
128 int newbit = newmask - table->size_mask;
132 for(i=0; i<table->size; i++)
134 lock_quick_lock(&table->array[i].lock);
135 p = table->array[i].overflow_list;
149 lock_quick_unlock(&table->array[i].lock);
154 lruhash_delete(struct lruhash* table)
157 if(!table)
160 lock_quick_destroy(&table->lock);
161 for(i=0; i<table->size; i++)
162 bin_delete(table, &table->array[i]);
163 free(table->array);
164 free(table);
183 reclaim_space(struct lruhash* table, struct lruhash_entry** list)
187 log_assert(table);
188 /* does not delete MRU entry, so table will not be empty. */
189 while(table->num > 1 && table->space_used > table->space_max) {
196 d = table->lru_end;
200 table->lru_end = d->lru_prev;
203 bin = &table->array[d->hash & table->size_mask];
204 table->num --;
210 table->space_used -= table->sizefunc(d->key, d->data);
211 if(table->markdelfunc)
212 (*table->markdelfunc)(d->key);
219 bin_find_entry(struct lruhash* table,
225 if(p->hash == hash && table->compfunc(p->key, key) == 0)
236 table_grow(struct lruhash* table)
241 if(table->size_mask == (int)(((size_t)-1)>>1)) {
246 newa = calloc(table->size*2, sizeof(struct lruhash_bin));
252 bin_init(newa, table->size*2);
253 newmask = (table->size_mask << 1) | 1;
254 bin_split(table, newa, newmask);
256 lock_unprotect(&table->lock, table->array);
257 for(i=0; i<table->size; i++) {
258 lock_quick_destroy(&table->array[i].lock);
260 free(table->array);
262 table->size *= 2;
263 table->size_mask = newmask;
264 table->array = newa;
265 lock_protect(&table->lock, table->array,
266 table->size*sizeof(struct lruhash_bin));
271 lru_front(struct lruhash* table, struct lruhash_entry* entry)
274 entry->lru_next = table->lru_start;
275 if(!table->lru_start)
276 table->lru_end = entry;
277 else table->lru_start->lru_prev = entry;
278 table->lru_start = entry;
282 lru_remove(struct lruhash* table, struct lruhash_entry* entry)
286 else table->lru_start = entry->lru_next;
289 else table->lru_end = entry->lru_prev;
293 lru_touch(struct lruhash* table, struct lruhash_entry* entry)
295 log_assert(table && entry);
296 if(entry == table->lru_start)
299 lru_remove(table, entry);
301 lru_front(table, entry);
305 lruhash_insert(struct lruhash* table, hashvalue_type hash,
312 fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
313 fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
314 fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
315 fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));
316 fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc));
317 need_size = table->sizefunc(entry->key, data);
318 if(cb_arg == NULL) cb_arg = table->cb_arg;
321 lock_quick_lock(&table->lock);
322 bin = &table->array[hash & table->size_mask];
326 if(!(found=bin_find_entry(table, bin, hash, entry->key, &collisions))) {
330 lru_front(table, entry);
331 table->num++;
332 if (table->max_collisions < collisions)
333 table->max_collisions = collisions;
334 table->space_used += need_size;
337 table->space_used += need_size -
338 (*table->sizefunc)(found->key, found->data);
339 (*table->delkeyfunc)(entry->key, cb_arg);
340 lru_touch(table, found);
342 (*table->deldatafunc)(found->data, cb_arg);
347 if(table->space_used > table->space_max)
348 reclaim_space(table, &reclaimlist);
349 if(table->num >= table->size)
350 table_grow(table);
351 lock_quick_unlock(&table->lock);
357 (*table->delkeyfunc)(reclaimlist->key, cb_arg);
358 (*table->deldatafunc)(d, cb_arg);
364 lruhash_lookup(struct lruhash* table, hashvalue_type hash, void* key, int wr)
368 fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));
370 lock_quick_lock(&table->lock);
371 bin = &table->array[hash & table->size_mask];
373 if((entry=bin_find_entry(table, bin, hash, key, NULL)))
374 lru_touch(table, entry);
375 lock_quick_unlock(&table->lock);
386 lruhash_remove(struct lruhash* table, hashvalue_type hash, void* key)
391 fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
392 fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
393 fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
394 fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));
395 fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc));
397 lock_quick_lock(&table->lock);
398 bin = &table->array[hash & table->size_mask];
400 if((entry=bin_find_entry(table, bin, hash, key, NULL))) {
402 lru_remove(table, entry);
404 lock_quick_unlock(&table->lock);
408 table->num--;
409 table->space_used -= (*table->sizefunc)(entry->key, entry->data);
411 if(table->markdelfunc)
412 (*table->markdelfunc)(entry->key);
415 lock_quick_unlock(&table->lock);
418 (*table->delkeyfunc)(entry->key, table->cb_arg);
419 (*table->deldatafunc)(d, table->cb_arg);
424 bin_clear(struct lruhash* table, struct lruhash_bin* bin)
434 if(table->markdelfunc)
435 (*table->markdelfunc)(p->key);
437 (*table->delkeyfunc)(p->key, table->cb_arg);
438 (*table->deldatafunc)(d, table->cb_arg);
446 lruhash_clear(struct lruhash* table)
449 if(!table)
451 fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
452 fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
453 fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc));
455 lock_quick_lock(&table->lock);
456 for(i=0; i<table->size; i++) {
457 bin_clear(table, &table->array[i]);
459 table->lru_start = NULL;
460 table->lru_end = NULL;
461 table->num = 0;
462 table->space_used = 0;
463 lock_quick_unlock(&table->lock);
467 lruhash_status(struct lruhash* table, const char* id, int extended)
469 lock_quick_lock(&table->lock);
471 id, (unsigned)table->num, (unsigned)table->space_used,
472 (unsigned)table->space_max);
474 (unsigned)(table->num? table->space_used/table->num : 0),
475 (unsigned)table->size, table->size_mask);
478 int min=(int)table->size*2, max=-2;
479 for(i=0; i<table->size; i++) {
482 lock_quick_lock(&table->array[i].lock);
483 en = table->array[i].overflow_list;
488 lock_quick_unlock(&table->array[i].lock);
495 (double)table->num/(double)table->size, max);
497 lock_quick_unlock(&table->lock);
501 lruhash_get_mem(struct lruhash* table)
504 lock_quick_lock(&table->lock);
505 s = sizeof(struct lruhash) + table->space_used;
507 if(table->size != 0) {
509 for(i=0; i<table->size; i++)
511 lock_get_mem(&table->array[i].lock);
514 if(table->size != 0)
515 s += (table->size)*(sizeof(struct lruhash_bin) +
516 lock_get_mem(&table->array[0].lock));
518 lock_quick_unlock(&table->lock);
519 s += lock_get_mem(&table->lock);
524 lruhash_setmarkdel(struct lruhash* table, lruhash_markdelfunc_type md)
526 lock_quick_lock(&table->lock);
527 table->markdelfunc = md;
528 lock_quick_unlock(&table->lock);
532 lruhash_update_space_used(struct lruhash* table, void* cb_arg, int diff_size)
536 fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
537 fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
538 fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
539 fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc));
541 if(cb_arg == NULL) cb_arg = table->cb_arg;
544 lock_quick_lock(&table->lock);
546 if((int)table->space_used + diff_size < 0)
547 table->space_used = 0;
548 else table->space_used = (size_t)((int)table->space_used + diff_size);
550 if(table->space_used > table->space_max)
551 reclaim_space(table, &reclaimlist);
553 lock_quick_unlock(&table->lock);
559 (*table->delkeyfunc)(reclaimlist->key, cb_arg);
560 (*table->deldatafunc)(d, cb_arg);
565 void lruhash_update_space_max(struct lruhash* table, void* cb_arg, size_t max)
569 fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
570 fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
571 fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
572 fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc));
574 if(cb_arg == NULL) cb_arg = table->cb_arg;
577 lock_quick_lock(&table->lock);
578 table->space_max = max;
580 if(table->space_used > table->space_max)
581 reclaim_space(table, &reclaimlist);
583 lock_quick_unlock(&table->lock);
589 (*table->delkeyfunc)(reclaimlist->key, cb_arg);
590 (*table->deldatafunc)(d, cb_arg);
625 lru_demote(struct lruhash* table, struct lruhash_entry* entry)
627 log_assert(table && entry);
628 if (entry == table->lru_end)
631 lru_remove(table, entry);
634 entry->lru_prev = table->lru_end;
636 if (table->lru_end == NULL)
638 table->lru_start = entry;
642 table->lru_end->lru_next = entry;
644 table->lru_end = entry;
648 lruhash_insert_or_retrieve(struct lruhash* table, hashvalue_type hash,
655 fptr_ok(fptr_whitelist_hash_sizefunc(table->sizefunc));
656 fptr_ok(fptr_whitelist_hash_delkeyfunc(table->delkeyfunc));
657 fptr_ok(fptr_whitelist_hash_deldatafunc(table->deldatafunc));
658 fptr_ok(fptr_whitelist_hash_compfunc(table->compfunc));
659 fptr_ok(fptr_whitelist_hash_markdelfunc(table->markdelfunc));
660 need_size = table->sizefunc(entry->key, data);
661 if (cb_arg == NULL) cb_arg = table->cb_arg;
664 lock_quick_lock(&table->lock);
665 bin = &table->array[hash & table->size_mask];
669 if ((found = bin_find_entry(table, bin, hash, entry->key, &collisions)) != NULL) {
678 lru_front(table, entry);
679 table->num++;
680 if (table->max_collisions < collisions)
681 table->max_collisions = collisions;
682 table->space_used += need_size;
688 if (table->space_used > table->space_max)
689 reclaim_space(table, &reclaimlist);
690 if (table->num >= table->size)
691 table_grow(table);
692 lock_quick_unlock(&table->lock);
698 (*table->delkeyfunc)(reclaimlist->key, cb_arg);
699 (*table->deldatafunc)(d, cb_arg);