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 private definitions
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#ifndef _HASHLIB_H
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _HASHLIB_H
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include <ast.h>
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define hash_info _hash_info_
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef void* (*Hash_alloc_f)(size_t);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef int (*Hash_compare_f)(const char*, const char*, ...);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef unsigned int (*Hash_hash_f)(const char*, ...);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef void (*Hash_free_f)(void*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef void* (*Hash_region_f)(void*, void*, size_t, int);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct /* root local pointers */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_hash_f hash; /* name hash routine */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_compare_f compare; /* name comparision routine */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_alloc_f alloc; /* value allocation routine */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_free_f free; /* value free routine */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_region_f region; /* region alloc/free routine */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin void* handle; /* region handle arg */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin} Hash_local_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _HASH_POSITION_PRIVATE_ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_table_t* tab; /* table pointer */ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int flags; /* scan flags */ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_bucket_t** slot; /* table slot */ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_bucket_t** limit; /* slot limit */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _HASH_LAST_PRIVATE_ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin const char* name; /* last lookup name */ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin unsigned int hash; /* last lookup hash */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _HASH_ROOT_PRIVATE_ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int namesize; /* fixed name size: 0 => string */ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int meanchain; /* resize mean chain length */ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_local_t* local; /* root local pointers */ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_root_t* next; /* next in list of all roots */ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_table_t* references; /* referencing table list */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _HASH_TABLE_PRIVATE_ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin unsigned char frozen; /* table freeze nesting */ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin unsigned char bucketsize; /* min bucket size in char*'s */ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_bucket_t** table; /* hash slot table */ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_table_t* next; /* root reference list link */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include <hash.h>
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASHMINSIZE (1<<4) /* min table slots (power of 2) */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASHMEANCHAIN 2 /* def resize mean chain len */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASHMOD(t,h) (h &= (t->size - 1))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASHVAL(x) ((x)&~HASH_FLAGS)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH(r,n,h) if (r->local->hash) h = r->namesize ? (*r->local->hash)(n, r->namesize) : (*r->local->hash)(n);\
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else\
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {\
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin register const char* _hash_s1 = n;\
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin h = 0;\
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (r->namesize)\
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {\
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin register const char* _hash_s2 = _hash_s1 + r->namesize;\
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin while (_hash_s1 < _hash_s2) HASHPART(h, *_hash_s1++);\
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }\
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else while (*_hash_s1) HASHPART(h, *_hash_s1++);\
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct /* library private info */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_root_t* list; /* root table list */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin} Hash_info_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Hash_info_t hash_info;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif