hprof_table.c

/*
 * Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 *   - Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *
 *   - Redistributions 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 Oracle nor the names of its
 *     contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/*
 * This source code is provided to illustrate the usage of a given feature
 * or technique and has been deliberately simplified. Additional steps
 * required for a production-quality application, such as security checks,
 * input validation and proper error handling, might not be present in
 * this sample code.
 */


/* 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 (can be 0). */
    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;

    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 */
    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);
                if ( ltable->info_size == 0 ) {
                    info = NULL;
                } else {
                    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);
}