1 /*********************************************************************** 2 * * 3 * This software is part of the BSD package * 4 *Copyright (c) 1978-2011 The Regents of the University of California an* 5 * * 6 * Redistribution and use in source and binary forms, with or * 7 * without modification, are permitted provided that the following * 8 * conditions are met: * 9 * * 10 * 1. Redistributions of source code must retain the above * 11 * copyright notice, this list of conditions and the * 12 * following disclaimer. * 13 * * 14 * 2. Redistributions in binary form must reproduce the above * 15 * copyright notice, this list of conditions and the * 16 * following disclaimer in the documentation and/or other * 17 * materials provided with the distribution. * 18 * * 19 * 3. Neither the name of The Regents of the University of California* 20 * names of its contributors may be used to endorse or * 21 * promote products derived from this software without * 22 * specific prior written permission. * 23 * * 24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND * 25 * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, * 26 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF * 27 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE * 28 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS * 29 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * 30 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED * 31 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * 32 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON * 33 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * 34 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * 35 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * 36 * POSSIBILITY OF SUCH DAMAGE. * 37 * * 38 * Redistribution and use in source and binary forms, with or without * 39 * modification, are permitted provided that the following conditions * 40 * are met: * 41 * 1. Redistributions of source code must retain the above copyright * 42 * notice, this list of conditions and the following disclaimer. * 43 * 2. Redistributions in binary form must reproduce the above copyright * 44 * notice, this list of conditions and the following disclaimer in * 45 * the documentation and/or other materials provided with the * 46 * distribution. * 47 * 3. Neither the name of the University nor the names of its * 48 * contributors may be used to endorse or promote products derived * 49 * from this software without specific prior written permission. * 50 * * 51 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS "AS IS" * 52 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED * 53 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A * 54 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS * 55 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, * 56 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT * 57 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF * 58 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND * 59 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, * 60 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT * 61 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * 62 * SUCH DAMAGE. * 63 * * 64 * Kurt Shoens (UCB) * 65 * gsf * 66 * * 67 ***********************************************************************/ 68 #ifndef _CDT_H 69 #define _CDT_H 1 70 71 /* 72 ** Public interface for the dictionary library 73 ** 74 ** Written by Kiem-Phong Vo (07/15/95) 75 ** AT&T Bell Laboratories 76 */ 77 78 /*{KPV: standard definitions */ 79 80 /* The symbol __STD_C indicates that the language is ANSI-C or C++ */ 81 #ifndef __STD_C 82 #ifdef __STDC__ 83 #define __STD_C 1 84 #else 85 #if __cplusplus || c_plusplus 86 #define __STD_C 1 87 #else 88 #define __STD_C 0 89 #endif /*__cplusplus*/ 90 #endif /*__STDC__*/ 91 #endif /*__STD_C*/ 92 93 /* For C++, extern symbols must be protected against name mangling */ 94 #ifndef _BEGIN_EXTERNS_ 95 #if __cplusplus || c_plusplus 96 #define _BEGIN_EXTERNS_ extern "C" { 97 #define _END_EXTERNS_ } 98 #else 99 #define _BEGIN_EXTERNS_ 100 #define _END_EXTERNS_ 101 #endif 102 #endif /*_BEGIN_EXTERNS_*/ 103 104 /* _ARG_ simplifies function prototypes between K&R-C and more modern Cs */ 105 #ifndef _ARG_ 106 #if __STD_C 107 #define _ARG_(x) x 108 #else 109 #define _ARG_(x) () 110 #endif 111 #endif /*_ARG_*/ 112 113 /* __INLINE__ if defined is the inline keyword */ 114 #if !defined(__INLINE__) 115 #if defined(__cplusplus) 116 #define __INLINE__ inline 117 #else 118 #if defined(_WIN32) || _WINIX 119 #define __INLINE__ __inline 120 #endif/*_WIN32*/ 121 #endif/*__cplusplus*/ 122 #endif/*__INLINE__*/ 123 124 /* The type Void_t is properly defined so that Void_t* can address any type */ 125 #ifndef Void_t 126 #if __STD_C 127 #define Void_t void 128 #else 129 #define Void_t char 130 #endif 131 #endif /*Void_t*/ 132 133 /* The NIL() macro simplifies defining nil pointers to a given type */ 134 #ifndef NIL 135 #define NIL(type) ((type)0) 136 #endif /*NIL*/ 137 138 /* For DLLs on systems allowing only pointers across client and library code. */ 139 #ifndef _PTR_ 140 #if _PACKAGE_ast && !__BLD_DLL && _DLL_INDIRECT_DATA 141 #define _ADR_ /* data access via ptrs only */ 142 #define _PTR_ * 143 #else 144 #define _ADR_ & /* normal exporting of data ok */ 145 #define _PTR_ 146 #endif 147 #endif /*_PTR_*/ 148 149 #if !_PACKAGE_ast && _BLD_DLL && defined(_WIN32) 150 #if _KPV_ONLY /* internal code compilation */ 151 #define extern __declspec(dllexport) 152 #else /* client code compilation */ 153 #define extern __declspec(dllimport) 154 #endif 155 #endif 156 157 #if __STD_C 158 #include <stddef.h> 159 #else 160 #include <sys/types.h> 161 #endif 162 163 /*KPV} */ 164 165 typedef struct _dtlink_s Dtlink_t; 166 typedef struct _dthold_s Dthold_t; 167 typedef struct _dtdisc_s Dtdisc_t; 168 typedef struct _dtmethod_s Dtmethod_t; 169 typedef struct _dtdata_s Dtdata_t; 170 typedef struct _dt_s Dt_t; 171 typedef struct _dt_s Dict_t; /* for libdict compatibility */ 172 typedef struct _dtstat_s Dtstat_t; 173 typedef Void_t* (*Dtsearch_f)_ARG_((Dt_t*,Void_t*,int)); 174 typedef Void_t* (*Dtmake_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*)); 175 typedef void (*Dtfree_f)_ARG_((Dt_t*,Void_t*,Dtdisc_t*)); 176 typedef int (*Dtcompar_f)_ARG_((Dt_t*,char*,char*,Dtdisc_t*)); 177 typedef unsigned long (*Dthash_f)_ARG_((Dt_t*,char*,Dtdisc_t*)); 178 typedef Void_t* (*Dtmemory_f)_ARG_((Dt_t*,Void_t*,size_t,Dtdisc_t*)); 179 typedef int (*Dtevent_f)_ARG_((Dt_t*,int,Void_t*,Dtdisc_t*)); 180 181 struct _dtlink_s 182 { Dtlink_t* right; /* right child */ 183 union 184 { unsigned long _hash; /* hash value */ 185 Dtlink_t* _left; /* left child */ 186 } hl; 187 }; 188 189 /* private structure to hold an object */ 190 struct _dthold_s 191 { Dtlink_t hdr; /* header */ 192 Void_t* obj; /* user object */ 193 }; 194 195 /* method to manipulate dictionary structure */ 196 struct _dtmethod_s 197 { Dtsearch_f searchf; /* search function */ 198 int type; /* type of operation */ 199 }; 200 201 /* stuff that may have to be in shared memory */ 202 struct _dtdata_s 203 { int type; /* type of dictionary */ 204 Dtlink_t* here; /* finger to last search element */ 205 union 206 { Dtlink_t** _htab; /* hash table */ 207 Dtlink_t* _head; /* linked list */ 208 } hh; 209 int ntab; /* number of hash slots */ 210 int size; /* number of objects */ 211 }; 212 213 /* structure to hold methods that manipulate an object */ 214 struct _dtdisc_s 215 { int key; /* where key begins in object */ 216 int size; /* key size */ 217 int link; /* offset to Dtlink_t field */ 218 Dtmake_f makef; /* object constructor */ 219 Dtfree_f freef; /* object destructor */ 220 Dtcompar_f comparf;/* to compare two objects */ 221 Dthash_f hashf; /* to compute a hash value for objects */ 222 Dtmemory_f memoryf;/* to get memory for objects */ 223 Dtevent_f eventf; /* to process events */ 224 }; 225 226 /* the dictionary structure itself */ 227 struct _dt_s 228 { Dtsearch_f searchf;/* searching function */ 229 Dtdisc_t* disc; /* method to manipulate objs */ 230 Dtdata_t* data; /* sharable data */ 231 Dtmemory_f memoryf;/* function to alloc/free memory */ 232 Dtmethod_t* meth; /* dictionary method */ 233 int type; /* type information */ 234 int nview; /* number of parent view dictionaries */ 235 Dt_t* view; /* next on viewpath */ 236 Dt_t* walk; /* dictionary being walked */ 237 }; 238 239 /* structure to get status of a dictionary */ 240 struct _dtstat_s 241 { int dt_meth; /* method type */ 242 int dt_size; /* number of elements */ 243 int dt_n; /* number of chains or levels */ 244 int dt_max; /* max size of a chain or a level */ 245 int* dt_count; /* counts of chains or levels by size */ 246 }; 247 248 /* supported storage methods */ 249 #define DT_HASH 000001 /* hashing with chaining */ 250 #define DT_TREE 000002 /* self-adjusting tree */ 251 #define DT_LIST 000004 /* linked list */ 252 #define DT_STACK 000010 /* stack */ 253 #define DT_QUEUE 000020 /* queue */ 254 #define DT_METHODS 000037 /* all currently supported methods */ 255 256 /* events */ 257 #define DT_OPEN 1 /* a dictionary is being opened */ 258 #define DT_CLOSE 2 /* a dictionary is being closed */ 259 #define DT_DISC 3 /* discipline is about to be changed */ 260 #define DT_METH 4 /* method is about to be changed */ 261 262 /* asserts to dtdisc() */ 263 #define DT_COMPARF 000001 /* compare functions equivalent */ 264 #define DT_HASHF 000002 /* hash functions equivalent */ 265 266 /* types of search - for internal use only */ 267 #define DT_INSERT 000001 /* insert object if not found */ 268 #define DT_DELETE 000002 /* delete object if found */ 269 #define DT_SEARCH 000004 /* look for an object */ 270 #define DT_NEXT 000010 /* look for next element */ 271 #define DT_PREV 000020 /* find previous element */ 272 #define DT_RENEW 000040 /* renewing an object */ 273 #define DT_CLEAR 000100 /* clearing all objects */ 274 #define DT_FIRST 000200 /* get first object */ 275 #define DT_LAST 000400 /* get last object */ 276 #define DT_MATCH 001000 /* find object matching key */ 277 278 _BEGIN_EXTERNS_ 279 extern Dt_t* dtopen _ARG_((Dtdisc_t*, Dtmethod_t*)); 280 extern int dtclose _ARG_((Dt_t*)); 281 extern Dt_t* dtview _ARG_((Dt_t*, Dt_t*)); 282 extern Dtdisc_t* dtdisc _ARG_((Dt_t* dt, Dtdisc_t*, int)); 283 extern Dtmethod_t* dtmethod _ARG_((Dt_t*, Dtmethod_t*)); 284 285 extern Dtlink_t* dtflatten _ARG_((Dt_t*)); 286 extern Dtlink_t* dtextract _ARG_((Dt_t*)); 287 extern int dtrestore _ARG_((Dt_t*, Dtlink_t*)); 288 289 extern int dtwalk _ARG_((Dt_t*, int(*)(Dt_t*,Void_t*,Void_t*), Void_t*)); 290 291 extern Void_t* dtrenew _ARG_((Dt_t*, Void_t*)); 292 293 extern int dtsize _ARG_((Dt_t*)); 294 extern int dtstat _ARG_((Dt_t*, Dtstat_t*, int)); 295 extern unsigned long dtstrhash _ARG_((unsigned long, char*, int)); 296 297 extern Dtmethod_t _PTR_ _Dthash; 298 extern Dtmethod_t _PTR_ _Dttree; 299 extern Dtmethod_t _PTR_ _Dtlist; 300 extern Dtmethod_t _PTR_ _Dtstack; 301 extern Dtmethod_t _PTR_ _Dtqueue; 302 _END_EXTERNS_ 303 304 #define Dtset (_ADR_ _Dthash) 305 #define Dtoset (_ADR_ _Dttree) 306 #define Dtlist (_ADR_ _Dtlist) 307 #define Dtstack (_ADR_ _Dtstack) 308 #define Dtqueue (_ADR_ _Dtqueue) 309 310 #define _DT_(d) ((Dt_t*)(d)) 311 312 #define dtlink(d,e) (((Dtlink_t*)(e))->right) 313 #define dtobj(d,e) ((_DT_(d)->disc->link < 0) ? (((Dthold_t*)(e))->obj) : \ 314 (Void_t*)((char*)(e) - _DT_(d)->disc->link) ) 315 #define dtfinger(d) (_DT_(d)->data->here ? dtobj((d),_DT_(d)->data->here) : \ 316 NIL(Void_t*) ) 317 318 #define dtfirst(d) (*(_DT_(d)->searchf))((d),NIL(Void_t*),DT_FIRST) 319 #define dtnext(d,o) (*(_DT_(d)->searchf))((d),(Void_t*)(o),DT_NEXT) 320 #define dtlast(d) (*(_DT_(d)->searchf))((d),NIL(Void_t*),DT_LAST) 321 #define dtprev(d,o) (*(_DT_(d)->searchf))((d),(Void_t*)(o),DT_PREV) 322 #define dtsearch(d,o) (*(_DT_(d)->searchf))((d),(Void_t*)(o),DT_SEARCH) 323 #define dtinsert(d,o) (*(_DT_(d)->searchf))((d),(Void_t*)(o),DT_INSERT) 324 #define dtdelete(d,o) (*(_DT_(d)->searchf))((d),(Void_t*)(o),DT_DELETE) 325 #define dtmatch(d,o) (*(_DT_(d)->searchf))((d),(Void_t*)(o),DT_MATCH) 326 #define dtclear(d) (*(_DT_(d)->searchf))((d),NIL(Void_t*),DT_CLEAR) 327 328 /* A linear congruential hash: h*127 + c + 987654321 */ 329 #define dtcharhash(h,c) ((((unsigned long)(h))<<7) - ((unsigned long)(h)) + \ 330 ((unsigned char)(c)) + 987654321L ) 331 332 #endif /* _CDT_H */ 333