hprof_table.c

来自「一个小公司要求给写的很简单的任务管理系统。」· C语言 代码 · 共 951 行 · 第 1/2 页

    obytes    = old_size * ltable->elem_size;
    nbytes    = new_size * ltable->elem_size;
    old_table = ltable->table;
    new_table = HPROF_MALLOC(nbytes);
    (void)memcpy(new_table, old_table, obytes);
    (void)memset(((char*)new_table)+obytes, 0, nbytes-obytes);
    ltable->table      = new_table;
    ltable->table_size = new_size;
    HPROF_FREE(old_table);

    /* Then bit vector for freed entries */
    if ( ltable->freed_bv != NULL ) {
	void *old_bv;
        void *new_bv;

        obytes = BV_ELEMENT_COUNT(old_size)*(int)sizeof(BV_CHUNK_TYPE);
        nbytes = BV_ELEMENT_COUNT(new_size)*(int)sizeof(BV_CHUNK_TYPE);
	old_bv = ltable->freed_bv;
        new_bv = HPROF_MALLOC(nbytes);
        (void)memcpy(new_bv, old_bv, obytes);
        (void)memset(((char*)new_bv)+obytes, 0, nbytes-obytes);
        ltable->freed_bv = new_bv;
        HPROF_FREE(old_bv);
    }

    /* Check to see if the hash table needs resizing */
    resize_hash_buckets(ltable);

    ltable->resizes++;
}

static jboolean
keys_equal(void *key_ptr1, void *key_ptr2, int key_len)
{
    unsigned char *     p1;
    unsigned char *     p2;
    int                 i;
   
    if ( key_len == 0 ) {
	return JNI_TRUE;
    }

    /* We know these are aligned because we malloc'd them. */

    /* Compare word by word, then byte by byte */
    p1 = (unsigned char*)key_ptr1;
    p2 = (unsigned char*)key_ptr2;
    for ( i = 0 ; i < key_len-3 ; i += 4 ) {
	/*LINTED*/
        if ( *(unsigned*)(p1+i) != *(unsigned*)(p2+i) ) {
	    return JNI_FALSE;
	}
    }
    for ( ; i < key_len ; i++ ) {
        if ( p1[i] != p2[i] ) {
	    return JNI_FALSE;
	}
    }
    return JNI_TRUE;
}

static TableIndex
find_entry(LookupTable *ltable, void *key_ptr, int key_len, HashCode hcode)
{
    TableIndex index;

    HPROF_ASSERT(ltable!=NULL);
    
    index = 0;
    if ( ltable->hash_bucket_count > 0 ) {
	TableIndex bucket;
	TableIndex prev_index;
	
	HPROF_ASSERT(key_ptr!=NULL);
	HPROF_ASSERT(key_len>0);
	prev_index  = 0;
	bucket      = (hcode % ltable->hash_bucket_count);
	index       = ltable->hash_buckets[bucket];
	while ( index != 0 ) {
	    TableElement *element;
	    TableElement *prev_element;

	    element = (TableElement*)ELEMENT_PTR(ltable, index);
	    if ( hcode == element->hcode &&
		 key_len == element->key.len &&
		 keys_equal(key_ptr, element->key.ptr, key_len) ) {
		/* Place this guy at the head of the bucket list */
		if ( prev_index != 0 ) {
		    prev_element = (TableElement*)ELEMENT_PTR(ltable, prev_index);
		    prev_element->next  = element->next;
		    element->next       = ltable->hash_buckets[bucket];
		    ltable->hash_buckets[bucket]    = index;
		}
		break;
	    }
	    prev_index = index;
	    index      = element->next;
	    ltable->bucket_walks++;
	}
    }
    return index;
}

static TableIndex
setup_new_entry(LookupTable *ltable, void *key_ptr, int key_len, void *info_ptr)
{
    TableIndex    index;
    TableElement *element;
    void         *info;
    void         *dup_key;
   
    /* Assume we need new allocations for key and info */
    dup_key  = NULL;
    info     = NULL;
   
    /* Look for a freed element */
    index = 0;
    if ( ltable->freed_count > 0 ) {
        index    = find_freed_entry(ltable);
    }
    if ( index != 0 ) {
	int old_key_len;

	/* Found a freed element, re-use what we can but clean it up. */
	element     = (TableElement*)ELEMENT_PTR(ltable, index);
	dup_key     = element->key.ptr;
	old_key_len = element->key.len;
	info        = element->info;
	(void)memset(element, 0, ltable->elem_size);
	
	/* Toss the key space if size is too small to hold new key */
	if ( key_ptr != NULL ) {
	    if ( old_key_len < key_len ) {
		/* This could leak space in the Blocks if keys are variable
		 *    in size AND the table does frees of elements.
		 */
		dup_key = NULL;
	    }
	}
    } else {

	/* Brand new table element */
	if ( ltable->next_index >= ltable->table_size ) {
	    resize(ltable);
	}
        index = ltable->next_index++;
        element = (TableElement*)ELEMENT_PTR(ltable, index);
    }

    /* Setup info area */
    if ( ltable->info_size > 0 ) {
	if ( info == NULL ) {
	    info = blocks_alloc(ltable->info_blocks, ltable->info_size);
        } 
	if ( info_ptr==NULL ) {
	    (void)memset(info, 0, ltable->info_size);
	} else {
	    (void)memcpy(info, info_ptr, ltable->info_size);
	}
    }
   
    /* Setup key area if one was provided */
    if ( key_ptr != NULL ) {
	if ( dup_key == NULL ) {
	    dup_key  = blocks_alloc(ltable->key_blocks, key_len);
	}
	(void)memcpy(dup_key, key_ptr, key_len);
    }
	
    /* Fill in element */
    element->key.ptr = dup_key;
    element->key.len = key_len;
    element->info    = info;

    return index;
}

