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