cde/programs/dtksh/ksh93/src/lib/libast/include/hash.h

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these libraries and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: hash.h /main/3 1995/11/01 17:36:47 rswiston $ */
  24 /***************************************************************
  25 *                                                              *
  26 *                      AT&T - PROPRIETARY                      *
  27 *                                                              *
  28 *         THIS IS PROPRIETARY SOURCE CODE LICENSED BY          *
  29 *                          AT&T CORP.                          *
  30 *                                                              *
  31 *                Copyright (c) 1995 AT&T Corp.                 *
  32 *                     All Rights Reserved                      *
  33 *                                                              *
  34 *           This software is licensed by AT&T Corp.            *
  35 *       under the terms and conditions of the license in       *
  36 *       http://www.research.att.com/orgs/ssr/book/reuse        *
  37 *                                                              *
  38 *               This software was created by the               *
  39 *           Software Engineering Research Department           *
  40 *                    AT&T Bell Laboratories                    *
  41 *                                                              *
  42 *               For further information contact                *
  43 *                     gsf@research.att.com                     *
  44 *                                                              *
  45 ***************************************************************/
  46
  47 /* : : generated by proto : : */
  48
  49 /*
  50  * Glenn Fowler
  51  * AT&T Bell Laboratories
  52  *
  53  * hash table library interface definitions
  54  */
  55
  56 #ifndef _HASH_H
  57 #if !defined(__PROTO__)
  58 #if defined(__STDC__) || defined(__cplusplus) || defined(_proto) || defined(c_plusplus)
  59 #if defined(__cplusplus)
  60 #define __MANGLE__      "C"
  61 #else
  62 #define __MANGLE__
  63 #endif
  64 #define __STDARG__
  65 #define __PROTO__(x)    x
  66 #define __OTORP__(x)
  67 #define __PARAM__(n,o)  n
  68 #if !defined(__STDC__) && !defined(__cplusplus)
  69 #if !defined(c_plusplus)
  70 #define const
  71 #endif
  72 #define signed
  73 #define void            int
  74 #define volatile
  75 #define __V_            char
  76 #else
  77 #define __V_            void
  78 #endif
  79 #else
  80 #define __PROTO__(x)    ()
  81 #define __OTORP__(x)    x
  82 #define __PARAM__(n,o)  o
  83 #define __MANGLE__
  84 #define __V_            char
  85 #define const
  86 #define signed
  87 #define void            int
  88 #define volatile
  89 #endif
  90 #if defined(__cplusplus) || defined(c_plusplus)
  91 #define __VARARG__      ...
  92 #else
  93 #define __VARARG__
  94 #endif
  95 #if defined(__STDARG__)
  96 #define __VA_START__(p,a)       va_start(p,a)
  97 #else
  98 #define __VA_START__(p,a)       va_start(p)
  99 #endif
 100 #endif
 101
 102 #define _HASH_H
 103
 104 /*
 105  * NOTE: hash_info is obsolete; use hashlast()
 106  */
 107
 108 #if _DLL_INDIRECT_DATA && !_DLL
 109 #define hash_info       (*_hash_info_)
 110 #else
 111 #define hash_info       _hash_info_
 112 #endif
 113
 114 #define HASH_ALLOCATE   (1L<<0)         /* allocate new key names       */
 115 #define HASH_FIXED      (1L<<1)         /* fixed table size             */
 116 #define HASH_HASHED     (1L<<6)         /* key names already hashed     */
 117 #define HASH_RESIZE     (1L<<2)         /* table has been resized       */
 118 #define HASH_SCANNING   (1L<<3)         /* currently scanning scope     */
 119 #define HASH_SCOPE      (1L<<4)         /* push scope / create in bot   */
 120 #define HASH_STATIC     (1L<<5)         /* static table allocation      */
 121
 122 #define HASH_CREATE     (1L<<8)         /* create bucket if not found   */
 123 #define HASH_DELETE     (1L<<9)         /* delete bucket if found       */
 124 #define HASH_LOOKUP     0               /* default op                   */
 125
 126 #define HASH_BUCKET     (1L<<11)        /* name is installed bucket     */
 127 #define HASH_INSTALL    (1L<<12)        /* install allocated bucket     */
 128 #define HASH_NOSCOPE    (1L<<13)        /* top scope only               */
 129 #define HASH_OPAQUE     (1L<<14)        /* opaque bucket                */
 130 #define HASH_VALUE      (1L<<15)        /* value bucket field used      */
 131
 132 #define HASH_SIZE(n)    (((long)(n))<<16)  /* fixed bucket size         */
 133 #define HASH_SIZEOF(f)  ((((long)(f))>>16)&0xffff) /* extract size      */
 134
 135 #define HASH_DELETED    ((unsigned long)1<<(8*sizeof(int)-1)) /* deleted placeholder    */
 136 #define HASH_KEEP       (1L<<(8*sizeof(int)-2)) /* no free on bucket    */
 137 #define HASH_HIDDEN     (1L<<(8*sizeof(int)-3)) /* hidden by scope      */
 138 #define HASH_HIDES      (1L<<(8*sizeof(int)-4)) /* hides lower scope    */
 139 #define HASH_OPAQUED    (1L<<(8*sizeof(int)-5)) /* opaqued placeholder  */
 140
 141 #define HASH_RESET      (HASH_RESIZE|HASH_SCOPE|HASH_STATIC|HASH_VALUE)
 142 #define HASH_INTERNAL   (HASH_BUCKET|HASH_RESIZE|HASH_SCANNING|HASH_STATIC)
 143 #define HASH_FLAGS      (HASH_DELETED|HASH_HIDDEN|HASH_HIDES|HASH_KEEP|HASH_OPAQUED)
 144
 145 #define HASH_alloc              1
 146 #define HASH_clear              2
 147 #define HASH_compare            3
 148 #define HASH_free               4
 149 #define HASH_hash               5
 150 #define HASH_meanchain          6
 151 #define HASH_name               7
 152 #define HASH_namesize           8
 153 #define HASH_set                9
 154 #define HASH_size               10
 155 #define HASH_table              11
 156 #define HASH_va_list            12
 157
 158 #define HASH_bucketsize         13
 159
 160 #define HASH_region             14
 161
 162 #include <hashpart.h>
 163
 164 #define hashclear(t,f)          ((t)->flags &= ~((f) & ~HASH_INTERNAL))
 165 #define hashcover(b)            (((b)->hash&HASH_HIDES)?(Hash_bucket_t*)((b)->name):(Hash_bucket_t*)0)
 166 #define hashdel(t,n)            hashlook(t, (char*)(n), HASH_DELETE, (char*)0)
 167 #define hashget(t,n)            hashlook(t, (char*)(n), HASH_LOOKUP|HASH_VALUE, (char*)0)
 168 #define hashkeep(b)             ((b)->hash|=HASH_KEEP)
 169 #define hashname(b)             ((((b)->hash&HASH_HIDES)?((Hash_bucket_t*)((b)->name)):(b))->name)
 170 #define hashput(t,n,v)          hashlook(t, (char*)(n), HASH_CREATE|HASH_VALUE, (char*)(v))
 171 #define hashref(t,n)            hashlook(t, (char*)(n), HASH_LOOKUP|HASH_INTERNAL|HASH_VALUE, (char*)0)
 172 #define hashscope(t)            ((t)->scope)
 173 #define hashset(t,f)            ((t)->flags |= ((f) & ~HASH_INTERNAL))
 174
 175 /*
 176  * DEPRECATED renames for compatibility
 177  */
 178
 179 #define Hashbin_t               Hash_bucket_t
 180 #define HASHBUCKET              Hash_bucket_t
 181 #define Hashhdr_t               Hash_header_t
 182 #define HASHHEADER              Hash_header_t
 183 #define Hashpos_t               Hash_position_t
 184 #define HASHPOSITION            Hash_position_t
 185 #define Hashtab_t               Hash_table_t
 186 #define HASHTABLE               Hash_table_t
 187
 188 #define vhashalloc              hashvalloc
 189 #define hashvalloc(t,a)         hashalloc(t,HASH_va_list,a,0)
 190
 191 /*
 192  * the #define's avoid union tags
 193  */
 194
 195 typedef struct Hash_bucket Hash_bucket_t;
 196 typedef struct Hash_root Hash_root_t;
 197 typedef struct Hash_table Hash_table_t;
 198
 199 #define HASH_HEADER                     /* common bucket header         */ \
 200         Hash_bucket_t*  next;           /* next in collision chain      */ \
 201         unsigned int    hash;           /* hash flags and value         */ \
 202         char*           name            /* key name                     */
 203
 204 #define HASH_DEFAULT                    /* HASH_VALUE bucket elements   */ \
 205         char*           value           /* key value                    */
 206
 207 typedef struct                          /* bucket header                */
 208 {
 209         HASH_HEADER;
 210 } Hash_header_t;
 211
 212 struct Hash_bucket                      /* prototype bucket             */
 213 {
 214         HASH_HEADER;
 215         HASH_DEFAULT;
 216 };
 217
 218 typedef struct                          /* hash scan bucket position    */
 219 {
 220         Hash_bucket_t*  bucket;         /* bucket                       */
 221 #ifdef _HASH_POSITION_PRIVATE_
 222         _HASH_POSITION_PRIVATE_
 223 #endif
 224 } Hash_position_t;
 225
 226 struct Hash_root                        /* root hash table information  */
 227 {
 228         int             accesses;       /* number of accesses           */
 229         int             collisions;     /* number of collisions         */
 230         int             flags;          /* flags: see HASH_[A-Z]*       */
 231 #ifdef _HASH_ROOT_PRIVATE_
 232         _HASH_ROOT_PRIVATE_
 233 #endif
 234 };
 235
 236 struct Hash_table                       /* hash table information       */
 237 {
 238         Hash_root_t*    root;           /* root hash table information  */
 239         int             size;           /* table size                   */
 240         int             buckets;        /* active bucket count          */
 241         char*           name;           /* table name                   */
 242         Hash_table_t*   scope;          /* scope covered table          */
 243         short           flags;          /* flags: see HASH_[A-Z]*       */
 244 #ifdef _HASH_TABLE_PRIVATE_
 245         _HASH_TABLE_PRIVATE_
 246 #endif
 247 };
 248
 249 typedef struct                          /* library hash info            */
 250 {
 251         Hash_bucket_t*  last;           /* most recent lookup bucket    */
 252         Hash_table_t*   table;          /* most recent lookup table     */
 253 #ifdef _HASH_INFO_PRIVATE_
 254         _HASH_INFO_PRIVATE_
 255 #endif
 256 } Hash_info_t;
 257
 258 extern __MANGLE__ Hash_info_t   hash_info;
 259
 260 extern __MANGLE__ Hash_table_t* hashalloc __PROTO__((Hash_table_t*, ...));
 261 extern __MANGLE__ void          hashdone __PROTO__((Hash_position_t*));
 262 extern __MANGLE__ void          hashdump __PROTO__((Hash_table_t*, int));
 263 extern __MANGLE__ Hash_table_t* hashfree __PROTO__((Hash_table_t*));
 264 extern __MANGLE__ Hash_bucket_t*        hashlast __PROTO__((Hash_table_t*));
 265 extern __MANGLE__ char*         hashlook __PROTO__((Hash_table_t*, const char*, long, const char*));
 266 extern __MANGLE__ Hash_bucket_t*        hashnext __PROTO__((Hash_position_t*));
 267 extern __MANGLE__ Hash_position_t*      hashscan __PROTO__((Hash_table_t*, int));
 268 extern __MANGLE__ void          hashsize __PROTO__((Hash_table_t*, int));
 269 extern __MANGLE__ int           hashwalk __PROTO__((Hash_table_t*, int, int (*)(const char*, char*, __V_*), __V_*));
 270
 271 extern __MANGLE__ unsigned int  memhash __PROTO__((const __V_*, int));
 272 extern __MANGLE__ unsigned long memsum __PROTO__((const __V_*, int, unsigned long));
 273 extern __MANGLE__ unsigned int  strhash __PROTO__((const char*));
 274 extern __MANGLE__ unsigned long strsum __PROTO__((const char*, unsigned long));
 275
 276 #endif