LookupTable *
table_initialize(const char *name, int size, int incr, int bucket_count, 
			int info_size)
{
    LookupTable * ltable;
    char          lock_name[80];
    int           elem_size;
    int           key_size;
    
    HPROF_ASSERT(name!=NULL);
    HPROF_ASSERT(size>0);
    HPROF_ASSERT(incr>0);
    HPROF_ASSERT(bucket_count>=0);
    HPROF_ASSERT(info_size>=0);
  
    key_size = 1;
    ltable = (LookupTable *)HPROF_MALLOC((int)sizeof(LookupTable));
    (void)memset(ltable, 0, (int)sizeof(LookupTable));

    (void)strncpy(ltable->name, name, sizeof(ltable->name));
    
    elem_size = (int)sizeof(TableElement);

    ltable->next_index          = 1; /* Never use index 0 */
    ltable->table_size          = size;
    ltable->table_incr          = incr;
    ltable->hash_bucket_count   = bucket_count;
    ltable->elem_size           = elem_size;
    ltable->info_size           = info_size;
    if ( info_size > 0 ) {
        ltable->info_blocks     = blocks_init(8, info_size, incr);
    }
    if ( key_size > 0 ) {
        ltable->key_blocks      = blocks_init(8, key_size, incr);
    }
    ltable->table               = HPROF_MALLOC(size * elem_size);
    (void)memset(ltable->table, 0, size * elem_size);
    if ( bucket_count > 0 ) {
	int nbytes;
	
	nbytes               = (int)(bucket_count*sizeof(TableIndex));
	ltable->hash_buckets = (TableIndex*)HPROF_MALLOC(nbytes);
        (void)memset(ltable->hash_buckets, 0, nbytes);
    }

    (void)md_snprintf(lock_name, sizeof(lock_name),
                "HPROF %s table lock", name);
    lock_name[sizeof(lock_name)-1] = 0; 
    ltable->lock        = lock_create(lock_name);
    ltable->serial_num  = gdata->table_serial_number_counter++;
    ltable->hare        = (ltable->serial_num << 28);
    
    LOG3("Table initialized", ltable->name, ltable->table_size);
    return ltable;
}

int
table_element_count(LookupTable *ltable)
{
    int nelems;
    
    HPROF_ASSERT(ltable!=NULL);
    
    lock_enter(ltable->lock); {
        nelems = ltable->next_index-1;
    } lock_exit(ltable->lock);
    
    return nelems;
}

void                    
table_free_entry(LookupTable *ltable, TableIndex index)
{
    HPROF_ASSERT(ltable!=NULL);
    SANITY_CHECK_HARE(index, ltable->hare);
    index = SANITY_REMOVE_HARE(index);
    SANITY_CHECK_INDEX(ltable, index);
    
    lock_enter(ltable->lock); {
        HPROF_ASSERT(!is_freed_entry(ltable, index));
	free_entry(ltable, index);
    } lock_exit(ltable->lock);
}

void
table_walk_items(LookupTable *ltable, LookupTableIterator func, void* arg)
{
    if ( ltable == NULL || ltable->next_index <= 1 ) {
	return;
    }
    HPROF_ASSERT(func!=NULL);
    
    lock_enter(ltable->lock); {
        TableIndex index;
	int        fcount;

        LOG3("table_walk_items() count+free", ltable->name, ltable->next_index);
	fcount = 0;
	for ( index = 1 ; index < ltable->next_index ; index++ ) {
	    if ( ! is_freed_entry(ltable, index) ) {
		void *key_ptr;
		int   key_len;
		void *info;
		
		get_key(ltable, index, &key_ptr, &key_len);
		info = get_info(ltable, index);
		(*func)(SANITY_ADD_HARE(index, ltable->hare), key_ptr, key_len, info, arg);
		if ( is_freed_entry(ltable, index) ) {
		    fcount++;
		}
	    } else {
		fcount++;
	    }
        }
        LOG3("table_walk_items() count-free", ltable->name, ltable->next_index);
	HPROF_ASSERT(fcount==ltable->freed_count);
    } lock_exit(ltable->lock);
}

