common/hash/hashalloc.c

da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/***********************************************************************
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                                                                      *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*               This software is part of the ast package               *
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner*          Copyright (c) 1985-2010 AT&T Intellectual Property          *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                      and is licensed under the                       *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                  Common Public License, Version 1.0                  *
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin*                    by AT&T Intellectual Property                     *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                                                                      *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                A copy of the License is available at                 *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*            http://www.opensource.org/licenses/cpl1.0.txt             *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*         (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9)         *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                                                                      *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*              Information and Software Systems Research               *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                            AT&T Research                             *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                           Florham Park NJ                            *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                                                                      *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                 Glenn Fowler <gsf@research.att.com>                  *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                  David Korn <dgk@research.att.com>                   *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                   Phong Vo <kpv@research.att.com>                    *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin*                                                                      *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin***********************************************************************/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#pragma prototyped
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * Glenn Fowler
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * AT&T Research
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * hash table library
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstatic const char id_hash[] = "\n@(#)$Id: hash (AT&T Research) 1996-08-11 $\0\n";
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include "hashlib.h"
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinHash_info_t hash_info = { 0 };
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * create a new hash table
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinHash_table_t*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinhashalloc(Hash_table_t* ref, ...)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    register Hash_table_t*  tab;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    register Hash_table_t*  ret = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    register int        internal;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    int         n;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    va_list         ap;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    va_list         va[4];
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    va_list*        vp = va;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    Hash_region_f       region = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    void*           handle;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    va_start(ap, ref);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    /*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin     * check for HASH_region which must be first
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin     */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    n = va_arg(ap, int);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    if (!ref && n == HASH_region)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        region = va_arg(ap, Hash_region_f);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        handle = va_arg(ap, void*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        n = va_arg(ap, int);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        if (!(tab = (Hash_table_t*)(*region)(handle, NiL, sizeof(Hash_table_t), 0)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        memset(tab, 0, sizeof(Hash_table_t));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    else if (!(tab = newof(0, Hash_table_t, 1, 0)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    tab->bucketsize = (sizeof(Hash_header_t) + sizeof(char*) - 1) / sizeof(char*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    if (ref)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        tab->flags = ref->flags & ~HASH_RESET;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        tab->root = ref->root;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        internal = HASH_INTERNAL;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        if (region)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (!(tab->root = (Hash_root_t*)(*region)(handle, NiL, sizeof(Hash_root_t), 0)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            memset(tab->root, 0, sizeof(Hash_root_t));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        else if (!(tab->root = newof(0, Hash_root_t, 1, 0)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        if (!(tab->root->local = newof(0, Hash_local_t, 1, 0)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        if (tab->root->local->region = region)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            tab->root->local->handle = handle;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        tab->root->meanchain = HASHMEANCHAIN;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        internal = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    tab->size = HASHMINSIZE;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    for (;;)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        switch (n)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        case HASH_alloc:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (ref) goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            tab->root->local->alloc = va_arg(ap, Hash_alloc_f);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        case HASH_bucketsize:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            n = (va_arg(ap, int) + sizeof(char*) - 1) / sizeof(char*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (n > UCHAR_MAX) goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (n > tab->bucketsize) tab->bucketsize = n;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        case HASH_clear:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            tab->flags &= ~(va_arg(ap, int) & ~internal);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        case HASH_compare:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (ref) goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            tab->root->local->compare = va_arg(ap, Hash_compare_f);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        case HASH_free:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (ref) goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            tab->root->local->free = va_arg(ap, Hash_free_f);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        case HASH_hash:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (ref) goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            tab->root->local->hash = va_arg(ap, Hash_hash_f);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        case HASH_meanchain:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (ref) goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            tab->root->meanchain = va_arg(ap, int);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        case HASH_name:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            tab->name = va_arg(ap, char*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        case HASH_namesize:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (ref) goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            tab->root->namesize = va_arg(ap, int);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        case HASH_region:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        case HASH_set:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            tab->flags |= (va_arg(ap, int) & ~internal);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        case HASH_size:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            tab->size = va_arg(ap, int);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (tab->size & (tab->size - 1)) tab->flags |= HASH_FIXED;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        case HASH_table:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            tab->table = va_arg(ap, Hash_bucket_t**);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            tab->flags |= HASH_STATIC;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        case HASH_va_list:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (vp < &va[elementsof(va)])
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                va_copy(*vp, ap);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                vp++;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            va_copy(ap, va_listval(va_arg(ap, va_listarg)));
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        case 0:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (vp > va)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                vp--;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                va_copy(ap, *vp);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (tab->flags & HASH_SCOPE)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                if (!(tab->scope = ref)) goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                ref->frozen++;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (!tab->table)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                if (region)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    if (!(tab->table = (Hash_bucket_t**)(*region)(handle, NiL, sizeof(Hash_bucket_t*) * tab->size, 0)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                        goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                    memset(tab->table, 0, sizeof(Hash_bucket_t*) * tab->size);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                else if (!(tab->table = newof(0, Hash_bucket_t*, tab->size, 0))) goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (!ref)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                tab->root->flags = tab->flags & HASH_INTERNAL;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                tab->root->next = hash_info.list;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                hash_info.list = tab->root;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            if (!region)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                tab->next = tab->root->references;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin                tab->root->references = tab;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            ret = tab;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        default:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin            goto out;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin        n = va_arg(ap, int);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin out:
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    va_end(ap);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    if (!ret) hashfree(tab);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin    return(ret);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}