hprof_table.c

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

/*
 * @(#)hprof_table.c	1.36 05/11/17
 * 
 * Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * -Redistribution of source code must retain the above copyright notice, this
 *  list of conditions and the following disclaimer.
 * 
 * -Redistribution in binary form must reproduce the above copyright notice, 
 *  this list of conditions and the following disclaimer in the documentation
 *  and/or other materials provided with the distribution.
 * 
 * Neither the name of Sun Microsystems, Inc. or the names of contributors may 
 * be used to endorse or promote products derived from this software without 
 * specific prior written permission.
 * 
 * This software is provided "AS IS," without a warranty of any kind. ALL 
 * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, INCLUDING
 * ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE
 * OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN MIDROSYSTEMS, INC. ("SUN")
 * AND ITS LICENSORS SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE
 * AS A RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
 * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR ANY LOST 
 * REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, 
 * INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY 
 * OF LIABILITY, ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, 
 * EVEN IF SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
 * 
 * You acknowledge that this software is not designed, licensed or intended
 * for use in the design, construction, operation or maintenance of any
 * nuclear facility.
 */

/* Lookup Table of generic elements. */

/*
 * Each table has a unique lock, all accesses are protected.
 *
 * Table elements are identified with a 32bit unsigned int.
 *   (Also see HARE trick below, which makes the TableIndex unique per table).
 *
 * Each element has a key (N bytes) and possible additional info. 
 *
 * Two elements with the same key should be the same element. 
 *
 * The storage for the Key and Info cannot move, the table itself can.
 *
 * The hash table will only be allocated if we have keys, and will resize
 *    when the table needs to resize. The hash buckets just provide the
 *    reference to the first TableIndex in the hash bucket, the next
 *    field of the TableElement takes you to the next item in the hash
 *    bucket. Lookups will drift the looked up item to the head of the
 *    list.
 *
 * The full 32bit hashcode and key length is saved for comparisons, the
 *    last thing done is the actual comparison of the Key contents with
 *    keys_equal().
 *
 * Freed elements (not many tables actually free items) are managed with
 *    a bit vector and a low index where a freed element might be found.
 *    Bytes are inspected until a non-zero byte indicates a freed bit is
 *    set. A count of freed elements is also kept.
 *
 */

#include "hprof.h"

/* Macros for bit vectors: unsigned char 2^3==8 OR  unsigned int 2^5==32 */

#define BV_CHUNK_POWER_2         3  /* 2 to this power == BV_CHUNK_BITSIZE */
#define BV_CHUNK_TYPE            unsigned char

#define BV_CHUNK_BITSIZE 	 (((int)sizeof(BV_CHUNK_TYPE))<<3) /* x8 */
#define BV_CHUNK_INDEX_MASK      ( (1 << BV_CHUNK_POWER_2) - 1 )
#define BV_ELEMENT_COUNT(nelems) ((((nelems+1)) >> BV_CHUNK_POWER_2) + 1)

#define BV_CHUNK_ROUND(i) ((i) & ~(BV_CHUNK_INDEX_MASK))
#define BV_CHUNK(ptr, i)          \
		(((BV_CHUNK_TYPE*)(ptr))[(i) >> BV_CHUNK_POWER_2])
#define BV_CHUNK_MASK(i)          \
		(1 << ((i) & BV_CHUNK_INDEX_MASK))

/* Hash code value */

typedef unsigned HashCode;

/* Basic key for an element. What makes the element unique. */

typedef struct TableKey {
    void        *ptr;	/* Pointer to arbitrary data that forms the key. */
    int          len;	/* Length in bytes of this key. */
} TableKey;

/* Basic TableElement (but only allocated if keys are used) */

typedef struct TableElement {
    TableKey	 key;	/* The element key. */
    HashCode     hcode; /* The full 32bit hashcode for the key. */
    TableIndex   next;  /* The next TableElement in the hash bucket chain. */
    void        *info;  /* Info pointer */
} TableElement;

/* Generic Lookup Table structure */

