hash.h revision 7c2fbfb345896881c631598ee3852ce9ce33fb07
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/***********************************************************************
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* This software is part of the ast package *
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin* Copyright (c) 1985-2008 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 interface definitions
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * NOTE: new code should use the more general <cdt.h>
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#ifndef _HASH_H
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define _HASH_H
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_ALLOCATE (1L<<0) /* allocate new key names */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_FIXED (1L<<1) /* fixed table size */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_HASHED (1L<<6) /* key names already hashed */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_RESIZE (1L<<2) /* table has been resized */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_SCANNING (1L<<3) /* currently scanning scope */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_SCOPE (1L<<4) /* push scope / create in bot */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_STATIC (1L<<5) /* static table allocation */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_CREATE (1L<<8) /* create bucket if not found */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_DELETE (1L<<9) /* delete bucket if found */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_LOOKUP 0 /* default op */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_RENAME (1L<<7) /* rename bucket if found */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_BUCKET (1L<<11) /* name is installed bucket */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_INSTALL (1L<<12) /* install allocated bucket */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_NOSCOPE (1L<<13) /* top scope only */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_OPAQUE (1L<<14) /* opaque bucket */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_VALUE (1L<<15) /* value bucket field used */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_SIZE(n) (((long)(n))<<16) /* fixed bucket size */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_SIZEOF(f) ((((long)(f))>>16)&0xffff) /* extract size */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_DELETED ((unsigned long)1<<(8*sizeof(int)-1)) /* deleted placeholder */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_KEEP (1L<<(8*sizeof(int)-2)) /* no free on bucket */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_HIDDEN (1L<<(8*sizeof(int)-3)) /* hidden by scope */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_HIDES (1L<<(8*sizeof(int)-4)) /* hides lower scope */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_OPAQUED (1L<<(8*sizeof(int)-5)) /* opaqued placeholder */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_FREENAME (1L<<(8*sizeof(int)-6)) /* free bucket name */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_RESET (HASH_RESIZE|HASH_SCOPE|HASH_STATIC|HASH_VALUE)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_INTERNAL (HASH_BUCKET|HASH_RESIZE|HASH_SCANNING|HASH_STATIC)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_FLAGS (HASH_DELETED|HASH_FREENAME|HASH_HIDDEN|HASH_HIDES|HASH_KEEP|HASH_OPAQUED)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_alloc 1
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_clear 2
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_compare 3
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_free 4
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_hash 5
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_meanchain 6
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_name 7
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_namesize 8
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_set 9
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_size 10
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_table 11
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_va_list 12
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_bucketsize 13
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_region 14
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include <hashpart.h>
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define hashclear(t,f) ((t)->flags &= ~((f) & ~HASH_INTERNAL))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define hashcover(b) (((b)->hash&HASH_HIDES)?(Hash_bucket_t*)((b)->name):(Hash_bucket_t*)0)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define hashdel(t,n) hashlook(t, (char*)(n), HASH_DELETE, (char*)0)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define hashget(t,n) hashlook(t, (char*)(n), HASH_LOOKUP|HASH_VALUE, (char*)0)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define hashgetbucket(s) ((Hash_bucket_t*)((s)-((sizeof(Hash_bucket_t)+sizeof(char*)-1)/sizeof(char*))*sizeof(char*)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define hashkeep(b) ((b)->hash|=HASH_KEEP)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define hashname(b) ((((b)->hash&HASH_HIDES)?((Hash_bucket_t*)((b)->name)):(b))->name)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define hashput(t,n,v) hashlook(t, (char*)(n), HASH_CREATE|HASH_VALUE, (char*)(v))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define hashref(t,n) hashlook(t, (char*)(n), HASH_LOOKUP|HASH_INTERNAL|HASH_VALUE, (char*)0)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define hashscope(t) ((t)->scope)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define hashset(t,f) ((t)->flags |= ((f) & ~HASH_INTERNAL))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * DEPRECATED renames for compatibility
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define Hashbin_t Hash_bucket_t
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASHBUCKET Hash_bucket_t
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define Hashhdr_t Hash_header_t
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASHHEADER Hash_header_t
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define Hashpos_t Hash_position_t
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASHPOSITION Hash_position_t
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define Hashtab_t Hash_table_t
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASHTABLE Hash_table_t
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define vhashalloc hashvalloc
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define hashvalloc(t,a) hashalloc(t,HASH_va_list,a,0)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * the #define's avoid union tags
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct Hash_bucket Hash_bucket_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct Hash_root Hash_root_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct Hash_table Hash_table_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_HEADER /* common bucket header */ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_bucket_t* next; /* next in collision chain */ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin unsigned int hash; /* hash flags and value */ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin char* name /* key name */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define HASH_DEFAULT /* HASH_VALUE bucket elements */ \
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin char* value /* key value */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct /* bucket header */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin HASH_HEADER;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin} Hash_header_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstruct Hash_bucket /* prototype bucket */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin HASH_HEADER;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin HASH_DEFAULT;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin};
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct /* hash scan bucket position */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_bucket_t* bucket; /* bucket */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#ifdef _HASH_POSITION_PRIVATE_
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin _HASH_POSITION_PRIVATE_
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin} Hash_position_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct /* last lookup cache */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_table_t* table; /* last lookup table */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_bucket_t* bucket; /* last lookup bucket */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#ifdef _HASH_LAST_PRIVATE_
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin _HASH_LAST_PRIVATE_
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin} Hash_last_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstruct Hash_root /* root hash table information */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int accesses; /* number of accesses */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int collisions; /* number of collisions */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int flags; /* flags: see HASH_[A-Z]* */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_last_t last; /* last lookup cache */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin void* context; /* user defined context */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#ifdef _HASH_ROOT_PRIVATE_
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin _HASH_ROOT_PRIVATE_
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin};
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstruct Hash_table /* hash table information */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_root_t* root; /* root hash table information */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int size; /* table size */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int buckets; /* active bucket count */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin char* name; /* table name */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin Hash_table_t* scope; /* scope covered table */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin short flags; /* flags: see HASH_[A-Z]* */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#ifdef _HASH_TABLE_PRIVATE_
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin _HASH_TABLE_PRIVATE_
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin};
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#if _BLD_ast && defined(__EXPORT__)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#define extern __EXPORT__
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Hash_table_t* hashalloc(Hash_table_t*, ...);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern void hashdone(Hash_position_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern void hashdump(Hash_table_t*, int);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Hash_table_t* hashfree(Hash_table_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Hash_bucket_t* hashlast(Hash_table_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern char* hashlook(Hash_table_t*, const char*, long, const char*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Hash_bucket_t* hashnext(Hash_position_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Hash_position_t* hashscan(Hash_table_t*, int);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern void hashsize(Hash_table_t*, int);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern Hash_table_t* hashview(Hash_table_t*, Hash_table_t*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinextern int hashwalk(Hash_table_t*, int, int (*)(const char*, char*, void*), void*);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#undef extern
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#endif