/ Hex Artifact Content
Login

Artifact 3927bd880e65329bdc6f506555b228b28924921b:


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 69 6d 70 6c 65 6d 65 6e 74 61  s the implementa
0190: 74 69 6f 6e 20 6f 66 20 67 65 6e 65 72 69 63 20  tion of generic 
01a0: 68 61 73 68 2d 74 61 62 6c 65 73 20 75 73 65 64  hash-tables used
01b0: 20 69 6e 20 53 51 4c 69 74 65 2e 0a 2a 2a 20 57   in SQLite..** W
01c0: 65 27 76 65 20 6d 6f 64 69 66 69 65 64 20 69 74  e've modified it
01d0: 20 73 6c 69 67 68 74 6c 79 20 74 6f 20 73 65 72   slightly to ser
01e0: 76 65 20 61 73 20 61 20 73 74 61 6e 64 61 6c 6f  ve as a standalo
01f0: 6e 65 20 68 61 73 68 20 74 61 62 6c 65 0a 2a 2a  ne hash table.**
0200: 20 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20   implementation 
0210: 66 6f 72 20 74 68 65 20 66 75 6c 6c 2d 74 65 78  for the full-tex
0220: 74 20 69 6e 64 65 78 69 6e 67 20 6d 6f 64 75 6c  t indexing modul
0230: 65 2e 0a 2a 2f 0a 23 69 6e 63 6c 75 64 65 20 3c  e..*/.#include <
0240: 61 73 73 65 72 74 2e 68 3e 0a 23 69 6e 63 6c 75  assert.h>.#inclu
0250: 64 65 20 3c 73 74 64 6c 69 62 2e 68 3e 0a 23 69  de <stdlib.h>.#i
0260: 6e 63 6c 75 64 65 20 3c 73 74 72 69 6e 67 2e 68  nclude <string.h
0270: 3e 0a 0a 23 69 6e 63 6c 75 64 65 20 22 66 74 5f  >..#include "ft_
0280: 68 61 73 68 2e 68 22 0a 0a 76 6f 69 64 20 2a 6d  hash.h"..void *m
0290: 61 6c 6c 6f 63 5f 61 6e 64 5f 7a 65 72 6f 28 69  alloc_and_zero(i
02a0: 6e 74 20 6e 29 7b 0a 20 20 76 6f 69 64 20 2a 70  nt n){.  void *p
02b0: 20 3d 20 6d 61 6c 6c 6f 63 28 6e 29 3b 0a 20 20   = malloc(n);.  
02c0: 69 66 28 20 70 20 29 7b 0a 20 20 20 20 6d 65 6d  if( p ){.    mem
02d0: 73 65 74 28 70 2c 20 30 2c 20 6e 29 3b 0a 20 20  set(p, 0, n);.  
02e0: 7d 0a 20 20 72 65 74 75 72 6e 20 70 3b 0a 7d 0a  }.  return p;.}.
02f0: 0a 2f 2a 20 54 75 72 6e 20 62 75 6c 6b 20 6d 65  ./* Turn bulk me
0300: 6d 6f 72 79 20 69 6e 74 6f 20 61 20 68 61 73 68  mory into a hash
0310: 20 74 61 62 6c 65 20 6f 62 6a 65 63 74 20 62 79   table object by
0320: 20 69 6e 69 74 69 61 6c 69 7a 69 6e 67 20 74 68   initializing th
0330: 65 0a 2a 2a 20 66 69 65 6c 64 73 20 6f 66 20 74  e.** fields of t
0340: 68 65 20 48 61 73 68 20 73 74 72 75 63 74 75 72  he Hash structur
0350: 65 2e 0a 2a 2a 0a 2a 2a 20 22 70 4e 65 77 22 20  e..**.** "pNew" 
0360: 69 73 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20  is a pointer to 
0370: 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 74  the hash table t
0380: 68 61 74 20 69 73 20 74 6f 20 62 65 20 69 6e 69  hat is to be ini
0390: 74 69 61 6c 69 7a 65 64 2e 0a 2a 2a 20 6b 65 79  tialized..** key
03a0: 43 6c 61 73 73 20 69 73 20 6f 6e 65 20 6f 66 20  Class is one of 
03b0: 74 68 65 20 63 6f 6e 73 74 61 6e 74 73 20 48 41  the constants HA
03c0: 53 48 5f 49 4e 54 2c 20 48 41 53 48 5f 50 4f 49  SH_INT, HASH_POI
03d0: 4e 54 45 52 2c 0a 2a 2a 20 48 41 53 48 5f 42 49  NTER,.** HASH_BI
03e0: 4e 41 52 59 2c 20 6f 72 20 48 41 53 48 5f 53 54  NARY, or HASH_ST
03f0: 52 49 4e 47 2e 20 20 54 68 65 20 76 61 6c 75 65  RING.  The value
0400: 20 6f 66 20 6b 65 79 43 6c 61 73 73 20 0a 2a 2a   of keyClass .**
0410: 20 64 65 74 65 72 6d 69 6e 65 73 20 77 68 61 74   determines what
0420: 20 6b 69 6e 64 20 6f 66 20 6b 65 79 20 74 68 65   kind of key the
0430: 20 68 61 73 68 20 74 61 62 6c 65 20 77 69 6c 6c   hash table will
0440: 20 75 73 65 2e 20 20 22 63 6f 70 79 4b 65 79 22   use.  "copyKey"
0450: 20 69 73 0a 2a 2a 20 74 72 75 65 20 69 66 20 74   is.** true if t
0460: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 73 68  he hash table sh
0470: 6f 75 6c 64 20 6d 61 6b 65 20 69 74 73 20 6f 77  ould make its ow
0480: 6e 20 70 72 69 76 61 74 65 20 63 6f 70 79 20 6f  n private copy o
0490: 66 20 6b 65 79 73 20 61 6e 64 0a 2a 2a 20 66 61  f keys and.** fa
04a0: 6c 73 65 20 69 66 20 69 74 20 73 68 6f 75 6c 64  lse if it should
04b0: 20 6a 75 73 74 20 75 73 65 20 74 68 65 20 73 75   just use the su
04c0: 70 70 6c 69 65 64 20 70 6f 69 6e 74 65 72 2e 20  pplied pointer. 
04d0: 20 43 6f 70 79 4b 65 79 20 6f 6e 6c 79 20 6d 61   CopyKey only ma
04e0: 6b 65 73 0a 2a 2a 20 73 65 6e 73 65 20 66 6f 72  kes.** sense for
04f0: 20 48 41 53 48 5f 53 54 52 49 4e 47 20 61 6e 64   HASH_STRING and
0500: 20 48 41 53 48 5f 42 49 4e 41 52 59 20 61 6e 64   HASH_BINARY and
0510: 20 69 73 20 69 67 6e 6f 72 65 64 0a 2a 2a 20 66   is ignored.** f
0520: 6f 72 20 6f 74 68 65 72 20 6b 65 79 20 63 6c 61  or other key cla
0530: 73 73 65 73 2e 0a 2a 2f 0a 76 6f 69 64 20 48 61  sses..*/.void Ha
0540: 73 68 49 6e 69 74 28 48 61 73 68 20 2a 70 4e 65  shInit(Hash *pNe
0550: 77 2c 20 69 6e 74 20 6b 65 79 43 6c 61 73 73 2c  w, int keyClass,
0560: 20 69 6e 74 20 63 6f 70 79 4b 65 79 29 7b 0a 20   int copyKey){. 
0570: 20 61 73 73 65 72 74 28 20 70 4e 65 77 21 3d 30   assert( pNew!=0
0580: 20 29 3b 0a 20 20 61 73 73 65 72 74 28 20 6b 65   );.  assert( ke
0590: 79 43 6c 61 73 73 3e 3d 48 41 53 48 5f 53 54 52  yClass>=HASH_STR
05a0: 49 4e 47 20 26 26 20 6b 65 79 43 6c 61 73 73 3c  ING && keyClass<
05b0: 3d 48 41 53 48 5f 42 49 4e 41 52 59 20 29 3b 0a  =HASH_BINARY );.
05c0: 20 20 70 4e 65 77 2d 3e 6b 65 79 43 6c 61 73 73    pNew->keyClass
05d0: 20 3d 20 6b 65 79 43 6c 61 73 73 3b 0a 23 69 66   = keyClass;.#if
05e0: 20 30 0a 20 20 69 66 28 20 6b 65 79 43 6c 61 73   0.  if( keyClas
05f0: 73 3d 3d 48 41 53 48 5f 50 4f 49 4e 54 45 52 20  s==HASH_POINTER 
0600: 7c 7c 20 6b 65 79 43 6c 61 73 73 3d 3d 48 41 53  || keyClass==HAS
0610: 48 5f 49 4e 54 20 29 20 63 6f 70 79 4b 65 79 20  H_INT ) copyKey 
0620: 3d 20 30 3b 0a 23 65 6e 64 69 66 0a 20 20 70 4e  = 0;.#endif.  pN
0630: 65 77 2d 3e 63 6f 70 79 4b 65 79 20 3d 20 63 6f  ew->copyKey = co
0640: 70 79 4b 65 79 3b 0a 20 20 70 4e 65 77 2d 3e 66  pyKey;.  pNew->f
0650: 69 72 73 74 20 3d 20 30 3b 0a 20 20 70 4e 65 77  irst = 0;.  pNew
0660: 2d 3e 63 6f 75 6e 74 20 3d 20 30 3b 0a 20 20 70  ->count = 0;.  p
0670: 4e 65 77 2d 3e 68 74 73 69 7a 65 20 3d 20 30 3b  New->htsize = 0;
0680: 0a 20 20 70 4e 65 77 2d 3e 68 74 20 3d 20 30 3b  .  pNew->ht = 0;
0690: 0a 20 20 70 4e 65 77 2d 3e 78 4d 61 6c 6c 6f 63  .  pNew->xMalloc
06a0: 20 3d 20 6d 61 6c 6c 6f 63 5f 61 6e 64 5f 7a 65   = malloc_and_ze
06b0: 72 6f 3b 0a 20 20 70 4e 65 77 2d 3e 78 46 72 65  ro;.  pNew->xFre
06c0: 65 20 3d 20 66 72 65 65 3b 0a 7d 0a 0a 2f 2a 20  e = free;.}../* 
06d0: 52 65 6d 6f 76 65 20 61 6c 6c 20 65 6e 74 72 69  Remove all entri
06e0: 65 73 20 66 72 6f 6d 20 61 20 68 61 73 68 20 74  es from a hash t
06f0: 61 62 6c 65 2e 20 20 52 65 63 6c 61 69 6d 20 61  able.  Reclaim a
0700: 6c 6c 20 6d 65 6d 6f 72 79 2e 0a 2a 2a 20 43 61  ll memory..** Ca
0710: 6c 6c 20 74 68 69 73 20 72 6f 75 74 69 6e 65 20  ll this routine 
0720: 74 6f 20 64 65 6c 65 74 65 20 61 20 68 61 73 68  to delete a hash
0730: 20 74 61 62 6c 65 20 6f 72 20 74 6f 20 72 65 73   table or to res
0740: 65 74 20 61 20 68 61 73 68 20 74 61 62 6c 65 0a  et a hash table.
0750: 2a 2a 20 74 6f 20 74 68 65 20 65 6d 70 74 79 20  ** to the empty 
0760: 73 74 61 74 65 2e 0a 2a 2f 0a 76 6f 69 64 20 48  state..*/.void H
0770: 61 73 68 43 6c 65 61 72 28 48 61 73 68 20 2a 70  ashClear(Hash *p
0780: 48 29 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a  H){.  HashElem *
0790: 65 6c 65 6d 3b 20 20 20 20 20 20 20 20 20 2f 2a  elem;         /*
07a0: 20 46 6f 72 20 6c 6f 6f 70 69 6e 67 20 6f 76 65   For looping ove
07b0: 72 20 61 6c 6c 20 65 6c 65 6d 65 6e 74 73 20 6f  r all elements o
07c0: 66 20 74 68 65 20 74 61 62 6c 65 20 2a 2f 0a 0a  f the table */..
07d0: 20 20 61 73 73 65 72 74 28 20 70 48 21 3d 30 20    assert( pH!=0 
07e0: 29 3b 0a 20 20 65 6c 65 6d 20 3d 20 70 48 2d 3e  );.  elem = pH->
07f0: 66 69 72 73 74 3b 0a 20 20 70 48 2d 3e 66 69 72  first;.  pH->fir
0800: 73 74 20 3d 20 30 3b 0a 20 20 69 66 28 20 70 48  st = 0;.  if( pH
0810: 2d 3e 68 74 20 29 20 70 48 2d 3e 78 46 72 65 65  ->ht ) pH->xFree
0820: 28 70 48 2d 3e 68 74 29 3b 0a 20 20 70 48 2d 3e  (pH->ht);.  pH->
0830: 68 74 20 3d 20 30 3b 0a 20 20 70 48 2d 3e 68 74  ht = 0;.  pH->ht
0840: 73 69 7a 65 20 3d 20 30 3b 0a 20 20 77 68 69 6c  size = 0;.  whil
0850: 65 28 20 65 6c 65 6d 20 29 7b 0a 20 20 20 20 48  e( elem ){.    H
0860: 61 73 68 45 6c 65 6d 20 2a 6e 65 78 74 5f 65 6c  ashElem *next_el
0870: 65 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b  em = elem->next;
0880: 0a 20 20 20 20 69 66 28 20 70 48 2d 3e 63 6f 70  .    if( pH->cop
0890: 79 4b 65 79 20 26 26 20 65 6c 65 6d 2d 3e 70 4b  yKey && elem->pK
08a0: 65 79 20 29 7b 0a 20 20 20 20 20 20 70 48 2d 3e  ey ){.      pH->
08b0: 78 46 72 65 65 28 65 6c 65 6d 2d 3e 70 4b 65 79  xFree(elem->pKey
08c0: 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20 70 48 2d  );.    }.    pH-
08d0: 3e 78 46 72 65 65 28 65 6c 65 6d 29 3b 0a 20 20  >xFree(elem);.  
08e0: 20 20 65 6c 65 6d 20 3d 20 6e 65 78 74 5f 65 6c    elem = next_el
08f0: 65 6d 3b 0a 20 20 7d 0a 20 20 70 48 2d 3e 63 6f  em;.  }.  pH->co
0900: 75 6e 74 20 3d 20 30 3b 0a 7d 0a 0a 23 69 66 20  unt = 0;.}..#if 
0910: 30 20 2f 2a 20 4e 4f 54 20 55 53 45 44 20 2a 2f  0 /* NOT USED */
0920: 0a 2f 2a 0a 2a 2a 20 48 61 73 68 20 61 6e 64 20  ./*.** Hash and 
0930: 63 6f 6d 70 61 72 69 73 6f 6e 20 66 75 6e 63 74  comparison funct
0940: 69 6f 6e 73 20 77 68 65 6e 20 74 68 65 20 6d 6f  ions when the mo
0950: 64 65 20 69 73 20 48 41 53 48 5f 49 4e 54 0a 2a  de is HASH_INT.*
0960: 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 69 6e 74  /.static int int
0970: 48 61 73 68 28 63 6f 6e 73 74 20 76 6f 69 64 20  Hash(const void 
0980: 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29  *pKey, int nKey)
0990: 7b 0a 20 20 72 65 74 75 72 6e 20 6e 4b 65 79 20  {.  return nKey 
09a0: 5e 20 28 6e 4b 65 79 3c 3c 38 29 20 5e 20 28 6e  ^ (nKey<<8) ^ (n
09b0: 4b 65 79 3e 3e 38 29 3b 0a 7d 0a 73 74 61 74 69  Key>>8);.}.stati
09c0: 63 20 69 6e 74 20 69 6e 74 43 6f 6d 70 61 72 65  c int intCompare
09d0: 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65  (const void *pKe
09e0: 79 31 2c 20 69 6e 74 20 6e 31 2c 20 63 6f 6e 73  y1, int n1, cons
09f0: 74 20 76 6f 69 64 20 2a 70 4b 65 79 32 2c 20 69  t void *pKey2, i
0a00: 6e 74 20 6e 32 29 7b 0a 20 20 72 65 74 75 72 6e  nt n2){.  return
0a10: 20 6e 32 20 2d 20 6e 31 3b 0a 7d 0a 23 65 6e 64   n2 - n1;.}.#end
0a20: 69 66 0a 0a 23 69 66 20 30 20 2f 2a 20 4e 4f 54  if..#if 0 /* NOT
0a30: 20 55 53 45 44 20 2a 2f 0a 2f 2a 0a 2a 2a 20 48   USED */./*.** H
0a40: 61 73 68 20 61 6e 64 20 63 6f 6d 70 61 72 69 73  ash and comparis
0a50: 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 20 77 68 65  on functions whe
0a60: 6e 20 74 68 65 20 6d 6f 64 65 20 69 73 20 48 41  n the mode is HA
0a70: 53 48 5f 50 4f 49 4e 54 45 52 0a 2a 2f 0a 73 74  SH_POINTER.*/.st
0a80: 61 74 69 63 20 69 6e 74 20 70 74 72 48 61 73 68  atic int ptrHash
0a90: 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65  (const void *pKe
0aa0: 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20 20  y, int nKey){.  
0ab0: 75 70 74 72 20 78 20 3d 20 41 64 64 72 28 70 4b  uptr x = Addr(pK
0ac0: 65 79 29 3b 0a 20 20 72 65 74 75 72 6e 20 78 20  ey);.  return x 
0ad0: 5e 20 28 78 3c 3c 38 29 20 5e 20 28 78 3e 3e 38  ^ (x<<8) ^ (x>>8
0ae0: 29 3b 0a 7d 0a 73 74 61 74 69 63 20 69 6e 74 20  );.}.static int 
0af0: 70 74 72 43 6f 6d 70 61 72 65 28 63 6f 6e 73 74  ptrCompare(const
0b00: 20 76 6f 69 64 20 2a 70 4b 65 79 31 2c 20 69 6e   void *pKey1, in
0b10: 74 20 6e 31 2c 20 63 6f 6e 73 74 20 76 6f 69 64  t n1, const void
0b20: 20 2a 70 4b 65 79 32 2c 20 69 6e 74 20 6e 32 29   *pKey2, int n2)
0b30: 7b 0a 20 20 69 66 28 20 70 4b 65 79 31 3d 3d 70  {.  if( pKey1==p
0b40: 4b 65 79 32 20 29 20 72 65 74 75 72 6e 20 30 3b  Key2 ) return 0;
0b50: 0a 20 20 69 66 28 20 70 4b 65 79 31 3c 70 4b 65  .  if( pKey1<pKe
0b60: 79 32 20 29 20 72 65 74 75 72 6e 20 2d 31 3b 0a  y2 ) return -1;.
0b70: 20 20 72 65 74 75 72 6e 20 31 3b 0a 7d 0a 23 65    return 1;.}.#e
0b80: 6e 64 69 66 0a 0a 2f 2a 0a 2a 2a 20 48 61 73 68  ndif../*.** Hash
0b90: 20 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e 20   and comparison 
0ba0: 66 75 6e 63 74 69 6f 6e 73 20 77 68 65 6e 20 74  functions when t
0bb0: 68 65 20 6d 6f 64 65 20 69 73 20 48 41 53 48 5f  he mode is HASH_
0bc0: 53 54 52 49 4e 47 0a 2a 2f 0a 73 74 61 74 69 63  STRING.*/.static
0bd0: 20 69 6e 74 20 73 74 72 48 61 73 68 28 63 6f 6e   int strHash(con
0be0: 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69  st void *pKey, i
0bf0: 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 63 6f 6e 73  nt nKey){.  cons
0c00: 74 20 63 68 61 72 20 2a 7a 20 3d 20 28 63 6f 6e  t char *z = (con
0c10: 73 74 20 63 68 61 72 20 2a 29 70 4b 65 79 3b 0a  st char *)pKey;.
0c20: 20 20 69 6e 74 20 68 20 3d 20 30 3b 0a 20 20 69    int h = 0;.  i
0c30: 66 28 20 6e 4b 65 79 3c 3d 30 20 29 20 6e 4b 65  f( nKey<=0 ) nKe
0c40: 79 20 3d 20 28 69 6e 74 29 20 73 74 72 6c 65 6e  y = (int) strlen
0c50: 28 7a 29 3b 0a 20 20 77 68 69 6c 65 28 20 6e 4b  (z);.  while( nK
0c60: 65 79 20 3e 20 30 20 20 29 7b 0a 20 20 20 20 68  ey > 0  ){.    h
0c70: 20 3d 20 28 68 3c 3c 33 29 20 5e 20 68 20 5e 20   = (h<<3) ^ h ^ 
0c80: 2a 7a 2b 2b 3b 0a 20 20 20 20 6e 4b 65 79 2d 2d  *z++;.    nKey--
0c90: 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 68  ;.  }.  return h
0ca0: 20 26 20 30 78 37 66 66 66 66 66 66 66 3b 0a 7d   & 0x7fffffff;.}
0cb0: 0a 73 74 61 74 69 63 20 69 6e 74 20 73 74 72 43  .static int strC
0cc0: 6f 6d 70 61 72 65 28 63 6f 6e 73 74 20 76 6f 69  ompare(const voi
0cd0: 64 20 2a 70 4b 65 79 31 2c 20 69 6e 74 20 6e 31  d *pKey1, int n1
0ce0: 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b  , const void *pK
0cf0: 65 79 32 2c 20 69 6e 74 20 6e 32 29 7b 0a 20 20  ey2, int n2){.  
0d00: 69 66 28 20 6e 31 21 3d 6e 32 20 29 20 72 65 74  if( n1!=n2 ) ret
0d10: 75 72 6e 20 31 3b 0a 20 20 72 65 74 75 72 6e 20  urn 1;.  return 
0d20: 73 74 72 6e 63 6d 70 28 28 63 6f 6e 73 74 20 63  strncmp((const c
0d30: 68 61 72 2a 29 70 4b 65 79 31 2c 28 63 6f 6e 73  har*)pKey1,(cons
0d40: 74 20 63 68 61 72 2a 29 70 4b 65 79 32 2c 6e 31  t char*)pKey2,n1
0d50: 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 48 61 73 68  );.}../*.** Hash
0d60: 20 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f 6e 20   and comparison 
0d70: 66 75 6e 63 74 69 6f 6e 73 20 77 68 65 6e 20 74  functions when t
0d80: 68 65 20 6d 6f 64 65 20 69 73 20 48 41 53 48 5f  he mode is HASH_
0d90: 42 49 4e 41 52 59 0a 2a 2f 0a 73 74 61 74 69 63  BINARY.*/.static
0da0: 20 69 6e 74 20 62 69 6e 48 61 73 68 28 63 6f 6e   int binHash(con
0db0: 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69  st void *pKey, i
0dc0: 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 69 6e 74 20  nt nKey){.  int 
0dd0: 68 20 3d 20 30 3b 0a 20 20 63 6f 6e 73 74 20 63  h = 0;.  const c
0de0: 68 61 72 20 2a 7a 20 3d 20 28 63 6f 6e 73 74 20  har *z = (const 
0df0: 63 68 61 72 20 2a 29 70 4b 65 79 3b 0a 20 20 77  char *)pKey;.  w
0e00: 68 69 6c 65 28 20 6e 4b 65 79 2d 2d 20 3e 20 30  hile( nKey-- > 0
0e10: 20 29 7b 0a 20 20 20 20 68 20 3d 20 28 68 3c 3c   ){.    h = (h<<
0e20: 33 29 20 5e 20 68 20 5e 20 2a 28 7a 2b 2b 29 3b  3) ^ h ^ *(z++);
0e30: 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 68 20  .  }.  return h 
0e40: 26 20 30 78 37 66 66 66 66 66 66 66 3b 0a 7d 0a  & 0x7fffffff;.}.
0e50: 73 74 61 74 69 63 20 69 6e 74 20 62 69 6e 43 6f  static int binCo
0e60: 6d 70 61 72 65 28 63 6f 6e 73 74 20 76 6f 69 64  mpare(const void
0e70: 20 2a 70 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c   *pKey1, int n1,
0e80: 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65   const void *pKe
0e90: 79 32 2c 20 69 6e 74 20 6e 32 29 7b 0a 20 20 69  y2, int n2){.  i
0ea0: 66 28 20 6e 31 21 3d 6e 32 20 29 20 72 65 74 75  f( n1!=n2 ) retu
0eb0: 72 6e 20 31 3b 0a 20 20 72 65 74 75 72 6e 20 6d  rn 1;.  return m
0ec0: 65 6d 63 6d 70 28 70 4b 65 79 31 2c 70 4b 65 79  emcmp(pKey1,pKey
0ed0: 32 2c 6e 31 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20  2,n1);.}../*.** 
0ee0: 52 65 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 72  Return a pointer
0ef0: 20 74 6f 20 74 68 65 20 61 70 70 72 6f 70 72 69   to the appropri
0f00: 61 74 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f  ate hash functio
0f10: 6e 20 67 69 76 65 6e 20 74 68 65 20 6b 65 79 20  n given the key 
0f20: 63 6c 61 73 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65  class..**.** The
0f30: 20 43 20 73 79 6e 74 61 78 20 69 6e 20 74 68 69   C syntax in thi
0f40: 73 20 66 75 6e 63 74 69 6f 6e 20 64 65 66 69 6e  s function defin
0f50: 69 74 69 6f 6e 20 6d 61 79 20 62 65 20 75 6e 66  ition may be unf
0f60: 61 6d 69 6c 61 72 20 74 6f 20 73 6f 6d 65 20 0a  amilar to some .
0f70: 2a 2a 20 70 72 6f 67 72 61 6d 6d 65 72 73 2c 20  ** programmers, 
0f80: 73 6f 20 77 65 20 70 72 6f 76 69 64 65 20 74 68  so we provide th
0f90: 65 20 66 6f 6c 6c 6f 77 69 6e 67 20 61 64 64 69  e following addi
0fa0: 74 69 6f 6e 61 6c 20 65 78 70 6c 61 6e 61 74 69  tional explanati
0fb0: 6f 6e 3a 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6e 61  on:.**.** The na
0fc0: 6d 65 20 6f 66 20 74 68 65 20 66 75 6e 63 74 69  me of the functi
0fd0: 6f 6e 20 69 73 20 22 68 61 73 68 46 75 6e 63 74  on is "hashFunct
0fe0: 69 6f 6e 22 2e 20 20 54 68 65 20 66 75 6e 63 74  ion".  The funct
0ff0: 69 6f 6e 20 74 61 6b 65 73 20 61 0a 2a 2a 20 73  ion takes a.** s
1000: 69 6e 67 6c 65 20 70 61 72 61 6d 65 74 65 72 20  ingle parameter 
1010: 22 6b 65 79 43 6c 61 73 73 22 2e 20 20 54 68 65  "keyClass".  The
1020: 20 72 65 74 75 72 6e 20 76 61 6c 75 65 20 6f 66   return value of
1030: 20 68 61 73 68 46 75 6e 63 74 69 6f 6e 28 29 0a   hashFunction().
1040: 2a 2a 20 69 73 20 61 20 70 6f 69 6e 74 65 72 20  ** is a pointer 
1050: 74 6f 20 61 6e 6f 74 68 65 72 20 66 75 6e 63 74  to another funct
1060: 69 6f 6e 2e 20 20 53 70 65 63 69 66 69 63 61 6c  ion.  Specifical
1070: 6c 79 2c 20 74 68 65 20 72 65 74 75 72 6e 20 76  ly, the return v
1080: 61 6c 75 65 0a 2a 2a 20 6f 66 20 68 61 73 68 46  alue.** of hashF
1090: 75 6e 63 74 69 6f 6e 28 29 20 69 73 20 61 20 70  unction() is a p
10a0: 6f 69 6e 74 65 72 20 74 6f 20 61 20 66 75 6e 63  ointer to a func
10b0: 74 69 6f 6e 20 74 68 61 74 20 74 61 6b 65 73 20  tion that takes 
10c0: 74 77 6f 20 70 61 72 61 6d 65 74 65 72 73 0a 2a  two parameters.*
10d0: 2a 20 77 69 74 68 20 74 79 70 65 73 20 22 63 6f  * with types "co
10e0: 6e 73 74 20 76 6f 69 64 2a 22 20 61 6e 64 20 22  nst void*" and "
10f0: 69 6e 74 22 20 61 6e 64 20 72 65 74 75 72 6e 73  int" and returns
1100: 20 61 6e 20 22 69 6e 74 22 2e 0a 2a 2f 0a 73 74   an "int"..*/.st
1110: 61 74 69 63 20 69 6e 74 20 28 2a 68 61 73 68 46  atic int (*hashF
1120: 75 6e 63 74 69 6f 6e 28 69 6e 74 20 6b 65 79 43  unction(int keyC
1130: 6c 61 73 73 29 29 28 63 6f 6e 73 74 20 76 6f 69  lass))(const voi
1140: 64 2a 2c 69 6e 74 29 7b 0a 23 69 66 20 30 20 20  d*,int){.#if 0  
1150: 2f 2a 20 48 41 53 48 5f 49 4e 54 20 61 6e 64 20  /* HASH_INT and 
1160: 48 41 53 48 5f 50 4f 49 4e 54 45 52 20 61 72 65  HASH_POINTER are
1170: 20 6e 65 76 65 72 20 75 73 65 64 20 2a 2f 0a 20   never used */. 
1180: 20 73 77 69 74 63 68 28 20 6b 65 79 43 6c 61 73   switch( keyClas
1190: 73 20 29 7b 0a 20 20 20 20 63 61 73 65 20 48 41  s ){.    case HA
11a0: 53 48 5f 49 4e 54 3a 20 20 20 20 20 72 65 74 75  SH_INT:     retu
11b0: 72 6e 20 26 69 6e 74 48 61 73 68 3b 0a 20 20 20  rn &intHash;.   
11c0: 20 63 61 73 65 20 48 41 53 48 5f 50 4f 49 4e 54   case HASH_POINT
11d0: 45 52 3a 20 72 65 74 75 72 6e 20 26 70 74 72 48  ER: return &ptrH
11e0: 61 73 68 3b 0a 20 20 20 20 63 61 73 65 20 48 41  ash;.    case HA
11f0: 53 48 5f 53 54 52 49 4e 47 3a 20 20 72 65 74 75  SH_STRING:  retu
1200: 72 6e 20 26 73 74 72 48 61 73 68 3b 0a 20 20 20  rn &strHash;.   
1210: 20 63 61 73 65 20 48 41 53 48 5f 42 49 4e 41 52   case HASH_BINAR
1220: 59 3a 20 20 72 65 74 75 72 6e 20 26 62 69 6e 48  Y:  return &binH
1230: 61 73 68 3b 3b 0a 20 20 20 20 64 65 66 61 75 6c  ash;;.    defaul
1240: 74 3a 20 62 72 65 61 6b 3b 0a 20 20 7d 0a 20 20  t: break;.  }.  
1250: 72 65 74 75 72 6e 20 30 3b 0a 23 65 6c 73 65 0a  return 0;.#else.
1260: 20 20 69 66 28 20 6b 65 79 43 6c 61 73 73 3d 3d    if( keyClass==
1270: 48 41 53 48 5f 53 54 52 49 4e 47 20 29 7b 0a 20  HASH_STRING ){. 
1280: 20 20 20 72 65 74 75 72 6e 20 26 73 74 72 48 61     return &strHa
1290: 73 68 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20  sh;.  }else{.   
12a0: 20 61 73 73 65 72 74 28 20 6b 65 79 43 6c 61 73   assert( keyClas
12b0: 73 3d 3d 48 41 53 48 5f 42 49 4e 41 52 59 20 29  s==HASH_BINARY )
12c0: 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 26 62 69  ;.    return &bi
12d0: 6e 48 61 73 68 3b 0a 20 20 7d 0a 23 65 6e 64 69  nHash;.  }.#endi
12e0: 66 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72  f.}../*.** Retur
12f0: 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74  n a pointer to t
1300: 68 65 20 61 70 70 72 6f 70 72 69 61 74 65 20 68  he appropriate h
1310: 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 67 69 76  ash function giv
1320: 65 6e 20 74 68 65 20 6b 65 79 20 63 6c 61 73 73  en the key class
1330: 2e 0a 2a 2a 0a 2a 2a 20 46 6f 72 20 68 65 6c 70  ..**.** For help
1340: 20 69 6e 20 69 6e 74 65 72 70 72 65 74 65 64 20   in interpreted 
1350: 74 68 65 20 6f 62 73 63 75 72 65 20 43 20 63 6f  the obscure C co
1360: 64 65 20 69 6e 20 74 68 65 20 66 75 6e 63 74 69  de in the functi
1370: 6f 6e 20 64 65 66 69 6e 69 74 69 6f 6e 2c 0a 2a  on definition,.*
1380: 2a 20 73 65 65 20 74 68 65 20 68 65 61 64 65 72  * see the header
1390: 20 63 6f 6d 6d 65 6e 74 20 6f 6e 20 74 68 65 20   comment on the 
13a0: 70 72 65 76 69 6f 75 73 20 66 75 6e 63 74 69 6f  previous functio
13b0: 6e 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74  n..*/.static int
13c0: 20 28 2a 63 6f 6d 70 61 72 65 46 75 6e 63 74 69   (*compareFuncti
13d0: 6f 6e 28 69 6e 74 20 6b 65 79 43 6c 61 73 73 29  on(int keyClass)
13e0: 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e  )(const void*,in
13f0: 74 2c 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e  t,const void*,in
1400: 74 29 7b 0a 23 69 66 20 30 20 2f 2a 20 48 41 53  t){.#if 0 /* HAS
1410: 48 5f 49 4e 54 20 61 6e 64 20 48 41 53 48 5f 50  H_INT and HASH_P
1420: 4f 49 4e 54 45 52 20 61 72 65 20 6e 65 76 65 72  OINTER are never
1430: 20 75 73 65 64 20 2a 2f 0a 20 20 73 77 69 74 63   used */.  switc
1440: 68 28 20 6b 65 79 43 6c 61 73 73 20 29 7b 0a 20  h( keyClass ){. 
1450: 20 20 20 63 61 73 65 20 48 41 53 48 5f 49 4e 54     case HASH_INT
1460: 3a 20 20 20 20 20 72 65 74 75 72 6e 20 26 69 6e  :     return &in
1470: 74 43 6f 6d 70 61 72 65 3b 0a 20 20 20 20 63 61  tCompare;.    ca
1480: 73 65 20 48 41 53 48 5f 50 4f 49 4e 54 45 52 3a  se HASH_POINTER:
1490: 20 72 65 74 75 72 6e 20 26 70 74 72 43 6f 6d 70   return &ptrComp
14a0: 61 72 65 3b 0a 20 20 20 20 63 61 73 65 20 48 41  are;.    case HA
14b0: 53 48 5f 53 54 52 49 4e 47 3a 20 20 72 65 74 75  SH_STRING:  retu
14c0: 72 6e 20 26 73 74 72 43 6f 6d 70 61 72 65 3b 0a  rn &strCompare;.
14d0: 20 20 20 20 63 61 73 65 20 48 41 53 48 5f 42 49      case HASH_BI
14e0: 4e 41 52 59 3a 20 20 72 65 74 75 72 6e 20 26 62  NARY:  return &b
14f0: 69 6e 43 6f 6d 70 61 72 65 3b 0a 20 20 20 20 64  inCompare;.    d
1500: 65 66 61 75 6c 74 3a 20 62 72 65 61 6b 3b 0a 20  efault: break;. 
1510: 20 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a 23   }.  return 0;.#
1520: 65 6c 73 65 0a 20 20 69 66 28 20 6b 65 79 43 6c  else.  if( keyCl
1530: 61 73 73 3d 3d 48 41 53 48 5f 53 54 52 49 4e 47  ass==HASH_STRING
1540: 20 29 7b 0a 20 20 20 20 72 65 74 75 72 6e 20 26   ){.    return &
1550: 73 74 72 43 6f 6d 70 61 72 65 3b 0a 20 20 7d 65  strCompare;.  }e
1560: 6c 73 65 7b 0a 20 20 20 20 61 73 73 65 72 74 28  lse{.    assert(
1570: 20 6b 65 79 43 6c 61 73 73 3d 3d 48 41 53 48 5f   keyClass==HASH_
1580: 42 49 4e 41 52 59 20 29 3b 0a 20 20 20 20 72 65  BINARY );.    re
1590: 74 75 72 6e 20 26 62 69 6e 43 6f 6d 70 61 72 65  turn &binCompare
15a0: 3b 0a 20 20 7d 0a 23 65 6e 64 69 66 0a 7d 0a 0a  ;.  }.#endif.}..
15b0: 2f 2a 20 4c 69 6e 6b 20 61 6e 20 65 6c 65 6d 65  /* Link an eleme
15c0: 6e 74 20 69 6e 74 6f 20 74 68 65 20 68 61 73 68  nt into the hash
15d0: 20 74 61 62 6c 65 0a 2a 2f 0a 73 74 61 74 69 63   table.*/.static
15e0: 20 76 6f 69 64 20 69 6e 73 65 72 74 45 6c 65 6d   void insertElem
15f0: 65 6e 74 28 0a 20 20 48 61 73 68 20 2a 70 48 2c  ent(.  Hash *pH,
1600: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
1610: 20 54 68 65 20 63 6f 6d 70 6c 65 74 65 20 68 61   The complete ha
1620: 73 68 20 74 61 62 6c 65 20 2a 2f 0a 20 20 73 74  sh table */.  st
1630: 72 75 63 74 20 5f 68 74 20 2a 70 45 6e 74 72 79  ruct _ht *pEntry
1640: 2c 20 20 20 20 2f 2a 20 54 68 65 20 65 6e 74 72  ,    /* The entr
1650: 79 20 69 6e 74 6f 20 77 68 69 63 68 20 70 4e 65  y into which pNe
1660: 77 20 69 73 20 69 6e 73 65 72 74 65 64 20 2a 2f  w is inserted */
1670: 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 70 4e 65  .  HashElem *pNe
1680: 77 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65  w         /* The
1690: 20 65 6c 65 6d 65 6e 74 20 74 6f 20 62 65 20 69   element to be i
16a0: 6e 73 65 72 74 65 64 20 2a 2f 0a 29 7b 0a 20 20  nserted */.){.  
16b0: 48 61 73 68 45 6c 65 6d 20 2a 70 48 65 61 64 3b  HashElem *pHead;
16c0: 20 20 20 20 20 20 20 2f 2a 20 46 69 72 73 74 20         /* First 
16d0: 65 6c 65 6d 65 6e 74 20 61 6c 72 65 61 64 79 20  element already 
16e0: 69 6e 20 70 45 6e 74 72 79 20 2a 2f 0a 20 20 70  in pEntry */.  p
16f0: 48 65 61 64 20 3d 20 70 45 6e 74 72 79 2d 3e 63  Head = pEntry->c
1700: 68 61 69 6e 3b 0a 20 20 69 66 28 20 70 48 65 61  hain;.  if( pHea
1710: 64 20 29 7b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e  d ){.    pNew->n
1720: 65 78 74 20 3d 20 70 48 65 61 64 3b 0a 20 20 20  ext = pHead;.   
1730: 20 70 4e 65 77 2d 3e 70 72 65 76 20 3d 20 70 48   pNew->prev = pH
1740: 65 61 64 2d 3e 70 72 65 76 3b 0a 20 20 20 20 69  ead->prev;.    i
1750: 66 28 20 70 48 65 61 64 2d 3e 70 72 65 76 20 29  f( pHead->prev )
1760: 7b 20 70 48 65 61 64 2d 3e 70 72 65 76 2d 3e 6e  { pHead->prev->n
1770: 65 78 74 20 3d 20 70 4e 65 77 3b 20 7d 0a 20 20  ext = pNew; }.  
1780: 20 20 65 6c 73 65 20 20 20 20 20 20 20 20 20 20    else          
1790: 20 20 20 7b 20 70 48 2d 3e 66 69 72 73 74 20 3d     { pH->first =
17a0: 20 70 4e 65 77 3b 20 7d 0a 20 20 20 20 70 48 65   pNew; }.    pHe
17b0: 61 64 2d 3e 70 72 65 76 20 3d 20 70 4e 65 77 3b  ad->prev = pNew;
17c0: 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 70 4e  .  }else{.    pN
17d0: 65 77 2d 3e 6e 65 78 74 20 3d 20 70 48 2d 3e 66  ew->next = pH->f
17e0: 69 72 73 74 3b 0a 20 20 20 20 69 66 28 20 70 48  irst;.    if( pH
17f0: 2d 3e 66 69 72 73 74 20 29 7b 20 70 48 2d 3e 66  ->first ){ pH->f
1800: 69 72 73 74 2d 3e 70 72 65 76 20 3d 20 70 4e 65  irst->prev = pNe
1810: 77 3b 20 7d 0a 20 20 20 20 70 4e 65 77 2d 3e 70  w; }.    pNew->p
1820: 72 65 76 20 3d 20 30 3b 0a 20 20 20 20 70 48 2d  rev = 0;.    pH-
1830: 3e 66 69 72 73 74 20 3d 20 70 4e 65 77 3b 0a 20  >first = pNew;. 
1840: 20 7d 0a 20 20 70 45 6e 74 72 79 2d 3e 63 6f 75   }.  pEntry->cou
1850: 6e 74 2b 2b 3b 0a 20 20 70 45 6e 74 72 79 2d 3e  nt++;.  pEntry->
1860: 63 68 61 69 6e 20 3d 20 70 4e 65 77 3b 0a 7d 0a  chain = pNew;.}.
1870: 0a 0a 2f 2a 20 52 65 73 69 7a 65 20 74 68 65 20  ../* Resize the 
1880: 68 61 73 68 20 74 61 62 6c 65 20 73 6f 20 74 68  hash table so th
1890: 61 74 20 69 74 20 63 61 6e 74 61 69 6e 73 20 22  at it cantains "
18a0: 6e 65 77 5f 73 69 7a 65 22 20 62 75 63 6b 65 74  new_size" bucket
18b0: 73 2e 0a 2a 2a 20 22 6e 65 77 5f 73 69 7a 65 22  s..** "new_size"
18c0: 20 6d 75 73 74 20 62 65 20 61 20 70 6f 77 65 72   must be a power
18d0: 20 6f 66 20 32 2e 20 20 54 68 65 20 68 61 73 68   of 2.  The hash
18e0: 20 74 61 62 6c 65 20 6d 69 67 68 74 20 66 61 69   table might fai
18f0: 6c 20 0a 2a 2a 20 74 6f 20 72 65 73 69 7a 65 20  l .** to resize 
1900: 69 66 20 73 71 6c 69 74 65 4d 61 6c 6c 6f 63 28  if sqliteMalloc(
1910: 29 20 66 61 69 6c 73 2e 0a 2a 2f 0a 73 74 61 74  ) fails..*/.stat
1920: 69 63 20 76 6f 69 64 20 72 65 68 61 73 68 28 48  ic void rehash(H
1930: 61 73 68 20 2a 70 48 2c 20 69 6e 74 20 6e 65 77  ash *pH, int new
1940: 5f 73 69 7a 65 29 7b 0a 20 20 73 74 72 75 63 74  _size){.  struct
1950: 20 5f 68 74 20 2a 6e 65 77 5f 68 74 3b 20 20 20   _ht *new_ht;   
1960: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20           /* The 
1970: 6e 65 77 20 68 61 73 68 20 74 61 62 6c 65 20 2a  new hash table *
1980: 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c  /.  HashElem *el
1990: 65 6d 2c 20 2a 6e 65 78 74 5f 65 6c 65 6d 3b 20  em, *next_elem; 
19a0: 20 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f 70 69 6e     /* For loopin
19b0: 67 20 6f 76 65 72 20 65 78 69 73 74 69 6e 67 20  g over existing 
19c0: 65 6c 65 6d 65 6e 74 73 20 2a 2f 0a 20 20 69 6e  elements */.  in
19d0: 74 20 28 2a 78 48 61 73 68 29 28 63 6f 6e 73 74  t (*xHash)(const
19e0: 20 76 6f 69 64 2a 2c 69 6e 74 29 3b 20 2f 2a 20   void*,int); /* 
19f0: 54 68 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f  The hash functio
1a00: 6e 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20  n */..  assert( 
1a10: 28 6e 65 77 5f 73 69 7a 65 20 26 20 28 6e 65 77  (new_size & (new
1a20: 5f 73 69 7a 65 2d 31 29 29 3d 3d 30 20 29 3b 0a  _size-1))==0 );.
1a30: 20 20 6e 65 77 5f 68 74 20 3d 20 28 73 74 72 75    new_ht = (stru
1a40: 63 74 20 5f 68 74 20 2a 29 70 48 2d 3e 78 4d 61  ct _ht *)pH->xMa
1a50: 6c 6c 6f 63 28 20 6e 65 77 5f 73 69 7a 65 2a 73  lloc( new_size*s
1a60: 69 7a 65 6f 66 28 73 74 72 75 63 74 20 5f 68 74  izeof(struct _ht
1a70: 29 20 29 3b 0a 20 20 69 66 28 20 6e 65 77 5f 68  ) );.  if( new_h
1a80: 74 3d 3d 30 20 29 20 72 65 74 75 72 6e 3b 0a 20  t==0 ) return;. 
1a90: 20 69 66 28 20 70 48 2d 3e 68 74 20 29 20 70 48   if( pH->ht ) pH
1aa0: 2d 3e 78 46 72 65 65 28 70 48 2d 3e 68 74 29 3b  ->xFree(pH->ht);
1ab0: 0a 20 20 70 48 2d 3e 68 74 20 3d 20 6e 65 77 5f  .  pH->ht = new_
1ac0: 68 74 3b 0a 20 20 70 48 2d 3e 68 74 73 69 7a 65  ht;.  pH->htsize
1ad0: 20 3d 20 6e 65 77 5f 73 69 7a 65 3b 0a 20 20 78   = new_size;.  x
1ae0: 48 61 73 68 20 3d 20 68 61 73 68 46 75 6e 63 74  Hash = hashFunct
1af0: 69 6f 6e 28 70 48 2d 3e 6b 65 79 43 6c 61 73 73  ion(pH->keyClass
1b00: 29 3b 0a 20 20 66 6f 72 28 65 6c 65 6d 3d 70 48  );.  for(elem=pH
1b10: 2d 3e 66 69 72 73 74 2c 20 70 48 2d 3e 66 69 72  ->first, pH->fir
1b20: 73 74 3d 30 3b 20 65 6c 65 6d 3b 20 65 6c 65 6d  st=0; elem; elem
1b30: 20 3d 20 6e 65 78 74 5f 65 6c 65 6d 29 7b 0a 20   = next_elem){. 
1b40: 20 20 20 69 6e 74 20 68 20 3d 20 28 2a 78 48 61     int h = (*xHa
1b50: 73 68 29 28 65 6c 65 6d 2d 3e 70 4b 65 79 2c 20  sh)(elem->pKey, 
1b60: 65 6c 65 6d 2d 3e 6e 4b 65 79 29 20 26 20 28 6e  elem->nKey) & (n
1b70: 65 77 5f 73 69 7a 65 2d 31 29 3b 0a 20 20 20 20  ew_size-1);.    
1b80: 6e 65 78 74 5f 65 6c 65 6d 20 3d 20 65 6c 65 6d  next_elem = elem
1b90: 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 69 6e 73 65  ->next;.    inse
1ba0: 72 74 45 6c 65 6d 65 6e 74 28 70 48 2c 20 26 6e  rtElement(pH, &n
1bb0: 65 77 5f 68 74 5b 68 5d 2c 20 65 6c 65 6d 29 3b  ew_ht[h], elem);
1bc0: 0a 20 20 7d 0a 7d 0a 0a 2f 2a 20 54 68 69 73 20  .  }.}../* This 
1bd0: 66 75 6e 63 74 69 6f 6e 20 28 66 6f 72 20 69 6e  function (for in
1be0: 74 65 72 6e 61 6c 20 75 73 65 20 6f 6e 6c 79 29  ternal use only)
1bf0: 20 6c 6f 63 61 74 65 73 20 61 6e 20 65 6c 65 6d   locates an elem
1c00: 65 6e 74 20 69 6e 20 61 6e 0a 2a 2a 20 68 61 73  ent in an.** has
1c10: 68 20 74 61 62 6c 65 20 74 68 61 74 20 6d 61 74  h table that mat
1c20: 63 68 65 73 20 74 68 65 20 67 69 76 65 6e 20 6b  ches the given k
1c30: 65 79 2e 20 20 54 68 65 20 68 61 73 68 20 66 6f  ey.  The hash fo
1c40: 72 20 74 68 69 73 20 6b 65 79 20 68 61 73 0a 2a  r this key has.*
1c50: 2a 20 61 6c 72 65 61 64 79 20 62 65 65 6e 20 63  * already been c
1c60: 6f 6d 70 75 74 65 64 20 61 6e 64 20 69 73 20 70  omputed and is p
1c70: 61 73 73 65 64 20 61 73 20 74 68 65 20 34 74 68  assed as the 4th
1c80: 20 70 61 72 61 6d 65 74 65 72 2e 0a 2a 2f 0a 73   parameter..*/.s
1c90: 74 61 74 69 63 20 48 61 73 68 45 6c 65 6d 20 2a  tatic HashElem *
1ca0: 66 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65 6e  findElementGiven
1cb0: 48 61 73 68 28 0a 20 20 63 6f 6e 73 74 20 48 61  Hash(.  const Ha
1cc0: 73 68 20 2a 70 48 2c 20 20 20 20 20 2f 2a 20 54  sh *pH,     /* T
1cd0: 68 65 20 70 48 20 74 6f 20 62 65 20 73 65 61 72  he pH to be sear
1ce0: 63 68 65 64 20 2a 2f 0a 20 20 63 6f 6e 73 74 20  ched */.  const 
1cf0: 76 6f 69 64 20 2a 70 4b 65 79 2c 20 20 20 2f 2a  void *pKey,   /*
1d00: 20 54 68 65 20 6b 65 79 20 77 65 20 61 72 65 20   The key we are 
1d10: 73 65 61 72 63 68 69 6e 67 20 66 6f 72 20 2a 2f  searching for */
1d20: 0a 20 20 69 6e 74 20 6e 4b 65 79 2c 0a 20 20 69  .  int nKey,.  i
1d30: 6e 74 20 68 20 20 20 20 20 20 20 20 20 20 20 20  nt h            
1d40: 20 20 20 2f 2a 20 54 68 65 20 68 61 73 68 20 66     /* The hash f
1d50: 6f 72 20 74 68 69 73 20 6b 65 79 2e 20 2a 2f 0a  or this key. */.
1d60: 29 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65  ){.  HashElem *e
1d70: 6c 65 6d 3b 20 20 20 20 20 20 20 20 20 20 20 20  lem;            
1d80: 20 20 20 20 2f 2a 20 55 73 65 64 20 74 6f 20 6c      /* Used to l
1d90: 6f 6f 70 20 74 68 72 75 20 74 68 65 20 65 6c 65  oop thru the ele
1da0: 6d 65 6e 74 20 6c 69 73 74 20 2a 2f 0a 20 20 69  ment list */.  i
1db0: 6e 74 20 63 6f 75 6e 74 3b 20 20 20 20 20 20 20  nt count;       
1dc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
1dd0: 20 4e 75 6d 62 65 72 20 6f 66 20 65 6c 65 6d 65   Number of eleme
1de0: 6e 74 73 20 6c 65 66 74 20 74 6f 20 74 65 73 74  nts left to test
1df0: 20 2a 2f 0a 20 20 69 6e 74 20 28 2a 78 43 6f 6d   */.  int (*xCom
1e00: 70 61 72 65 29 28 63 6f 6e 73 74 20 76 6f 69 64  pare)(const void
1e10: 2a 2c 69 6e 74 2c 63 6f 6e 73 74 20 76 6f 69 64  *,int,const void
1e20: 2a 2c 69 6e 74 29 3b 20 20 2f 2a 20 63 6f 6d 70  *,int);  /* comp
1e30: 61 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 20  arison function 
1e40: 2a 2f 0a 0a 20 20 69 66 28 20 70 48 2d 3e 68 74  */..  if( pH->ht
1e50: 20 29 7b 0a 20 20 20 20 73 74 72 75 63 74 20 5f   ){.    struct _
1e60: 68 74 20 2a 70 45 6e 74 72 79 20 3d 20 26 70 48  ht *pEntry = &pH
1e70: 2d 3e 68 74 5b 68 5d 3b 0a 20 20 20 20 65 6c 65  ->ht[h];.    ele
1e80: 6d 20 3d 20 70 45 6e 74 72 79 2d 3e 63 68 61 69  m = pEntry->chai
1e90: 6e 3b 0a 20 20 20 20 63 6f 75 6e 74 20 3d 20 70  n;.    count = p
1ea0: 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 3b 0a 20 20  Entry->count;.  
1eb0: 20 20 78 43 6f 6d 70 61 72 65 20 3d 20 63 6f 6d    xCompare = com
1ec0: 70 61 72 65 46 75 6e 63 74 69 6f 6e 28 70 48 2d  pareFunction(pH-
1ed0: 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20 20 20  >keyClass);.    
1ee0: 77 68 69 6c 65 28 20 63 6f 75 6e 74 2d 2d 20 26  while( count-- &
1ef0: 26 20 65 6c 65 6d 20 29 7b 0a 20 20 20 20 20 20  & elem ){.      
1f00: 69 66 28 20 28 2a 78 43 6f 6d 70 61 72 65 29 28  if( (*xCompare)(
1f10: 65 6c 65 6d 2d 3e 70 4b 65 79 2c 65 6c 65 6d 2d  elem->pKey,elem-
1f20: 3e 6e 4b 65 79 2c 70 4b 65 79 2c 6e 4b 65 79 29  >nKey,pKey,nKey)
1f30: 3d 3d 30 20 29 7b 20 0a 20 20 20 20 20 20 20 20  ==0 ){ .        
1f40: 72 65 74 75 72 6e 20 65 6c 65 6d 3b 0a 20 20 20  return elem;.   
1f50: 20 20 20 7d 0a 20 20 20 20 20 20 65 6c 65 6d 20     }.      elem 
1f60: 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20  = elem->next;.  
1f70: 20 20 7d 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e    }.  }.  return
1f80: 20 30 3b 0a 7d 0a 0a 2f 2a 20 52 65 6d 6f 76 65   0;.}../* Remove
1f90: 20 61 20 73 69 6e 67 6c 65 20 65 6e 74 72 79 20   a single entry 
1fa0: 66 72 6f 6d 20 74 68 65 20 68 61 73 68 20 74 61  from the hash ta
1fb0: 62 6c 65 20 67 69 76 65 6e 20 61 20 70 6f 69 6e  ble given a poin
1fc0: 74 65 72 20 74 6f 20 74 68 61 74 0a 2a 2a 20 65  ter to that.** e
1fd0: 6c 65 6d 65 6e 74 20 61 6e 64 20 61 20 68 61 73  lement and a has
1fe0: 68 20 6f 6e 20 74 68 65 20 65 6c 65 6d 65 6e 74  h on the element
1ff0: 27 73 20 6b 65 79 2e 0a 2a 2f 0a 73 74 61 74 69  's key..*/.stati
2000: 63 20 76 6f 69 64 20 72 65 6d 6f 76 65 45 6c 65  c void removeEle
2010: 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28 0a 20  mentGivenHash(. 
2020: 20 48 61 73 68 20 2a 70 48 2c 20 20 20 20 20 20   Hash *pH,      
2030: 20 20 20 2f 2a 20 54 68 65 20 70 48 20 63 6f 6e     /* The pH con
2040: 74 61 69 6e 69 6e 67 20 22 65 6c 65 6d 22 20 2a  taining "elem" *
2050: 2f 0a 20 20 48 61 73 68 45 6c 65 6d 2a 20 65 6c  /.  HashElem* el
2060: 65 6d 2c 20 20 20 2f 2a 20 54 68 65 20 65 6c 65  em,   /* The ele
2070: 6d 65 6e 74 20 74 6f 20 62 65 20 72 65 6d 6f 76  ment to be remov
2080: 65 64 20 66 72 6f 6d 20 74 68 65 20 70 48 20 2a  ed from the pH *
2090: 2f 0a 20 20 69 6e 74 20 68 20 20 20 20 20 20 20  /.  int h       
20a0: 20 20 20 20 20 20 2f 2a 20 48 61 73 68 20 76 61        /* Hash va
20b0: 6c 75 65 20 66 6f 72 20 74 68 65 20 65 6c 65 6d  lue for the elem
20c0: 65 6e 74 20 2a 2f 0a 29 7b 0a 20 20 73 74 72 75  ent */.){.  stru
20d0: 63 74 20 5f 68 74 20 2a 70 45 6e 74 72 79 3b 0a  ct _ht *pEntry;.
20e0: 20 20 69 66 28 20 65 6c 65 6d 2d 3e 70 72 65 76    if( elem->prev
20f0: 20 29 7b 0a 20 20 20 20 65 6c 65 6d 2d 3e 70 72   ){.    elem->pr
2100: 65 76 2d 3e 6e 65 78 74 20 3d 20 65 6c 65 6d 2d  ev->next = elem-
2110: 3e 6e 65 78 74 3b 20 0a 20 20 7d 65 6c 73 65 7b  >next; .  }else{
2120: 0a 20 20 20 20 70 48 2d 3e 66 69 72 73 74 20 3d  .    pH->first =
2130: 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 7d   elem->next;.  }
2140: 0a 20 20 69 66 28 20 65 6c 65 6d 2d 3e 6e 65 78  .  if( elem->nex
2150: 74 20 29 7b 0a 20 20 20 20 65 6c 65 6d 2d 3e 6e  t ){.    elem->n
2160: 65 78 74 2d 3e 70 72 65 76 20 3d 20 65 6c 65 6d  ext->prev = elem
2170: 2d 3e 70 72 65 76 3b 0a 20 20 7d 0a 20 20 70 45  ->prev;.  }.  pE
2180: 6e 74 72 79 20 3d 20 26 70 48 2d 3e 68 74 5b 68  ntry = &pH->ht[h
2190: 5d 3b 0a 20 20 69 66 28 20 70 45 6e 74 72 79 2d  ];.  if( pEntry-
21a0: 3e 63 68 61 69 6e 3d 3d 65 6c 65 6d 20 29 7b 0a  >chain==elem ){.
21b0: 20 20 20 20 70 45 6e 74 72 79 2d 3e 63 68 61 69      pEntry->chai
21c0: 6e 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a  n = elem->next;.
21d0: 20 20 7d 0a 20 20 70 45 6e 74 72 79 2d 3e 63 6f    }.  pEntry->co
21e0: 75 6e 74 2d 2d 3b 0a 20 20 69 66 28 20 70 45 6e  unt--;.  if( pEn
21f0: 74 72 79 2d 3e 63 6f 75 6e 74 3c 3d 30 20 29 7b  try->count<=0 ){
2200: 0a 20 20 20 20 70 45 6e 74 72 79 2d 3e 63 68 61  .    pEntry->cha
2210: 69 6e 20 3d 20 30 3b 0a 20 20 7d 0a 20 20 69 66  in = 0;.  }.  if
2220: 28 20 70 48 2d 3e 63 6f 70 79 4b 65 79 20 26 26  ( pH->copyKey &&
2230: 20 65 6c 65 6d 2d 3e 70 4b 65 79 20 29 7b 0a 20   elem->pKey ){. 
2240: 20 20 20 70 48 2d 3e 78 46 72 65 65 28 65 6c 65     pH->xFree(ele
2250: 6d 2d 3e 70 4b 65 79 29 3b 0a 20 20 7d 0a 20 20  m->pKey);.  }.  
2260: 70 48 2d 3e 78 46 72 65 65 28 20 65 6c 65 6d 20  pH->xFree( elem 
2270: 29 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 2d 2d  );.  pH->count--
2280: 3b 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f 75 6e  ;.  if( pH->coun
2290: 74 3c 3d 30 20 29 7b 0a 20 20 20 20 61 73 73 65  t<=0 ){.    asse
22a0: 72 74 28 20 70 48 2d 3e 66 69 72 73 74 3d 3d 30  rt( pH->first==0
22b0: 20 29 3b 0a 20 20 20 20 61 73 73 65 72 74 28 20   );.    assert( 
22c0: 70 48 2d 3e 63 6f 75 6e 74 3d 3d 30 20 29 3b 0a  pH->count==0 );.
22d0: 20 20 20 20 48 61 73 68 43 6c 65 61 72 28 70 48      HashClear(pH
22e0: 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 20 41 74 74  );.  }.}../* Att
22f0: 65 6d 70 74 20 74 6f 20 6c 6f 63 61 74 65 20 61  empt to locate a
2300: 6e 20 65 6c 65 6d 65 6e 74 20 6f 66 20 74 68 65  n element of the
2310: 20 68 61 73 68 20 74 61 62 6c 65 20 70 48 20 77   hash table pH w
2320: 69 74 68 20 61 20 6b 65 79 0a 2a 2a 20 74 68 61  ith a key.** tha
2330: 74 20 6d 61 74 63 68 65 73 20 70 4b 65 79 2c 6e  t matches pKey,n
2340: 4b 65 79 2e 20 20 52 65 74 75 72 6e 20 74 68 65  Key.  Return the
2350: 20 64 61 74 61 20 66 6f 72 20 74 68 69 73 20 65   data for this e
2360: 6c 65 6d 65 6e 74 20 69 66 20 69 74 20 69 73 0a  lement if it is.
2370: 2a 2a 20 66 6f 75 6e 64 2c 20 6f 72 20 4e 55 4c  ** found, or NUL
2380: 4c 20 69 66 20 74 68 65 72 65 20 69 73 20 6e 6f  L if there is no
2390: 20 6d 61 74 63 68 2e 0a 2a 2f 0a 76 6f 69 64 20   match..*/.void 
23a0: 2a 48 61 73 68 46 69 6e 64 28 63 6f 6e 73 74 20  *HashFind(const 
23b0: 48 61 73 68 20 2a 70 48 2c 20 63 6f 6e 73 74 20  Hash *pH, const 
23c0: 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20  void *pKey, int 
23d0: 6e 4b 65 79 29 7b 0a 20 20 69 6e 74 20 68 3b 20  nKey){.  int h; 
23e0: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 41              /* A
23f0: 20 68 61 73 68 20 6f 6e 20 6b 65 79 20 2a 2f 0a   hash on key */.
2400: 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d    HashElem *elem
2410: 3b 20 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d  ;    /* The elem
2420: 65 6e 74 20 74 68 61 74 20 6d 61 74 63 68 65 73  ent that matches
2430: 20 6b 65 79 20 2a 2f 0a 20 20 69 6e 74 20 28 2a   key */.  int (*
2440: 78 48 61 73 68 29 28 63 6f 6e 73 74 20 76 6f 69  xHash)(const voi
2450: 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a 20 54 68 65  d*,int);  /* The
2460: 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 2a   hash function *
2470: 2f 0a 0a 20 20 69 66 28 20 70 48 3d 3d 30 20 7c  /..  if( pH==0 |
2480: 7c 20 70 48 2d 3e 68 74 3d 3d 30 20 29 20 72 65  | pH->ht==0 ) re
2490: 74 75 72 6e 20 30 3b 0a 20 20 78 48 61 73 68 20  turn 0;.  xHash 
24a0: 3d 20 68 61 73 68 46 75 6e 63 74 69 6f 6e 28 70  = hashFunction(p
24b0: 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20  H->keyClass);.  
24c0: 61 73 73 65 72 74 28 20 78 48 61 73 68 21 3d 30  assert( xHash!=0
24d0: 20 29 3b 0a 20 20 68 20 3d 20 28 2a 78 48 61 73   );.  h = (*xHas
24e0: 68 29 28 70 4b 65 79 2c 6e 4b 65 79 29 3b 0a 20  h)(pKey,nKey);. 
24f0: 20 61 73 73 65 72 74 28 20 28 70 48 2d 3e 68 74   assert( (pH->ht
2500: 73 69 7a 65 20 26 20 28 70 48 2d 3e 68 74 73 69  size & (pH->htsi
2510: 7a 65 2d 31 29 29 3d 3d 30 20 29 3b 0a 20 20 65  ze-1))==0 );.  e
2520: 6c 65 6d 20 3d 20 66 69 6e 64 45 6c 65 6d 65 6e  lem = findElemen
2530: 74 47 69 76 65 6e 48 61 73 68 28 70 48 2c 70 4b  tGivenHash(pH,pK
2540: 65 79 2c 6e 4b 65 79 2c 20 68 20 26 20 28 70 48  ey,nKey, h & (pH
2550: 2d 3e 68 74 73 69 7a 65 2d 31 29 29 3b 0a 20 20  ->htsize-1));.  
2560: 72 65 74 75 72 6e 20 65 6c 65 6d 20 3f 20 65 6c  return elem ? el
2570: 65 6d 2d 3e 64 61 74 61 20 3a 20 30 3b 0a 7d 0a  em->data : 0;.}.
2580: 0a 2f 2a 20 49 6e 73 65 72 74 20 61 6e 20 65 6c  ./* Insert an el
2590: 65 6d 65 6e 74 20 69 6e 74 6f 20 74 68 65 20 68  ement into the h
25a0: 61 73 68 20 74 61 62 6c 65 20 70 48 2e 20 20 54  ash table pH.  T
25b0: 68 65 20 6b 65 79 20 69 73 20 70 4b 65 79 2c 6e  he key is pKey,n
25c0: 4b 65 79 0a 2a 2a 20 61 6e 64 20 74 68 65 20 64  Key.** and the d
25d0: 61 74 61 20 69 73 20 22 64 61 74 61 22 2e 0a 2a  ata is "data"..*
25e0: 2a 0a 2a 2a 20 49 66 20 6e 6f 20 65 6c 65 6d 65  *.** If no eleme
25f0: 6e 74 20 65 78 69 73 74 73 20 77 69 74 68 20 61  nt exists with a
2600: 20 6d 61 74 63 68 69 6e 67 20 6b 65 79 2c 20 74   matching key, t
2610: 68 65 6e 20 61 20 6e 65 77 0a 2a 2a 20 65 6c 65  hen a new.** ele
2620: 6d 65 6e 74 20 69 73 20 63 72 65 61 74 65 64 2e  ment is created.
2630: 20 20 41 20 63 6f 70 79 20 6f 66 20 74 68 65 20    A copy of the 
2640: 6b 65 79 20 69 73 20 6d 61 64 65 20 69 66 20 74  key is made if t
2650: 68 65 20 63 6f 70 79 4b 65 79 0a 2a 2a 20 66 6c  he copyKey.** fl
2660: 61 67 20 69 73 20 73 65 74 2e 20 20 4e 55 4c 4c  ag is set.  NULL
2670: 20 69 73 20 72 65 74 75 72 6e 65 64 2e 0a 2a 2a   is returned..**
2680: 0a 2a 2a 20 49 66 20 61 6e 6f 74 68 65 72 20 65  .** If another e
2690: 6c 65 6d 65 6e 74 20 61 6c 72 65 61 64 79 20 65  lement already e
26a0: 78 69 73 74 73 20 77 69 74 68 20 74 68 65 20 73  xists with the s
26b0: 61 6d 65 20 6b 65 79 2c 20 74 68 65 6e 20 74 68  ame key, then th
26c0: 65 0a 2a 2a 20 6e 65 77 20 64 61 74 61 20 72 65  e.** new data re
26d0: 70 6c 61 63 65 73 20 74 68 65 20 6f 6c 64 20 64  places the old d
26e0: 61 74 61 20 61 6e 64 20 74 68 65 20 6f 6c 64 20  ata and the old 
26f0: 64 61 74 61 20 69 73 20 72 65 74 75 72 6e 65 64  data is returned
2700: 2e 0a 2a 2a 20 54 68 65 20 6b 65 79 20 69 73 20  ..** The key is 
2710: 6e 6f 74 20 63 6f 70 69 65 64 20 69 6e 20 74 68  not copied in th
2720: 69 73 20 69 6e 73 74 61 6e 63 65 2e 20 20 49 66  is instance.  If
2730: 20 61 20 6d 61 6c 6c 6f 63 20 66 61 69 6c 73 2c   a malloc fails,
2740: 20 74 68 65 6e 0a 2a 2a 20 74 68 65 20 6e 65 77   then.** the new
2750: 20 64 61 74 61 20 69 73 20 72 65 74 75 72 6e 65   data is returne
2760: 64 20 61 6e 64 20 74 68 65 20 68 61 73 68 20 74  d and the hash t
2770: 61 62 6c 65 20 69 73 20 75 6e 63 68 61 6e 67 65  able is unchange
2780: 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 65 20  d..**.** If the 
2790: 22 64 61 74 61 22 20 70 61 72 61 6d 65 74 65 72  "data" parameter
27a0: 20 74 6f 20 74 68 69 73 20 66 75 6e 63 74 69 6f   to this functio
27b0: 6e 20 69 73 20 4e 55 4c 4c 2c 20 74 68 65 6e 20  n is NULL, then 
27c0: 74 68 65 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 63  the.** element c
27d0: 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 74 6f 20  orresponding to 
27e0: 22 6b 65 79 22 20 69 73 20 72 65 6d 6f 76 65 64  "key" is removed
27f0: 20 66 72 6f 6d 20 74 68 65 20 68 61 73 68 20 74   from the hash t
2800: 61 62 6c 65 2e 0a 2a 2f 0a 76 6f 69 64 20 2a 48  able..*/.void *H
2810: 61 73 68 49 6e 73 65 72 74 28 48 61 73 68 20 2a  ashInsert(Hash *
2820: 70 48 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a  pH, const void *
2830: 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 2c 20  pKey, int nKey, 
2840: 76 6f 69 64 20 2a 64 61 74 61 29 7b 0a 20 20 69  void *data){.  i
2850: 6e 74 20 68 72 61 77 3b 20 20 20 20 20 20 20 20  nt hraw;        
2860: 20 20 20 20 20 2f 2a 20 52 61 77 20 68 61 73 68       /* Raw hash
2870: 20 76 61 6c 75 65 20 6f 66 20 74 68 65 20 6b 65   value of the ke
2880: 79 20 2a 2f 0a 20 20 69 6e 74 20 68 3b 20 20 20  y */.  int h;   
2890: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
28a0: 74 68 65 20 68 61 73 68 20 6f 66 20 74 68 65 20  the hash of the 
28b0: 6b 65 79 20 6d 6f 64 75 6c 6f 20 68 61 73 68 20  key modulo hash 
28c0: 74 61 62 6c 65 20 73 69 7a 65 20 2a 2f 0a 20 20  table size */.  
28d0: 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20  HashElem *elem; 
28e0: 20 20 20 20 20 20 2f 2a 20 55 73 65 64 20 74 6f        /* Used to
28f0: 20 6c 6f 6f 70 20 74 68 72 75 20 74 68 65 20 65   loop thru the e
2900: 6c 65 6d 65 6e 74 20 6c 69 73 74 20 2a 2f 0a 20  lement list */. 
2910: 20 48 61 73 68 45 6c 65 6d 20 2a 6e 65 77 5f 65   HashElem *new_e
2920: 6c 65 6d 3b 20 20 20 2f 2a 20 4e 65 77 20 65 6c  lem;   /* New el
2930: 65 6d 65 6e 74 20 61 64 64 65 64 20 74 6f 20 74  ement added to t
2940: 68 65 20 70 48 20 2a 2f 0a 20 20 69 6e 74 20 28  he pH */.  int (
2950: 2a 78 48 61 73 68 29 28 63 6f 6e 73 74 20 76 6f  *xHash)(const vo
2960: 69 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a 20 54 68  id*,int);  /* Th
2970: 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e 20  e hash function 
2980: 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 70 48  */..  assert( pH
2990: 21 3d 30 20 29 3b 0a 20 20 78 48 61 73 68 20 3d  !=0 );.  xHash =
29a0: 20 68 61 73 68 46 75 6e 63 74 69 6f 6e 28 70 48   hashFunction(pH
29b0: 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20 61  ->keyClass);.  a
29c0: 73 73 65 72 74 28 20 78 48 61 73 68 21 3d 30 20  ssert( xHash!=0 
29d0: 29 3b 0a 20 20 68 72 61 77 20 3d 20 28 2a 78 48  );.  hraw = (*xH
29e0: 61 73 68 29 28 70 4b 65 79 2c 20 6e 4b 65 79 29  ash)(pKey, nKey)
29f0: 3b 0a 20 20 61 73 73 65 72 74 28 20 28 70 48 2d  ;.  assert( (pH-
2a00: 3e 68 74 73 69 7a 65 20 26 20 28 70 48 2d 3e 68  >htsize & (pH->h
2a10: 74 73 69 7a 65 2d 31 29 29 3d 3d 30 20 29 3b 0a  tsize-1))==0 );.
2a20: 20 20 68 20 3d 20 68 72 61 77 20 26 20 28 70 48    h = hraw & (pH
2a30: 2d 3e 68 74 73 69 7a 65 2d 31 29 3b 0a 20 20 65  ->htsize-1);.  e
2a40: 6c 65 6d 20 3d 20 66 69 6e 64 45 6c 65 6d 65 6e  lem = findElemen
2a50: 74 47 69 76 65 6e 48 61 73 68 28 70 48 2c 70 4b  tGivenHash(pH,pK
2a60: 65 79 2c 6e 4b 65 79 2c 68 29 3b 0a 20 20 69 66  ey,nKey,h);.  if
2a70: 28 20 65 6c 65 6d 20 29 7b 0a 20 20 20 20 76 6f  ( elem ){.    vo
2a80: 69 64 20 2a 6f 6c 64 5f 64 61 74 61 20 3d 20 65  id *old_data = e
2a90: 6c 65 6d 2d 3e 64 61 74 61 3b 0a 20 20 20 20 69  lem->data;.    i
2aa0: 66 28 20 64 61 74 61 3d 3d 30 20 29 7b 0a 20 20  f( data==0 ){.  
2ab0: 20 20 20 20 72 65 6d 6f 76 65 45 6c 65 6d 65 6e      removeElemen
2ac0: 74 47 69 76 65 6e 48 61 73 68 28 70 48 2c 65 6c  tGivenHash(pH,el
2ad0: 65 6d 2c 68 29 3b 0a 20 20 20 20 7d 65 6c 73 65  em,h);.    }else
2ae0: 7b 0a 20 20 20 20 20 20 65 6c 65 6d 2d 3e 64 61  {.      elem->da
2af0: 74 61 20 3d 20 64 61 74 61 3b 0a 20 20 20 20 7d  ta = data;.    }
2b00: 0a 20 20 20 20 72 65 74 75 72 6e 20 6f 6c 64 5f  .    return old_
2b10: 64 61 74 61 3b 0a 20 20 7d 0a 20 20 69 66 28 20  data;.  }.  if( 
2b20: 64 61 74 61 3d 3d 30 20 29 20 72 65 74 75 72 6e  data==0 ) return
2b30: 20 30 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 20 3d   0;.  new_elem =
2b40: 20 28 48 61 73 68 45 6c 65 6d 2a 29 70 48 2d 3e   (HashElem*)pH->
2b50: 78 4d 61 6c 6c 6f 63 28 20 73 69 7a 65 6f 66 28  xMalloc( sizeof(
2b60: 48 61 73 68 45 6c 65 6d 29 20 29 3b 0a 20 20 69  HashElem) );.  i
2b70: 66 28 20 6e 65 77 5f 65 6c 65 6d 3d 3d 30 20 29  f( new_elem==0 )
2b80: 20 72 65 74 75 72 6e 20 64 61 74 61 3b 0a 20 20   return data;.  
2b90: 69 66 28 20 70 48 2d 3e 63 6f 70 79 4b 65 79 20  if( pH->copyKey 
2ba0: 26 26 20 70 4b 65 79 21 3d 30 20 29 7b 0a 20 20  && pKey!=0 ){.  
2bb0: 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79    new_elem->pKey
2bc0: 20 3d 20 70 48 2d 3e 78 4d 61 6c 6c 6f 63 28 20   = pH->xMalloc( 
2bd0: 6e 4b 65 79 20 29 3b 0a 20 20 20 20 69 66 28 20  nKey );.    if( 
2be0: 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 3d 3d  new_elem->pKey==
2bf0: 30 20 29 7b 0a 20 20 20 20 20 20 70 48 2d 3e 78  0 ){.      pH->x
2c00: 46 72 65 65 28 6e 65 77 5f 65 6c 65 6d 29 3b 0a  Free(new_elem);.
2c10: 20 20 20 20 20 20 72 65 74 75 72 6e 20 64 61 74        return dat
2c20: 61 3b 0a 20 20 20 20 7d 0a 20 20 20 20 6d 65 6d  a;.    }.    mem
2c30: 63 70 79 28 28 76 6f 69 64 2a 29 6e 65 77 5f 65  cpy((void*)new_e
2c40: 6c 65 6d 2d 3e 70 4b 65 79 2c 20 70 4b 65 79 2c  lem->pKey, pKey,
2c50: 20 6e 4b 65 79 29 3b 0a 20 20 7d 65 6c 73 65 7b   nKey);.  }else{
2c60: 0a 20 20 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70  .    new_elem->p
2c70: 4b 65 79 20 3d 20 28 76 6f 69 64 2a 29 70 4b 65  Key = (void*)pKe
2c80: 79 3b 0a 20 20 7d 0a 20 20 6e 65 77 5f 65 6c 65  y;.  }.  new_ele
2c90: 6d 2d 3e 6e 4b 65 79 20 3d 20 6e 4b 65 79 3b 0a  m->nKey = nKey;.
2ca0: 20 20 70 48 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20    pH->count++;. 
2cb0: 20 69 66 28 20 70 48 2d 3e 68 74 73 69 7a 65 3d   if( pH->htsize=
2cc0: 3d 30 20 29 7b 0a 20 20 20 20 72 65 68 61 73 68  =0 ){.    rehash
2cd0: 28 70 48 2c 38 29 3b 0a 20 20 20 20 69 66 28 20  (pH,8);.    if( 
2ce0: 70 48 2d 3e 68 74 73 69 7a 65 3d 3d 30 20 29 7b  pH->htsize==0 ){
2cf0: 0a 20 20 20 20 20 20 70 48 2d 3e 63 6f 75 6e 74  .      pH->count
2d00: 20 3d 20 30 3b 0a 20 20 20 20 20 20 70 48 2d 3e   = 0;.      pH->
2d10: 78 46 72 65 65 28 6e 65 77 5f 65 6c 65 6d 29 3b  xFree(new_elem);
2d20: 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 64 61  .      return da
2d30: 74 61 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20  ta;.    }.  }.  
2d40: 69 66 28 20 70 48 2d 3e 63 6f 75 6e 74 20 3e 20  if( pH->count > 
2d50: 70 48 2d 3e 68 74 73 69 7a 65 20 29 7b 0a 20 20  pH->htsize ){.  
2d60: 20 20 72 65 68 61 73 68 28 70 48 2c 70 48 2d 3e    rehash(pH,pH->
2d70: 68 74 73 69 7a 65 2a 32 29 3b 0a 20 20 7d 0a 20  htsize*2);.  }. 
2d80: 20 61 73 73 65 72 74 28 20 70 48 2d 3e 68 74 73   assert( pH->hts
2d90: 69 7a 65 3e 30 20 29 3b 0a 20 20 61 73 73 65 72  ize>0 );.  asser
2da0: 74 28 20 28 70 48 2d 3e 68 74 73 69 7a 65 20 26  t( (pH->htsize &
2db0: 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29 29   (pH->htsize-1))
2dc0: 3d 3d 30 20 29 3b 0a 20 20 68 20 3d 20 68 72 61  ==0 );.  h = hra
2dd0: 77 20 26 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d  w & (pH->htsize-
2de0: 31 29 3b 0a 20 20 69 6e 73 65 72 74 45 6c 65 6d  1);.  insertElem
2df0: 65 6e 74 28 70 48 2c 20 26 70 48 2d 3e 68 74 5b  ent(pH, &pH->ht[
2e00: 68 5d 2c 20 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20  h], new_elem);. 
2e10: 20 6e 65 77 5f 65 6c 65 6d 2d 3e 64 61 74 61 20   new_elem->data 
2e20: 3d 20 64 61 74 61 3b 0a 20 20 72 65 74 75 72 6e  = data;.  return
2e30: 20 30 3b 0a 7d 0a                                 0;.}.