/*
 * $RCSfile: idmap_special.h,v $
 *
 * x-kernel v3.3
 *
 * Copyright (c) 1993,1991,1990,1996  Arizona Board of Regents
 *
 * $Log: idmap_special.h,v $
 * Revision 1.2  1996/01/29 20:03:17  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.1.1.2  1994/10/27  21:11:20  hkaram
 * Davids New Version
 *
 * Revision 1.3  1994/10/08  00:37:45  davidm
 * (m16bind,m16unbind,m16remove): It is not worthwhile to specialize these
 * 	functions on the Alpha.
 *
 * Revision 1.2  1994/10/05  18:45:40  davidm
 * *** empty log message ***
 *
 * Revision 1.1  1994/10/03  19:45:49  davidm
 * Initial revision
 */
/*
 * This generates special hash/comparison/assignment functions
 * for keys of size 2, 4, 6, 8, and 16 bytes.   It also generates
 * the generic functions that can deal with any size.
 */
#ifdef XK_USE_INLINE
#define INLINE __inline__
#else
#define INLINE /* empty */
#endif

#ifndef const
#ifndef __STDC__
#define const /* empty */
#endif
#endif

static INLINE int hash2(VOID *key, int num_buckets);
static INLINE int hash4(VOID *key, int num_buckets);

#ifdef XK_MAP_SPECIALIZE

/*
 * The first argument to beqlx() and bsetx() must be long-word aligned!
 * (this is guaranteed because the left argument is always a pointer
 *  to a KEY field in a `struct map_element' structure).
 */
#ifndef __alpha__
static INLINE int  beql2(const char *, const char *);
static INLINE void bset2(char *, const char *);
#endif

static INLINE int beql4(const char *, const char *);
static INLINE int bset4(char *, const char *);

#ifndef __alpha__
static int        hash6(void *, int);
static INLINE int beql6(const char *, const char *);
static INLINE int bset6(char *, const char *);
#endif

static int        hash8(void *, int);
static INLINE int beql8(const char *, const char *);
static INLINE int bset8(char *, const char *);

#ifndef __alpha__
static int        hash10(void *, int);
static INLINE int beql10(const char *, const char *);
static INLINE int bset10(char *, const char *);
#endif

static int        hash12(void *, int);
static INLINE int beql12(const char *, const char *);
static INLINE int bset12(char *, const char *);

static int        hash16(void *, int);
static INLINE int beql16(const char *, const char *);
static INLINE int bset16(char *, const char *);

/* Generic compare/copy routines: */
#define ANY_EQL(s1, s2, n) (bcmp((char*)(s1), (char*)(s2), (n)) == 0)
#define ANY_SET(s1, s2, n) (bcopy((char*)(s2), (char*)(s1), (n)), 1)

/*
 * Macro Cx(i,o) expands to code that applies binary operator "o" to an 8*x bit
 * integers at addresses s1+i and s2+i.  s1 and s2 must be of type "char *".
 */
#define C2(i,o) (*(xk_int16*)((s1)+(i)) o *(xk_int16*)((s2)+(i)))
#define C4(i,o) (*(xk_int32*)((s1)+(i)) o *(xk_int32*)((s2)+(i)))
#ifdef xk_int64
#define C8(i,o) (*(xk_int64*)((s1)+(i)) o *(xk_int64*)((s2)+(i)))
#endif

/*
 * Macro C(t,e,gen,n) expands to code that evaluates expression "e" if both,
 * "s1" and "s2" are aligned to type "t".  If either pointer is not properly
 * aligned, the expression "gen(s1,s2,n)" is evaluated instead.
 */
#define C(t,e,gen,n) ({                  \
    long r;                              \
    if (XK_ALIGNED((s2),t) PREDICT_TRUE) \
	r = (e);                         \
    else                                 \
	r = gen((s1),(s2),n);            \
    r;                                   \
})

/***************** keysize = 2 bytes *****************/

#ifndef __alpha__

#define SCLASS       static
#define RESOLVE_NAME m2resolve
#define BIND_NAME    m2bind
#define UNBIND_NAME  m2unbind
#define REMOVE_NAME  m2remove
#define INIT_NAME    m2init

