/ Hex Artifact Content
Login

Artifact 06df7bba40dadd19597aa400a875dbc2fed705ea:


0000: 2f 2a 0a 2a 2a 20 32 30 30 31 20 53 65 70 74 65  /*.** 2001 Septe
0010: 6d 62 65 72 20 32 32 0a 2a 2a 0a 2a 2a 20 54 68  mber 22.**.** Th
0020: 65 20 61 75 74 68 6f 72 20 64 69 73 63 6c 61 69  e author disclai
0030: 6d 73 20 63 6f 70 79 72 69 67 68 74 20 74 6f 20  ms copyright to 
0040: 74 68 69 73 20 73 6f 75 72 63 65 20 63 6f 64 65  this source code
0050: 2e 20 20 49 6e 20 70 6c 61 63 65 20 6f 66 0a 2a  .  In place of.*
0060: 2a 20 61 20 6c 65 67 61 6c 20 6e 6f 74 69 63 65  * a legal notice
0070: 2c 20 68 65 72 65 20 69 73 20 61 20 62 6c 65 73  , here is a bles
0080: 73 69 6e 67 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 4d  sing:.**.**    M
0090: 61 79 20 79 6f 75 20 64 6f 20 67 6f 6f 64 20 61  ay you do good a
00a0: 6e 64 20 6e 6f 74 20 65 76 69 6c 2e 0a 2a 2a 20  nd not evil..** 
00b0: 20 20 20 4d 61 79 20 79 6f 75 20 66 69 6e 64 20     May you find 
00c0: 66 6f 72 67 69 76 65 6e 65 73 73 20 66 6f 72 20  forgiveness for 
00d0: 79 6f 75 72 73 65 6c 66 20 61 6e 64 20 66 6f 72  yourself and for
00e0: 67 69 76 65 20 6f 74 68 65 72 73 2e 0a 2a 2a 20  give others..** 
00f0: 20 20 20 4d 61 79 20 79 6f 75 20 73 68 61 72 65     May you share
0100: 20 66 72 65 65 6c 79 2c 20 6e 65 76 65 72 20 74   freely, never t
0110: 61 6b 69 6e 67 20 6d 6f 72 65 20 74 68 61 6e 20  aking more than 
0120: 79 6f 75 20 67 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a  you give..**.***
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0170: 2a 2a 2a 2a 2a 2a 0a 2a 2a 20 54 68 69 73 20 69  ******.** This i
0180: 73 20 74 68 65 20 68 65 61 64 65 72 20 66 69 6c  s the header fil
0190: 65 20 66 6f 72 20 74 68 65 20 67 65 6e 65 72 69  e for the generi
01a0: 63 20 68 61 73 68 2d 74 61 62 6c 65 20 69 6d 70  c hash-table imp
01b0: 6c 65 6d 65 6e 74 61 74 69 6f 6e 0a 2a 2a 20 75  lementation.** u
01c0: 73 65 64 20 69 6e 20 53 51 4c 69 74 65 2e 20 20  sed in SQLite.  
01d0: 57 65 27 76 65 20 6d 6f 64 69 66 69 65 64 20 69  We've modified i
01e0: 74 20 73 6c 69 67 68 74 6c 79 20 74 6f 20 73 65  t slightly to se
01f0: 72 76 65 20 61 73 20 61 20 73 74 61 6e 64 61 6c  rve as a standal
0200: 6f 6e 65 0a 2a 2a 20 68 61 73 68 20 74 61 62 6c  one.** hash tabl
0210: 65 20 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e  e implementation
0220: 20 66 6f 72 20 74 68 65 20 66 75 6c 6c 2d 74 65   for the full-te
0230: 78 74 20 69 6e 64 65 78 69 6e 67 20 6d 6f 64 75  xt indexing modu
0240: 6c 65 2e 0a 2a 2a 0a 2a 2f 0a 23 69 66 6e 64 65  le..**.*/.#ifnde
0250: 66 20 5f 48 41 53 48 5f 48 5f 0a 23 64 65 66 69  f _HASH_H_.#defi
0260: 6e 65 20 5f 48 41 53 48 5f 48 5f 0a 0a 2f 2a 20  ne _HASH_H_../* 
0270: 46 6f 72 77 61 72 64 20 64 65 63 6c 61 72 61 74  Forward declarat
0280: 69 6f 6e 73 20 6f 66 20 73 74 72 75 63 74 75 72  ions of structur
0290: 65 73 2e 20 2a 2f 0a 74 79 70 65 64 65 66 20 73  es. */.typedef s
02a0: 74 72 75 63 74 20 48 61 73 68 20 48 61 73 68 3b  truct Hash Hash;
02b0: 0a 74 79 70 65 64 65 66 20 73 74 72 75 63 74 20  .typedef struct 
02c0: 48 61 73 68 45 6c 65 6d 20 48 61 73 68 45 6c 65  HashElem HashEle
02d0: 6d 3b 0a 0a 2f 2a 20 41 20 63 6f 6d 70 6c 65 74  m;../* A complet
02e0: 65 20 68 61 73 68 20 74 61 62 6c 65 20 69 73 20  e hash table is 
02f0: 61 6e 20 69 6e 73 74 61 6e 63 65 20 6f 66 20 74  an instance of t
0300: 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 73 74 72  he following str
0310: 75 63 74 75 72 65 2e 0a 2a 2a 20 54 68 65 20 69  ucture..** The i
0320: 6e 74 65 72 6e 61 6c 73 20 6f 66 20 74 68 69 73  nternals of this
0330: 20 73 74 72 75 63 74 75 72 65 20 61 72 65 20 69   structure are i
0340: 6e 74 65 6e 64 65 64 20 74 6f 20 62 65 20 6f 70  ntended to be op
0350: 61 71 75 65 20 2d 2d 20 63 6c 69 65 6e 74 0a 2a  aque -- client.*
0360: 2a 20 63 6f 64 65 20 73 68 6f 75 6c 64 20 6e 6f  * code should no
0370: 74 20 61 74 74 65 6d 70 74 20 74 6f 20 61 63 63  t attempt to acc
0380: 65 73 73 20 6f 72 20 6d 6f 64 69 66 79 20 74 68  ess or modify th
0390: 65 20 66 69 65 6c 64 73 20 6f 66 20 74 68 69 73  e fields of this
03a0: 20 73 74 72 75 63 74 75 72 65 0a 2a 2a 20 64 69   structure.** di
03b0: 72 65 63 74 6c 79 2e 20 20 43 68 61 6e 67 65 20  rectly.  Change 
03c0: 74 68 69 73 20 73 74 72 75 63 74 75 72 65 20 6f  this structure o
03d0: 6e 6c 79 20 62 79 20 75 73 69 6e 67 20 74 68 65  nly by using the
03e0: 20 72 6f 75 74 69 6e 65 73 20 62 65 6c 6f 77 2e   routines below.
03f0: 0a 2a 2a 20 48 6f 77 65 76 65 72 2c 20 6d 61 6e  .** However, man
0400: 79 20 6f 66 20 74 68 65 20 22 70 72 6f 63 65 64  y of the "proced
0410: 75 72 65 73 22 20 61 6e 64 20 22 66 75 6e 63 74  ures" and "funct
0420: 69 6f 6e 73 22 20 66 6f 72 20 6d 6f 64 69 66 79  ions" for modify
0430: 69 6e 67 20 61 6e 64 0a 2a 2a 20 61 63 63 65 73  ing and.** acces
0440: 73 69 6e 67 20 74 68 69 73 20 73 74 72 75 63 74  sing this struct
0450: 75 72 65 20 61 72 65 20 72 65 61 6c 6c 79 20 6d  ure are really m
0460: 61 63 72 6f 73 2c 20 73 6f 20 77 65 20 63 61 6e  acros, so we can
0470: 27 74 20 72 65 61 6c 6c 79 20 6d 61 6b 65 0a 2a  't really make.*
0480: 2a 20 74 68 69 73 20 73 74 72 75 63 74 75 72 65  * this structure
0490: 20 6f 70 61 71 75 65 2e 0a 2a 2f 0a 73 74 72 75   opaque..*/.stru
04a0: 63 74 20 48 61 73 68 20 7b 0a 20 20 63 68 61 72  ct Hash {.  char
04b0: 20 6b 65 79 43 6c 61 73 73 3b 20 20 20 20 20 20   keyClass;      
04c0: 20 20 20 20 2f 2a 20 48 41 53 48 5f 49 4e 54 2c      /* HASH_INT,
04d0: 20 5f 50 4f 49 4e 54 45 52 2c 20 5f 53 54 52 49   _POINTER, _STRI
04e0: 4e 47 2c 20 5f 42 49 4e 41 52 59 20 2a 2f 0a 20  NG, _BINARY */. 
04f0: 20 63 68 61 72 20 63 6f 70 79 4b 65 79 3b 20 20   char copyKey;  
0500: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 72 75 65           /* True
0510: 20 69 66 20 63 6f 70 79 20 6f 66 20 6b 65 79 20   if copy of key 
0520: 6d 61 64 65 20 6f 6e 20 69 6e 73 65 72 74 20 2a  made on insert *
0530: 2f 0a 20 20 69 6e 74 20 63 6f 75 6e 74 3b 20 20  /.  int count;  
0540: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e              /* N
0550: 75 6d 62 65 72 20 6f 66 20 65 6e 74 72 69 65 73  umber of entries
0560: 20 69 6e 20 74 68 69 73 20 74 61 62 6c 65 20 2a   in this table *
0570: 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 66 69  /.  HashElem *fi
0580: 72 73 74 3b 20 20 20 20 20 20 20 20 2f 2a 20 54  rst;        /* T
0590: 68 65 20 66 69 72 73 74 20 65 6c 65 6d 65 6e 74  he first element
05a0: 20 6f 66 20 74 68 65 20 61 72 72 61 79 20 2a 2f   of the array */
05b0: 0a 20 20 76 6f 69 64 20 2a 28 2a 78 4d 61 6c 6c  .  void *(*xMall
05c0: 6f 63 29 28 69 6e 74 29 3b 20 20 2f 2a 20 6d 61  oc)(int);  /* ma
05d0: 6c 6c 6f 63 28 29 20 66 75 6e 63 74 69 6f 6e 20  lloc() function 
05e0: 74 6f 20 75 73 65 20 2a 2f 0a 20 20 76 6f 69 64  to use */.  void
05f0: 20 28 2a 78 46 72 65 65 29 28 76 6f 69 64 20 2a   (*xFree)(void *
0600: 29 3b 20 20 2f 2a 20 66 72 65 65 28 29 20 66 75  );  /* free() fu
0610: 6e 63 74 69 6f 6e 20 74 6f 20 75 73 65 20 2a 2f  nction to use */
0620: 0a 20 20 69 6e 74 20 68 74 73 69 7a 65 3b 20 20  .  int htsize;  
0630: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75             /* Nu
0640: 6d 62 65 72 20 6f 66 20 62 75 63 6b 65 74 73 20  mber of buckets 
0650: 69 6e 20 74 68 65 20 68 61 73 68 20 74 61 62 6c  in the hash tabl
0660: 65 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 5f 68  e */.  struct _h
0670: 74 20 7b 20 20 20 20 20 20 20 20 20 20 20 20 2f  t {            /
0680: 2a 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65  * the hash table
0690: 20 2a 2f 0a 20 20 20 20 69 6e 74 20 63 6f 75 6e   */.    int coun
06a0: 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 20 20  t;              
06b0: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65 6e   /* Number of en
06c0: 74 72 69 65 73 20 77 69 74 68 20 74 68 69 73 20  tries with this 
06d0: 68 61 73 68 20 2a 2f 0a 20 20 20 20 48 61 73 68  hash */.    Hash
06e0: 45 6c 65 6d 20 2a 63 68 61 69 6e 3b 20 20 20 20  Elem *chain;    
06f0: 20 20 20 20 20 2f 2a 20 50 6f 69 6e 74 65 72 20       /* Pointer 
0700: 74 6f 20 66 69 72 73 74 20 65 6e 74 72 79 20 77  to first entry w
0710: 69 74 68 20 74 68 69 73 20 68 61 73 68 20 2a 2f  ith this hash */
0720: 0a 20 20 7d 20 2a 68 74 3b 0a 7d 3b 0a 0a 2f 2a  .  } *ht;.};../*
0730: 20 45 61 63 68 20 65 6c 65 6d 65 6e 74 20 69 6e   Each element in
0740: 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20   the hash table 
0750: 69 73 20 61 6e 20 69 6e 73 74 61 6e 63 65 20 6f  is an instance o
0760: 66 20 74 68 65 20 66 6f 6c 6c 6f 77 69 6e 67 20  f the following 
0770: 0a 2a 2a 20 73 74 72 75 63 74 75 72 65 2e 20 20  .** structure.  
0780: 41 6c 6c 20 65 6c 65 6d 65 6e 74 73 20 61 72 65  All elements are
0790: 20 73 74 6f 72 65 64 20 6f 6e 20 61 20 73 69 6e   stored on a sin
07a0: 67 6c 65 20 64 6f 75 62 6c 79 2d 6c 69 6e 6b 65  gle doubly-linke
07b0: 64 20 6c 69 73 74 2e 0a 2a 2a 0a 2a 2a 20 41 67  d list..**.** Ag
07c0: 61 69 6e 2c 20 74 68 69 73 20 73 74 72 75 63 74  ain, this struct
07d0: 75 72 65 20 69 73 20 69 6e 74 65 6e 64 65 64 20  ure is intended 
07e0: 74 6f 20 62 65 20 6f 70 61 71 75 65 2c 20 62 75  to be opaque, bu
07f0: 74 20 69 74 20 63 61 6e 27 74 20 72 65 61 6c 6c  t it can't reall
0800: 79 0a 2a 2a 20 62 65 20 6f 70 61 71 75 65 20 62  y.** be opaque b
0810: 65 63 61 75 73 65 20 69 74 20 69 73 20 75 73 65  ecause it is use
0820: 64 20 62 79 20 6d 61 63 72 6f 73 2e 0a 2a 2f 0a  d by macros..*/.
0830: 73 74 72 75 63 74 20 48 61 73 68 45 6c 65 6d 20  struct HashElem 
0840: 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 6e 65  {.  HashElem *ne
0850: 78 74 2c 20 2a 70 72 65 76 3b 20 20 20 2f 2a 20  xt, *prev;   /* 
0860: 4e 65 78 74 20 61 6e 64 20 70 72 65 76 69 6f 75  Next and previou
0870: 73 20 65 6c 65 6d 65 6e 74 73 20 69 6e 20 74 68  s elements in th
0880: 65 20 74 61 62 6c 65 20 2a 2f 0a 20 20 76 6f 69  e table */.  voi
0890: 64 20 2a 64 61 74 61 3b 20 20 20 20 20 20 20 20  d *data;        
08a0: 20 20 20 20 20 20 2f 2a 20 44 61 74 61 20 61 73        /* Data as
08b0: 73 6f 63 69 61 74 65 64 20 77 69 74 68 20 74 68  sociated with th
08c0: 69 73 20 65 6c 65 6d 65 6e 74 20 2a 2f 0a 20 20  is element */.  
08d0: 76 6f 69 64 20 2a 70 4b 65 79 3b 20 69 6e 74 20  void *pKey; int 
08e0: 6e 4b 65 79 3b 20 20 20 20 2f 2a 20 4b 65 79 20  nKey;    /* Key 
08f0: 61 73 73 6f 63 69 61 74 65 64 20 77 69 74 68 20  associated with 
0900: 74 68 69 73 20 65 6c 65 6d 65 6e 74 20 2a 2f 0a  this element */.
0910: 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 72 65 20  };../*.** There 
0920: 61 72 65 20 34 20 64 69 66 66 65 72 65 6e 74 20  are 4 different 
0930: 6d 6f 64 65 73 20 6f 66 20 6f 70 65 72 61 74 69  modes of operati
0940: 6f 6e 20 66 6f 72 20 61 20 68 61 73 68 20 74 61  on for a hash ta
0950: 62 6c 65 3a 0a 2a 2a 0a 2a 2a 20 20 20 48 41 53  ble:.**.**   HAS
0960: 48 5f 49 4e 54 20 20 20 20 20 20 20 20 20 6e 4b  H_INT         nK
0970: 65 79 20 69 73 20 75 73 65 64 20 61 73 20 74 68  ey is used as th
0980: 65 20 6b 65 79 20 61 6e 64 20 70 4b 65 79 20 69  e key and pKey i
0990: 73 20 69 67 6e 6f 72 65 64 2e 0a 2a 2a 0a 2a 2a  s ignored..**.**
09a0: 20 20 20 48 41 53 48 5f 50 4f 49 4e 54 45 52 20     HASH_POINTER 
09b0: 20 20 20 20 70 4b 65 79 20 69 73 20 75 73 65 64      pKey is used
09c0: 20 61 73 20 74 68 65 20 6b 65 79 20 61 6e 64 20   as the key and 
09d0: 6e 4b 65 79 20 69 73 20 69 67 6e 6f 72 65 64 2e  nKey is ignored.
09e0: 0a 2a 2a 0a 2a 2a 20 20 20 48 41 53 48 5f 53 54  .**.**   HASH_ST
09f0: 52 49 4e 47 20 20 20 20 20 20 70 4b 65 79 20 70  RING      pKey p
0a00: 6f 69 6e 74 73 20 74 6f 20 61 20 73 74 72 69 6e  oints to a strin
0a10: 67 20 74 68 61 74 20 69 73 20 6e 4b 65 79 20 62  g that is nKey b
0a20: 79 74 65 73 20 6c 6f 6e 67 0a 2a 2a 20 20 20 20  ytes long.**    
0a30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0a40: 20 20 20 20 20 20 20 28 69 6e 63 6c 75 64 69 6e         (includin
0a50: 67 20 74 68 65 20 6e 75 6c 6c 2d 74 65 72 6d 69  g the null-termi
0a60: 6e 61 74 6f 72 2c 20 69 66 20 61 6e 79 29 2e 20  nator, if any). 
0a70: 20 43 61 73 65 0a 2a 2a 20 20 20 20 20 20 20 20   Case.**        
0a80: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0a90: 20 20 20 69 73 20 72 65 73 70 65 63 74 65 64 20     is respected 
0aa0: 69 6e 20 63 6f 6d 70 61 72 69 73 6f 6e 73 2e 0a  in comparisons..
0ab0: 2a 2a 0a 2a 2a 20 20 20 48 41 53 48 5f 42 49 4e  **.**   HASH_BIN
0ac0: 41 52 59 20 20 20 20 20 20 70 4b 65 79 20 70 6f  ARY      pKey po
0ad0: 69 6e 74 73 20 74 6f 20 62 69 6e 61 72 79 20 64  ints to binary d
0ae0: 61 74 61 20 6e 4b 65 79 20 62 79 74 65 73 20 6c  ata nKey bytes l
0af0: 6f 6e 67 2e 20 0a 2a 2a 20 20 20 20 20 20 20 20  ong. .**        
0b00: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
0b10: 20 20 20 6d 65 6d 63 6d 70 28 29 20 69 73 20 75     memcmp() is u
0b20: 73 65 64 20 74 6f 20 63 6f 6d 70 61 72 65 20 6b  sed to compare k
0b30: 65 79 73 2e 0a 2a 2a 0a 2a 2a 20 41 20 63 6f 70  eys..**.** A cop
0b40: 79 20 6f 66 20 74 68 65 20 6b 65 79 20 69 73 20  y of the key is 
0b50: 6d 61 64 65 20 66 6f 72 20 48 41 53 48 5f 53 54  made for HASH_ST
0b60: 52 49 4e 47 20 61 6e 64 20 48 41 53 48 5f 42 49  RING and HASH_BI
0b70: 4e 41 52 59 0a 2a 2a 20 69 66 20 74 68 65 20 63  NARY.** if the c
0b80: 6f 70 79 4b 65 79 20 70 61 72 61 6d 65 74 65 72  opyKey parameter
0b90: 20 74 6f 20 48 61 73 68 49 6e 69 74 20 69 73 20   to HashInit is 
0ba0: 31 2e 20 20 0a 2a 2f 0a 2f 2a 20 23 64 65 66 69  1.  .*/./* #defi
0bb0: 6e 65 20 48 41 53 48 5f 49 4e 54 20 20 20 20 20  ne HASH_INT     
0bc0: 20 20 31 20 2f 2f 20 4e 4f 54 20 55 53 45 44 20    1 // NOT USED 
0bd0: 2a 2f 0a 2f 2a 20 23 64 65 66 69 6e 65 20 48 41  */./* #define HA
0be0: 53 48 5f 50 4f 49 4e 54 45 52 20 20 20 32 20 2f  SH_POINTER   2 /
0bf0: 2f 20 4e 4f 54 20 55 53 45 44 20 2a 2f 0a 23 64  / NOT USED */.#d
0c00: 65 66 69 6e 65 20 48 41 53 48 5f 53 54 52 49 4e  efine HASH_STRIN
0c10: 47 20 20 20 20 33 0a 23 64 65 66 69 6e 65 20 48  G    3.#define H
0c20: 41 53 48 5f 42 49 4e 41 52 59 20 20 20 20 34 0a  ASH_BINARY    4.
0c30: 0a 2f 2a 0a 2a 2a 20 41 63 63 65 73 73 20 72 6f  ./*.** Access ro
0c40: 75 74 69 6e 65 73 2e 20 20 54 6f 20 64 65 6c 65  utines.  To dele
0c50: 74 65 2c 20 69 6e 73 65 72 74 20 61 20 4e 55 4c  te, insert a NUL
0c60: 4c 20 70 6f 69 6e 74 65 72 2e 0a 2a 2f 0a 76 6f  L pointer..*/.vo
0c70: 69 64 20 48 61 73 68 49 6e 69 74 28 48 61 73 68  id HashInit(Hash
0c80: 2a 2c 20 69 6e 74 20 6b 65 79 74 79 70 65 2c 20  *, int keytype, 
0c90: 69 6e 74 20 63 6f 70 79 4b 65 79 29 3b 0a 76 6f  int copyKey);.vo
0ca0: 69 64 20 2a 48 61 73 68 49 6e 73 65 72 74 28 48  id *HashInsert(H
0cb0: 61 73 68 2a 2c 20 63 6f 6e 73 74 20 76 6f 69 64  ash*, const void
0cc0: 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79   *pKey, int nKey
0cd0: 2c 20 76 6f 69 64 20 2a 70 44 61 74 61 29 3b 0a  , void *pData);.
0ce0: 76 6f 69 64 20 2a 48 61 73 68 46 69 6e 64 28 63  void *HashFind(c
0cf0: 6f 6e 73 74 20 48 61 73 68 2a 2c 20 63 6f 6e 73  onst Hash*, cons
0d00: 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e  t void *pKey, in
0d10: 74 20 6e 4b 65 79 29 3b 0a 76 6f 69 64 20 48 61  t nKey);.void Ha
0d20: 73 68 43 6c 65 61 72 28 48 61 73 68 2a 29 3b 0a  shClear(Hash*);.
0d30: 0a 2f 2a 0a 2a 2a 20 4d 61 63 72 6f 73 20 66 6f  ./*.** Macros fo
0d40: 72 20 6c 6f 6f 70 69 6e 67 20 6f 76 65 72 20 61  r looping over a
0d50: 6c 6c 20 65 6c 65 6d 65 6e 74 73 20 6f 66 20 61  ll elements of a
0d60: 20 68 61 73 68 20 74 61 62 6c 65 2e 20 20 54 68   hash table.  Th
0d70: 65 20 69 64 69 6f 6d 20 69 73 0a 2a 2a 20 6c 69  e idiom is.** li
0d80: 6b 65 20 74 68 69 73 3a 0a 2a 2a 0a 2a 2a 20 20  ke this:.**.**  
0d90: 20 48 61 73 68 20 68 3b 0a 2a 2a 20 20 20 48 61   Hash h;.**   Ha
0da0: 73 68 45 6c 65 6d 20 2a 70 3b 0a 2a 2a 20 20 20  shElem *p;.**   
0db0: 2e 2e 2e 0a 2a 2a 20 20 20 66 6f 72 28 70 3d 48  ....**   for(p=H
0dc0: 61 73 68 46 69 72 73 74 28 26 68 29 3b 20 70 3b  ashFirst(&h); p;
0dd0: 20 70 3d 48 61 73 68 4e 65 78 74 28 70 29 29 7b   p=HashNext(p)){
0de0: 0a 2a 2a 20 20 20 20 20 53 6f 6d 65 53 74 72 75  .**     SomeStru
0df0: 63 74 75 72 65 20 2a 70 44 61 74 61 20 3d 20 48  cture *pData = H
0e00: 61 73 68 44 61 74 61 28 70 29 3b 0a 2a 2a 20 20  ashData(p);.**  
0e10: 20 20 20 2f 2f 20 64 6f 20 73 6f 6d 65 74 68 69     // do somethi
0e20: 6e 67 20 77 69 74 68 20 70 44 61 74 61 0a 2a 2a  ng with pData.**
0e30: 20 20 20 7d 0a 2a 2f 0a 23 64 65 66 69 6e 65 20     }.*/.#define 
0e40: 48 61 73 68 46 69 72 73 74 28 48 29 20 20 28 28  HashFirst(H)  ((
0e50: 48 29 2d 3e 66 69 72 73 74 29 0a 23 64 65 66 69  H)->first).#defi
0e60: 6e 65 20 48 61 73 68 4e 65 78 74 28 45 29 20 20  ne HashNext(E)  
0e70: 20 28 28 45 29 2d 3e 6e 65 78 74 29 0a 23 64 65   ((E)->next).#de
0e80: 66 69 6e 65 20 48 61 73 68 44 61 74 61 28 45 29  fine HashData(E)
0e90: 20 20 20 28 28 45 29 2d 3e 64 61 74 61 29 0a 23     ((E)->data).#
0ea0: 64 65 66 69 6e 65 20 48 61 73 68 4b 65 79 28 45  define HashKey(E
0eb0: 29 20 20 20 20 28 28 45 29 2d 3e 70 4b 65 79 29  )    ((E)->pKey)
0ec0: 0a 23 64 65 66 69 6e 65 20 48 61 73 68 4b 65 79  .#define HashKey
0ed0: 73 69 7a 65 28 45 29 20 28 28 45 29 2d 3e 6e 4b  size(E) ((E)->nK
0ee0: 65 79 29 0a 0a 2f 2a 0a 2a 2a 20 4e 75 6d 62 65  ey)../*.** Numbe
0ef0: 72 20 6f 66 20 65 6e 74 72 69 65 73 20 69 6e 20  r of entries in 
0f00: 61 20 68 61 73 68 20 74 61 62 6c 65 0a 2a 2f 0a  a hash table.*/.
0f10: 23 64 65 66 69 6e 65 20 48 61 73 68 43 6f 75 6e  #define HashCoun
0f20: 74 28 48 29 20 20 28 28 48 29 2d 3e 63 6f 75 6e  t(H)  ((H)->coun
0f30: 74 29 0a 0a 23 65 6e 64 69 66 20 2f 2a 20 5f 48  t)..#endif /* _H
0f40: 41 53 48 5f 48 5f 20 2a 2f 0a                    ASH_H_ */.