/*
 * $RCSfile: idmap.c,v $
 *
 * x-kernel v3.3
 *
 * Copyright (c) 1993,1991,1990,1996  Arizona Board of Regents
 *
 * $Log: idmap.c,v $
 * Revision 1.2  1996/01/29 20:05:05  slm
 * Removed code for variable length keys;
 * updated copyright and version.
 *
 * Revision 1.1  1995/07/28  21:47:49  slm
 * Initial revision
 *
 * Revision 1.40.1.2.1.4  1994/12/02  17:57:12  hkaram
 * Added casts
 *
 * Revision 1.40.1.2.1.3  1994/11/22  20:56:13  hkaram
 * Removed some junk.
 *
 * Revision 1.40.1.2.1.2  1994/10/27  21:11:20  hkaram
 * Davids New Version
 *
 * Revision 1.1  1994/10/05  18:45:17  davidm
 * Initial revision
 *
 * Revision 1.38  1993/12/11  00:23:33  menze
 * fixed #endif comments
 *
 * Revision 1.37  1993/12/07  02:25:12  menze
 * generichash was sometimes looking at too many bytes past the end of
 * the key.
 */
#include "platform.h"
#include "idmap.h"

#include "upi.h"
#include "x_util.h"
#include "idmap_internal.h"
#include "xk_assert.h"
#include "xk_debug.h"
#include "platform.h"

#define XK_MAP_SPECIALIZE

#ifdef XK_MAP_SPECIALIZE

#define MAX_SPECIALIZED_KEY_SIZE 16

static struct map_functions {
    XMapResolveFunc resolve;
    XMapBindFunc    bind;
    XMapUnbindFunc  unbind;
    XMapRemoveFunc  remove;
} map_functions[MAX_SPECIALIZED_KEY_SIZE + 1];

#endif /* XK_MAP_SPECIALIZE */

int traceidmap;

/*
 * Hash-values are in the range 0..1023, so it makes no sense
 * to have more than 1024 buckets:
 */
#define MAX_BUCKETS 1024

static int      any_hash(char *, int, int);
static XkReturn any_resolve(Map, void *, void **);
static Binding  any_bind(Map, void *, void *);
static XkReturn any_unbind(Map, void *);
static XkReturn any_remove(Map, Binding);
static void     removeList(MapElement *);

/* Returns ceil(log_2(x)) */
static int
ceil_log2(x)
unsigned int x;
{
    int y = 0;

    while (x) {
	x >>= 1;
	++y;
    } /* while */
    return y;
} /* ceil_log2 */

/*
 * Create and return a new map containing a table with table_len
 * entries mapping keys of size keySize to integers:
 */
Map
mapCreate(table_len, keySize)
int table_len;
int keySize;
{
    Map m;
    int log2;
    int entries = table_len;

    xTrace1(idmap, TR_FULL_TRACE, "mapCreate called, %d entries", table_len);
    xAssert(table_len);
    xAssert(keySize > 0);
    log2 = ceil_log2(table_len);
    xAssert(log2 < 8*sizeof(int) - 1);
    if (entries == 1<<(log2-1))
	table_len = entries;		/* table_len is a power of 2 */
    else
	table_len = 1<<log2;		/* use next higher power of two */
    xAssert(table_len <= MAX_BUCKETS);

    xTrace1(idmap, TR_EVENTS, "mapCreate: actual map size %d\n", table_len);
    m = (Map)xMalloc(sizeof(*m));
    m->num_buckets = table_len;
    m->key_size    = keySize;
    m->cache       = 0;
    m->buckets     =
	(struct map_bucket*)xMalloc(table_len * sizeof(m->buckets[0]));
    bzero((char *)m->buckets, table_len * sizeof(m->buckets[0]));
    m->chain.next  = &m->chain;
    m->freelist    = 0;
    m->resolve     = any_resolve;
    m->bind        = any_bind;
    m->unbind      = any_unbind;
    m->remove      = any_remove;
#ifdef XK_MAP_SPECIALIZE
    if (keySize <= MAX_SPECIALIZED_KEY_SIZE) {
	if (map_functions[keySize].resolve)
	    m->resolve = map_functions[keySize].resolve;
	if (map_functions[keySize].bind)
	    m->bind = map_functions[keySize].bind;
	if (map_functions[keySize].unbind)
	    m->unbind = map_functions[keySize].unbind;
	if (map_functions[keySize].remove)
	    m->remove = map_functions[keySize].remove;
    } /* if */
#endif /* XK_MAP_SPECIALIZE */
    return m;
} /* mapCreate */

static void
removeList(e)
MapElement *e;
{
    MapElement *next;

    while (e) {
	xTrace1(idmap, TR_FULL_TRACE, "mapClose removing element %lx",
		(unsigned long)e);
	next = e->next;
	xFree((char *)e);
	e = next;
    } /* while */
} /* removeList */

void
mapClose(map)
Map map;
{
    int i;

    xTrace1(idmap, TR_MAJOR_EVENTS, "mapClose of map %lx", (unsigned long)map);
    /* free any elements still bound into the map */
    for (i = 0; i < map->num_buckets; i++)
	removeList(map->buckets[i].first);
    /* remove freelist */
    removeList(map->freelist);
    xFree((char *)map->buckets);
    xFree((char *)map);
} /* mapClose */

void
mapForEach(map, func, arg)
Map           map;
MapForEachFun func;
void          *arg;
{
    struct map_bucket *bucket, *prev_bucket;
    MapElement *el, *next_el;
    int action = 0;

    xTrace0(idmap, TR_FULL_TRACE, "mapForEach()");

    prev_bucket = &map->chain;
    for (bucket = map->chain.next; bucket != &map->chain; bucket = bucket->next)
    {
	if (!bucket->first) {
	    /* now is the time to remove buckets that have become empty */
	    prev_bucket->next = bucket->next;
	    bucket->next = 0;
	    bucket = prev_bucket;
	    continue;
	} /* if */
	prev_bucket = bucket;
	/* visit all elements in this BUCKET */
	el = bucket->first;
	do {
	    /*
	     * By convention, (*F)() must not remove EL, so keeping
	     * a pointer to it while invoking (*F)() is safe
	     */
	    if (map->key_size > 0)
		action = (*func)(el->u.fixed.key, el->value, arg);
	    else
		action = (*func)(el->u.var.key, el->value, arg);
	    next_el = el->next;
	    if (!(action & MFE_CONTINUE))
		return;
	    if (action & MFE_REMOVE)
		(*map->remove)(map, el);
	    el = next_el;
	} while (el);
    } /* for */
} /* mapForEach */

#include "idmap_special.h"

void
map_init()
{
#ifdef XK_MAP_SPECIALIZE
    bzero((char *)map_functions, sizeof(map_functions));

#ifndef __alpha__
    m2init(&map_functions[2]);
    m6init(&map_functions[6]);
    m10init(&map_functions[10]);
#endif
    m4init(&map_functions[4]);
    m8init(&map_functions[8]);
    m12init(&map_functions[12]);
    m16init(&map_functions[16]);
#endif /* XK_MAP_SPECIALIZE */
} /* map_init */

			/*** end of idmap.c ***/