Lines Matching refs:ltable
136 #define ELEMENT_PTR(ltable, i) \
137 ((void*)(((char*)(ltable)->table) + (ltable)->elem_size * (i)))
146 #define SANITY_CHECK_INDEX(ltable,i) SANITY_CHECK((i) < ltable->next_index)
200 get_key(LookupTable *ltable, TableIndex index, void **pkey_ptr, int *pkey_len)
202 *pkey_ptr = ((TableElement*)ELEMENT_PTR(ltable,index))->key.ptr;
203 *pkey_len = ((TableElement*)ELEMENT_PTR(ltable,index))->key.len;
207 get_info(LookupTable *ltable, TableIndex index)
211 if ( ltable->info_size == 0 ) {
214 element = (TableElement*)ELEMENT_PTR(ltable,index);
219 hash_out(LookupTable *ltable, TableIndex index)
221 if ( ltable->hash_bucket_count > 0 ) {
227 element = (TableElement*)ELEMENT_PTR(ltable,index);
228 bucket = (element->hcode % ltable->hash_bucket_count);
229 i = ltable->hash_buckets[bucket];
233 prev_e = (TableElement*)ELEMENT_PTR(ltable,i);
238 ltable->hash_buckets[bucket] = element->next;
248 is_freed_entry(LookupTable *ltable, TableIndex index)
250 if ( ltable->freed_bv == NULL ) {
253 if ( ( BV_CHUNK(ltable->freed_bv, index) & BV_CHUNK_MASK(index) ) != 0 ) {
260 set_freed_bit(LookupTable *ltable, TableIndex index)
264 HPROF_ASSERT(!is_freed_entry(ltable, index));
265 p = ltable->freed_bv;
270 HPROF_ASSERT(ltable->freed_start==0);
271 HPROF_ASSERT(ltable->freed_start==0);
272 size = BV_ELEMENT_COUNT(ltable->table_size);
274 ltable->freed_bv = p;
278 ltable->freed_count++;
279 if ( ltable->freed_count == 1 ) {
281 HPROF_ASSERT(ltable->freed_start==0);
282 ltable->freed_start = index;
283 } else if ( index < ltable->freed_start ) {
285 HPROF_ASSERT(ltable->freed_start!=0);
286 ltable->freed_start = index;
288 HPROF_ASSERT(ltable->freed_start!=0);
289 HPROF_ASSERT(ltable->freed_start < ltable->next_index);
290 HPROF_ASSERT(is_freed_entry(ltable, index));
294 find_freed_entry(LookupTable *ltable)
296 if ( ltable->freed_count > 0 ) {
304 p = ltable->freed_bv;
308 HPROF_ASSERT(ltable->freed_start!=0);
309 HPROF_ASSERT(ltable->freed_start < ltable->next_index);
310 istart = BV_CHUNK_ROUND(ltable->freed_start);
314 for( ; istart < ltable->next_index ; istart += BV_CHUNK_BITSIZE ) {
322 HPROF_ASSERT(istart < ltable->next_index);
333 ltable->freed_count--;
334 HPROF_ASSERT(i < ltable->next_index);
335 if ( ltable->freed_count > 0 ) {
337 HPROF_ASSERT((i+1) < ltable->next_index);
338 ltable->freed_start = i+1;
341 ltable->freed_start = 0;
343 HPROF_ASSERT(!is_freed_entry(ltable, i));
353 free_entry(LookupTable *ltable, TableIndex index)
355 set_freed_bit(ltable, index);
356 hash_out(ltable, index);
389 hash_in(LookupTable *ltable, TableIndex index, HashCode hcode)
391 if ( ltable->hash_bucket_count > 0 ) {
395 bucket = (hcode % ltable->hash_bucket_count);
396 element = (TableElement*)ELEMENT_PTR(ltable, index);
398 element->next = ltable->hash_buckets[bucket];
399 ltable->hash_buckets[bucket] = index;
404 resize_hash_buckets(LookupTable *ltable)
411 if ( ( ltable->hash_bucket_count < (ltable->next_index >> 4) )
412 && ( ltable->hash_bucket_count > 0 )
413 && ( ( ltable->resizes % 10 ) == 0 )
414 && ( ltable->bucket_walks > 1000*ltable->hash_bucket_count )
424 LOG3("Table resize", ltable->name, ltable->resizes);
426 old_size = ltable->hash_bucket_count;
427 old_buckets = ltable->hash_buckets;
428 new_size = (ltable->next_index >> 3); /* 1/8 current used count */
432 ltable->hash_bucket_count = new_size;
433 ltable->hash_buckets = new_buckets;
443 element = (TableElement*)ELEMENT_PTR(ltable, index);
446 hash_in(ltable, index, element->hcode);
452 ltable->bucket_walks = 0;
457 resize(LookupTable *ltable)
466 LOG3("Table resize", ltable->name, ltable->resizes);
471 old_size = ltable->table_size;
472 if ( ltable->table_incr < (unsigned)(old_size >> 2) ) {
473 ltable->table_incr = (old_size >> 2);
475 if ( ltable->table_incr < 512 ) {
476 ltable->table_incr = 512;
478 new_size = old_size + ltable->table_incr;
481 obytes = old_size * ltable->elem_size;
482 nbytes = new_size * ltable->elem_size;
483 old_table = ltable->table;
487 ltable->table = new_table;
488 ltable->table_size = new_size;
492 if ( ltable->freed_bv != NULL ) {
498 old_bv = ltable->freed_bv;
502 ltable->freed_bv = new_bv;
507 resize_hash_buckets(ltable);
509 ltable->resizes++;
543 find_entry(LookupTable *ltable, void *key_ptr, int key_len, HashCode hcode)
547 HPROF_ASSERT(ltable!=NULL);
550 if ( ltable->hash_bucket_count > 0 ) {
557 bucket = (hcode % ltable->hash_bucket_count);
558 index = ltable->hash_buckets[bucket];
563 element = (TableElement*)ELEMENT_PTR(ltable, index);
569 prev_element = (TableElement*)ELEMENT_PTR(ltable, prev_index);
571 element->next = ltable->hash_buckets[bucket];
572 ltable->hash_buckets[bucket] = index;
578 ltable->bucket_walks++;
585 setup_new_entry(LookupTable *ltable, void *key_ptr, int key_len, void *info_ptr)
598 if ( ltable->freed_count > 0 ) {
599 index = find_freed_entry(ltable);
605 element = (TableElement*)ELEMENT_PTR(ltable, index);
609 (void)memset(element, 0, ltable->elem_size);
623 if ( ltable->next_index >= ltable->table_size ) {
624 resize(ltable);
626 index = ltable->next_index++;
627 element = (TableElement*)ELEMENT_PTR(ltable, index);
631 if ( ltable->info_size > 0 ) {
633 info = blocks_alloc(ltable->info_blocks, ltable->info_size);
636 (void)memset(info, 0, ltable->info_size);
638 (void)memcpy(info, info_ptr, ltable->info_size);
645 dup_key = blocks_alloc(ltable->key_blocks, key_len);
662 LookupTable * ltable;
674 ltable = (LookupTable *)HPROF_MALLOC((int)sizeof(LookupTable));
675 (void)memset(ltable, 0, (int)sizeof(LookupTable));
677 (void)strncpy(ltable->name, name, sizeof(ltable->name));
681 ltable->next_index = 1; /* Never use index 0 */
682 ltable->table_size = size;
683 ltable->table_incr = incr;
684 ltable->hash_bucket_count = bucket_count;
685 ltable->elem_size = elem_size;
686 ltable->info_size = info_size;
688 ltable->info_blocks = blocks_init(8, info_size, incr);
691 ltable->key_blocks = blocks_init(8, key_size, incr);
693 ltable->table = HPROF_MALLOC(size * elem_size);
694 (void)memset(ltable->table, 0, size * elem_size);
699 ltable->hash_buckets = (TableIndex*)HPROF_MALLOC(nbytes);
700 (void)memset(ltable->hash_buckets, 0, nbytes);
706 ltable->lock = lock_create(lock_name);
707 ltable->serial_num = gdata->table_serial_number_counter++;
708 ltable->hare = (ltable->serial_num << 28);
710 LOG3("Table initialized", ltable->name, ltable->table_size);
711 return ltable;
715 table_element_count(LookupTable *ltable)
719 HPROF_ASSERT(ltable!=NULL);
721 lock_enter(ltable->lock); {
722 nelems = ltable->next_index-1;
723 } lock_exit(ltable->lock);
729 table_free_entry(LookupTable *ltable, TableIndex index)
731 HPROF_ASSERT(ltable!=NULL);
732 SANITY_CHECK_HARE(index, ltable->hare);
734 SANITY_CHECK_INDEX(ltable, index);
736 lock_enter(ltable->lock); {
737 HPROF_ASSERT(!is_freed_entry(ltable, index));
738 free_entry(ltable, index);
739 } lock_exit(ltable->lock);
743 table_walk_items(LookupTable *ltable, LookupTableIterator func, void* arg)
745 if ( ltable == NULL || ltable->next_index <= 1 ) {
750 lock_enter(ltable->lock); {
754 LOG3("table_walk_items() count+free", ltable->name, ltable->next_index);
756 for ( index = 1 ; index < ltable->next_index ; index++ ) {
757 if ( ! is_freed_entry(ltable, index) ) {
762 get_key(ltable, index, &key_ptr, &key_len);
763 info = get_info(ltable, index);
764 (*func)(SANITY_ADD_HARE(index, ltable->hare), key_ptr, key_len, info, arg);
765 if ( is_freed_entry(ltable, index) ) {
772 LOG3("table_walk_items() count-free", ltable->name, ltable->next_index);
773 HPROF_ASSERT(fcount==ltable->freed_count);
774 } lock_exit(ltable->lock);
778 table_cleanup(LookupTable *ltable, LookupTableIterator func, void *arg)
780 if ( ltable == NULL ) {
785 table_walk_items(ltable, func, arg);
788 lock_enter(ltable->lock); {
790 HPROF_FREE(ltable->table);
791 if ( ltable->hash_buckets != NULL ) {
792 HPROF_FREE(ltable->hash_buckets);
794 if ( ltable->freed_bv != NULL ) {
795 HPROF_FREE(ltable->freed_bv);
797 if ( ltable->info_blocks != NULL ) {
798 blocks_term(ltable->info_blocks);
799 ltable->info_blocks = NULL;
801 if ( ltable->key_blocks != NULL ) {
802 blocks_term(ltable->key_blocks);
803 ltable->key_blocks = NULL;
806 } lock_exit(ltable->lock);
808 lock_destroy(ltable->lock);
809 ltable->lock = NULL;
811 HPROF_FREE(ltable);
812 ltable = NULL;
816 table_create_entry(LookupTable *ltable, void *key_ptr, int key_len, void *info_ptr)
821 HPROF_ASSERT(ltable!=NULL);
825 if ( ltable->hash_bucket_count > 0 ) {
830 lock_enter(ltable->lock); {
833 index = setup_new_entry(ltable, key_ptr, key_len, info_ptr);
836 if ( ltable->hash_bucket_count > 0 ) {
837 hash_in(ltable, index, hcode);
840 } lock_exit(ltable->lock);
841 return SANITY_ADD_HARE(index, ltable->hare);
845 table_find_entry(LookupTable *ltable, void *key_ptr, int key_len)
852 if ( ltable->hash_bucket_count > 0 ) {
857 lock_enter(ltable->lock); {
858 index = find_entry(ltable, key_ptr, key_len, hcode);
859 } lock_exit(ltable->lock);
861 return index==0 ? index : SANITY_ADD_HARE(index, ltable->hare);
865 table_find_or_create_entry(LookupTable *ltable, void *key_ptr, int key_len,
878 if ( ltable->hash_bucket_count > 0 ) {
884 lock_enter(ltable->lock); {
885 if ( ltable->hash_bucket_count > 0 ) {
886 index = find_entry(ltable, key_ptr, key_len, hcode);
891 index = setup_new_entry(ltable, key_ptr, key_len, info_ptr);
894 if ( ltable->hash_bucket_count > 0 ) {
895 hash_in(ltable, index, hcode);
902 } lock_exit(ltable->lock);
904 return SANITY_ADD_HARE(index, ltable->hare);
908 table_get_info(LookupTable *ltable, TableIndex index)
912 HPROF_ASSERT(ltable!=NULL);
913 HPROF_ASSERT(ltable->info_size > 0);
914 SANITY_CHECK_HARE(index, ltable->hare);
916 SANITY_CHECK_INDEX(ltable, index);
918 lock_enter(ltable->lock); {
919 HPROF_ASSERT(!is_freed_entry(ltable, index));
920 info = get_info(ltable,index);
921 } lock_exit(ltable->lock);
927 table_get_key(LookupTable *ltable, TableIndex index, void **pkey_ptr, int *pkey_len)
929 HPROF_ASSERT(ltable!=NULL);
932 SANITY_CHECK_HARE(index, ltable->hare);
933 HPROF_ASSERT(ltable->elem_size!=0);
935 SANITY_CHECK_INDEX(ltable, index);
937 lock_enter(ltable->lock); {
938 HPROF_ASSERT(!is_freed_entry(ltable, index));
939 get_key(ltable, index, pkey_ptr, pkey_len);
940 } lock_exit(ltable->lock);
944 table_lock_enter(LookupTable *ltable)
946 lock_enter(ltable->lock);
950 table_lock_exit(LookupTable *ltable)
952 lock_exit(ltable->lock);