/ Hex Artifact Content
Login

Artifact a12580e143f10301ed5166ea4964ae2853d3905a511d4e0c44497245c7ce1f7a:


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 0a 2a 2a 20 75  hash-tables.** u
01b0: 73 65 64 20 69 6e 20 53 51 4c 69 74 65 2e 0a 2a  sed in SQLite..*
01c0: 2f 0a 23 69 6e 63 6c 75 64 65 20 22 73 71 6c 69  /.#include "sqli
01d0: 74 65 49 6e 74 2e 68 22 0a 23 69 6e 63 6c 75 64  teInt.h".#includ
01e0: 65 20 3c 61 73 73 65 72 74 2e 68 3e 0a 0a 2f 2a  e <assert.h>../*
01f0: 20 54 75 72 6e 20 62 75 6c 6b 20 6d 65 6d 6f 72   Turn bulk memor
0200: 79 20 69 6e 74 6f 20 61 20 68 61 73 68 20 74 61  y into a hash ta
0210: 62 6c 65 20 6f 62 6a 65 63 74 20 62 79 20 69 6e  ble object by in
0220: 69 74 69 61 6c 69 7a 69 6e 67 20 74 68 65 0a 2a  itializing the.*
0230: 2a 20 66 69 65 6c 64 73 20 6f 66 20 74 68 65 20  * fields of the 
0240: 48 61 73 68 20 73 74 72 75 63 74 75 72 65 2e 0a  Hash structure..
0250: 2a 2a 0a 2a 2a 20 22 70 4e 65 77 22 20 69 73 20  **.** "pNew" is 
0260: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65  a pointer to the
0270: 20 68 61 73 68 20 74 61 62 6c 65 20 74 68 61 74   hash table that
0280: 20 69 73 20 74 6f 20 62 65 20 69 6e 69 74 69 61   is to be initia
0290: 6c 69 7a 65 64 2e 0a 2a 2f 0a 76 6f 69 64 20 73  lized..*/.void s
02a0: 71 6c 69 74 65 33 48 61 73 68 49 6e 69 74 28 48  qlite3HashInit(H
02b0: 61 73 68 20 2a 70 4e 65 77 29 7b 0a 20 20 61 73  ash *pNew){.  as
02c0: 73 65 72 74 28 20 70 4e 65 77 21 3d 30 20 29 3b  sert( pNew!=0 );
02d0: 0a 20 20 70 4e 65 77 2d 3e 66 69 72 73 74 20 3d  .  pNew->first =
02e0: 20 30 3b 0a 20 20 70 4e 65 77 2d 3e 63 6f 75 6e   0;.  pNew->coun
02f0: 74 20 3d 20 30 3b 0a 20 20 70 4e 65 77 2d 3e 68  t = 0;.  pNew->h
0300: 74 73 69 7a 65 20 3d 20 30 3b 0a 20 20 70 4e 65  tsize = 0;.  pNe
0310: 77 2d 3e 68 74 20 3d 20 30 3b 0a 7d 0a 0a 2f 2a  w->ht = 0;.}../*
0320: 20 52 65 6d 6f 76 65 20 61 6c 6c 20 65 6e 74 72   Remove all entr
0330: 69 65 73 20 66 72 6f 6d 20 61 20 68 61 73 68 20  ies from a hash 
0340: 74 61 62 6c 65 2e 20 20 52 65 63 6c 61 69 6d 20  table.  Reclaim 
0350: 61 6c 6c 20 6d 65 6d 6f 72 79 2e 0a 2a 2a 20 43  all memory..** C
0360: 61 6c 6c 20 74 68 69 73 20 72 6f 75 74 69 6e 65  all this routine
0370: 20 74 6f 20 64 65 6c 65 74 65 20 61 20 68 61 73   to delete a has
0380: 68 20 74 61 62 6c 65 20 6f 72 20 74 6f 20 72 65  h table or to re
0390: 73 65 74 20 61 20 68 61 73 68 20 74 61 62 6c 65  set a hash table
03a0: 0a 2a 2a 20 74 6f 20 74 68 65 20 65 6d 70 74 79  .** to the empty
03b0: 20 73 74 61 74 65 2e 0a 2a 2f 0a 76 6f 69 64 20   state..*/.void 
03c0: 73 71 6c 69 74 65 33 48 61 73 68 43 6c 65 61 72  sqlite3HashClear
03d0: 28 48 61 73 68 20 2a 70 48 29 7b 0a 20 20 48 61  (Hash *pH){.  Ha
03e0: 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20  shElem *elem;   
03f0: 20 20 20 20 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f        /* For loo
0400: 70 69 6e 67 20 6f 76 65 72 20 61 6c 6c 20 65 6c  ping over all el
0410: 65 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 74 61  ements of the ta
0420: 62 6c 65 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74  ble */..  assert
0430: 28 20 70 48 21 3d 30 20 29 3b 0a 20 20 65 6c 65  ( pH!=0 );.  ele
0440: 6d 20 3d 20 70 48 2d 3e 66 69 72 73 74 3b 0a 20  m = pH->first;. 
0450: 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 30 3b 0a   pH->first = 0;.
0460: 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70    sqlite3_free(p
0470: 48 2d 3e 68 74 29 3b 0a 20 20 70 48 2d 3e 68 74  H->ht);.  pH->ht
0480: 20 3d 20 30 3b 0a 20 20 70 48 2d 3e 68 74 73 69   = 0;.  pH->htsi
0490: 7a 65 20 3d 20 30 3b 0a 20 20 77 68 69 6c 65 28  ze = 0;.  while(
04a0: 20 65 6c 65 6d 20 29 7b 0a 20 20 20 20 48 61 73   elem ){.    Has
04b0: 68 45 6c 65 6d 20 2a 6e 65 78 74 5f 65 6c 65 6d  hElem *next_elem
04c0: 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20   = elem->next;. 
04d0: 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28     sqlite3_free(
04e0: 65 6c 65 6d 29 3b 0a 20 20 20 20 65 6c 65 6d 20  elem);.    elem 
04f0: 3d 20 6e 65 78 74 5f 65 6c 65 6d 3b 0a 20 20 7d  = next_elem;.  }
0500: 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 20 3d 20 30  .  pH->count = 0
0510: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 68  ;.}../*.** The h
0520: 61 73 68 69 6e 67 20 66 75 6e 63 74 69 6f 6e 2e  ashing function.
0530: 0a 2a 2f 0a 73 74 61 74 69 63 20 75 6e 73 69 67  .*/.static unsig
0540: 6e 65 64 20 69 6e 74 20 73 74 72 48 61 73 68 28  ned int strHash(
0550: 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a 29 7b 0a  const char *z){.
0560: 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 68    unsigned int h
0570: 20 3d 20 30 3b 0a 20 20 75 6e 73 69 67 6e 65 64   = 0;.  unsigned
0580: 20 63 68 61 72 20 63 3b 0a 20 20 77 68 69 6c 65   char c;.  while
0590: 28 20 28 63 20 3d 20 28 75 6e 73 69 67 6e 65 64  ( (c = (unsigned
05a0: 20 63 68 61 72 29 2a 7a 2b 2b 29 21 3d 30 20 29   char)*z++)!=0 )
05b0: 7b 20 20 20 20 20 2f 2a 4f 50 54 49 4d 49 5a 41  {     /*OPTIMIZA
05c0: 54 49 4f 4e 2d 49 46 2d 54 52 55 45 2a 2f 0a 20  TION-IF-TRUE*/. 
05d0: 20 20 20 2f 2a 20 4b 6e 75 74 68 20 6d 75 6c 74     /* Knuth mult
05e0: 69 70 6c 69 63 61 74 69 76 65 20 68 61 73 68 69  iplicative hashi
05f0: 6e 67 2e 20 20 28 53 6f 72 74 69 6e 67 20 26 20  ng.  (Sorting & 
0600: 53 65 61 72 63 68 69 6e 67 2c 20 70 2e 20 35 31  Searching, p. 51
0610: 30 29 2e 0a 20 20 20 20 2a 2a 20 30 78 39 65 33  0)..    ** 0x9e3
0620: 37 37 39 62 31 20 69 73 20 32 36 35 34 34 33 35  779b1 is 2654435
0630: 37 36 31 20 77 68 69 63 68 20 69 73 20 74 68 65  761 which is the
0640: 20 63 6c 6f 73 65 73 74 20 70 72 69 6d 65 20 6e   closest prime n
0650: 75 6d 62 65 72 20 74 6f 0a 20 20 20 20 2a 2a 20  umber to.    ** 
0660: 28 32 2a 2a 33 32 29 2a 67 6f 6c 64 65 6e 5f 72  (2**32)*golden_r
0670: 61 74 69 6f 2c 20 77 68 65 72 65 20 67 6f 6c 64  atio, where gold
0680: 65 6e 5f 72 61 74 69 6f 20 3d 20 28 73 71 72 74  en_ratio = (sqrt
0690: 28 35 29 20 2d 20 31 29 2f 32 2e 20 2a 2f 0a 20  (5) - 1)/2. */. 
06a0: 20 20 20 68 20 2b 3d 20 73 71 6c 69 74 65 33 55     h += sqlite3U
06b0: 70 70 65 72 54 6f 4c 6f 77 65 72 5b 63 5d 3b 0a  pperToLower[c];.
06c0: 20 20 20 20 68 20 2a 3d 20 30 78 39 65 33 37 37      h *= 0x9e377
06d0: 39 62 31 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72  9b1;.  }.  retur
06e0: 6e 20 68 3b 0a 7d 0a 0a 0a 2f 2a 20 4c 69 6e 6b  n h;.}.../* Link
06f0: 20 70 4e 65 77 20 65 6c 65 6d 65 6e 74 20 69 6e   pNew element in
0700: 74 6f 20 74 68 65 20 68 61 73 68 20 74 61 62 6c  to the hash tabl
0710: 65 20 70 48 2e 20 20 49 66 20 70 45 6e 74 72 79  e pH.  If pEntry
0720: 21 3d 30 20 74 68 65 6e 20 61 6c 73 6f 0a 2a 2a  !=0 then also.**
0730: 20 69 6e 73 65 72 74 20 70 4e 65 77 20 69 6e 74   insert pNew int
0740: 6f 20 74 68 65 20 70 45 6e 74 72 79 20 68 61 73  o the pEntry has
0750: 68 20 62 75 63 6b 65 74 2e 0a 2a 2f 0a 73 74 61  h bucket..*/.sta
0760: 74 69 63 20 76 6f 69 64 20 69 6e 73 65 72 74 45  tic void insertE
0770: 6c 65 6d 65 6e 74 28 0a 20 20 48 61 73 68 20 2a  lement(.  Hash *
0780: 70 48 2c 20 20 20 20 20 20 20 20 20 20 20 20 20  pH,             
0790: 20 2f 2a 20 54 68 65 20 63 6f 6d 70 6c 65 74 65   /* The complete
07a0: 20 68 61 73 68 20 74 61 62 6c 65 20 2a 2f 0a 20   hash table */. 
07b0: 20 73 74 72 75 63 74 20 5f 68 74 20 2a 70 45 6e   struct _ht *pEn
07c0: 74 72 79 2c 20 20 20 20 2f 2a 20 54 68 65 20 65  try,    /* The e
07d0: 6e 74 72 79 20 69 6e 74 6f 20 77 68 69 63 68 20  ntry into which 
07e0: 70 4e 65 77 20 69 73 20 69 6e 73 65 72 74 65 64  pNew is inserted
07f0: 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a   */.  HashElem *
0800: 70 4e 65 77 20 20 20 20 20 20 20 20 20 2f 2a 20  pNew         /* 
0810: 54 68 65 20 65 6c 65 6d 65 6e 74 20 74 6f 20 62  The element to b
0820: 65 20 69 6e 73 65 72 74 65 64 20 2a 2f 0a 29 7b  e inserted */.){
0830: 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 70 48 65  .  HashElem *pHe
0840: 61 64 3b 20 20 20 20 20 20 20 2f 2a 20 46 69 72  ad;       /* Fir
0850: 73 74 20 65 6c 65 6d 65 6e 74 20 61 6c 72 65 61  st element alrea
0860: 64 79 20 69 6e 20 70 45 6e 74 72 79 20 2a 2f 0a  dy in pEntry */.
0870: 20 20 69 66 28 20 70 45 6e 74 72 79 20 29 7b 0a    if( pEntry ){.
0880: 20 20 20 20 70 48 65 61 64 20 3d 20 70 45 6e 74      pHead = pEnt
0890: 72 79 2d 3e 63 6f 75 6e 74 20 3f 20 70 45 6e 74  ry->count ? pEnt
08a0: 72 79 2d 3e 63 68 61 69 6e 20 3a 20 30 3b 0a 20  ry->chain : 0;. 
08b0: 20 20 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74     pEntry->count
08c0: 2b 2b 3b 0a 20 20 20 20 70 45 6e 74 72 79 2d 3e  ++;.    pEntry->
08d0: 63 68 61 69 6e 20 3d 20 70 4e 65 77 3b 0a 20 20  chain = pNew;.  
08e0: 7d 65 6c 73 65 7b 0a 20 20 20 20 70 48 65 61 64  }else{.    pHead
08f0: 20 3d 20 30 3b 0a 20 20 7d 0a 20 20 69 66 28 20   = 0;.  }.  if( 
0900: 70 48 65 61 64 20 29 7b 0a 20 20 20 20 70 4e 65  pHead ){.    pNe
0910: 77 2d 3e 6e 65 78 74 20 3d 20 70 48 65 61 64 3b  w->next = pHead;
0920: 0a 20 20 20 20 70 4e 65 77 2d 3e 70 72 65 76 20  .    pNew->prev 
0930: 3d 20 70 48 65 61 64 2d 3e 70 72 65 76 3b 0a 20  = pHead->prev;. 
0940: 20 20 20 69 66 28 20 70 48 65 61 64 2d 3e 70 72     if( pHead->pr
0950: 65 76 20 29 7b 20 70 48 65 61 64 2d 3e 70 72 65  ev ){ pHead->pre
0960: 76 2d 3e 6e 65 78 74 20 3d 20 70 4e 65 77 3b 20  v->next = pNew; 
0970: 7d 0a 20 20 20 20 65 6c 73 65 20 20 20 20 20 20  }.    else      
0980: 20 20 20 20 20 20 20 7b 20 70 48 2d 3e 66 69 72         { pH->fir
0990: 73 74 20 3d 20 70 4e 65 77 3b 20 7d 0a 20 20 20  st = pNew; }.   
09a0: 20 70 48 65 61 64 2d 3e 70 72 65 76 20 3d 20 70   pHead->prev = p
09b0: 4e 65 77 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20  New;.  }else{.  
09c0: 20 20 70 4e 65 77 2d 3e 6e 65 78 74 20 3d 20 70    pNew->next = p
09d0: 48 2d 3e 66 69 72 73 74 3b 0a 20 20 20 20 69 66  H->first;.    if
09e0: 28 20 70 48 2d 3e 66 69 72 73 74 20 29 7b 20 70  ( pH->first ){ p
09f0: 48 2d 3e 66 69 72 73 74 2d 3e 70 72 65 76 20 3d  H->first->prev =
0a00: 20 70 4e 65 77 3b 20 7d 0a 20 20 20 20 70 4e 65   pNew; }.    pNe
0a10: 77 2d 3e 70 72 65 76 20 3d 20 30 3b 0a 20 20 20  w->prev = 0;.   
0a20: 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 70 4e 65   pH->first = pNe
0a30: 77 3b 0a 20 20 7d 0a 7d 0a 0a 0a 2f 2a 20 52 65  w;.  }.}.../* Re
0a40: 73 69 7a 65 20 74 68 65 20 68 61 73 68 20 74 61  size the hash ta
0a50: 62 6c 65 20 73 6f 20 74 68 61 74 20 69 74 20 63  ble so that it c
0a60: 61 6e 74 61 69 6e 73 20 22 6e 65 77 5f 73 69 7a  antains "new_siz
0a70: 65 22 20 62 75 63 6b 65 74 73 2e 0a 2a 2a 0a 2a  e" buckets..**.*
0a80: 2a 20 54 68 65 20 68 61 73 68 20 74 61 62 6c 65  * The hash table
0a90: 20 6d 69 67 68 74 20 66 61 69 6c 20 74 6f 20 72   might fail to r
0aa0: 65 73 69 7a 65 20 69 66 20 73 71 6c 69 74 65 33  esize if sqlite3
0ab0: 5f 6d 61 6c 6c 6f 63 28 29 20 66 61 69 6c 73 20  _malloc() fails 
0ac0: 6f 72 0a 2a 2a 20 69 66 20 74 68 65 20 6e 65 77  or.** if the new
0ad0: 20 73 69 7a 65 20 69 73 20 74 68 65 20 73 61 6d   size is the sam
0ae0: 65 20 61 73 20 74 68 65 20 70 72 69 6f 72 20 73  e as the prior s
0af0: 69 7a 65 2e 0a 2a 2a 20 52 65 74 75 72 6e 20 54  ize..** Return T
0b00: 52 55 45 20 69 66 20 74 68 65 20 72 65 73 69 7a  RUE if the resiz
0b10: 65 20 6f 63 63 75 72 73 20 61 6e 64 20 66 61 6c  e occurs and fal
0b20: 73 65 20 69 66 20 6e 6f 74 2e 0a 2a 2f 0a 73 74  se if not..*/.st
0b30: 61 74 69 63 20 69 6e 74 20 72 65 68 61 73 68 28  atic int rehash(
0b40: 48 61 73 68 20 2a 70 48 2c 20 75 6e 73 69 67 6e  Hash *pH, unsign
0b50: 65 64 20 69 6e 74 20 6e 65 77 5f 73 69 7a 65 29  ed int new_size)
0b60: 7b 0a 20 20 73 74 72 75 63 74 20 5f 68 74 20 2a  {.  struct _ht *
0b70: 6e 65 77 5f 68 74 3b 20 20 20 20 20 20 20 20 20  new_ht;         
0b80: 20 20 20 2f 2a 20 54 68 65 20 6e 65 77 20 68 61     /* The new ha
0b90: 73 68 20 74 61 62 6c 65 20 2a 2f 0a 20 20 48 61  sh table */.  Ha
0ba0: 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 2c 20 2a 6e  shElem *elem, *n
0bb0: 65 78 74 5f 65 6c 65 6d 3b 20 20 20 20 2f 2a 20  ext_elem;    /* 
0bc0: 46 6f 72 20 6c 6f 6f 70 69 6e 67 20 6f 76 65 72  For looping over
0bd0: 20 65 78 69 73 74 69 6e 67 20 65 6c 65 6d 65 6e   existing elemen
0be0: 74 73 20 2a 2f 0a 0a 23 69 66 20 53 51 4c 49 54  ts */..#if SQLIT
0bf0: 45 5f 4d 41 4c 4c 4f 43 5f 53 4f 46 54 5f 4c 49  E_MALLOC_SOFT_LI
0c00: 4d 49 54 3e 30 0a 20 20 69 66 28 20 6e 65 77 5f  MIT>0.  if( new_
0c10: 73 69 7a 65 2a 73 69 7a 65 6f 66 28 73 74 72 75  size*sizeof(stru
0c20: 63 74 20 5f 68 74 29 3e 53 51 4c 49 54 45 5f 4d  ct _ht)>SQLITE_M
0c30: 41 4c 4c 4f 43 5f 53 4f 46 54 5f 4c 49 4d 49 54  ALLOC_SOFT_LIMIT
0c40: 20 29 7b 0a 20 20 20 20 6e 65 77 5f 73 69 7a 65   ){.    new_size
0c50: 20 3d 20 53 51 4c 49 54 45 5f 4d 41 4c 4c 4f 43   = SQLITE_MALLOC
0c60: 5f 53 4f 46 54 5f 4c 49 4d 49 54 2f 73 69 7a 65  _SOFT_LIMIT/size
0c70: 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29 3b 0a  of(struct _ht);.
0c80: 20 20 7d 0a 20 20 69 66 28 20 6e 65 77 5f 73 69    }.  if( new_si
0c90: 7a 65 3d 3d 70 48 2d 3e 68 74 73 69 7a 65 20 29  ze==pH->htsize )
0ca0: 20 72 65 74 75 72 6e 20 30 3b 0a 23 65 6e 64 69   return 0;.#endi
0cb0: 66 0a 0a 20 20 2f 2a 20 54 68 65 20 69 6e 61 62  f..  /* The inab
0cc0: 69 6c 69 74 79 20 74 6f 20 61 6c 6c 6f 63 61 74  ility to allocat
0cd0: 65 73 20 73 70 61 63 65 20 66 6f 72 20 61 20 6c  es space for a l
0ce0: 61 72 67 65 72 20 68 61 73 68 20 74 61 62 6c 65  arger hash table
0cf0: 20 69 73 0a 20 20 2a 2a 20 61 20 70 65 72 66 6f   is.  ** a perfo
0d00: 72 6d 61 6e 63 65 20 68 69 74 20 62 75 74 20 69  rmance hit but i
0d10: 74 20 69 73 20 6e 6f 74 20 61 20 66 61 74 61 6c  t is not a fatal
0d20: 20 65 72 72 6f 72 2e 20 20 53 6f 20 6d 61 72 6b   error.  So mark
0d30: 20 74 68 65 0a 20 20 2a 2a 20 61 6c 6c 6f 63 61   the.  ** alloca
0d40: 74 69 6f 6e 20 61 73 20 61 20 62 65 6e 69 67 6e  tion as a benign
0d50: 2e 20 55 73 65 20 73 71 6c 69 74 65 33 4d 61 6c  . Use sqlite3Mal
0d60: 6c 6f 63 28 29 2f 6d 65 6d 73 65 74 28 30 29 20  loc()/memset(0) 
0d70: 69 6e 73 74 65 61 64 20 6f 66 20 0a 20 20 2a 2a  instead of .  **
0d80: 20 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 5a 65   sqlite3MallocZe
0d90: 72 6f 28 29 20 74 6f 20 6d 61 6b 65 20 74 68 65  ro() to make the
0da0: 20 61 6c 6c 6f 63 61 74 69 6f 6e 2c 20 61 73 20   allocation, as 
0db0: 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 5a 65 72  sqlite3MallocZer
0dc0: 6f 28 29 0a 20 20 2a 2a 20 6f 6e 6c 79 20 7a 65  o().  ** only ze
0dd0: 72 6f 65 73 20 74 68 65 20 72 65 71 75 65 73 74  roes the request
0de0: 65 64 20 6e 75 6d 62 65 72 20 6f 66 20 62 79 74  ed number of byt
0df0: 65 73 20 77 68 65 72 65 61 73 20 74 68 69 73 20  es whereas this 
0e00: 6d 6f 64 75 6c 65 20 77 69 6c 6c 0a 20 20 2a 2a  module will.  **
0e10: 20 75 73 65 20 74 68 65 20 61 63 74 75 61 6c 20   use the actual 
0e20: 61 6d 6f 75 6e 74 20 6f 66 20 73 70 61 63 65 20  amount of space 
0e30: 61 6c 6c 6f 63 61 74 65 64 20 66 6f 72 20 74 68  allocated for th
0e40: 65 20 68 61 73 68 20 74 61 62 6c 65 20 28 77 68  e hash table (wh
0e50: 69 63 68 0a 20 20 2a 2a 20 6d 61 79 20 62 65 20  ich.  ** may be 
0e60: 6c 61 72 67 65 72 20 74 68 61 6e 20 74 68 65 20  larger than the 
0e70: 72 65 71 75 65 73 74 65 64 20 61 6d 6f 75 6e 74  requested amount
0e80: 29 2e 0a 20 20 2a 2f 0a 20 20 73 71 6c 69 74 65  )..  */.  sqlite
0e90: 33 42 65 67 69 6e 42 65 6e 69 67 6e 4d 61 6c 6c  3BeginBenignMall
0ea0: 6f 63 28 29 3b 0a 20 20 6e 65 77 5f 68 74 20 3d  oc();.  new_ht =
0eb0: 20 28 73 74 72 75 63 74 20 5f 68 74 20 2a 29 73   (struct _ht *)s
0ec0: 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 28 20 6e 65  qlite3Malloc( ne
0ed0: 77 5f 73 69 7a 65 2a 73 69 7a 65 6f 66 28 73 74  w_size*sizeof(st
0ee0: 72 75 63 74 20 5f 68 74 29 20 29 3b 0a 20 20 73  ruct _ht) );.  s
0ef0: 71 6c 69 74 65 33 45 6e 64 42 65 6e 69 67 6e 4d  qlite3EndBenignM
0f00: 61 6c 6c 6f 63 28 29 3b 0a 0a 20 20 69 66 28 20  alloc();..  if( 
0f10: 6e 65 77 5f 68 74 3d 3d 30 20 29 20 72 65 74 75  new_ht==0 ) retu
0f20: 72 6e 20 30 3b 0a 20 20 73 71 6c 69 74 65 33 5f  rn 0;.  sqlite3_
0f30: 66 72 65 65 28 70 48 2d 3e 68 74 29 3b 0a 20 20  free(pH->ht);.  
0f40: 70 48 2d 3e 68 74 20 3d 20 6e 65 77 5f 68 74 3b  pH->ht = new_ht;
0f50: 0a 20 20 70 48 2d 3e 68 74 73 69 7a 65 20 3d 20  .  pH->htsize = 
0f60: 6e 65 77 5f 73 69 7a 65 20 3d 20 73 71 6c 69 74  new_size = sqlit
0f70: 65 33 4d 61 6c 6c 6f 63 53 69 7a 65 28 6e 65 77  e3MallocSize(new
0f80: 5f 68 74 29 2f 73 69 7a 65 6f 66 28 73 74 72 75  _ht)/sizeof(stru
0f90: 63 74 20 5f 68 74 29 3b 0a 20 20 6d 65 6d 73 65  ct _ht);.  memse
0fa0: 74 28 6e 65 77 5f 68 74 2c 20 30 2c 20 6e 65 77  t(new_ht, 0, new
0fb0: 5f 73 69 7a 65 2a 73 69 7a 65 6f 66 28 73 74 72  _size*sizeof(str
0fc0: 75 63 74 20 5f 68 74 29 29 3b 0a 20 20 66 6f 72  uct _ht));.  for
0fd0: 28 65 6c 65 6d 3d 70 48 2d 3e 66 69 72 73 74 2c  (elem=pH->first,
0fe0: 20 70 48 2d 3e 66 69 72 73 74 3d 30 3b 20 65 6c   pH->first=0; el
0ff0: 65 6d 3b 20 65 6c 65 6d 20 3d 20 6e 65 78 74 5f  em; elem = next_
1000: 65 6c 65 6d 29 7b 0a 20 20 20 20 75 6e 73 69 67  elem){.    unsig
1010: 6e 65 64 20 69 6e 74 20 68 20 3d 20 73 74 72 48  ned int h = strH
1020: 61 73 68 28 65 6c 65 6d 2d 3e 70 4b 65 79 29 20  ash(elem->pKey) 
1030: 25 20 6e 65 77 5f 73 69 7a 65 3b 0a 20 20 20 20  % new_size;.    
1040: 6e 65 78 74 5f 65 6c 65 6d 20 3d 20 65 6c 65 6d  next_elem = elem
1050: 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 69 6e 73 65  ->next;.    inse
1060: 72 74 45 6c 65 6d 65 6e 74 28 70 48 2c 20 26 6e  rtElement(pH, &n
1070: 65 77 5f 68 74 5b 68 5d 2c 20 65 6c 65 6d 29 3b  ew_ht[h], elem);
1080: 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 31 3b  .  }.  return 1;
1090: 0a 7d 0a 0a 2f 2a 20 54 68 69 73 20 66 75 6e 63  .}../* This func
10a0: 74 69 6f 6e 20 28 66 6f 72 20 69 6e 74 65 72 6e  tion (for intern
10b0: 61 6c 20 75 73 65 20 6f 6e 6c 79 29 20 6c 6f 63  al use only) loc
10c0: 61 74 65 73 20 61 6e 20 65 6c 65 6d 65 6e 74 20  ates an element 
10d0: 69 6e 20 61 6e 0a 2a 2a 20 68 61 73 68 20 74 61  in an.** hash ta
10e0: 62 6c 65 20 74 68 61 74 20 6d 61 74 63 68 65 73  ble that matches
10f0: 20 74 68 65 20 67 69 76 65 6e 20 6b 65 79 2e 20   the given key. 
1100: 20 49 66 20 6e 6f 20 65 6c 65 6d 65 6e 74 20 69   If no element i
1110: 73 20 66 6f 75 6e 64 2c 0a 2a 2a 20 61 20 70 6f  s found,.** a po
1120: 69 6e 74 65 72 20 74 6f 20 61 20 73 74 61 74 69  inter to a stati
1130: 63 20 6e 75 6c 6c 20 65 6c 65 6d 65 6e 74 20 77  c null element w
1140: 69 74 68 20 48 61 73 68 45 6c 65 6d 2e 64 61 74  ith HashElem.dat
1150: 61 3d 3d 30 20 69 73 20 72 65 74 75 72 6e 65 64  a==0 is returned
1160: 2e 0a 2a 2a 20 49 66 20 70 48 20 69 73 20 6e 6f  ..** If pH is no
1170: 74 20 4e 55 4c 4c 2c 20 74 68 65 6e 20 74 68 65  t NULL, then the
1180: 20 68 61 73 68 20 66 6f 72 20 74 68 69 73 20 6b   hash for this k
1190: 65 79 20 69 73 20 77 72 69 74 74 65 6e 20 74 6f  ey is written to
11a0: 20 2a 70 48 2e 0a 2a 2f 0a 73 74 61 74 69 63 20   *pH..*/.static 
11b0: 48 61 73 68 45 6c 65 6d 20 2a 66 69 6e 64 45 6c  HashElem *findEl
11c0: 65 6d 65 6e 74 57 69 74 68 48 61 73 68 28 0a 20  ementWithHash(. 
11d0: 20 63 6f 6e 73 74 20 48 61 73 68 20 2a 70 48 2c   const Hash *pH,
11e0: 20 20 20 20 20 2f 2a 20 54 68 65 20 70 48 20 74       /* The pH t
11f0: 6f 20 62 65 20 73 65 61 72 63 68 65 64 20 2a 2f  o be searched */
1200: 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70  .  const char *p
1210: 4b 65 79 2c 20 20 20 2f 2a 20 54 68 65 20 6b 65  Key,   /* The ke
1220: 79 20 77 65 20 61 72 65 20 73 65 61 72 63 68 69  y we are searchi
1230: 6e 67 20 66 6f 72 20 2a 2f 0a 20 20 75 6e 73 69  ng for */.  unsi
1240: 67 6e 65 64 20 69 6e 74 20 2a 70 48 61 73 68 20  gned int *pHash 
1250: 2f 2a 20 57 72 69 74 65 20 74 68 65 20 68 61 73  /* Write the has
1260: 68 20 76 61 6c 75 65 20 68 65 72 65 20 2a 2f 0a  h value here */.
1270: 29 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65  ){.  HashElem *e
1280: 6c 65 6d 3b 20 20 20 20 20 20 20 20 20 20 20 20  lem;            
1290: 20 20 20 20 2f 2a 20 55 73 65 64 20 74 6f 20 6c      /* Used to l
12a0: 6f 6f 70 20 74 68 72 75 20 74 68 65 20 65 6c 65  oop thru the ele
12b0: 6d 65 6e 74 20 6c 69 73 74 20 2a 2f 0a 20 20 69  ment list */.  i
12c0: 6e 74 20 63 6f 75 6e 74 3b 20 20 20 20 20 20 20  nt count;       
12d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a                /*
12e0: 20 4e 75 6d 62 65 72 20 6f 66 20 65 6c 65 6d 65   Number of eleme
12f0: 6e 74 73 20 6c 65 66 74 20 74 6f 20 74 65 73 74  nts left to test
1300: 20 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64 20 69   */.  unsigned i
1310: 6e 74 20 68 3b 20 20 20 20 20 20 20 20 20 20 20  nt h;           
1320: 20 20 20 20 20 2f 2a 20 54 68 65 20 63 6f 6d 70       /* The comp
1330: 75 74 65 64 20 68 61 73 68 20 2a 2f 0a 20 20 73  uted hash */.  s
1340: 74 61 74 69 63 20 48 61 73 68 45 6c 65 6d 20 6e  tatic HashElem n
1350: 75 6c 6c 45 6c 65 6d 65 6e 74 20 3d 20 7b 20 30  ullElement = { 0
1360: 2c 20 30 2c 20 30 2c 20 30 20 7d 3b 0a 0a 20 20  , 0, 0, 0 };..  
1370: 69 66 28 20 70 48 2d 3e 68 74 20 29 7b 20 20 20  if( pH->ht ){   
1380: 2f 2a 4f 50 54 49 4d 49 5a 41 54 49 4f 4e 2d 49  /*OPTIMIZATION-I
1390: 46 2d 54 52 55 45 2a 2f 0a 20 20 20 20 73 74 72  F-TRUE*/.    str
13a0: 75 63 74 20 5f 68 74 20 2a 70 45 6e 74 72 79 3b  uct _ht *pEntry;
13b0: 0a 20 20 20 20 68 20 3d 20 73 74 72 48 61 73 68  .    h = strHash
13c0: 28 70 4b 65 79 29 20 25 20 70 48 2d 3e 68 74 73  (pKey) % pH->hts
13d0: 69 7a 65 3b 0a 20 20 20 20 70 45 6e 74 72 79 20  ize;.    pEntry 
13e0: 3d 20 26 70 48 2d 3e 68 74 5b 68 5d 3b 0a 20 20  = &pH->ht[h];.  
13f0: 20 20 65 6c 65 6d 20 3d 20 70 45 6e 74 72 79 2d    elem = pEntry-
1400: 3e 63 68 61 69 6e 3b 0a 20 20 20 20 63 6f 75 6e  >chain;.    coun
1410: 74 20 3d 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e  t = pEntry->coun
1420: 74 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20  t;.  }else{.    
1430: 68 20 3d 20 30 3b 0a 20 20 20 20 65 6c 65 6d 20  h = 0;.    elem 
1440: 3d 20 70 48 2d 3e 66 69 72 73 74 3b 0a 20 20 20  = pH->first;.   
1450: 20 63 6f 75 6e 74 20 3d 20 70 48 2d 3e 63 6f 75   count = pH->cou
1460: 6e 74 3b 0a 20 20 7d 0a 20 20 69 66 28 20 70 48  nt;.  }.  if( pH
1470: 61 73 68 20 29 20 2a 70 48 61 73 68 20 3d 20 68  ash ) *pHash = h
1480: 3b 0a 20 20 77 68 69 6c 65 28 20 63 6f 75 6e 74  ;.  while( count
1490: 2d 2d 20 29 7b 0a 20 20 20 20 61 73 73 65 72 74  -- ){.    assert
14a0: 28 20 65 6c 65 6d 21 3d 30 20 29 3b 0a 20 20 20  ( elem!=0 );.   
14b0: 20 69 66 28 20 73 71 6c 69 74 65 33 53 74 72 49   if( sqlite3StrI
14c0: 43 6d 70 28 65 6c 65 6d 2d 3e 70 4b 65 79 2c 70  Cmp(elem->pKey,p
14d0: 4b 65 79 29 3d 3d 30 20 29 7b 20 0a 20 20 20 20  Key)==0 ){ .    
14e0: 20 20 72 65 74 75 72 6e 20 65 6c 65 6d 3b 0a 20    return elem;. 
14f0: 20 20 20 7d 0a 20 20 20 20 65 6c 65 6d 20 3d 20     }.    elem = 
1500: 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 7d 0a  elem->next;.  }.
1510: 20 20 72 65 74 75 72 6e 20 26 6e 75 6c 6c 45 6c    return &nullEl
1520: 65 6d 65 6e 74 3b 0a 7d 0a 0a 2f 2a 20 52 65 6d  ement;.}../* Rem
1530: 6f 76 65 20 61 20 73 69 6e 67 6c 65 20 65 6e 74  ove a single ent
1540: 72 79 20 66 72 6f 6d 20 74 68 65 20 68 61 73 68  ry from the hash
1550: 20 74 61 62 6c 65 20 67 69 76 65 6e 20 61 20 70   table given a p
1560: 6f 69 6e 74 65 72 20 74 6f 20 74 68 61 74 0a 2a  ointer to that.*
1570: 2a 20 65 6c 65 6d 65 6e 74 20 61 6e 64 20 61 20  * element and a 
1580: 68 61 73 68 20 6f 6e 20 74 68 65 20 65 6c 65 6d  hash on the elem
1590: 65 6e 74 27 73 20 6b 65 79 2e 0a 2a 2f 0a 73 74  ent's key..*/.st
15a0: 61 74 69 63 20 76 6f 69 64 20 72 65 6d 6f 76 65  atic void remove
15b0: 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61 73 68  ElementGivenHash
15c0: 28 0a 20 20 48 61 73 68 20 2a 70 48 2c 20 20 20  (.  Hash *pH,   
15d0: 20 20 20 20 20 20 2f 2a 20 54 68 65 20 70 48 20        /* The pH 
15e0: 63 6f 6e 74 61 69 6e 69 6e 67 20 22 65 6c 65 6d  containing "elem
15f0: 22 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 2a  " */.  HashElem*
1600: 20 65 6c 65 6d 2c 20 20 20 2f 2a 20 54 68 65 20   elem,   /* The 
1610: 65 6c 65 6d 65 6e 74 20 74 6f 20 62 65 20 72 65  element to be re
1620: 6d 6f 76 65 64 20 66 72 6f 6d 20 74 68 65 20 70  moved from the p
1630: 48 20 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64 20  H */.  unsigned 
1640: 69 6e 74 20 68 20 20 20 20 2f 2a 20 48 61 73 68  int h    /* Hash
1650: 20 76 61 6c 75 65 20 66 6f 72 20 74 68 65 20 65   value for the e
1660: 6c 65 6d 65 6e 74 20 2a 2f 0a 29 7b 0a 20 20 73  lement */.){.  s
1670: 74 72 75 63 74 20 5f 68 74 20 2a 70 45 6e 74 72  truct _ht *pEntr
1680: 79 3b 0a 20 20 69 66 28 20 65 6c 65 6d 2d 3e 70  y;.  if( elem->p
1690: 72 65 76 20 29 7b 0a 20 20 20 20 65 6c 65 6d 2d  rev ){.    elem-
16a0: 3e 70 72 65 76 2d 3e 6e 65 78 74 20 3d 20 65 6c  >prev->next = el
16b0: 65 6d 2d 3e 6e 65 78 74 3b 20 0a 20 20 7d 65 6c  em->next; .  }el
16c0: 73 65 7b 0a 20 20 20 20 70 48 2d 3e 66 69 72 73  se{.    pH->firs
16d0: 74 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a  t = elem->next;.
16e0: 20 20 7d 0a 20 20 69 66 28 20 65 6c 65 6d 2d 3e    }.  if( elem->
16f0: 6e 65 78 74 20 29 7b 0a 20 20 20 20 65 6c 65 6d  next ){.    elem
1700: 2d 3e 6e 65 78 74 2d 3e 70 72 65 76 20 3d 20 65  ->next->prev = e
1710: 6c 65 6d 2d 3e 70 72 65 76 3b 0a 20 20 7d 0a 20  lem->prev;.  }. 
1720: 20 69 66 28 20 70 48 2d 3e 68 74 20 29 7b 0a 20   if( pH->ht ){. 
1730: 20 20 20 70 45 6e 74 72 79 20 3d 20 26 70 48 2d     pEntry = &pH-
1740: 3e 68 74 5b 68 5d 3b 0a 20 20 20 20 69 66 28 20  >ht[h];.    if( 
1750: 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3d 3d 65  pEntry->chain==e
1760: 6c 65 6d 20 29 7b 0a 20 20 20 20 20 20 70 45 6e  lem ){.      pEn
1770: 74 72 79 2d 3e 63 68 61 69 6e 20 3d 20 65 6c 65  try->chain = ele
1780: 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 7d 0a 20  m->next;.    }. 
1790: 20 20 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74     pEntry->count
17a0: 2d 2d 3b 0a 20 20 20 20 61 73 73 65 72 74 28 20  --;.    assert( 
17b0: 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 3e 3d 30  pEntry->count>=0
17c0: 20 29 3b 0a 20 20 7d 0a 20 20 73 71 6c 69 74 65   );.  }.  sqlite
17d0: 33 5f 66 72 65 65 28 20 65 6c 65 6d 20 29 3b 0a  3_free( elem );.
17e0: 20 20 70 48 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a 20    pH->count--;. 
17f0: 20 69 66 28 20 70 48 2d 3e 63 6f 75 6e 74 3d 3d   if( pH->count==
1800: 30 20 29 7b 0a 20 20 20 20 61 73 73 65 72 74 28  0 ){.    assert(
1810: 20 70 48 2d 3e 66 69 72 73 74 3d 3d 30 20 29 3b   pH->first==0 );
1820: 0a 20 20 20 20 61 73 73 65 72 74 28 20 70 48 2d  .    assert( pH-
1830: 3e 63 6f 75 6e 74 3d 3d 30 20 29 3b 0a 20 20 20  >count==0 );.   
1840: 20 73 71 6c 69 74 65 33 48 61 73 68 43 6c 65 61   sqlite3HashClea
1850: 72 28 70 48 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a  r(pH);.  }.}../*
1860: 20 41 74 74 65 6d 70 74 20 74 6f 20 6c 6f 63 61   Attempt to loca
1870: 74 65 20 61 6e 20 65 6c 65 6d 65 6e 74 20 6f 66  te an element of
1880: 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20   the hash table 
1890: 70 48 20 77 69 74 68 20 61 20 6b 65 79 0a 2a 2a  pH with a key.**
18a0: 20 74 68 61 74 20 6d 61 74 63 68 65 73 20 70 4b   that matches pK
18b0: 65 79 2e 20 20 52 65 74 75 72 6e 20 74 68 65 20  ey.  Return the 
18c0: 64 61 74 61 20 66 6f 72 20 74 68 69 73 20 65 6c  data for this el
18d0: 65 6d 65 6e 74 20 69 66 20 69 74 20 69 73 0a 2a  ement if it is.*
18e0: 2a 20 66 6f 75 6e 64 2c 20 6f 72 20 4e 55 4c 4c  * found, or NULL
18f0: 20 69 66 20 74 68 65 72 65 20 69 73 20 6e 6f 20   if there is no 
1900: 6d 61 74 63 68 2e 0a 2a 2f 0a 76 6f 69 64 20 2a  match..*/.void *
1910: 73 71 6c 69 74 65 33 48 61 73 68 46 69 6e 64 28  sqlite3HashFind(
1920: 63 6f 6e 73 74 20 48 61 73 68 20 2a 70 48 2c 20  const Hash *pH, 
1930: 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 4b 65 79  const char *pKey
1940: 29 7b 0a 20 20 61 73 73 65 72 74 28 20 70 48 21  ){.  assert( pH!
1950: 3d 30 20 29 3b 0a 20 20 61 73 73 65 72 74 28 20  =0 );.  assert( 
1960: 70 4b 65 79 21 3d 30 20 29 3b 0a 20 20 72 65 74  pKey!=0 );.  ret
1970: 75 72 6e 20 66 69 6e 64 45 6c 65 6d 65 6e 74 57  urn findElementW
1980: 69 74 68 48 61 73 68 28 70 48 2c 20 70 4b 65 79  ithHash(pH, pKey
1990: 2c 20 30 29 2d 3e 64 61 74 61 3b 0a 7d 0a 0a 2f  , 0)->data;.}../
19a0: 2a 20 49 6e 73 65 72 74 20 61 6e 20 65 6c 65 6d  * Insert an elem
19b0: 65 6e 74 20 69 6e 74 6f 20 74 68 65 20 68 61 73  ent into the has
19c0: 68 20 74 61 62 6c 65 20 70 48 2e 20 20 54 68 65  h table pH.  The
19d0: 20 6b 65 79 20 69 73 20 70 4b 65 79 0a 2a 2a 20   key is pKey.** 
19e0: 61 6e 64 20 74 68 65 20 64 61 74 61 20 69 73 20  and the data is 
19f0: 22 64 61 74 61 22 2e 0a 2a 2a 0a 2a 2a 20 49 66  "data"..**.** If
1a00: 20 6e 6f 20 65 6c 65 6d 65 6e 74 20 65 78 69 73   no element exis
1a10: 74 73 20 77 69 74 68 20 61 20 6d 61 74 63 68 69  ts with a matchi
1a20: 6e 67 20 6b 65 79 2c 20 74 68 65 6e 20 61 20 6e  ng key, then a n
1a30: 65 77 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 69 73  ew.** element is
1a40: 20 63 72 65 61 74 65 64 20 61 6e 64 20 4e 55 4c   created and NUL
1a50: 4c 20 69 73 20 72 65 74 75 72 6e 65 64 2e 0a 2a  L is returned..*
1a60: 2a 0a 2a 2a 20 49 66 20 61 6e 6f 74 68 65 72 20  *.** If another 
1a70: 65 6c 65 6d 65 6e 74 20 61 6c 72 65 61 64 79 20  element already 
1a80: 65 78 69 73 74 73 20 77 69 74 68 20 74 68 65 20  exists with the 
1a90: 73 61 6d 65 20 6b 65 79 2c 20 74 68 65 6e 20 74  same key, then t
1aa0: 68 65 0a 2a 2a 20 6e 65 77 20 64 61 74 61 20 72  he.** new data r
1ab0: 65 70 6c 61 63 65 73 20 74 68 65 20 6f 6c 64 20  eplaces the old 
1ac0: 64 61 74 61 20 61 6e 64 20 74 68 65 20 6f 6c 64  data and the old
1ad0: 20 64 61 74 61 20 69 73 20 72 65 74 75 72 6e 65   data is returne
1ae0: 64 2e 0a 2a 2a 20 54 68 65 20 6b 65 79 20 69 73  d..** The key is
1af0: 20 6e 6f 74 20 63 6f 70 69 65 64 20 69 6e 20 74   not copied in t
1b00: 68 69 73 20 69 6e 73 74 61 6e 63 65 2e 20 20 49  his instance.  I
1b10: 66 20 61 20 6d 61 6c 6c 6f 63 20 66 61 69 6c 73  f a malloc fails
1b20: 2c 20 74 68 65 6e 0a 2a 2a 20 74 68 65 20 6e 65  , then.** the ne
1b30: 77 20 64 61 74 61 20 69 73 20 72 65 74 75 72 6e  w data is return
1b40: 65 64 20 61 6e 64 20 74 68 65 20 68 61 73 68 20  ed and the hash 
1b50: 74 61 62 6c 65 20 69 73 20 75 6e 63 68 61 6e 67  table is unchang
1b60: 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 65  ed..**.** If the
1b70: 20 22 64 61 74 61 22 20 70 61 72 61 6d 65 74 65   "data" paramete
1b80: 72 20 74 6f 20 74 68 69 73 20 66 75 6e 63 74 69  r to this functi
1b90: 6f 6e 20 69 73 20 4e 55 4c 4c 2c 20 74 68 65 6e  on is NULL, then
1ba0: 20 74 68 65 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20   the.** element 
1bb0: 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 74 6f  corresponding to
1bc0: 20 22 6b 65 79 22 20 69 73 20 72 65 6d 6f 76 65   "key" is remove
1bd0: 64 20 66 72 6f 6d 20 74 68 65 20 68 61 73 68 20  d from the hash 
1be0: 74 61 62 6c 65 2e 0a 2a 2f 0a 76 6f 69 64 20 2a  table..*/.void *
1bf0: 73 71 6c 69 74 65 33 48 61 73 68 49 6e 73 65 72  sqlite3HashInser
1c00: 74 28 48 61 73 68 20 2a 70 48 2c 20 63 6f 6e 73  t(Hash *pH, cons
1c10: 74 20 63 68 61 72 20 2a 70 4b 65 79 2c 20 76 6f  t char *pKey, vo
1c20: 69 64 20 2a 64 61 74 61 29 7b 0a 20 20 75 6e 73  id *data){.  uns
1c30: 69 67 6e 65 64 20 69 6e 74 20 68 3b 20 20 20 20  igned int h;    
1c40: 20 20 20 2f 2a 20 74 68 65 20 68 61 73 68 20 6f     /* the hash o
1c50: 66 20 74 68 65 20 6b 65 79 20 6d 6f 64 75 6c 6f  f the key modulo
1c60: 20 68 61 73 68 20 74 61 62 6c 65 20 73 69 7a 65   hash table size
1c70: 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a   */.  HashElem *
1c80: 65 6c 65 6d 3b 20 20 20 20 20 20 20 2f 2a 20 55  elem;       /* U
1c90: 73 65 64 20 74 6f 20 6c 6f 6f 70 20 74 68 72 75  sed to loop thru
1ca0: 20 74 68 65 20 65 6c 65 6d 65 6e 74 20 6c 69 73   the element lis
1cb0: 74 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20  t */.  HashElem 
1cc0: 2a 6e 65 77 5f 65 6c 65 6d 3b 20 20 20 2f 2a 20  *new_elem;   /* 
1cd0: 4e 65 77 20 65 6c 65 6d 65 6e 74 20 61 64 64 65  New element adde
1ce0: 64 20 74 6f 20 74 68 65 20 70 48 20 2a 2f 0a 0a  d to the pH */..
1cf0: 20 20 61 73 73 65 72 74 28 20 70 48 21 3d 30 20    assert( pH!=0 
1d00: 29 3b 0a 20 20 61 73 73 65 72 74 28 20 70 4b 65  );.  assert( pKe
1d10: 79 21 3d 30 20 29 3b 0a 20 20 65 6c 65 6d 20 3d  y!=0 );.  elem =
1d20: 20 66 69 6e 64 45 6c 65 6d 65 6e 74 57 69 74 68   findElementWith
1d30: 48 61 73 68 28 70 48 2c 70 4b 65 79 2c 26 68 29  Hash(pH,pKey,&h)
1d40: 3b 0a 20 20 69 66 28 20 65 6c 65 6d 2d 3e 64 61  ;.  if( elem->da
1d50: 74 61 20 29 7b 0a 20 20 20 20 76 6f 69 64 20 2a  ta ){.    void *
1d60: 6f 6c 64 5f 64 61 74 61 20 3d 20 65 6c 65 6d 2d  old_data = elem-
1d70: 3e 64 61 74 61 3b 0a 20 20 20 20 69 66 28 20 64  >data;.    if( d
1d80: 61 74 61 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20  ata==0 ){.      
1d90: 72 65 6d 6f 76 65 45 6c 65 6d 65 6e 74 47 69 76  removeElementGiv
1da0: 65 6e 48 61 73 68 28 70 48 2c 65 6c 65 6d 2c 68  enHash(pH,elem,h
1db0: 29 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20  );.    }else{.  
1dc0: 20 20 20 20 65 6c 65 6d 2d 3e 64 61 74 61 20 3d      elem->data =
1dd0: 20 64 61 74 61 3b 0a 20 20 20 20 20 20 65 6c 65   data;.      ele
1de0: 6d 2d 3e 70 4b 65 79 20 3d 20 70 4b 65 79 3b 0a  m->pKey = pKey;.
1df0: 20 20 20 20 7d 0a 20 20 20 20 72 65 74 75 72 6e      }.    return
1e00: 20 6f 6c 64 5f 64 61 74 61 3b 0a 20 20 7d 0a 20   old_data;.  }. 
1e10: 20 69 66 28 20 64 61 74 61 3d 3d 30 20 29 20 72   if( data==0 ) r
1e20: 65 74 75 72 6e 20 30 3b 0a 20 20 6e 65 77 5f 65  eturn 0;.  new_e
1e30: 6c 65 6d 20 3d 20 28 48 61 73 68 45 6c 65 6d 2a  lem = (HashElem*
1e40: 29 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 28 20  )sqlite3Malloc( 
1e50: 73 69 7a 65 6f 66 28 48 61 73 68 45 6c 65 6d 29  sizeof(HashElem)
1e60: 20 29 3b 0a 20 20 69 66 28 20 6e 65 77 5f 65 6c   );.  if( new_el
1e70: 65 6d 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 64  em==0 ) return d
1e80: 61 74 61 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d  ata;.  new_elem-
1e90: 3e 70 4b 65 79 20 3d 20 70 4b 65 79 3b 0a 20 20  >pKey = pKey;.  
1ea0: 6e 65 77 5f 65 6c 65 6d 2d 3e 64 61 74 61 20 3d  new_elem->data =
1eb0: 20 64 61 74 61 3b 0a 20 20 70 48 2d 3e 63 6f 75   data;.  pH->cou
1ec0: 6e 74 2b 2b 3b 0a 20 20 69 66 28 20 70 48 2d 3e  nt++;.  if( pH->
1ed0: 63 6f 75 6e 74 3e 3d 31 30 20 26 26 20 70 48 2d  count>=10 && pH-
1ee0: 3e 63 6f 75 6e 74 20 3e 20 32 2a 70 48 2d 3e 68  >count > 2*pH->h
1ef0: 74 73 69 7a 65 20 29 7b 0a 20 20 20 20 69 66 28  tsize ){.    if(
1f00: 20 72 65 68 61 73 68 28 70 48 2c 20 70 48 2d 3e   rehash(pH, pH->
1f10: 63 6f 75 6e 74 2a 32 29 20 29 7b 0a 20 20 20 20  count*2) ){.    
1f20: 20 20 61 73 73 65 72 74 28 20 70 48 2d 3e 68 74    assert( pH->ht
1f30: 73 69 7a 65 3e 30 20 29 3b 0a 20 20 20 20 20 20  size>0 );.      
1f40: 68 20 3d 20 73 74 72 48 61 73 68 28 70 4b 65 79  h = strHash(pKey
1f50: 29 20 25 20 70 48 2d 3e 68 74 73 69 7a 65 3b 0a  ) % pH->htsize;.
1f60: 20 20 20 20 7d 0a 20 20 7d 0a 20 20 69 6e 73 65      }.  }.  inse
1f70: 72 74 45 6c 65 6d 65 6e 74 28 70 48 2c 20 70 48  rtElement(pH, pH
1f80: 2d 3e 68 74 20 3f 20 26 70 48 2d 3e 68 74 5b 68  ->ht ? &pH->ht[h
1f90: 5d 20 3a 20 30 2c 20 6e 65 77 5f 65 6c 65 6d 29  ] : 0, new_elem)
1fa0: 3b 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a  ;.  return 0;.}.