/* * idmap.h * * x-kernel v3.3 * * Copyright (c) 1993,1991,1990,1996 Arizona Board of Regents * * $Revision: 1.2 $ * $Date: 1996/01/29 20:25:55 $ * * $Log: idmap.h,v $ * Revision 1.2 1996/01/29 20:25:55 slm * Updated copyright and version. * * Revision 1.1 1995/07/28 21:29:10 slm * Initial revision * * Revision 1.24.2.4 1994/12/02 17:41:14 hkaram * Moved to new mapResolve interface * * Revision 1.24.2.3 1994/11/22 19:49:56 hkaram * Fixed declarations to work with cc; misc changes * * Revision 1.24.2.2 1994/10/27 21:04:04 hkaram * Davids new Version * * Revision 1.1 1994/10/05 18:45:01 davidm * Initial revision */ #ifndef idmap_h #define idmap_h #include "xtype.h" #define ERR_BIND ((Binding)XK_FAILURE) typedef struct map *Map; typedef struct map_element MapElement, *Binding; #if defined(__STDC__) || defined(__GNUC__) typedef XkReturn (*XMapResolveFunc)(Map, void *, void **); #else typedef XkReturn (*XMapResolveFunc)(); #endif #if defined(__STDC__) || defined(__GNUC__) typedef Binding (*XMapBindFunc)(Map, void *, void *); #else typedef Binding (*XMapBindFunc)(); #endif #if defined(__STDC__) || defined(__GNUC__) typedef XkReturn (*XMapRemoveFunc)(Map, Binding); #else typedef XkReturn (*XMapRemoveFunc)(); #endif #if defined(__STDC__) || defined(__GNUC__) typedef XkReturn (*XMapUnbindFunc)(Map, void *); #else typedef XkReturn (*XMapUnbindFunc)(); #endif /* * A map consists of three interwoven datastructures: * * (a) the actual hash-table to allow for efficient lookups and insertions; * (b) a one-entry cache storing the key of the last successful lookup or * insert operation; removing a mapping from the hash table resets the * cache to the empty state; * (c) a linked list to allow for fast sequential traversal of the map. * * The hash table consists of an array of NUM_BUCKETS buckets. A bucket * contains a linked list of map-elements. This linked list contains all * bindings with keys that hash to the same bucket (in no particular order). * * Non-empty buckets are chained together in a circular linked list that starts * at MAP->FIRST_BUCKET. For performance, removing elements from the list is * delayed until the list is traversed. The invariant is that (i) every * non-empty bucket is on the list and (ii) every bucket is at most once on the * list. A bucket that is not on the non-empty-buckets list has a NEXT_BUCKET * pointer of 0. */ struct map_bucket { MapElement *first; /* first map element in this bucket */ struct map_bucket *next; /* next (non-empty) bucket */ }; struct map { XMapBindFunc bind; XMapRemoveFunc remove; XMapUnbindFunc unbind; XMapResolveFunc resolve; MapElement *cache; /* cached entry or 0 */ int key_size; /* key-size (for fixed size maps) */ int num_buckets; /* length of array BUCKETS */ struct map_bucket *buckets; /* bucket table */ struct map_bucket chain; /* chain of (non-empty) buckets */ MapElement *freelist; }; struct map_element { struct map_element *next; /* next element with same hash value */ void *value; /* VALUE that KEY maps to */ union { struct { long key_size; /* key size for this element */ char key[1]; /* in reality of size map->keySize */ } var; struct { char key[1]; /* in reality of size map->keySize */ } fixed; } u; }; /* * The above type declarations should be moved into a separate header file * (e.g., idmap_s.h) such that other x-kernel header files can fetch the * declarations without dragging platform.h (which won't work due to circular * includes). When this is done, the includes below can be replaced by an * include of "platform.h". */ #include "xk_assert.h" /* XXX fixme! */ #include "xk_arch.h" /* XXX fixme! */ #if defined(__STDC__) || defined(__GNUC__) extern Map mapCreate(int table_len, int keySize); #else extern Map mapCreate(); #endif #if defined(__GNUC__) #ifndef XK_IS_TRUE_CONST /* * These should probably go into platform.h: */ #define XK_IS_TRUE_CONST(e) (__builtin_constant_p(e) && (e)) #define XK_ALIGNOF(e) (__alignof__(e)) #endif /* XK_IS_TRUE_CONST */ /* * Resolve for fixed sized keys. The macro mapResolve() is fat and ugly but * it yields highly efficient code in the `good case' and the normal indirect * call through map->resolve in the `bad' case. * * The good case occurs when the KEY_SIZE argument to mapResolve() is a * constant and a multiple of 2 (4 on Alphas) and if the type of the variable * to which the KEY argument points has a proper alignment (read the code for * the exact definition of `proper`). */ #ifdef __alpha__ /* * On the Alpha, it is not worthwhile to specialize case key-sizes that are a * multiple of 2 but not of 4 (because there is no hw support for short * loads/stores). */ #define mapResolve(_map, _key, _id) ({ \ __label__ _regular_lookup; \ MapElement *el = (_map)->cache; \ XkReturn r = XK_SUCCESS; \ char *lk = (char*)(_key); \ \ if (XK_IS_TRUE_CONST(XK_ALIGNOF(*(_key)) == sizeof(long) && \ (_map)->key_size % 4 == 0) && el PREDICT_TRUE) { \ char *rk = el->u.fixed.key; \ xk_u_int64 l1, r1, l2, r2; \ \ switch ((_map)->key_size) { \ case 12: l1 = *(xk_u_int64*)lk; r1 = *(xk_u_int64*)rk; \ lk += 8; rk += 8; \ case 4: l2 = *(xk_u_int32*)lk; r2 = *(xk_u_int32*)rk; \ break; \ case 16: l1 = *(xk_u_int64*)lk; r1 = *(xk_u_int64*)rk; \ lk += 8; rk += 8; \ case 8: l2 = *(xk_u_int64*)lk; r2 = *(xk_u_int64*)rk; \ break; \ default: break; \ } /* switch */ \ switch ((_map)->key_size) { \ case 12: case 16: \ if (l1 != r1 PREDICT_FALSE) \ goto _regular_lookup; \ case 4: case 8: \ if (l2 == r2 PREDICT_TRUE) { \ if ((_id)) \ *((void**)(_id)) = el->value; \ break; \ } else { \ (_map)->cache = 0; \ goto _regular_lookup; \ } /* if */ \ default: goto _regular_lookup; \ } /* switch */ \ } else { \ _regular_lookup: \ r = (*(_map)->resolve)((_map), (_key), (_id)); \ } /* if */ \ r; \ }) /* mapResolve */ #else /* !__alpha__ */ /* * On machines with short loads/stores, we also specialize 2, 6, and 10 byte * keys: */ #define mapResolve(_map, _key, _id) ({ \ __label__ _regular_lookup; \ MapElement *el = (_map)->cache; \ XkReturn r = XK_SUCCESS; \ char *lk = (char*)(_key); \ \ if (XK_IS_TRUE_CONST((XK_ALIGNOF(*(_key)) == sizeof(long) || \ XK_ALIGNOF(*(_key)) >= (_map)->key_size) && \ (_map)->key_size % 2 == 0) && el PREDICT_TRUE) { \ char *rk = el->u.fixed.key; \ \ switch ((_map)->key_size) { \ case 16: \ if (*((xk_u_int32*)lk) != *((xk_u_int32*)rk)) \ goto _regular_lookup; \ lk += 4; rk += 4; \ case 12: \ if (*((xk_u_int32*)lk) != *((xk_u_int32*)rk)) \ goto _regular_lookup; \ lk += 4; rk += 4; \ case 8: \ if (*((xk_u_int32*)lk) != *((xk_u_int32*)rk)) \ goto _regular_lookup; \ lk += 4; rk += 4; \ case 4: \ if (*((xk_u_int32*)lk) == *((xk_u_int32*)rk)) { \ if ((_id)) \ *((void**)(_id)) = el->value; \ break; \ } /* if */ \ (_map)->cache = 0; \ goto _regular_lookup; \ case 10: \ if (*((xk_u_int32*)lk) != *((xk_u_int32*)rk)) \ goto _regular_lookup; \ lk += 4; rk += 4; \ case 6: \ if (*((xk_u_int32*)lk) != *((xk_u_int32*)rk)) \ goto _regular_lookup; \ lk += 4; rk += 4; \ case 2: \ if (*((xk_u_int16*)lk) == *((xk_u_int16*)rk)) { \ if ((_id)) \ *((void**)(_id)) = el->value; \ break; \ } /* if */ \ (_map)->cache = 0; \ goto _regular_lookup; \ default: goto _regular_lookup; \ } /* switch */ \ } else { \ _regular_lookup: \ r = (*(_map)->resolve)((_map), (_key), (_id)); \ } /* if */ \ r; \ }) /* mapResolve */ #endif /* !__alpha__ */ #else /* !__GNUC__ */ #define mapResolve(_map, _key, _id) ((*(_map)->resolve)((_map), (_key), (_id))) #endif /* !__GNUC__ */ #define mapBind(_map, _key, _id) \ (_map)->bind((_map), (void *)(_key), (void *)(_id)) #define mapRemoveBinding(_map, _bind) (_map)->remove((_map), (_bind)) #define mapRemoveKey(_map, _key) (_map)->unbind((_map), (void *)(_key)) #if defined(__STDC__) || defined(__GNUC__) extern void mapClose(Map map); #else extern void mapClose(); #endif /* mapForEach return value flags */ #define MFE_CONTINUE (1<<0) #define MFE_REMOVE (1<<1) #if defined(__STDC__) || defined(__GNUC__) typedef int (*MapForEachFun)(void *key, void *id, void *arg); #else typedef int (*MapForEachFun)(); #endif #if defined(__STDC__) || defined(__GNUC__) extern void mapForEach(Map map, MapForEachFun func, void *arg); #else extern void mapForEach(); #endif /* * map_init is not part of the public map interface. It is to be * called once at xkernel initialization time. */ #if defined(__STDC__) || defined(__GNUC__) extern void map_init(void); #else extern void map_init(); #endif #endif /* idmap_h */