typedef struct LookupTable {
    char           name[48];		/* Name of table. */
    void          *table;		/* Pointer to array of elements. */
    TableIndex    *hash_buckets;	/* Pointer to hash bucket chains. */
    Blocks        *info_blocks;         /* Blocks space for info */
    Blocks        *key_blocks;          /* Blocks space for keys */
    TableIndex     next_index;		/* Next element available. */
    TableIndex     table_size;		/* Current size of table. */
    TableIndex     table_incr;		/* Suggested increment size. */
    TableIndex     hash_bucket_count;	/* Number of hash buckets. */
    int		   elem_size;		/* Size of element. */
    int            info_size;		/* Size of info structure. */
    void          *freed_bv;		/* Freed element bit vector */
    int            freed_count;         /* Count of freed'd elements */
    TableIndex     freed_start;         /* First freed in table */
    int            resizes;		/* Count of table resizes done. */
    unsigned       bucket_walks;	/* Count of bucket walks. */
    jrawMonitorID  lock;		/* Lock for table access. */
    SerialNumber   serial_num;		/* Table serial number. */
    TableIndex     hare;       		/* Rabbit (HARE) trick. */
} LookupTable;

/* To get a pointer to an element, regardless of element size. */

#define ELEMENT_PTR(ltable, i) \
	((void*)(((char*)(ltable)->table) + (ltable)->elem_size * (i)))

/* Sanity, check all the time. */