static INLINE int
beql2(s1, s2)
const char *s1;
const char *s2;
{
    return (s1[0] == s2[0]) && (s1[1] == s2[1]);
} /* beql2 */

static INLINE void
bset2(s1, s2)
char       *s1;
const char *s2;
{
    s1[0] = s2[0]; s1[1] = s2[1];
} /* bset2 */

#define GET_EL(m,el)    GETMAPELEM(m,el)
#define FREE_EL(m,el)   FREEIT(m,el)
#define HASH(m,k)       hash2((k), (m)->num_buckets)
#define HASH_EL(m,el)   HASH(m, (el)->u.fixed.key)
#define KEY_MATCH(el,k) beql2((el)->u.fixed.key, (k))
#define KEY_SIZE_DECL   /* empty */
#define KEY_SIZE_ARG    /* empty */
#define SET_KEY(el,k)   bset2((el)->u.fixed.key, (char*)k)

#include "idmap_templ.c"

#endif /* !__alpha__ */

/***************** keysize = 4 bytes *****************/

#define SCLASS       static
#define RESOLVE_NAME m4resolve
#define BIND_NAME    m4bind
#define UNBIND_NAME  m4unbind
#define REMOVE_NAME  m4remove
#define INIT_NAME    m4init

static INLINE int
beql4(s1, s2)
const char *s1;
const char *s2;
{
    return C(xk_int32, (C4(0,==)), ANY_EQL, 4);
} /* beql4 */

static INLINE int
bset4(s1, s2)
char       *s1;
const char *s2;
{
    return C(xk_int32, (C4(0,=)), ANY_SET, 4);
} /* bset4 */

#define GET_EL(m,el)    GETMAPELEM(m,el)
#define FREE_EL(m,el)   FREEIT(m,el)
#define HASH(m,k)       hash4((k), (m)->num_buckets)
#define HASH_EL(m,el)   HASH(m, (el)->u.fixed.key)
#define KEY_MATCH(el,k) beql4((el)->u.fixed.key, (k))
#define KEY_SIZE_DECL   /* empty */
#define KEY_SIZE_ARG    /* empty */
#define SET_KEY(el,k)   bset4((el)->u.fixed.key, (char*)k)

#include "idmap_templ.c"

/***************** keysize = 6 bytes *****************/

#ifndef __alpha__

#define SCLASS       static
#define RESOLVE_NAME m6resolve
#define BIND_NAME    m6bind
#define UNBIND_NAME  m6unbind
#define REMOVE_NAME  m6remove
#define INIT_NAME    m6init

static int
hash6(key, num_buckets)
VOID *key;
int  num_buckets;
{
    xk_u_int8 *k = (xk_u_int8*)key;
    u_int     h;

    h = hash4(k, num_buckets) ^ hash2(k + 4, num_buckets);

    xTrace1(idmap, TR_FULL_TRACE, "6 byte optimized hash returns %d", h);
    return h;
} /* hash6 */

static INLINE int
beql6(s1, s2)
const char *s1;
const char *s2;
{
    return C(xk_int32, (C4(0,==) && C2(4,==)), ANY_EQL, 6);
} /* beql6 */

static INLINE int
bset6(s1, s2)
char       *s1;
const char *s2;
{
    return C(xk_int32, (C4(0,=), C2(4,=)), ANY_SET, 6);
} /* bset6 */

#define GET_EL(m,el)    GETMAPELEM(m,el)
#define FREE_EL(m,el)   FREEIT(m,el)
#define HASH(m,k)       hash6((k), (m)->num_buckets)
#define HASH_EL(m,el)   HASH(m, (el)->u.fixed.key)
#define KEY_MATCH(el,k) beql6((el)->u.fixed.key, (k))
#define KEY_SIZE_DECL   /* empty */
#define KEY_SIZE_ARG    /* empty */
#define SET_KEY(el,k)   bset6((el)->u.fixed.key, (char*)k)

#include "idmap_templ.c"

#endif /* !__alpha__ */

/***************** keysize = 8 bytes *****************/

