/*

 * 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) ) {