#define SANITY_CHECK(condition) ( (condition) ? (void)0 : \
		HPROF_ERROR(JNI_FALSE, "SANITY IN QUESTION: " #condition))

/* To see if an index is valid. */

#define SANITY_CHECK_INDEX(ltable,i) SANITY_CHECK((i) < ltable->next_index)

/* Small rabbits (hares) can be hidden in the index value returned.
 *   Only the right rabbits are allowed in certain pens (LookupTables).
 *   When herding rabbits it's important to keep them separate,
 *   there are lots of rabbits, all different kinds and sizes,
 *   keeping them all separate is important to avoid cross breeding.
 */

#define _SANITY_USE_HARE
#ifdef _SANITY_USE_HARE
    #define SANITY_ADD_HARE(i,hare)    (SANITY_REMOVE_HARE(i) | (hare))
    #define SANITY_REMOVE_HARE(i)      ((i)  & 0x0FFFFFFF)
    #define SANITY_CHECK_HARE(i,hare)  SANITY_CHECK(SANITY_ADD_HARE(i,hare)==(i))
#else
    #define SANITY_ADD_HARE(i,hare)    (i)
    #define SANITY_REMOVE_HARE(i)      (i)
    #define SANITY_CHECK_HARE(i,hare)
#endif

static jrawMonitorID
lock_create(char *name)
{
    jrawMonitorID stanley;
    
    stanley = createRawMonitor(name);
    return stanley;
}

static void
lock_destroy(jrawMonitorID stanley)
{
    if ( stanley != NULL ) {
	destroyRawMonitor(stanley);
    }
}

static void
lock_enter(jrawMonitorID stanley)
{
    if ( stanley != NULL ) {
	rawMonitorEnter(stanley);
    }
}

static void
lock_exit(jrawMonitorID stanley)
{
    if ( stanley != NULL ) {
	rawMonitorExit(stanley);
    }
}

static void
get_key(LookupTable *ltable, TableIndex index, void **pkey_ptr, int *pkey_len)
{
    *pkey_ptr = ((TableElement*)ELEMENT_PTR(ltable,index))->key.ptr;
    *pkey_len = ((TableElement*)ELEMENT_PTR(ltable,index))->key.len;
}

static void *
get_info(LookupTable *ltable, TableIndex index)
{
    TableElement *element;
    
    if ( ltable->info_size == 0 ) {
	return NULL;
    }
    element = (TableElement*)ELEMENT_PTR(ltable,index);
    return element->info;
}

static void
hash_out(LookupTable *ltable, TableIndex index)
{
    if ( ltable->hash_bucket_count > 0 ) {
	TableElement *element;
	TableElement *prev_e;
	TableIndex    bucket;
	TableIndex    i;
   
	element = (TableElement*)ELEMENT_PTR(ltable,index);
	bucket = (element->hcode % ltable->hash_bucket_count);
	i = ltable->hash_buckets[bucket];
	HPROF_ASSERT(i!=0);
	prev_e = NULL;
	while ( i != 0 && i != index ) {
	    prev_e = (TableElement*)ELEMENT_PTR(ltable,i);
	    i = prev_e->next;
	}
	HPROF_ASSERT(i==index);
	if ( prev_e == NULL ) {
	    ltable->hash_buckets[bucket] = element->next;
	} else {
	    prev_e->next = element->next;
	}
	element->next = 0;
	element->hcode = 0;
    }
}

static jboolean
is_freed_entry(LookupTable *ltable, TableIndex index)
{
    if ( ltable->freed_bv == NULL ) {
	return JNI_FALSE;
    }
    if ( ( BV_CHUNK(ltable->freed_bv, index) & BV_CHUNK_MASK(index) ) != 0 ) {
        return JNI_TRUE;
    } 
    return JNI_FALSE;
}

static void
set_freed_bit(LookupTable *ltable, TableIndex index)
{
    void *p;

    HPROF_ASSERT(!is_freed_entry(ltable, index));
    p = ltable->freed_bv;
    if ( p == NULL ) {
	int size;

	/* First time for a free */
        HPROF_ASSERT(ltable->freed_start==0);
        HPROF_ASSERT(ltable->freed_start==0);
	size             = BV_ELEMENT_COUNT(ltable->table_size);
	p                = HPROF_MALLOC(size*(int)sizeof(BV_CHUNK_TYPE));
	ltable->freed_bv = p;
	(void)memset(p, 0, size*(int)sizeof(BV_CHUNK_TYPE));
    }
    BV_CHUNK(p, index) |= BV_CHUNK_MASK(index);
    ltable->freed_count++;
    if ( ltable->freed_count == 1 ) {
	/* Set freed_start for first time. */
        HPROF_ASSERT(ltable->freed_start==0);
	ltable->freed_start = index;
    } else if ( index < ltable->freed_start ) {
	/* Set freed_start to smaller value so we can be smart about search */
        HPROF_ASSERT(ltable->freed_start!=0);
	ltable->freed_start = index;
    }
    HPROF_ASSERT(ltable->freed_start!=0);
    HPROF_ASSERT(ltable->freed_start < ltable->next_index);
    HPROF_ASSERT(is_freed_entry(ltable, index));
}

static TableIndex
find_freed_entry(LookupTable *ltable)
{
    if ( ltable->freed_count > 0 ) {
	TableIndex i;
	TableIndex istart;
	void *p;
	BV_CHUNK_TYPE chunk;
	
        HPROF_ASSERT(BV_CHUNK_BITSIZE==(1<<BV_CHUNK_POWER_2));
	
	p = ltable->freed_bv;
	HPROF_ASSERT(p!=NULL);
	
	/* Go to beginning of chunk */
	HPROF_ASSERT(ltable->freed_start!=0);
	HPROF_ASSERT(ltable->freed_start < ltable->next_index);
        istart = BV_CHUNK_ROUND(ltable->freed_start);
	
	/* Find chunk with any bit set */
	chunk = 0;
	for( ; istart < ltable->next_index ; istart += BV_CHUNK_BITSIZE ) {
	    chunk = BV_CHUNK(p, istart);
	    if ( chunk != 0 ) {
		break;
	    }
	}
	HPROF_ASSERT(chunk!=0);
	HPROF_ASSERT(chunk==BV_CHUNK(p,istart));
	HPROF_ASSERT(istart < ltable->next_index);
	
	/* Find bit in chunk and return index of freed item */
	for( i = istart ; i < (istart+BV_CHUNK_BITSIZE) ; i++) {
	    BV_CHUNK_TYPE mask;

	    mask = BV_CHUNK_MASK(i);
	    if ( (chunk & mask) != 0 ) {
		HPROF_ASSERT(chunk==BV_CHUNK(p,i));
		chunk &= ~mask;
		BV_CHUNK(p, i) = chunk;
		ltable->freed_count--;
	        HPROF_ASSERT(i < ltable->next_index);
		if ( ltable->freed_count > 0 ) {
		    /* Set freed_start so we can be smart about search */
		    HPROF_ASSERT((i+1) < ltable->next_index);
		    ltable->freed_start = i+1;
		} else {
		    /* Clear freed_start because there are no freed entries */
		    ltable->freed_start = 0;
		}
                HPROF_ASSERT(!is_freed_entry(ltable, i));
		return i;
	    }
	}
	HPROF_ASSERT(0);
    }
    return 0;
}

static void
free_entry(LookupTable *ltable, TableIndex index)
{
    set_freed_bit(ltable, index);
    hash_out(ltable, index);
}

/* Fairly generic hash code generator (not a hash table index) */
static HashCode
hashcode(void *key_ptr, int key_len)
{
    unsigned char *     p;
    HashCode            hcode;
    int                 i;
   
    hcode       = 0;
    if ( key_ptr == NULL || key_len == 0 ) {
	return hcode;
    }
    i           = 0;
    p           = (unsigned char*)key_ptr;
    for ( ; i < key_len-3 ; i += 4 ) {
        /* Do a little loop unrolling */
        hcode += (
                ( (unsigned)(p[i])   << 24 ) |
                ( (unsigned)(p[i+1]) << 16 ) |
                ( (unsigned)(p[i+2]) <<  8 ) |
                ( (unsigned)(p[i+3])       )
                );
    }
    for ( ; i < key_len ; i++ ) {
        hcode += (unsigned)(p[i]);
    }
    return hcode;
}

static void
hash_in(LookupTable *ltable, TableIndex index, HashCode hcode)
{
    if ( ltable->hash_bucket_count > 0 ) {
	TableElement *element;
	TableIndex    bucket;
	
	bucket                        = (hcode % ltable->hash_bucket_count);
	element                       = (TableElement*)ELEMENT_PTR(ltable, index);
	element->hcode                = hcode;
	element->next                 = ltable->hash_buckets[bucket];
	ltable->hash_buckets[bucket]  = index;
    }
}

static void
resize_hash_buckets(LookupTable *ltable)
{
    /*    Don't want to do this too often. */
    
    /* Hash table needs resizing when it's smaller than 1/16 the number of
     *   elements used in the table. This is just a guess. 
     */
    if (    ( ltable->hash_bucket_count < (ltable->next_index >> 4) )
         && ( ltable->hash_bucket_count > 0 )
	 && ( ( ltable->resizes % 10 ) == 0 )
	 && ( ltable->bucket_walks > 1000*ltable->hash_bucket_count )
	 ) {
	int         old_size;
	int         new_size;
	TableIndex *new_buckets;
	TableIndex *old_buckets;
	int         bucket;

	/* Increase size of hash_buckets array, and rehash all elements */
	
	LOG3("Table resize", ltable->name, ltable->resizes);
	
	old_size    = ltable->hash_bucket_count;
	old_buckets = ltable->hash_buckets;
	new_size    = (ltable->next_index >> 3); /* 1/8 current used count */
	SANITY_CHECK(new_size > old_size);
	new_buckets = HPROF_MALLOC(new_size*(int)sizeof(TableIndex));
	(void)memset(new_buckets, 0, new_size*(int)sizeof(TableIndex));
	ltable->hash_bucket_count = new_size;
	ltable->hash_buckets      = new_buckets;
	
	for ( bucket = 0 ; bucket < old_size ; bucket++ ) {
	    TableIndex    index;

	    index = old_buckets[bucket];
	    while ( index != 0 ) {
		TableElement *element;
		TableIndex    next;
		
		element       = (TableElement*)ELEMENT_PTR(ltable, index);
		next          = element->next;
		element->next = 0;
		hash_in(ltable, index, element->hcode);
		index         = next;
	    }
	}
	HPROF_FREE(old_buckets);
	
	ltable->bucket_walks = 0;
    }
}

static void
resize(LookupTable *ltable)
{
    int   old_size;
    int   new_size;
    void *old_table;
    void *new_table;
    int   nbytes;
    int   obytes;

    LOG3("Table resize", ltable->name, ltable->resizes);

    /* Adjust increment on every resize
     *    Minimum is 1/4 the size of the current table or 512.
     */
    old_size = ltable->table_size;
    if ( ltable->table_incr < (unsigned)(old_size >> 2) ) {
        ltable->table_incr = (old_size >> 2);
    }
    if ( ltable->table_incr < 512 ) {
        ltable->table_incr = 512;
    }
    new_size  = old_size + ltable->table_incr;
   
    /* Basic table element array */