15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 2001 September 22 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The author disclaims copyright to this source code. In place of 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** a legal notice, here is a blessing: 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** May you do good and not evil. 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** May you find forgiveness for yourself and forgive others. 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** May you share freely, never taking more than you give. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)************************************************************************* 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** This is the header file for the generic hash-table implemenation 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** used in SQLite. We've modified it slightly to serve as a standalone 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** hash table implementation for the full-text indexing module. 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifndef _HASH_H_ 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define _HASH_H_ 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Forward declarations of structures. */ 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct Hash Hash; 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct HashElem HashElem; 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* A complete hash table is an instance of the following structure. 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The internals of this structure are intended to be opaque -- client 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** code should not attempt to access or modify the fields of this structure 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** directly. Change this structure only by using the routines below. 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** However, many of the "procedures" and "functions" for modifying and 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** accessing this structure are really macros, so we can't really make 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** this structure opaque. 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct Hash { 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char keyClass; /* HASH_INT, _POINTER, _STRING, _BINARY */ 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) char copyKey; /* True if copy of key made on insert */ 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int count; /* Number of entries in this table */ 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HashElem *first; /* The first element of the array */ 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *(*xMalloc)(int); /* malloc() function to use */ 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void (*xFree)(void *); /* free() function to use */ 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int htsize; /* Number of buckets in the hash table */ 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct _ht { /* the hash table */ 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int count; /* Number of entries with this hash */ 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HashElem *chain; /* Pointer to first entry with this hash */ 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } *ht; 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Each element in the hash table is an instance of the following 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** structure. All elements are stored on a single doubly-linked list. 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Again, this structure is intended to be opaque, but it can't really 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** be opaque because it is used by macros. 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct HashElem { 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HashElem *next, *prev; /* Next and previous elements in the table */ 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *data; /* Data associated with this element */ 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *pKey; int nKey; /* Key associated with this element */ 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** There are 4 different modes of operation for a hash table: 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** HASH_INT nKey is used as the key and pKey is ignored. 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** HASH_POINTER pKey is used as the key and nKey is ignored. 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** HASH_STRING pKey points to a string that is nKey bytes long 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** (including the null-terminator, if any). Case 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** is respected in comparisons. 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** HASH_BINARY pKey points to binary data nKey bytes long. 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** memcmp() is used to compare keys. 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** A copy of the key is made for HASH_STRING and HASH_BINARY 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** if the copyKey parameter to HashInit is 1. 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* #define HASH_INT 1 // NOT USED */ 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* #define HASH_POINTER 2 // NOT USED */ 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HASH_STRING 3 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HASH_BINARY 4 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Access routines. To delete, insert a NULL pointer. 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void HashInit(Hash*, int keytype, int copyKey); 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void *HashInsert(Hash*, const void *pKey, int nKey, void *pData); 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void *HashFind(const Hash*, const void *pKey, int nKey); 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void HashClear(Hash*); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Macros for looping over all elements of a hash table. The idiom is 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** like this: 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Hash h; 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** HashElem *p; 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** ... 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** for(p=HashFirst(&h); p; p=HashNext(p)){ 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** SomeStructure *pData = HashData(p); 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** // do something with pData 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** } 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HashFirst(H) ((H)->first) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HashNext(E) ((E)->next) 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HashData(E) ((E)->data) 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HashKey(E) ((E)->pKey) 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HashKeysize(E) ((E)->nKey) 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Number of entries in a hash table 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HashCount(H) ((H)->count) 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* _HASH_H_ */ 112