void
table_cleanup(LookupTable *ltable, LookupTableIterator func, void *arg)
{
    if ( ltable == NULL ) {
	return;
    }

    if ( func != NULL ) {
	table_walk_items(ltable, func, arg);
    }

    lock_enter(ltable->lock); {

        HPROF_FREE(ltable->table);
        if ( ltable->hash_buckets != NULL ) {
	    HPROF_FREE(ltable->hash_buckets);
        }
	if ( ltable->freed_bv != NULL ) {
	    HPROF_FREE(ltable->freed_bv);
        } 
	if ( ltable->info_blocks != NULL ) {
	    blocks_term(ltable->info_blocks);
	    ltable->info_blocks = NULL;
	}
	if ( ltable->key_blocks != NULL ) {
	    blocks_term(ltable->key_blocks);
	    ltable->key_blocks = NULL;
	}

    } lock_exit(ltable->lock);
    
    lock_destroy(ltable->lock);
    ltable->lock = NULL;
    
    HPROF_FREE(ltable);
    ltable = NULL;
}

TableIndex
table_create_entry(LookupTable *ltable, void *key_ptr, int key_len, void *info_ptr)
{
    TableIndex index;
    HashCode   hcode;
    
    HPROF_ASSERT(ltable!=NULL);
   
    /* Create hash code if needed */
    hcode = 0;
    if ( ltable->hash_bucket_count > 0 ) {
	hcode = hashcode(key_ptr, key_len);
    }
    
    /* Create a new entry */
    lock_enter(ltable->lock); {
        
	/* Need to create a new entry */
	index = setup_new_entry(ltable, key_ptr, key_len, info_ptr);
	
	/* Add to hash table if we have one */
	if ( ltable->hash_bucket_count > 0 ) {
	    hash_in(ltable, index, hcode);
	}
    
    } lock_exit(ltable->lock);
    return SANITY_ADD_HARE(index, ltable->hare);
}

TableIndex
table_find_entry(LookupTable *ltable, void *key_ptr, int key_len)
{
    TableIndex index;
    HashCode   hcode;
    
    /* Create hash code if needed */
    hcode = 0;
    if ( ltable->hash_bucket_count > 0 ) {
	hcode = hashcode(key_ptr, key_len);
    }
   
    /* Look for element */
    lock_enter(ltable->lock); {
        index = find_entry(ltable, key_ptr, key_len, hcode);
    } lock_exit(ltable->lock);
    
    return index==0 ? index : SANITY_ADD_HARE(index, ltable->hare);
}

TableIndex
table_find_or_create_entry(LookupTable *ltable, void *key_ptr, int key_len,
		jboolean *pnew_entry, void *info_ptr)
{
    TableIndex index;
    HashCode   hcode;
   
    /* Assume it is NOT a new entry for now */
    if ( pnew_entry ) {
	*pnew_entry = JNI_FALSE;
    }
    
    /* Create hash code if needed */
    hcode = 0;
    if ( ltable->hash_bucket_count > 0 ) {
	hcode = hashcode(key_ptr, key_len);
    }
    
    /* Look for element */
    index = 0;
    lock_enter(ltable->lock); {
	if ( ltable->hash_bucket_count > 0 ) {
	    index = find_entry(ltable, key_ptr, key_len, hcode);
	}
	if ( index == 0 ) {
	    
	    /* Need to create a new entry */
	    index = setup_new_entry(ltable, key_ptr, key_len, info_ptr);
	    
	    /* Add to hash table if we have one */
	    if ( ltable->hash_bucket_count > 0 ) {
		hash_in(ltable, index, hcode);
	    }
	    
	    if ( pnew_entry ) {
		*pnew_entry = JNI_TRUE;
	    }
	}
    } lock_exit(ltable->lock);
    
    return SANITY_ADD_HARE(index, ltable->hare);
}

void *
table_get_info(LookupTable *ltable, TableIndex index)
{
    void *info;
    
    HPROF_ASSERT(ltable!=NULL);
    HPROF_ASSERT(ltable->info_size > 0);
    SANITY_CHECK_HARE(index, ltable->hare);
    index = SANITY_REMOVE_HARE(index);
    SANITY_CHECK_INDEX(ltable, index);
    
    lock_enter(ltable->lock); {
        HPROF_ASSERT(!is_freed_entry(ltable, index));
        info = get_info(ltable,index);
    } lock_exit(ltable->lock);
    
    return info;
}

void
table_get_key(LookupTable *ltable, TableIndex index, void **pkey_ptr, int *pkey_len)
{
    HPROF_ASSERT(ltable!=NULL);
    HPROF_ASSERT(pkey_ptr!=NULL);
    HPROF_ASSERT(pkey_len!=NULL);
    SANITY_CHECK_HARE(index, ltable->hare);
    HPROF_ASSERT(ltable->elem_size!=0);
    index = SANITY_REMOVE_HARE(index);
    SANITY_CHECK_INDEX(ltable, index);
    
    lock_enter(ltable->lock); {
        HPROF_ASSERT(!is_freed_entry(ltable, index));
	get_key(ltable, index, pkey_ptr, pkey_len);
    } lock_exit(ltable->lock);
}

void
table_lock_enter(LookupTable *ltable)
{
    lock_enter(ltable->lock);
}

void
table_lock_exit(LookupTable *ltable)
{
    lock_exit(ltable->lock);
}