#define SCLASS       static
#define RESOLVE_NAME m8resolve
#define BIND_NAME    m8bind
#define UNBIND_NAME  m8unbind
#define REMOVE_NAME  m8remove
#define INIT_NAME    m8init

static int
hash8(key, num_buckets)
VOID *key;
int  num_buckets;
{
    xk_u_int8 *k = (xk_u_int8*)key;
    u_int     h;

    /* num_buckets must be power of two: */
    xAssert((num_buckets & (num_buckets - 1)) == 0);

    h = hash4(k, num_buckets) ^ hash4(k + 4, num_buckets);
    xTrace1(idmap, TR_FULL_TRACE, "8 byte optimized hash returns %d", h);
    return h;
} /* hash8 */

static INLINE int
beql8(s1, s2)
const char *s1;
const char *s2;
{
#ifdef xk_int64
    return C(xk_int64, (C8(0,==)), ANY_EQL, 8);
#else
    return C(xk_int32, (C4(0,==) && C4(4,==)), ANY_EQL, 8);
#endif
} /* beql8 */

static INLINE int
bset8(s1, s2)
char       *s1;
const char *s2;
{
#ifdef xk_int64
    return C(xk_int64, (C8(0,=)), ANY_SET, 8);
#else
    return C(xk_int32, (C4(0,=), C4(4,=)), ANY_SET, 8);
#endif
} /* bset8 */

#define GET_EL(m,el)    GETMAPELEM(m,el)
#define FREE_EL(m,el)   FREEIT(m,el)
#define HASH(m,k)       hash8((k), (m)->num_buckets)
#define HASH_EL(m,el)   HASH(m, (el)->u.fixed.key)
#define KEY_MATCH(el,k) beql8((el)->u.fixed.key, (k))
#define KEY_SIZE_DECL   /* empty */
#define KEY_SIZE_ARG    /* empty */
#define SET_KEY(el,k)   bset8((el)->u.fixed.key, (char*)k)

#include "idmap_templ.c"

/***************** keysize = 10 bytes *****************/

#ifndef __alpha__

#define SCLASS       static
#define RESOLVE_NAME m10resolve
#define BIND_NAME    m10bind
#define UNBIND_NAME  m10unbind
#define REMOVE_NAME  m10remove
#define INIT_NAME    m10init

static int
hash10(key, num_buckets)
VOID *key;
int  num_buckets;
{
    xk_u_int8 *k = (xk_u_int8*)key;
    u_int     h;

    h = (hash4(k, num_buckets) ^ hash4(k + 4, num_buckets)
	 ^ hash2(k + 8, num_buckets));

    xTrace1(idmap, TR_FULL_TRACE, "10 byte optimized hash returns %d", h);
    return h;
} /* hash10 */

static INLINE int
beql10(s1, s2)
const char *s1;
const char *s2;
{
#ifdef xk_int64
    return C(xk_int64, (C8(0,==) && C2(8,==)), ANY_EQL, 10);
#else
    return C(xk_int32, (C4(0,==) && C4(4,==) && C2(8,==)), ANY_EQL, 10);
#endif
} /* beql10 */

static INLINE int
bset10(s1, s2)
char       *s1;
const char *s2;
{
#ifdef xk_int64
    return C(xk_int64, (C8(0,=), C2(8,=)), ANY_SET, 10);
#else
    return C(xk_int32, (C4(0,=), C4(4,=), C2(8,=)), ANY_SET, 10);
#endif
} /* bset10 */

#define GET_EL(m,el)    GETMAPELEM(m,el)
#define FREE_EL(m,el)   FREEIT(m,el)
#define HASH(m,k)       hash10((k), (m)->num_buckets)
#define HASH_EL(m,el)   HASH(m, (el)->u.fixed.key)
#define KEY_MATCH(el,k) beql10((el)->u.fixed.key, (k))
#define KEY_SIZE_DECL   /* empty */
#define KEY_SIZE_ARG    /* empty */
#define SET_KEY(el,k)   bset10((el)->u.fixed.key, (char*)k)

#include "idmap_templ.c"

#endif /* !__alpha__ */

