/ Hex Artifact Content
Login

Artifact d139319967164f139c8d1bb8a11b14db9c4ba3cd:


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 2c 20 69  const char *z, i
0560: 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 75 6e 73 69  nt nKey){.  unsi
0570: 67 6e 65 64 20 69 6e 74 20 68 20 3d 20 30 3b 0a  gned int h = 0;.
0580: 20 20 61 73 73 65 72 74 28 20 6e 4b 65 79 3e 3d    assert( nKey>=
0590: 30 20 29 3b 0a 20 20 77 68 69 6c 65 28 20 6e 4b  0 );.  while( nK
05a0: 65 79 20 3e 20 30 20 20 29 7b 0a 20 20 20 20 68  ey > 0  ){.    h
05b0: 20 3d 20 28 68 3c 3c 33 29 20 5e 20 68 20 5e 20   = (h<<3) ^ h ^ 
05c0: 73 71 6c 69 74 65 33 55 70 70 65 72 54 6f 4c 6f  sqlite3UpperToLo
05d0: 77 65 72 5b 28 75 6e 73 69 67 6e 65 64 20 63 68  wer[(unsigned ch
05e0: 61 72 29 2a 7a 2b 2b 5d 3b 0a 20 20 20 20 6e 4b  ar)*z++];.    nK
05f0: 65 79 2d 2d 3b 0a 20 20 7d 0a 20 20 72 65 74 75  ey--;.  }.  retu
0600: 72 6e 20 68 3b 0a 7d 0a 0a 0a 2f 2a 20 4c 69 6e  rn h;.}.../* Lin
0610: 6b 20 70 4e 65 77 20 65 6c 65 6d 65 6e 74 20 69  k pNew element i
0620: 6e 74 6f 20 74 68 65 20 68 61 73 68 20 74 61 62  nto the hash tab
0630: 6c 65 20 70 48 2e 20 20 49 66 20 70 45 6e 74 72  le pH.  If pEntr
0640: 79 21 3d 30 20 74 68 65 6e 20 61 6c 73 6f 0a 2a  y!=0 then also.*
0650: 2a 20 69 6e 73 65 72 74 20 70 4e 65 77 20 69 6e  * insert pNew in
0660: 74 6f 20 74 68 65 20 70 45 6e 74 72 79 20 68 61  to the pEntry ha
0670: 73 68 20 62 75 63 6b 65 74 2e 0a 2a 2f 0a 73 74  sh bucket..*/.st
0680: 61 74 69 63 20 76 6f 69 64 20 69 6e 73 65 72 74  atic void insert
0690: 45 6c 65 6d 65 6e 74 28 0a 20 20 48 61 73 68 20  Element(.  Hash 
06a0: 2a 70 48 2c 20 20 20 20 20 20 20 20 20 20 20 20  *pH,            
06b0: 20 20 2f 2a 20 54 68 65 20 63 6f 6d 70 6c 65 74    /* The complet
06c0: 65 20 68 61 73 68 20 74 61 62 6c 65 20 2a 2f 0a  e hash table */.
06d0: 20 20 73 74 72 75 63 74 20 5f 68 74 20 2a 70 45    struct _ht *pE
06e0: 6e 74 72 79 2c 20 20 20 20 2f 2a 20 54 68 65 20  ntry,    /* The 
06f0: 65 6e 74 72 79 20 69 6e 74 6f 20 77 68 69 63 68  entry into which
0700: 20 70 4e 65 77 20 69 73 20 69 6e 73 65 72 74 65   pNew is inserte
0710: 64 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20  d */.  HashElem 
0720: 2a 70 4e 65 77 20 20 20 20 20 20 20 20 20 2f 2a  *pNew         /*
0730: 20 54 68 65 20 65 6c 65 6d 65 6e 74 20 74 6f 20   The element to 
0740: 62 65 20 69 6e 73 65 72 74 65 64 20 2a 2f 0a 29  be inserted */.)
0750: 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 70 48  {.  HashElem *pH
0760: 65 61 64 3b 20 20 20 20 20 20 20 2f 2a 20 46 69  ead;       /* Fi
0770: 72 73 74 20 65 6c 65 6d 65 6e 74 20 61 6c 72 65  rst element alre
0780: 61 64 79 20 69 6e 20 70 45 6e 74 72 79 20 2a 2f  ady in pEntry */
0790: 0a 20 20 69 66 28 20 70 45 6e 74 72 79 20 29 7b  .  if( pEntry ){
07a0: 0a 20 20 20 20 70 48 65 61 64 20 3d 20 70 45 6e  .    pHead = pEn
07b0: 74 72 79 2d 3e 63 6f 75 6e 74 20 3f 20 70 45 6e  try->count ? pEn
07c0: 74 72 79 2d 3e 63 68 61 69 6e 20 3a 20 30 3b 0a  try->chain : 0;.
07d0: 20 20 20 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e      pEntry->coun
07e0: 74 2b 2b 3b 0a 20 20 20 20 70 45 6e 74 72 79 2d  t++;.    pEntry-
07f0: 3e 63 68 61 69 6e 20 3d 20 70 4e 65 77 3b 0a 20  >chain = pNew;. 
0800: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 70 48 65 61   }else{.    pHea
0810: 64 20 3d 20 30 3b 0a 20 20 7d 0a 20 20 69 66 28  d = 0;.  }.  if(
0820: 20 70 48 65 61 64 20 29 7b 0a 20 20 20 20 70 4e   pHead ){.    pN
0830: 65 77 2d 3e 6e 65 78 74 20 3d 20 70 48 65 61 64  ew->next = pHead
0840: 3b 0a 20 20 20 20 70 4e 65 77 2d 3e 70 72 65 76  ;.    pNew->prev
0850: 20 3d 20 70 48 65 61 64 2d 3e 70 72 65 76 3b 0a   = pHead->prev;.
0860: 20 20 20 20 69 66 28 20 70 48 65 61 64 2d 3e 70      if( pHead->p
0870: 72 65 76 20 29 7b 20 70 48 65 61 64 2d 3e 70 72  rev ){ pHead->pr
0880: 65 76 2d 3e 6e 65 78 74 20 3d 20 70 4e 65 77 3b  ev->next = pNew;
0890: 20 7d 0a 20 20 20 20 65 6c 73 65 20 20 20 20 20   }.    else     
08a0: 20 20 20 20 20 20 20 20 7b 20 70 48 2d 3e 66 69          { pH->fi
08b0: 72 73 74 20 3d 20 70 4e 65 77 3b 20 7d 0a 20 20  rst = pNew; }.  
08c0: 20 20 70 48 65 61 64 2d 3e 70 72 65 76 20 3d 20    pHead->prev = 
08d0: 70 4e 65 77 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20  pNew;.  }else{. 
08e0: 20 20 20 70 4e 65 77 2d 3e 6e 65 78 74 20 3d 20     pNew->next = 
08f0: 70 48 2d 3e 66 69 72 73 74 3b 0a 20 20 20 20 69  pH->first;.    i
0900: 66 28 20 70 48 2d 3e 66 69 72 73 74 20 29 7b 20  f( pH->first ){ 
0910: 70 48 2d 3e 66 69 72 73 74 2d 3e 70 72 65 76 20  pH->first->prev 
0920: 3d 20 70 4e 65 77 3b 20 7d 0a 20 20 20 20 70 4e  = pNew; }.    pN
0930: 65 77 2d 3e 70 72 65 76 20 3d 20 30 3b 0a 20 20  ew->prev = 0;.  
0940: 20 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 70 4e    pH->first = pN
0950: 65 77 3b 0a 20 20 7d 0a 7d 0a 0a 0a 2f 2a 20 52  ew;.  }.}.../* R
0960: 65 73 69 7a 65 20 74 68 65 20 68 61 73 68 20 74  esize the hash t
0970: 61 62 6c 65 20 73 6f 20 74 68 61 74 20 69 74 20  able so that it 
0980: 63 61 6e 74 61 69 6e 73 20 22 6e 65 77 5f 73 69  cantains "new_si
0990: 7a 65 22 20 62 75 63 6b 65 74 73 2e 0a 2a 2a 0a  ze" buckets..**.
09a0: 2a 2a 20 54 68 65 20 68 61 73 68 20 74 61 62 6c  ** The hash tabl
09b0: 65 20 6d 69 67 68 74 20 66 61 69 6c 20 74 6f 20  e might fail to 
09c0: 72 65 73 69 7a 65 20 69 66 20 73 71 6c 69 74 65  resize if sqlite
09d0: 33 5f 6d 61 6c 6c 6f 63 28 29 20 66 61 69 6c 73  3_malloc() fails
09e0: 20 6f 72 0a 2a 2a 20 69 66 20 74 68 65 20 6e 65   or.** if the ne
09f0: 77 20 73 69 7a 65 20 69 73 20 74 68 65 20 73 61  w size is the sa
0a00: 6d 65 20 61 73 20 74 68 65 20 70 72 69 6f 72 20  me as the prior 
0a10: 73 69 7a 65 2e 0a 2a 2a 20 52 65 74 75 72 6e 20  size..** Return 
0a20: 54 52 55 45 20 69 66 20 74 68 65 20 72 65 73 69  TRUE if the resi
0a30: 7a 65 20 6f 63 63 75 72 73 20 61 6e 64 20 66 61  ze occurs and fa
0a40: 6c 73 65 20 69 66 20 6e 6f 74 2e 0a 2a 2f 0a 73  lse if not..*/.s
0a50: 74 61 74 69 63 20 69 6e 74 20 72 65 68 61 73 68  tatic int rehash
0a60: 28 48 61 73 68 20 2a 70 48 2c 20 75 6e 73 69 67  (Hash *pH, unsig
0a70: 6e 65 64 20 69 6e 74 20 6e 65 77 5f 73 69 7a 65  ned int new_size
0a80: 29 7b 0a 20 20 73 74 72 75 63 74 20 5f 68 74 20  ){.  struct _ht 
0a90: 2a 6e 65 77 5f 68 74 3b 20 20 20 20 20 20 20 20  *new_ht;        
0aa0: 20 20 20 20 2f 2a 20 54 68 65 20 6e 65 77 20 68      /* The new h
0ab0: 61 73 68 20 74 61 62 6c 65 20 2a 2f 0a 20 20 48  ash table */.  H
0ac0: 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 2c 20 2a  ashElem *elem, *
0ad0: 6e 65 78 74 5f 65 6c 65 6d 3b 20 20 20 20 2f 2a  next_elem;    /*
0ae0: 20 46 6f 72 20 6c 6f 6f 70 69 6e 67 20 6f 76 65   For looping ove
0af0: 72 20 65 78 69 73 74 69 6e 67 20 65 6c 65 6d 65  r existing eleme
0b00: 6e 74 73 20 2a 2f 0a 0a 23 69 66 20 53 51 4c 49  nts */..#if SQLI
0b10: 54 45 5f 4d 41 4c 4c 4f 43 5f 53 4f 46 54 5f 4c  TE_MALLOC_SOFT_L
0b20: 49 4d 49 54 3e 30 0a 20 20 69 66 28 20 6e 65 77  IMIT>0.  if( new
0b30: 5f 73 69 7a 65 2a 73 69 7a 65 6f 66 28 73 74 72  _size*sizeof(str
0b40: 75 63 74 20 5f 68 74 29 3e 53 51 4c 49 54 45 5f  uct _ht)>SQLITE_
0b50: 4d 41 4c 4c 4f 43 5f 53 4f 46 54 5f 4c 49 4d 49  MALLOC_SOFT_LIMI
0b60: 54 20 29 7b 0a 20 20 20 20 6e 65 77 5f 73 69 7a  T ){.    new_siz
0b70: 65 20 3d 20 53 51 4c 49 54 45 5f 4d 41 4c 4c 4f  e = SQLITE_MALLO
0b80: 43 5f 53 4f 46 54 5f 4c 49 4d 49 54 2f 73 69 7a  C_SOFT_LIMIT/siz
0b90: 65 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29 3b  eof(struct _ht);
0ba0: 0a 20 20 7d 0a 20 20 69 66 28 20 6e 65 77 5f 73  .  }.  if( new_s
0bb0: 69 7a 65 3d 3d 70 48 2d 3e 68 74 73 69 7a 65 20  ize==pH->htsize 
0bc0: 29 20 72 65 74 75 72 6e 20 30 3b 0a 23 65 6e 64  ) return 0;.#end
0bd0: 69 66 0a 0a 20 20 2f 2a 20 54 68 65 20 69 6e 61  if..  /* The ina
0be0: 62 69 6c 69 74 79 20 74 6f 20 61 6c 6c 6f 63 61  bility to alloca
0bf0: 74 65 73 20 73 70 61 63 65 20 66 6f 72 20 61 20  tes space for a 
0c00: 6c 61 72 67 65 72 20 68 61 73 68 20 74 61 62 6c  larger hash tabl
0c10: 65 20 69 73 0a 20 20 2a 2a 20 61 20 70 65 72 66  e is.  ** a perf
0c20: 6f 72 6d 61 6e 63 65 20 68 69 74 20 62 75 74 20  ormance hit but 
0c30: 69 74 20 69 73 20 6e 6f 74 20 61 20 66 61 74 61  it is not a fata
0c40: 6c 20 65 72 72 6f 72 2e 20 20 53 6f 20 6d 61 72  l error.  So mar
0c50: 6b 20 74 68 65 0a 20 20 2a 2a 20 61 6c 6c 6f 63  k the.  ** alloc
0c60: 61 74 69 6f 6e 20 61 73 20 61 20 62 65 6e 69 67  ation as a benig
0c70: 6e 2e 20 55 73 65 20 73 71 6c 69 74 65 33 4d 61  n. Use sqlite3Ma
0c80: 6c 6c 6f 63 28 29 2f 6d 65 6d 73 65 74 28 30 29  lloc()/memset(0)
0c90: 20 69 6e 73 74 65 61 64 20 6f 66 20 0a 20 20 2a   instead of .  *
0ca0: 2a 20 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 5a  * sqlite3MallocZ
0cb0: 65 72 6f 28 29 20 74 6f 20 6d 61 6b 65 20 74 68  ero() to make th
0cc0: 65 20 61 6c 6c 6f 63 61 74 69 6f 6e 2c 20 61 73  e allocation, as
0cd0: 20 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 5a 65   sqlite3MallocZe
0ce0: 72 6f 28 29 0a 20 20 2a 2a 20 6f 6e 6c 79 20 7a  ro().  ** only z
0cf0: 65 72 6f 65 73 20 74 68 65 20 72 65 71 75 65 73  eroes the reques
0d00: 74 65 64 20 6e 75 6d 62 65 72 20 6f 66 20 62 79  ted number of by
0d10: 74 65 73 20 77 68 65 72 65 61 73 20 74 68 69 73  tes whereas this
0d20: 20 6d 6f 64 75 6c 65 20 77 69 6c 6c 0a 20 20 2a   module will.  *
0d30: 2a 20 75 73 65 20 74 68 65 20 61 63 74 75 61 6c  * use the actual
0d40: 20 61 6d 6f 75 6e 74 20 6f 66 20 73 70 61 63 65   amount of space
0d50: 20 61 6c 6c 6f 63 61 74 65 64 20 66 6f 72 20 74   allocated for t
0d60: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 28 77  he hash table (w
0d70: 68 69 63 68 0a 20 20 2a 2a 20 6d 61 79 20 62 65  hich.  ** may be
0d80: 20 6c 61 72 67 65 72 20 74 68 61 6e 20 74 68 65   larger than the
0d90: 20 72 65 71 75 65 73 74 65 64 20 61 6d 6f 75 6e   requested amoun
0da0: 74 29 2e 0a 20 20 2a 2f 0a 20 20 73 71 6c 69 74  t)..  */.  sqlit
0db0: 65 33 42 65 67 69 6e 42 65 6e 69 67 6e 4d 61 6c  e3BeginBenignMal
0dc0: 6c 6f 63 28 29 3b 0a 20 20 6e 65 77 5f 68 74 20  loc();.  new_ht 
0dd0: 3d 20 28 73 74 72 75 63 74 20 5f 68 74 20 2a 29  = (struct _ht *)
0de0: 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 28 20 6e  sqlite3Malloc( n
0df0: 65 77 5f 73 69 7a 65 2a 73 69 7a 65 6f 66 28 73  ew_size*sizeof(s
0e00: 74 72 75 63 74 20 5f 68 74 29 20 29 3b 0a 20 20  truct _ht) );.  
0e10: 73 71 6c 69 74 65 33 45 6e 64 42 65 6e 69 67 6e  sqlite3EndBenign
0e20: 4d 61 6c 6c 6f 63 28 29 3b 0a 0a 20 20 69 66 28  Malloc();..  if(
0e30: 20 6e 65 77 5f 68 74 3d 3d 30 20 29 20 72 65 74   new_ht==0 ) ret
0e40: 75 72 6e 20 30 3b 0a 20 20 73 71 6c 69 74 65 33  urn 0;.  sqlite3
0e50: 5f 66 72 65 65 28 70 48 2d 3e 68 74 29 3b 0a 20  _free(pH->ht);. 
0e60: 20 70 48 2d 3e 68 74 20 3d 20 6e 65 77 5f 68 74   pH->ht = new_ht
0e70: 3b 0a 20 20 70 48 2d 3e 68 74 73 69 7a 65 20 3d  ;.  pH->htsize =
0e80: 20 6e 65 77 5f 73 69 7a 65 20 3d 20 73 71 6c 69   new_size = sqli
0e90: 74 65 33 4d 61 6c 6c 6f 63 53 69 7a 65 28 6e 65  te3MallocSize(ne
0ea0: 77 5f 68 74 29 2f 73 69 7a 65 6f 66 28 73 74 72  w_ht)/sizeof(str
0eb0: 75 63 74 20 5f 68 74 29 3b 0a 20 20 6d 65 6d 73  uct _ht);.  mems
0ec0: 65 74 28 6e 65 77 5f 68 74 2c 20 30 2c 20 6e 65  et(new_ht, 0, 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 29 3b 0a 20 20 66 6f  ruct _ht));.  fo
0ef0: 72 28 65 6c 65 6d 3d 70 48 2d 3e 66 69 72 73 74  r(elem=pH->first
0f00: 2c 20 70 48 2d 3e 66 69 72 73 74 3d 30 3b 20 65  , pH->first=0; e
0f10: 6c 65 6d 3b 20 65 6c 65 6d 20 3d 20 6e 65 78 74  lem; elem = next
0f20: 5f 65 6c 65 6d 29 7b 0a 20 20 20 20 75 6e 73 69  _elem){.    unsi
0f30: 67 6e 65 64 20 69 6e 74 20 68 20 3d 20 73 74 72  gned int h = str
0f40: 48 61 73 68 28 65 6c 65 6d 2d 3e 70 4b 65 79 2c  Hash(elem->pKey,
0f50: 20 65 6c 65 6d 2d 3e 6e 4b 65 79 29 20 25 20 6e   elem->nKey) % n
0f60: 65 77 5f 73 69 7a 65 3b 0a 20 20 20 20 6e 65 78  ew_size;.    nex
0f70: 74 5f 65 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e 6e  t_elem = elem->n
0f80: 65 78 74 3b 0a 20 20 20 20 69 6e 73 65 72 74 45  ext;.    insertE
0f90: 6c 65 6d 65 6e 74 28 70 48 2c 20 26 6e 65 77 5f  lement(pH, &new_
0fa0: 68 74 5b 68 5d 2c 20 65 6c 65 6d 29 3b 0a 20 20  ht[h], elem);.  
0fb0: 7d 0a 20 20 72 65 74 75 72 6e 20 31 3b 0a 7d 0a  }.  return 1;.}.
0fc0: 0a 2f 2a 20 54 68 69 73 20 66 75 6e 63 74 69 6f  ./* This functio
0fd0: 6e 20 28 66 6f 72 20 69 6e 74 65 72 6e 61 6c 20  n (for internal 
0fe0: 75 73 65 20 6f 6e 6c 79 29 20 6c 6f 63 61 74 65  use only) locate
0ff0: 73 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69 6e 20  s an element in 
1000: 61 6e 0a 2a 2a 20 68 61 73 68 20 74 61 62 6c 65  an.** hash table
1010: 20 74 68 61 74 20 6d 61 74 63 68 65 73 20 74 68   that matches th
1020: 65 20 67 69 76 65 6e 20 6b 65 79 2e 20 20 54 68  e given key.  Th
1030: 65 20 68 61 73 68 20 66 6f 72 20 74 68 69 73 20  e hash for this 
1040: 6b 65 79 20 68 61 73 0a 2a 2a 20 61 6c 72 65 61  key has.** alrea
1050: 64 79 20 62 65 65 6e 20 63 6f 6d 70 75 74 65 64  dy been computed
1060: 20 61 6e 64 20 69 73 20 70 61 73 73 65 64 20 61   and is passed a
1070: 73 20 74 68 65 20 34 74 68 20 70 61 72 61 6d 65  s the 4th parame
1080: 74 65 72 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 48  ter..*/.static H
1090: 61 73 68 45 6c 65 6d 20 2a 66 69 6e 64 45 6c 65  ashElem *findEle
10a0: 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28 0a 20  mentGivenHash(. 
10b0: 20 63 6f 6e 73 74 20 48 61 73 68 20 2a 70 48 2c   const Hash *pH,
10c0: 20 20 20 20 20 2f 2a 20 54 68 65 20 70 48 20 74       /* The pH t
10d0: 6f 20 62 65 20 73 65 61 72 63 68 65 64 20 2a 2f  o be searched */
10e0: 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70  .  const char *p
10f0: 4b 65 79 2c 20 20 20 2f 2a 20 54 68 65 20 6b 65  Key,   /* The ke
1100: 79 20 77 65 20 61 72 65 20 73 65 61 72 63 68 69  y we are searchi
1110: 6e 67 20 66 6f 72 20 2a 2f 0a 20 20 69 6e 74 20  ng for */.  int 
1120: 6e 4b 65 79 2c 20 20 20 20 20 20 20 20 20 20 20  nKey,           
1130: 2f 2a 20 42 79 74 65 73 20 69 6e 20 6b 65 79 20  /* Bytes in key 
1140: 28 6e 6f 74 20 63 6f 75 6e 74 69 6e 67 20 7a 65  (not counting ze
1150: 72 6f 20 74 65 72 6d 69 6e 61 74 6f 72 29 20 2a  ro terminator) *
1160: 2f 0a 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74  /.  unsigned int
1170: 20 68 20 20 20 20 20 20 2f 2a 20 54 68 65 20 68   h      /* The h
1180: 61 73 68 20 66 6f 72 20 74 68 69 73 20 6b 65 79  ash for this key
1190: 2e 20 2a 2f 0a 29 7b 0a 20 20 48 61 73 68 45 6c  . */.){.  HashEl
11a0: 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 20 20 20  em *elem;       
11b0: 20 20 20 20 20 20 20 20 20 2f 2a 20 55 73 65 64           /* Used
11c0: 20 74 6f 20 6c 6f 6f 70 20 74 68 72 75 20 74 68   to loop thru th
11d0: 65 20 65 6c 65 6d 65 6e 74 20 6c 69 73 74 20 2a  e element list *
11e0: 2f 0a 20 20 69 6e 74 20 63 6f 75 6e 74 3b 20 20  /.  int count;  
11f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1200: 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20     /* Number of 
1210: 65 6c 65 6d 65 6e 74 73 20 6c 65 66 74 20 74 6f  elements left to
1220: 20 74 65 73 74 20 2a 2f 0a 0a 20 20 69 66 28 20   test */..  if( 
1230: 70 48 2d 3e 68 74 20 29 7b 0a 20 20 20 20 73 74  pH->ht ){.    st
1240: 72 75 63 74 20 5f 68 74 20 2a 70 45 6e 74 72 79  ruct _ht *pEntry
1250: 20 3d 20 26 70 48 2d 3e 68 74 5b 68 5d 3b 0a 20   = &pH->ht[h];. 
1260: 20 20 20 65 6c 65 6d 20 3d 20 70 45 6e 74 72 79     elem = pEntry
1270: 2d 3e 63 68 61 69 6e 3b 0a 20 20 20 20 63 6f 75  ->chain;.    cou
1280: 6e 74 20 3d 20 70 45 6e 74 72 79 2d 3e 63 6f 75  nt = pEntry->cou
1290: 6e 74 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20  nt;.  }else{.   
12a0: 20 65 6c 65 6d 20 3d 20 70 48 2d 3e 66 69 72 73   elem = pH->firs
12b0: 74 3b 0a 20 20 20 20 63 6f 75 6e 74 20 3d 20 70  t;.    count = p
12c0: 48 2d 3e 63 6f 75 6e 74 3b 0a 20 20 7d 0a 20 20  H->count;.  }.  
12d0: 77 68 69 6c 65 28 20 63 6f 75 6e 74 2d 2d 20 26  while( count-- &
12e0: 26 20 41 4c 57 41 59 53 28 65 6c 65 6d 29 20 29  & ALWAYS(elem) )
12f0: 7b 0a 20 20 20 20 69 66 28 20 65 6c 65 6d 2d 3e  {.    if( elem->
1300: 6e 4b 65 79 3d 3d 6e 4b 65 79 20 26 26 20 73 71  nKey==nKey && sq
1310: 6c 69 74 65 33 53 74 72 4e 49 43 6d 70 28 65 6c  lite3StrNICmp(el
1320: 65 6d 2d 3e 70 4b 65 79 2c 70 4b 65 79 2c 6e 4b  em->pKey,pKey,nK
1330: 65 79 29 3d 3d 30 20 29 7b 20 0a 20 20 20 20 20  ey)==0 ){ .     
1340: 20 72 65 74 75 72 6e 20 65 6c 65 6d 3b 0a 20 20   return elem;.  
1350: 20 20 7d 0a 20 20 20 20 65 6c 65 6d 20 3d 20 65    }.    elem = e
1360: 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20  lem->next;.  }. 
1370: 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a 0a 2f 2a   return 0;.}../*
1380: 20 52 65 6d 6f 76 65 20 61 20 73 69 6e 67 6c 65   Remove a single
1390: 20 65 6e 74 72 79 20 66 72 6f 6d 20 74 68 65 20   entry from the 
13a0: 68 61 73 68 20 74 61 62 6c 65 20 67 69 76 65 6e  hash table given
13b0: 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68   a pointer to th
13c0: 61 74 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 61 6e  at.** element an
13d0: 64 20 61 20 68 61 73 68 20 6f 6e 20 74 68 65 20  d a hash on the 
13e0: 65 6c 65 6d 65 6e 74 27 73 20 6b 65 79 2e 0a 2a  element's key..*
13f0: 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 72 65  /.static void re
1400: 6d 6f 76 65 45 6c 65 6d 65 6e 74 47 69 76 65 6e  moveElementGiven
1410: 48 61 73 68 28 0a 20 20 48 61 73 68 20 2a 70 48  Hash(.  Hash *pH
1420: 2c 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65  ,         /* The
1430: 20 70 48 20 63 6f 6e 74 61 69 6e 69 6e 67 20 22   pH containing "
1440: 65 6c 65 6d 22 20 2a 2f 0a 20 20 48 61 73 68 45  elem" */.  HashE
1450: 6c 65 6d 2a 20 65 6c 65 6d 2c 20 20 20 2f 2a 20  lem* elem,   /* 
1460: 54 68 65 20 65 6c 65 6d 65 6e 74 20 74 6f 20 62  The element to b
1470: 65 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74  e removed from t
1480: 68 65 20 70 48 20 2a 2f 0a 20 20 75 6e 73 69 67  he pH */.  unsig
1490: 6e 65 64 20 69 6e 74 20 68 20 20 20 20 2f 2a 20  ned int h    /* 
14a0: 48 61 73 68 20 76 61 6c 75 65 20 66 6f 72 20 74  Hash value for t
14b0: 68 65 20 65 6c 65 6d 65 6e 74 20 2a 2f 0a 29 7b  he element */.){
14c0: 0a 20 20 73 74 72 75 63 74 20 5f 68 74 20 2a 70  .  struct _ht *p
14d0: 45 6e 74 72 79 3b 0a 20 20 69 66 28 20 65 6c 65  Entry;.  if( ele
14e0: 6d 2d 3e 70 72 65 76 20 29 7b 0a 20 20 20 20 65  m->prev ){.    e
14f0: 6c 65 6d 2d 3e 70 72 65 76 2d 3e 6e 65 78 74 20  lem->prev->next 
1500: 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 20 0a 20  = elem->next; . 
1510: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 70 48 2d 3e   }else{.    pH->
1520: 66 69 72 73 74 20 3d 20 65 6c 65 6d 2d 3e 6e 65  first = elem->ne
1530: 78 74 3b 0a 20 20 7d 0a 20 20 69 66 28 20 65 6c  xt;.  }.  if( el
1540: 65 6d 2d 3e 6e 65 78 74 20 29 7b 0a 20 20 20 20  em->next ){.    
1550: 65 6c 65 6d 2d 3e 6e 65 78 74 2d 3e 70 72 65 76  elem->next->prev
1560: 20 3d 20 65 6c 65 6d 2d 3e 70 72 65 76 3b 0a 20   = elem->prev;. 
1570: 20 7d 0a 20 20 69 66 28 20 70 48 2d 3e 68 74 20   }.  if( pH->ht 
1580: 29 7b 0a 20 20 20 20 70 45 6e 74 72 79 20 3d 20  ){.    pEntry = 
1590: 26 70 48 2d 3e 68 74 5b 68 5d 3b 0a 20 20 20 20  &pH->ht[h];.    
15a0: 69 66 28 20 70 45 6e 74 72 79 2d 3e 63 68 61 69  if( pEntry->chai
15b0: 6e 3d 3d 65 6c 65 6d 20 29 7b 0a 20 20 20 20 20  n==elem ){.     
15c0: 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 20 3d   pEntry->chain =
15d0: 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20   elem->next;.   
15e0: 20 7d 0a 20 20 20 20 70 45 6e 74 72 79 2d 3e 63   }.    pEntry->c
15f0: 6f 75 6e 74 2d 2d 3b 0a 20 20 20 20 61 73 73 65  ount--;.    asse
1600: 72 74 28 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e  rt( pEntry->coun
1610: 74 3e 3d 30 20 29 3b 0a 20 20 7d 0a 20 20 73 71  t>=0 );.  }.  sq
1620: 6c 69 74 65 33 5f 66 72 65 65 28 20 65 6c 65 6d  lite3_free( elem
1630: 20 29 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 2d   );.  pH->count-
1640: 2d 3b 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f 75  -;.  if( pH->cou
1650: 6e 74 3d 3d 30 20 29 7b 0a 20 20 20 20 61 73 73  nt==0 ){.    ass
1660: 65 72 74 28 20 70 48 2d 3e 66 69 72 73 74 3d 3d  ert( pH->first==
1670: 30 20 29 3b 0a 20 20 20 20 61 73 73 65 72 74 28  0 );.    assert(
1680: 20 70 48 2d 3e 63 6f 75 6e 74 3d 3d 30 20 29 3b   pH->count==0 );
1690: 0a 20 20 20 20 73 71 6c 69 74 65 33 48 61 73 68  .    sqlite3Hash
16a0: 43 6c 65 61 72 28 70 48 29 3b 0a 20 20 7d 0a 7d  Clear(pH);.  }.}
16b0: 0a 0a 2f 2a 20 41 74 74 65 6d 70 74 20 74 6f 20  ../* Attempt to 
16c0: 6c 6f 63 61 74 65 20 61 6e 20 65 6c 65 6d 65 6e  locate an elemen
16d0: 74 20 6f 66 20 74 68 65 20 68 61 73 68 20 74 61  t of the hash ta
16e0: 62 6c 65 20 70 48 20 77 69 74 68 20 61 20 6b 65  ble pH with a ke
16f0: 79 0a 2a 2a 20 74 68 61 74 20 6d 61 74 63 68 65  y.** that matche
1700: 73 20 70 4b 65 79 2c 6e 4b 65 79 2e 20 20 52 65  s pKey,nKey.  Re
1710: 74 75 72 6e 20 74 68 65 20 64 61 74 61 20 66 6f  turn the data fo
1720: 72 20 74 68 69 73 20 65 6c 65 6d 65 6e 74 20 69  r this element i
1730: 66 20 69 74 20 69 73 0a 2a 2a 20 66 6f 75 6e 64  f it is.** found
1740: 2c 20 6f 72 20 4e 55 4c 4c 20 69 66 20 74 68 65  , or NULL if the
1750: 72 65 20 69 73 20 6e 6f 20 6d 61 74 63 68 2e 0a  re is no match..
1760: 2a 2f 0a 76 6f 69 64 20 2a 73 71 6c 69 74 65 33  */.void *sqlite3
1770: 48 61 73 68 46 69 6e 64 28 63 6f 6e 73 74 20 48  HashFind(const H
1780: 61 73 68 20 2a 70 48 2c 20 63 6f 6e 73 74 20 63  ash *pH, const c
1790: 68 61 72 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e  har *pKey, int n
17a0: 4b 65 79 29 7b 0a 20 20 48 61 73 68 45 6c 65 6d  Key){.  HashElem
17b0: 20 2a 65 6c 65 6d 3b 20 20 20 20 2f 2a 20 54 68   *elem;    /* Th
17c0: 65 20 65 6c 65 6d 65 6e 74 20 74 68 61 74 20 6d  e element that m
17d0: 61 74 63 68 65 73 20 6b 65 79 20 2a 2f 0a 20 20  atches key */.  
17e0: 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 68 3b 20  unsigned int h; 
17f0: 20 20 20 2f 2a 20 41 20 68 61 73 68 20 6f 6e 20     /* A hash on 
1800: 6b 65 79 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74  key */..  assert
1810: 28 20 70 48 21 3d 30 20 29 3b 0a 20 20 61 73 73  ( pH!=0 );.  ass
1820: 65 72 74 28 20 70 4b 65 79 21 3d 30 20 29 3b 0a  ert( pKey!=0 );.
1830: 20 20 61 73 73 65 72 74 28 20 6e 4b 65 79 3e 3d    assert( nKey>=
1840: 30 20 29 3b 0a 20 20 69 66 28 20 70 48 2d 3e 68  0 );.  if( pH->h
1850: 74 20 29 7b 0a 20 20 20 20 68 20 3d 20 73 74 72  t ){.    h = str
1860: 48 61 73 68 28 70 4b 65 79 2c 20 6e 4b 65 79 29  Hash(pKey, nKey)
1870: 20 25 20 70 48 2d 3e 68 74 73 69 7a 65 3b 0a 20   % pH->htsize;. 
1880: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 68 20 3d 20   }else{.    h = 
1890: 30 3b 0a 20 20 7d 0a 20 20 65 6c 65 6d 20 3d 20  0;.  }.  elem = 
18a0: 66 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65 6e  findElementGiven
18b0: 48 61 73 68 28 70 48 2c 20 70 4b 65 79 2c 20 6e  Hash(pH, pKey, n
18c0: 4b 65 79 2c 20 68 29 3b 0a 20 20 72 65 74 75 72  Key, h);.  retur
18d0: 6e 20 65 6c 65 6d 20 3f 20 65 6c 65 6d 2d 3e 64  n elem ? elem->d
18e0: 61 74 61 20 3a 20 30 3b 0a 7d 0a 0a 2f 2a 20 49  ata : 0;.}../* I
18f0: 6e 73 65 72 74 20 61 6e 20 65 6c 65 6d 65 6e 74  nsert an element
1900: 20 69 6e 74 6f 20 74 68 65 20 68 61 73 68 20 74   into the hash t
1910: 61 62 6c 65 20 70 48 2e 20 20 54 68 65 20 6b 65  able pH.  The ke
1920: 79 20 69 73 20 70 4b 65 79 2c 6e 4b 65 79 0a 2a  y is pKey,nKey.*
1930: 2a 20 61 6e 64 20 74 68 65 20 64 61 74 61 20 69  * and the data i
1940: 73 20 22 64 61 74 61 22 2e 0a 2a 2a 0a 2a 2a 20  s "data"..**.** 
1950: 49 66 20 6e 6f 20 65 6c 65 6d 65 6e 74 20 65 78  If no element ex
1960: 69 73 74 73 20 77 69 74 68 20 61 20 6d 61 74 63  ists with a matc
1970: 68 69 6e 67 20 6b 65 79 2c 20 74 68 65 6e 20 61  hing key, then a
1980: 20 6e 65 77 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20   new.** element 
1990: 69 73 20 63 72 65 61 74 65 64 20 61 6e 64 20 4e  is created and N
19a0: 55 4c 4c 20 69 73 20 72 65 74 75 72 6e 65 64 2e  ULL is returned.
19b0: 0a 2a 2a 0a 2a 2a 20 49 66 20 61 6e 6f 74 68 65  .**.** If anothe
19c0: 72 20 65 6c 65 6d 65 6e 74 20 61 6c 72 65 61 64  r element alread
19d0: 79 20 65 78 69 73 74 73 20 77 69 74 68 20 74 68  y exists with th
19e0: 65 20 73 61 6d 65 20 6b 65 79 2c 20 74 68 65 6e  e same key, then
19f0: 20 74 68 65 0a 2a 2a 20 6e 65 77 20 64 61 74 61   the.** new data
1a00: 20 72 65 70 6c 61 63 65 73 20 74 68 65 20 6f 6c   replaces the ol
1a10: 64 20 64 61 74 61 20 61 6e 64 20 74 68 65 20 6f  d data and the o
1a20: 6c 64 20 64 61 74 61 20 69 73 20 72 65 74 75 72  ld data is retur
1a30: 6e 65 64 2e 0a 2a 2a 20 54 68 65 20 6b 65 79 20  ned..** The key 
1a40: 69 73 20 6e 6f 74 20 63 6f 70 69 65 64 20 69 6e  is not copied in
1a50: 20 74 68 69 73 20 69 6e 73 74 61 6e 63 65 2e 20   this instance. 
1a60: 20 49 66 20 61 20 6d 61 6c 6c 6f 63 20 66 61 69   If a malloc fai
1a70: 6c 73 2c 20 74 68 65 6e 0a 2a 2a 20 74 68 65 20  ls, then.** the 
1a80: 6e 65 77 20 64 61 74 61 20 69 73 20 72 65 74 75  new data is retu
1a90: 72 6e 65 64 20 61 6e 64 20 74 68 65 20 68 61 73  rned and the has
1aa0: 68 20 74 61 62 6c 65 20 69 73 20 75 6e 63 68 61  h table is uncha
1ab0: 6e 67 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 74  nged..**.** If t
1ac0: 68 65 20 22 64 61 74 61 22 20 70 61 72 61 6d 65  he "data" parame
1ad0: 74 65 72 20 74 6f 20 74 68 69 73 20 66 75 6e 63  ter to this func
1ae0: 74 69 6f 6e 20 69 73 20 4e 55 4c 4c 2c 20 74 68  tion is NULL, th
1af0: 65 6e 20 74 68 65 0a 2a 2a 20 65 6c 65 6d 65 6e  en the.** elemen
1b00: 74 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20  t corresponding 
1b10: 74 6f 20 22 6b 65 79 22 20 69 73 20 72 65 6d 6f  to "key" is remo
1b20: 76 65 64 20 66 72 6f 6d 20 74 68 65 20 68 61 73  ved from the has
1b30: 68 20 74 61 62 6c 65 2e 0a 2a 2f 0a 76 6f 69 64  h table..*/.void
1b40: 20 2a 73 71 6c 69 74 65 33 48 61 73 68 49 6e 73   *sqlite3HashIns
1b50: 65 72 74 28 48 61 73 68 20 2a 70 48 2c 20 63 6f  ert(Hash *pH, co
1b60: 6e 73 74 20 63 68 61 72 20 2a 70 4b 65 79 2c 20  nst char *pKey, 
1b70: 69 6e 74 20 6e 4b 65 79 2c 20 76 6f 69 64 20 2a  int nKey, void *
1b80: 64 61 74 61 29 7b 0a 20 20 75 6e 73 69 67 6e 65  data){.  unsigne
1b90: 64 20 69 6e 74 20 68 3b 20 20 20 20 20 20 20 2f  d int h;       /
1ba0: 2a 20 74 68 65 20 68 61 73 68 20 6f 66 20 74 68  * the hash of th
1bb0: 65 20 6b 65 79 20 6d 6f 64 75 6c 6f 20 68 61 73  e key modulo has
1bc0: 68 20 74 61 62 6c 65 20 73 69 7a 65 20 2a 2f 0a  h table size */.
1bd0: 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d    HashElem *elem
1be0: 3b 20 20 20 20 20 20 20 2f 2a 20 55 73 65 64 20  ;       /* Used 
1bf0: 74 6f 20 6c 6f 6f 70 20 74 68 72 75 20 74 68 65  to loop thru the
1c00: 20 65 6c 65 6d 65 6e 74 20 6c 69 73 74 20 2a 2f   element list */
1c10: 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 6e 65 77  .  HashElem *new
1c20: 5f 65 6c 65 6d 3b 20 20 20 2f 2a 20 4e 65 77 20  _elem;   /* New 
1c30: 65 6c 65 6d 65 6e 74 20 61 64 64 65 64 20 74 6f  element added to
1c40: 20 74 68 65 20 70 48 20 2a 2f 0a 0a 20 20 61 73   the pH */..  as
1c50: 73 65 72 74 28 20 70 48 21 3d 30 20 29 3b 0a 20  sert( pH!=0 );. 
1c60: 20 61 73 73 65 72 74 28 20 70 4b 65 79 21 3d 30   assert( pKey!=0
1c70: 20 29 3b 0a 20 20 61 73 73 65 72 74 28 20 6e 4b   );.  assert( nK
1c80: 65 79 3e 3d 30 20 29 3b 0a 20 20 69 66 28 20 70  ey>=0 );.  if( p
1c90: 48 2d 3e 68 74 73 69 7a 65 20 29 7b 0a 20 20 20  H->htsize ){.   
1ca0: 20 68 20 3d 20 73 74 72 48 61 73 68 28 70 4b 65   h = strHash(pKe
1cb0: 79 2c 20 6e 4b 65 79 29 20 25 20 70 48 2d 3e 68  y, nKey) % pH->h
1cc0: 74 73 69 7a 65 3b 0a 20 20 7d 65 6c 73 65 7b 0a  tsize;.  }else{.
1cd0: 20 20 20 20 68 20 3d 20 30 3b 0a 20 20 7d 0a 20      h = 0;.  }. 
1ce0: 20 65 6c 65 6d 20 3d 20 66 69 6e 64 45 6c 65 6d   elem = findElem
1cf0: 65 6e 74 47 69 76 65 6e 48 61 73 68 28 70 48 2c  entGivenHash(pH,
1d00: 70 4b 65 79 2c 6e 4b 65 79 2c 68 29 3b 0a 20 20  pKey,nKey,h);.  
1d10: 69 66 28 20 65 6c 65 6d 20 29 7b 0a 20 20 20 20  if( elem ){.    
1d20: 76 6f 69 64 20 2a 6f 6c 64 5f 64 61 74 61 20 3d  void *old_data =
1d30: 20 65 6c 65 6d 2d 3e 64 61 74 61 3b 0a 20 20 20   elem->data;.   
1d40: 20 69 66 28 20 64 61 74 61 3d 3d 30 20 29 7b 0a   if( data==0 ){.
1d50: 20 20 20 20 20 20 72 65 6d 6f 76 65 45 6c 65 6d        removeElem
1d60: 65 6e 74 47 69 76 65 6e 48 61 73 68 28 70 48 2c  entGivenHash(pH,
1d70: 65 6c 65 6d 2c 68 29 3b 0a 20 20 20 20 7d 65 6c  elem,h);.    }el
1d80: 73 65 7b 0a 20 20 20 20 20 20 65 6c 65 6d 2d 3e  se{.      elem->
1d90: 64 61 74 61 20 3d 20 64 61 74 61 3b 0a 20 20 20  data = data;.   
1da0: 20 20 20 65 6c 65 6d 2d 3e 70 4b 65 79 20 3d 20     elem->pKey = 
1db0: 70 4b 65 79 3b 0a 20 20 20 20 20 20 61 73 73 65  pKey;.      asse
1dc0: 72 74 28 6e 4b 65 79 3d 3d 65 6c 65 6d 2d 3e 6e  rt(nKey==elem->n
1dd0: 4b 65 79 29 3b 0a 20 20 20 20 7d 0a 20 20 20 20  Key);.    }.    
1de0: 72 65 74 75 72 6e 20 6f 6c 64 5f 64 61 74 61 3b  return old_data;
1df0: 0a 20 20 7d 0a 20 20 69 66 28 20 64 61 74 61 3d  .  }.  if( data=
1e00: 3d 30 20 29 20 72 65 74 75 72 6e 20 30 3b 0a 20  =0 ) return 0;. 
1e10: 20 6e 65 77 5f 65 6c 65 6d 20 3d 20 28 48 61 73   new_elem = (Has
1e20: 68 45 6c 65 6d 2a 29 73 71 6c 69 74 65 33 4d 61  hElem*)sqlite3Ma
1e30: 6c 6c 6f 63 28 20 73 69 7a 65 6f 66 28 48 61 73  lloc( sizeof(Has
1e40: 68 45 6c 65 6d 29 20 29 3b 0a 20 20 69 66 28 20  hElem) );.  if( 
1e50: 6e 65 77 5f 65 6c 65 6d 3d 3d 30 20 29 20 72 65  new_elem==0 ) re
1e60: 74 75 72 6e 20 64 61 74 61 3b 0a 20 20 6e 65 77  turn data;.  new
1e70: 5f 65 6c 65 6d 2d 3e 70 4b 65 79 20 3d 20 70 4b  _elem->pKey = pK
1e80: 65 79 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e  ey;.  new_elem->
1e90: 6e 4b 65 79 20 3d 20 6e 4b 65 79 3b 0a 20 20 6e  nKey = nKey;.  n
1ea0: 65 77 5f 65 6c 65 6d 2d 3e 64 61 74 61 20 3d 20  ew_elem->data = 
1eb0: 64 61 74 61 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e  data;.  pH->coun
1ec0: 74 2b 2b 3b 0a 20 20 69 66 28 20 70 48 2d 3e 63  t++;.  if( pH->c
1ed0: 6f 75 6e 74 3e 3d 31 30 20 26 26 20 70 48 2d 3e  ount>=10 && pH->
1ee0: 63 6f 75 6e 74 20 3e 20 32 2a 70 48 2d 3e 68 74  count > 2*pH->ht
1ef0: 73 69 7a 65 20 29 7b 0a 20 20 20 20 69 66 28 20  size ){.    if( 
1f00: 72 65 68 61 73 68 28 70 48 2c 20 70 48 2d 3e 63  rehash(pH, pH->c
1f10: 6f 75 6e 74 2a 32 29 20 29 7b 0a 20 20 20 20 20  ount*2) ){.     
1f20: 20 61 73 73 65 72 74 28 20 70 48 2d 3e 68 74 73   assert( pH->hts
1f30: 69 7a 65 3e 30 20 29 3b 0a 20 20 20 20 20 20 68  ize>0 );.      h
1f40: 20 3d 20 73 74 72 48 61 73 68 28 70 4b 65 79 2c   = strHash(pKey,
1f50: 20 6e 4b 65 79 29 20 25 20 70 48 2d 3e 68 74 73   nKey) % pH->hts
1f60: 69 7a 65 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20  ize;.    }.  }. 
1f70: 20 69 66 28 20 70 48 2d 3e 68 74 20 29 7b 0a 20   if( pH->ht ){. 
1f80: 20 20 20 69 6e 73 65 72 74 45 6c 65 6d 65 6e 74     insertElement
1f90: 28 70 48 2c 20 26 70 48 2d 3e 68 74 5b 68 5d 2c  (pH, &pH->ht[h],
1fa0: 20 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20 20 7d 65   new_elem);.  }e
1fb0: 6c 73 65 7b 0a 20 20 20 20 69 6e 73 65 72 74 45  lse{.    insertE
1fc0: 6c 65 6d 65 6e 74 28 70 48 2c 20 30 2c 20 6e 65  lement(pH, 0, ne
1fd0: 77 5f 65 6c 65 6d 29 3b 0a 20 20 7d 0a 20 20 72  w_elem);.  }.  r
1fe0: 65 74 75 72 6e 20 30 3b 0a 7d 0a                 eturn 0;.}.