view release on metacpan or  search on metacpan

src/tccexsymtab.c  view on Meta::CPAN

) {
    /* find the associated bucket */
    token_string_hash_linked_list ** to_return
        = tsh->buckets + _token_hash_hash_string(tsh, name);

    /* Check the names of all elements in the bucket until we find it */
    while(*to_return) {
        if (strcmp((*to_return)->name, name) == 0) return to_return;
        to_return = &((*to_return)->next);
    }
    return to_return;
}

void _token_string_hash_extend(token_string_hash * tsh)
{
    /* Back up the old buckets */
    int n;
    token_string_hash_linked_list ** old_buckets = tsh->buckets;
    int old_N_buckets = tsh->N_buckets;

    /* Extend the new buckets by a factor of 2 */
    tsh->N_buckets <<= 1;
    tsh->buckets = tcc_mallocz(tsh->N_buckets * sizeof(void*));

    /* rehash the data */
    for (n = 0; n < old_N_buckets; n++) {
        token_string_hash_linked_list * curr_ll = old_buckets[n];
        while(curr_ll != NULL) {
            token_string_hash_linked_list * tmp;

            /* Make the new slot point to this linked list object */
            *(_token_string_hash_get_ll_ref(tsh, curr_ll->name)) = curr_ll;

            /* Make sure the old "next" is cleared, since it probably
             * won't be in this bucket after rehashing. */
            tmp = curr_ll->next;
            curr_ll->next = NULL;

            /* On to the old "next" */
            curr_ll = tmp;
        }
    }
    tcc_free(old_buckets);
}

/* Returns a reference to the data slot of the token string hash entry
 * for the given name, creating the hash entry if necessary. */

void ** token_string_hash_get_ref(token_string_hash * tsh, const char * name)
{
    token_string_hash_linked_list** ll_slot = _token_string_hash_get_ll_ref(tsh, name);
    token_string_hash_linked_list* return_container = *ll_slot;

    /* create a new entry if necessary */
    if (return_container == NULL)
    {
        return_container = tcc_mallocz(sizeof(token_string_hash_linked_list) + strlen(name));
        strcpy(return_container->name, name);
        *ll_slot = return_container;

        /* Rehash if too big; note rehashing does not invalidate return_container */
        if (++tsh->N > tsh->N_buckets) _token_string_hash_extend(tsh);
    }
    return &(return_container->data);
}

/* string_string_hash_count: returns the number of elements in the hash table */
int token_string_hash_count(token_string_hash * tsh) {
    return tsh->N;
}

void token_string_hash_free(token_string_hash * tsh)
{
    int n;
    if (tsh == NULL) return;
    for (n = 0; n < tsh->N_buckets; n++) {
        token_string_hash_linked_list * curr_ll = tsh->buckets[n];
        while(curr_ll != NULL) {
            token_string_hash_linked_list * tmp = curr_ll->next;
            tcc_free(curr_ll);
            curr_ll = tmp;
        }
    }
    tcc_free(tsh->buckets);
    tcc_free(tsh);
}

/****************************************************************************/
/*                                 ram hash                                 */
/****************************************************************************/

/* This provides a mechanism for mapping a set of old pointers to a set of
 * new pointers. Assuming that a collection of data structures are being
 * copied, this basically provides an interface to say, "What is the new
 * address for this old address?"
 * 
 * The current hashing function is pretty basic, taken from this discussion:
 * http://stackoverflow.com/questions/20953390/what-is-the-fastest-hash-function-for-pointers
 * However, it performs pretty well. With perl.h, the maximum bucket depth
 * is 6, and on average each bucket has about 1.3 entries.
 * 
 * As currently implemented, you should create a new ram_hash with
 * ram_hash_new and free the memory associated with your ram_hash with
 * ram_hash_free:
 * 
 *  ram_hash * my_ram_hash = ram_hash_new();
 * 
 */

ram_hash_linked_list * ram_hash_get(ram_hash * rh, void * key);

ram_hash * ram_hash_new()
{
    ram_hash * to_return = tcc_mallocz(sizeof(ram_hash));
    to_return->N_buckets = 4;
    to_return->buckets = tcc_mallocz(4*sizeof(ram_hash_linked_list));

    /* Add entry for null pointer */
    ram_hash_get(to_return, NULL)->value = NULL;
    return to_return;
}