/***************** keysize = 12 bytes *****************/

#define SCLASS       static
#define RESOLVE_NAME m12resolve
#define BIND_NAME    m12bind
#define UNBIND_NAME  m12unbind
#define REMOVE_NAME  m12remove
#define INIT_NAME    m12init

static int
hash12(key, num_buckets)
VOID *key;
int  num_buckets;
{
    xk_u_int8 *k = (xk_u_int8*)key;
    u_int     h;

    h = (hash4(k, num_buckets) ^ hash4(k + 4, num_buckets)
	 ^ hash4(k + 8, num_buckets));

    xTrace1(idmap, TR_FULL_TRACE, "12 byte optimized hash returns %d", h);
    return h;
} /* hash12 */

static INLINE int
beql12(s1, s2)
const char *s1;
const char *s2;
{
#ifdef xk_int64
    return C(xk_int64, (C8(0,==) && C4(8,==)), ANY_EQL, 12);
#else
    return C(xk_int32, (C4(0,==) && C4(4,==) && C4(8,==)), ANY_EQL, 12);
#endif
} /* beql12 */

static INLINE int
bset12(s1, s2)
char       *s1;
const char *s2;
{
#ifdef xk_int64
    return C(xk_int64, (C8(0,=), C4(8,=)), ANY_SET, 12);
#else
    return C(xk_int32, (C4(0,=), C4(4,=), C4(8,=)), ANY_SET, 12);
#endif
} /* bset12 */

#define GET_EL(m,el)    GETMAPELEM(m,el)
#define FREE_EL(m,el)   FREEIT(m,el)
#define HASH(m,k)       hash12((k), (m)->num_buckets)
#define HASH_EL(m,el)   HASH(m, (el)->u.fixed.key)
#define KEY_MATCH(el,k) beql12((el)->u.fixed.key, (k))
#define KEY_SIZE_DECL   /* empty */
#define KEY_SIZE_ARG    /* empty */
#define SET_KEY(el,k)   bset12((el)->u.fixed.key, (char*)k)

#include "idmap_templ.c"

/***************** keysize = 16 bytes *****************/

#define SCLASS       static
#define RESOLVE_NAME m16resolve
#ifndef __alpha__
#define BIND_NAME    m16bind
#define UNBIND_NAME  m16unbind
#define REMOVE_NAME  m16remove
#endif
#define INIT_NAME    m16init

static int
hash16(key, num_buckets)
VOID *key;
int  num_buckets;
{
    xk_u_int8 *k = (xk_u_int8*)key;
    u_int     h;

    h = (hash4(k, num_buckets) ^ hash4(k + 4, num_buckets)
	 ^ hash4(k + 8, num_buckets) ^ hash4(k + 12, num_buckets));

    xTrace1(idmap, TR_FULL_TRACE, "16 byte optimized hash returns %d", h);
    return h;
} /* hash16 */

static INLINE int
beql16(s1, s2)
const char *s1;
const char *s2;
{
#ifdef xk_int64
    return C(xk_int64, (C8(0,==) && C8(8,==)), ANY_EQL, 16);
#else
    return C(xk_int32, (C4(0,==) && C4(4,==) && C4(8,==) && C4(12,==)),
	     ANY_EQL, 16);
#endif
} /* beql16 */

static INLINE int
bset16(s1, s2)
char       *s1;
const char *s2;
{
#ifdef xk_int64
    return C(xk_int64, (C8(0,=), C8(8,=)), ANY_SET, 16);
#else
    return C(xk_int32, (C4(0,=), C4(4,=), C4(8,=), C4(12,=)), ANY_SET, 16);
#endif
} /* bset16 */

#define GET_EL(m,el)    GETMAPELEM(m,el)
#define FREE_EL(m,el)   FREEIT(m,el)
#define HASH(m,k)       hash16((k), (m)->num_buckets)
#define HASH_EL(m,el)   HASH(m, (el)->u.fixed.key)
#define KEY_MATCH(el,k) beql16((el)->u.fixed.key, (k))
#define KEY_SIZE_DECL   /* empty */
#define KEY_SIZE_ARG    /* empty */
#define SET_KEY(el,k)   bset16((el)->u.fixed.key, (char*)k)

#include "idmap_templ.c"

#endif /* XK_MAP_SPECIALIZE */

/*
 * Now is the right time to define hash2() and hash4().  The idea is to have
 * them inlined within the generic functions, but not in the specialized
 * key-functions defined above, because the latter would increase code-size
 * significantly without much benefit.
 */

static INLINE int
hash2(key, num_buckets)
VOID *key;
int  num_buckets;
{
    xk_u_int8 h0, h1;
    u_int     h;

    /* num_buckets must be power of two: */
    xAssert((num_buckets & (num_buckets - 1)) == 0);

    h0 = ((xk_u_int8*)key)[0];
    h1 = ((xk_u_int8*)key)[1];
    h = (((h0<<2) + h1) ^ ((h1<<2) + h0)) & (num_buckets - 1);

    xTrace2(idmap, TR_DETAILED, "2 byte optimized hash of %x is %d",
	    h0 | (h1<<8), h);
    return h;
} /* hash2 */

static INLINE int
hash4(key, num_buckets)
VOID *key;
int  num_buckets;
{
    xk_u_int8 h0, h1, h2, h3;
    u_int     h;

    /* num_buckets must be power of two: */
    xAssert((num_buckets & (num_buckets - 1)) == 0);

    h0 = ((xk_u_int8*)key)[0];
    h1 = ((xk_u_int8*)key)[1];
    h2 = ((xk_u_int8*)key)[2];
    h3 = ((xk_u_int8*)key)[3];

    h = ((h0 + (h2<<2)) ^ (h1 + (h3<<1)) ^ (h2 + (h0<<1)) ^ ((h3 + h1)<<2))
      & (num_buckets - 1);

    xTrace4(idmap, TR_DETAILED,
	    "4 byte optimized hash of %lx (at %lx) is %d in %d buckets",
	    (h0 | ((xk_u_int32) h1<<8) | ((xk_u_int32) h2<<16)
	     | ((xk_u_int32) h3<<24)),
	    (u_long)key, h, num_buckets);
    return h;
} /* hash4 */

/***************** generic operations *****************/

static int
any_hash(key, num_buckets, key_size)
char *key;
int  num_buckets;
int  key_size;
{
    int   how_many_words = key_size / 4;
    u_int h = 0;

    xTrace2(idmap, TR_FULL_TRACE,
	    "any idmap hash -- num_buckets %d, key_size %d",
	    num_buckets, key_size);

    /* num_buckets must be power of two: */
    xAssert((num_buckets & (num_buckets - 1)) == 0);

    while (how_many_words--) {
	h ^= hash4(key, num_buckets);
	key += 4;
    } /* while */
    if (key_size & 0x2) {
	h ^= hash2(key, num_buckets);
	key += 2;
    } /* while */
    if (key_size & 0x1)
	h ^= *(xk_u_int8*)key;

    h = h & (num_buckets - 1);

    xTrace1(idmap, TR_FULL_TRACE, "any_hash() returns %d", h);
    return h;
} /* any_hash */

#define SCLASS       static
#define BIND_NAME    any_bind
#define UNBIND_NAME  any_unbind
#define REMOVE_NAME  any_remove
#define RESOLVE_NAME any_resolve

/* Some of the following macros assume that M is the map being processed. */
#define GET_EL(m,el)    GETMAPELEM(m,el)
#define FREE_EL(m,el)   FREEIT(m,el)
#define HASH(m,k)       any_hash((char*)(k), (m)->num_buckets,(m)->key_size)
#define HASH_EL(m,el)   HASH(m, (el)->u.fixed.key)
#define KEY_SIZE_DECL   /* empty */
#define KEY_SIZE_ARG    /* empty */
#define KEY_MATCH(el,k) (bcmp((el)->u.fixed.key, (k), m->key_size) == 0)
#define SET_KEY(el,k)   bcopy((char*)k, (el)->u.fixed.key, m->key_size)

#include "idmap_templ.c"

			/*** end of idmap_special.h ***/