/ Hex Artifact Content
Login

Artifact 15d39cbe87de9b9991054750bd3e0861888b7b06:


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: 2a 0a 2a 2a 20 24 49 64 3a 20 68 61 73 68 2e 63  *.** $Id: hash.c
01d0: 2c 76 20 31 2e 33 34 20 32 30 30 39 2f 30 34 2f  ,v 1.34 2009/04/
01e0: 32 38 20 31 33 3a 30 31 3a 30 39 20 64 72 68 20  28 13:01:09 drh 
01f0: 45 78 70 20 24 0a 2a 2f 0a 23 69 6e 63 6c 75 64  Exp $.*/.#includ
0200: 65 20 22 73 71 6c 69 74 65 49 6e 74 2e 68 22 0a  e "sqliteInt.h".
0210: 23 69 6e 63 6c 75 64 65 20 3c 61 73 73 65 72 74  #include <assert
0220: 2e 68 3e 0a 0a 2f 2a 20 54 75 72 6e 20 62 75 6c  .h>../* Turn bul
0230: 6b 20 6d 65 6d 6f 72 79 20 69 6e 74 6f 20 61 20  k memory into a 
0240: 68 61 73 68 20 74 61 62 6c 65 20 6f 62 6a 65 63  hash table objec
0250: 74 20 62 79 20 69 6e 69 74 69 61 6c 69 7a 69 6e  t by initializin
0260: 67 20 74 68 65 0a 2a 2a 20 66 69 65 6c 64 73 20  g the.** fields 
0270: 6f 66 20 74 68 65 20 48 61 73 68 20 73 74 72 75  of the Hash stru
0280: 63 74 75 72 65 2e 0a 2a 2a 0a 2a 2a 20 22 70 4e  cture..**.** "pN
0290: 65 77 22 20 69 73 20 61 20 70 6f 69 6e 74 65 72  ew" is a pointer
02a0: 20 74 6f 20 74 68 65 20 68 61 73 68 20 74 61 62   to the hash tab
02b0: 6c 65 20 74 68 61 74 20 69 73 20 74 6f 20 62 65  le that is to be
02c0: 20 69 6e 69 74 69 61 6c 69 7a 65 64 2e 0a 2a 2a   initialized..**
02d0: 20 22 63 6f 70 79 4b 65 79 22 20 69 73 20 74 72   "copyKey" is tr
02e0: 75 65 20 69 66 20 74 68 65 20 68 61 73 68 20 74  ue if the hash t
02f0: 61 62 6c 65 20 73 68 6f 75 6c 64 20 6d 61 6b 65  able should make
0300: 20 69 74 73 20 6f 77 6e 20 70 72 69 76 61 74 65   its own private
0310: 0a 2a 2a 20 63 6f 70 79 20 6f 66 20 6b 65 79 73  .** copy of keys
0320: 20 61 6e 64 20 66 61 6c 73 65 20 69 66 20 69 74   and false if it
0330: 20 73 68 6f 75 6c 64 20 6a 75 73 74 20 75 73 65   should just use
0340: 20 74 68 65 20 73 75 70 70 6c 69 65 64 20 70 6f   the supplied po
0350: 69 6e 74 65 72 2e 0a 2a 2f 0a 76 6f 69 64 20 73  inter..*/.void s
0360: 71 6c 69 74 65 33 48 61 73 68 49 6e 69 74 28 48  qlite3HashInit(H
0370: 61 73 68 20 2a 70 4e 65 77 2c 20 69 6e 74 20 63  ash *pNew, int c
0380: 6f 70 79 4b 65 79 29 7b 0a 20 20 61 73 73 65 72  opyKey){.  asser
0390: 74 28 20 70 4e 65 77 21 3d 30 20 29 3b 0a 20 20  t( pNew!=0 );.  
03a0: 70 4e 65 77 2d 3e 63 6f 70 79 4b 65 79 20 3d 20  pNew->copyKey = 
03b0: 63 6f 70 79 4b 65 79 21 3d 30 3b 0a 20 20 70 4e  copyKey!=0;.  pN
03c0: 65 77 2d 3e 66 69 72 73 74 20 3d 20 30 3b 0a 20  ew->first = 0;. 
03d0: 20 70 4e 65 77 2d 3e 63 6f 75 6e 74 20 3d 20 30   pNew->count = 0
03e0: 3b 0a 20 20 70 4e 65 77 2d 3e 68 74 73 69 7a 65  ;.  pNew->htsize
03f0: 20 3d 20 30 3b 0a 20 20 70 4e 65 77 2d 3e 68 74   = 0;.  pNew->ht
0400: 20 3d 20 30 3b 0a 7d 0a 0a 2f 2a 20 52 65 6d 6f   = 0;.}../* Remo
0410: 76 65 20 61 6c 6c 20 65 6e 74 72 69 65 73 20 66  ve all entries f
0420: 72 6f 6d 20 61 20 68 61 73 68 20 74 61 62 6c 65  rom a hash table
0430: 2e 20 20 52 65 63 6c 61 69 6d 20 61 6c 6c 20 6d  .  Reclaim all m
0440: 65 6d 6f 72 79 2e 0a 2a 2a 20 43 61 6c 6c 20 74  emory..** Call t
0450: 68 69 73 20 72 6f 75 74 69 6e 65 20 74 6f 20 64  his routine to d
0460: 65 6c 65 74 65 20 61 20 68 61 73 68 20 74 61 62  elete a hash tab
0470: 6c 65 20 6f 72 20 74 6f 20 72 65 73 65 74 20 61  le or to reset a
0480: 20 68 61 73 68 20 74 61 62 6c 65 0a 2a 2a 20 74   hash table.** t
0490: 6f 20 74 68 65 20 65 6d 70 74 79 20 73 74 61 74  o the empty stat
04a0: 65 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74  e..*/.void sqlit
04b0: 65 33 48 61 73 68 43 6c 65 61 72 28 48 61 73 68  e3HashClear(Hash
04c0: 20 2a 70 48 29 7b 0a 20 20 48 61 73 68 45 6c 65   *pH){.  HashEle
04d0: 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 20 20 20 20  m *elem;        
04e0: 20 2f 2a 20 46 6f 72 20 6c 6f 6f 70 69 6e 67 20   /* For looping 
04f0: 6f 76 65 72 20 61 6c 6c 20 65 6c 65 6d 65 6e 74  over all element
0500: 73 20 6f 66 20 74 68 65 20 74 61 62 6c 65 20 2a  s of the table *
0510: 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 70 48 21  /..  assert( pH!
0520: 3d 30 20 29 3b 0a 20 20 65 6c 65 6d 20 3d 20 70  =0 );.  elem = p
0530: 48 2d 3e 66 69 72 73 74 3b 0a 20 20 70 48 2d 3e  H->first;.  pH->
0540: 66 69 72 73 74 20 3d 20 30 3b 0a 20 20 73 71 6c  first = 0;.  sql
0550: 69 74 65 33 5f 66 72 65 65 28 70 48 2d 3e 68 74  ite3_free(pH->ht
0560: 29 3b 0a 20 20 70 48 2d 3e 68 74 20 3d 20 30 3b  );.  pH->ht = 0;
0570: 0a 20 20 70 48 2d 3e 68 74 73 69 7a 65 20 3d 20  .  pH->htsize = 
0580: 30 3b 0a 20 20 77 68 69 6c 65 28 20 65 6c 65 6d  0;.  while( elem
0590: 20 29 7b 0a 20 20 20 20 48 61 73 68 45 6c 65 6d   ){.    HashElem
05a0: 20 2a 6e 65 78 74 5f 65 6c 65 6d 20 3d 20 65 6c   *next_elem = el
05b0: 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 69 66  em->next;.    if
05c0: 28 20 70 48 2d 3e 63 6f 70 79 4b 65 79 20 29 7b  ( pH->copyKey ){
05d0: 0a 20 20 20 20 20 20 73 71 6c 69 74 65 33 5f 66  .      sqlite3_f
05e0: 72 65 65 28 65 6c 65 6d 2d 3e 70 4b 65 79 29 3b  ree(elem->pKey);
05f0: 0a 20 20 20 20 7d 0a 20 20 20 20 73 71 6c 69 74  .    }.    sqlit
0600: 65 33 5f 66 72 65 65 28 65 6c 65 6d 29 3b 0a 20  e3_free(elem);. 
0610: 20 20 20 65 6c 65 6d 20 3d 20 6e 65 78 74 5f 65     elem = next_e
0620: 6c 65 6d 3b 0a 20 20 7d 0a 20 20 70 48 2d 3e 63  lem;.  }.  pH->c
0630: 6f 75 6e 74 20 3d 20 30 3b 0a 7d 0a 0a 2f 2a 0a  ount = 0;.}../*.
0640: 2a 2a 20 48 61 73 68 20 61 6e 64 20 63 6f 6d 70  ** Hash and comp
0650: 61 72 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 73  arison functions
0660: 20 77 68 65 6e 20 74 68 65 20 6d 6f 64 65 20 69   when the mode i
0670: 73 20 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54  s SQLITE_HASH_ST
0680: 52 49 4e 47 0a 2a 2f 0a 73 74 61 74 69 63 20 69  RING.*/.static i
0690: 6e 74 20 73 74 72 48 61 73 68 28 63 6f 6e 73 74  nt strHash(const
06a0: 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74   void *pKey, int
06b0: 20 6e 4b 65 79 29 7b 0a 20 20 63 6f 6e 73 74 20   nKey){.  const 
06c0: 63 68 61 72 20 2a 7a 20 3d 20 28 63 6f 6e 73 74  char *z = (const
06d0: 20 63 68 61 72 20 2a 29 70 4b 65 79 3b 0a 20 20   char *)pKey;.  
06e0: 69 6e 74 20 68 20 3d 20 30 3b 0a 20 20 61 73 73  int h = 0;.  ass
06f0: 65 72 74 28 20 6e 4b 65 79 3e 30 20 29 3b 0a 20  ert( nKey>0 );. 
0700: 20 77 68 69 6c 65 28 20 6e 4b 65 79 20 3e 20 30   while( nKey > 0
0710: 20 20 29 7b 0a 20 20 20 20 68 20 3d 20 28 68 3c    ){.    h = (h<
0720: 3c 33 29 20 5e 20 68 20 5e 20 73 71 6c 69 74 65  <3) ^ h ^ sqlite
0730: 33 55 70 70 65 72 54 6f 4c 6f 77 65 72 5b 28 75  3UpperToLower[(u
0740: 6e 73 69 67 6e 65 64 20 63 68 61 72 29 2a 7a 2b  nsigned char)*z+
0750: 2b 5d 3b 0a 20 20 20 20 6e 4b 65 79 2d 2d 3b 0a  +];.    nKey--;.
0760: 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 68 20 26    }.  return h &
0770: 20 30 78 37 66 66 66 66 66 66 66 3b 0a 7d 0a 73   0x7fffffff;.}.s
0780: 74 61 74 69 63 20 69 6e 74 20 73 74 72 43 6f 6d  tatic int strCom
0790: 70 61 72 65 28 63 6f 6e 73 74 20 76 6f 69 64 20  pare(const void 
07a0: 2a 70 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c 20  *pKey1, int n1, 
07b0: 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79  const void *pKey
07c0: 32 2c 20 69 6e 74 20 6e 32 29 7b 0a 20 20 69 66  2, int n2){.  if
07d0: 28 20 6e 31 21 3d 6e 32 20 29 20 72 65 74 75 72  ( n1!=n2 ) retur
07e0: 6e 20 31 3b 0a 20 20 72 65 74 75 72 6e 20 73 71  n 1;.  return sq
07f0: 6c 69 74 65 33 53 74 72 4e 49 43 6d 70 28 28 63  lite3StrNICmp((c
0800: 6f 6e 73 74 20 63 68 61 72 2a 29 70 4b 65 79 31  onst char*)pKey1
0810: 2c 28 63 6f 6e 73 74 20 63 68 61 72 2a 29 70 4b  ,(const char*)pK
0820: 65 79 32 2c 6e 31 29 3b 0a 7d 0a 0a 0a 2f 2a 20  ey2,n1);.}.../* 
0830: 4c 69 6e 6b 20 61 6e 20 65 6c 65 6d 65 6e 74 20  Link an element 
0840: 69 6e 74 6f 20 74 68 65 20 68 61 73 68 20 74 61  into the hash ta
0850: 62 6c 65 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f  ble.*/.static vo
0860: 69 64 20 69 6e 73 65 72 74 45 6c 65 6d 65 6e 74  id insertElement
0870: 28 0a 20 20 48 61 73 68 20 2a 70 48 2c 20 20 20  (.  Hash *pH,   
0880: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68             /* Th
0890: 65 20 63 6f 6d 70 6c 65 74 65 20 68 61 73 68 20  e complete hash 
08a0: 74 61 62 6c 65 20 2a 2f 0a 20 20 73 74 72 75 63  table */.  struc
08b0: 74 20 5f 68 74 20 2a 70 45 6e 74 72 79 2c 20 20  t _ht *pEntry,  
08c0: 20 20 2f 2a 20 54 68 65 20 65 6e 74 72 79 20 69    /* The entry i
08d0: 6e 74 6f 20 77 68 69 63 68 20 70 4e 65 77 20 69  nto which pNew i
08e0: 73 20 69 6e 73 65 72 74 65 64 20 2a 2f 0a 20 20  s inserted */.  
08f0: 48 61 73 68 45 6c 65 6d 20 2a 70 4e 65 77 20 20  HashElem *pNew  
0900: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 65 6c         /* The el
0910: 65 6d 65 6e 74 20 74 6f 20 62 65 20 69 6e 73 65  ement to be inse
0920: 72 74 65 64 20 2a 2f 0a 29 7b 0a 20 20 48 61 73  rted */.){.  Has
0930: 68 45 6c 65 6d 20 2a 70 48 65 61 64 3b 20 20 20  hElem *pHead;   
0940: 20 20 20 20 2f 2a 20 46 69 72 73 74 20 65 6c 65      /* First ele
0950: 6d 65 6e 74 20 61 6c 72 65 61 64 79 20 69 6e 20  ment already in 
0960: 70 45 6e 74 72 79 20 2a 2f 0a 20 20 70 48 65 61  pEntry */.  pHea
0970: 64 20 3d 20 70 45 6e 74 72 79 2d 3e 63 68 61 69  d = pEntry->chai
0980: 6e 3b 0a 20 20 69 66 28 20 70 48 65 61 64 20 29  n;.  if( pHead )
0990: 7b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 65 78 74  {.    pNew->next
09a0: 20 3d 20 70 48 65 61 64 3b 0a 20 20 20 20 70 4e   = pHead;.    pN
09b0: 65 77 2d 3e 70 72 65 76 20 3d 20 70 48 65 61 64  ew->prev = pHead
09c0: 2d 3e 70 72 65 76 3b 0a 20 20 20 20 69 66 28 20  ->prev;.    if( 
09d0: 70 48 65 61 64 2d 3e 70 72 65 76 20 29 7b 20 70  pHead->prev ){ p
09e0: 48 65 61 64 2d 3e 70 72 65 76 2d 3e 6e 65 78 74  Head->prev->next
09f0: 20 3d 20 70 4e 65 77 3b 20 7d 0a 20 20 20 20 65   = pNew; }.    e
0a00: 6c 73 65 20 20 20 20 20 20 20 20 20 20 20 20 20  lse             
0a10: 7b 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 70 4e  { pH->first = pN
0a20: 65 77 3b 20 7d 0a 20 20 20 20 70 48 65 61 64 2d  ew; }.    pHead-
0a30: 3e 70 72 65 76 20 3d 20 70 4e 65 77 3b 0a 20 20  >prev = pNew;.  
0a40: 7d 65 6c 73 65 7b 0a 20 20 20 20 70 4e 65 77 2d  }else{.    pNew-
0a50: 3e 6e 65 78 74 20 3d 20 70 48 2d 3e 66 69 72 73  >next = pH->firs
0a60: 74 3b 0a 20 20 20 20 69 66 28 20 70 48 2d 3e 66  t;.    if( pH->f
0a70: 69 72 73 74 20 29 7b 20 70 48 2d 3e 66 69 72 73  irst ){ pH->firs
0a80: 74 2d 3e 70 72 65 76 20 3d 20 70 4e 65 77 3b 20  t->prev = pNew; 
0a90: 7d 0a 20 20 20 20 70 4e 65 77 2d 3e 70 72 65 76  }.    pNew->prev
0aa0: 20 3d 20 30 3b 0a 20 20 20 20 70 48 2d 3e 66 69   = 0;.    pH->fi
0ab0: 72 73 74 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 0a  rst = pNew;.  }.
0ac0: 20 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 2b    pEntry->count+
0ad0: 2b 3b 0a 20 20 70 45 6e 74 72 79 2d 3e 63 68 61  +;.  pEntry->cha
0ae0: 69 6e 20 3d 20 70 4e 65 77 3b 0a 7d 0a 0a 0a 2f  in = pNew;.}.../
0af0: 2a 20 52 65 73 69 7a 65 20 74 68 65 20 68 61 73  * Resize the has
0b00: 68 20 74 61 62 6c 65 20 73 6f 20 74 68 61 74 20  h table so that 
0b10: 69 74 20 63 61 6e 74 61 69 6e 73 20 22 6e 65 77  it cantains "new
0b20: 5f 73 69 7a 65 22 20 62 75 63 6b 65 74 73 2e 0a  _size" buckets..
0b30: 2a 2a 20 22 6e 65 77 5f 73 69 7a 65 22 20 6d 75  ** "new_size" mu
0b40: 73 74 20 62 65 20 61 20 70 6f 77 65 72 20 6f 66  st be a power of
0b50: 20 32 2e 20 20 54 68 65 20 68 61 73 68 20 74 61   2.  The hash ta
0b60: 62 6c 65 20 6d 69 67 68 74 20 66 61 69 6c 20 0a  ble might fail .
0b70: 2a 2a 20 74 6f 20 72 65 73 69 7a 65 20 69 66 20  ** to resize if 
0b80: 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 29  sqlite3_malloc()
0b90: 20 66 61 69 6c 73 2e 0a 2a 2f 0a 73 74 61 74 69   fails..*/.stati
0ba0: 63 20 76 6f 69 64 20 72 65 68 61 73 68 28 48 61  c void rehash(Ha
0bb0: 73 68 20 2a 70 48 2c 20 69 6e 74 20 6e 65 77 5f  sh *pH, int new_
0bc0: 73 69 7a 65 29 7b 0a 20 20 73 74 72 75 63 74 20  size){.  struct 
0bd0: 5f 68 74 20 2a 6e 65 77 5f 68 74 3b 20 20 20 20  _ht *new_ht;    
0be0: 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 6e          /* The n
0bf0: 65 77 20 68 61 73 68 20 74 61 62 6c 65 20 2a 2f  ew hash table */
0c00: 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65  .  HashElem *ele
0c10: 6d 2c 20 2a 6e 65 78 74 5f 65 6c 65 6d 3b 20 20  m, *next_elem;  
0c20: 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f 70 69 6e 67    /* For looping
0c30: 20 6f 76 65 72 20 65 78 69 73 74 69 6e 67 20 65   over existing e
0c40: 6c 65 6d 65 6e 74 73 20 2a 2f 0a 0a 23 69 66 64  lements */..#ifd
0c50: 65 66 20 53 51 4c 49 54 45 5f 4d 41 4c 4c 4f 43  ef SQLITE_MALLOC
0c60: 5f 53 4f 46 54 5f 4c 49 4d 49 54 0a 20 20 69 66  _SOFT_LIMIT.  if
0c70: 28 20 6e 65 77 5f 73 69 7a 65 2a 73 69 7a 65 6f  ( new_size*sizeo
0c80: 66 28 73 74 72 75 63 74 20 5f 68 74 29 3e 53 51  f(struct _ht)>SQ
0c90: 4c 49 54 45 5f 4d 41 4c 4c 4f 43 5f 53 4f 46 54  LITE_MALLOC_SOFT
0ca0: 5f 4c 49 4d 49 54 20 29 7b 0a 20 20 20 20 6e 65  _LIMIT ){.    ne
0cb0: 77 5f 73 69 7a 65 20 3d 20 53 51 4c 49 54 45 5f  w_size = SQLITE_
0cc0: 4d 41 4c 4c 4f 43 5f 53 4f 46 54 5f 4c 49 4d 49  MALLOC_SOFT_LIMI
0cd0: 54 2f 73 69 7a 65 6f 66 28 73 74 72 75 63 74 20  T/sizeof(struct 
0ce0: 5f 68 74 29 3b 0a 20 20 7d 0a 20 20 69 66 28 20  _ht);.  }.  if( 
0cf0: 6e 65 77 5f 73 69 7a 65 3d 3d 70 48 2d 3e 68 74  new_size==pH->ht
0d00: 73 69 7a 65 20 29 20 72 65 74 75 72 6e 3b 0a 23  size ) return;.#
0d10: 65 6e 64 69 66 0a 0a 20 20 2f 2a 20 54 68 65 72  endif..  /* Ther
0d20: 65 20 69 73 20 61 20 63 61 6c 6c 20 74 6f 20 73  e is a call to s
0d30: 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 29 20  qlite3_malloc() 
0d40: 69 6e 73 69 64 65 20 72 65 68 61 73 68 28 29 2e  inside rehash().
0d50: 20 49 66 20 74 68 65 72 65 20 69 73 0a 20 20 2a   If there is.  *
0d60: 2a 20 61 6c 72 65 61 64 79 20 61 6e 20 61 6c 6c  * already an all
0d70: 6f 63 61 74 69 6f 6e 20 61 74 20 70 48 2d 3e 68  ocation at pH->h
0d80: 74 2c 20 74 68 65 6e 20 69 66 20 74 68 69 73 20  t, then if this 
0d90: 6d 61 6c 6c 6f 63 28 29 20 66 61 69 6c 73 20 69  malloc() fails i
0da0: 74 0a 20 20 2a 2a 20 69 73 20 62 65 6e 69 67 6e  t.  ** is benign
0db0: 20 28 73 69 6e 63 65 20 66 61 69 6c 69 6e 67 20   (since failing 
0dc0: 74 6f 20 72 65 73 69 7a 65 20 61 20 68 61 73 68  to resize a hash
0dd0: 20 74 61 62 6c 65 20 69 73 20 61 20 70 65 72 66   table is a perf
0de0: 6f 72 6d 61 6e 63 65 0a 20 20 2a 2a 20 68 69 74  ormance.  ** hit
0df0: 20 6f 6e 6c 79 2c 20 6e 6f 74 20 61 20 66 61 74   only, not a fat
0e00: 61 6c 20 65 72 72 6f 72 29 2e 0a 20 20 2a 2f 0a  al error)..  */.
0e10: 20 20 69 66 28 20 70 48 2d 3e 68 74 73 69 7a 65    if( pH->htsize
0e20: 3e 30 20 29 20 73 71 6c 69 74 65 33 42 65 67 69  >0 ) sqlite3Begi
0e30: 6e 42 65 6e 69 67 6e 4d 61 6c 6c 6f 63 28 29 3b  nBenignMalloc();
0e40: 0a 20 20 6e 65 77 5f 68 74 20 3d 20 28 73 74 72  .  new_ht = (str
0e50: 75 63 74 20 5f 68 74 20 2a 29 73 71 6c 69 74 65  uct _ht *)sqlite
0e60: 33 4d 61 6c 6c 6f 63 5a 65 72 6f 28 20 6e 65 77  3MallocZero( new
0e70: 5f 73 69 7a 65 2a 73 69 7a 65 6f 66 28 73 74 72  _size*sizeof(str
0e80: 75 63 74 20 5f 68 74 29 20 29 3b 0a 20 20 69 66  uct _ht) );.  if
0e90: 28 20 70 48 2d 3e 68 74 73 69 7a 65 3e 30 20 29  ( pH->htsize>0 )
0ea0: 20 73 71 6c 69 74 65 33 45 6e 64 42 65 6e 69 67   sqlite3EndBenig
0eb0: 6e 4d 61 6c 6c 6f 63 28 29 3b 0a 0a 20 20 69 66  nMalloc();..  if
0ec0: 28 20 6e 65 77 5f 68 74 3d 3d 30 20 29 20 72 65  ( new_ht==0 ) re
0ed0: 74 75 72 6e 3b 0a 20 20 73 71 6c 69 74 65 33 5f  turn;.  sqlite3_
0ee0: 66 72 65 65 28 70 48 2d 3e 68 74 29 3b 0a 20 20  free(pH->ht);.  
0ef0: 70 48 2d 3e 68 74 20 3d 20 6e 65 77 5f 68 74 3b  pH->ht = new_ht;
0f00: 0a 20 20 70 48 2d 3e 68 74 73 69 7a 65 20 3d 20  .  pH->htsize = 
0f10: 6e 65 77 5f 73 69 7a 65 3b 0a 20 20 66 6f 72 28  new_size;.  for(
0f20: 65 6c 65 6d 3d 70 48 2d 3e 66 69 72 73 74 2c 20  elem=pH->first, 
0f30: 70 48 2d 3e 66 69 72 73 74 3d 30 3b 20 65 6c 65  pH->first=0; ele
0f40: 6d 3b 20 65 6c 65 6d 20 3d 20 6e 65 78 74 5f 65  m; elem = next_e
0f50: 6c 65 6d 29 7b 0a 20 20 20 20 69 6e 74 20 68 20  lem){.    int h 
0f60: 3d 20 73 74 72 48 61 73 68 28 65 6c 65 6d 2d 3e  = strHash(elem->
0f70: 70 4b 65 79 2c 20 65 6c 65 6d 2d 3e 6e 4b 65 79  pKey, elem->nKey
0f80: 29 20 26 20 28 6e 65 77 5f 73 69 7a 65 2d 31 29  ) & (new_size-1)
0f90: 3b 0a 20 20 20 20 6e 65 78 74 5f 65 6c 65 6d 20  ;.    next_elem 
0fa0: 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20  = elem->next;.  
0fb0: 20 20 69 6e 73 65 72 74 45 6c 65 6d 65 6e 74 28    insertElement(
0fc0: 70 48 2c 20 26 6e 65 77 5f 68 74 5b 68 5d 2c 20  pH, &new_ht[h], 
0fd0: 65 6c 65 6d 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a  elem);.  }.}../*
0fe0: 20 54 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 28   This function (
0ff0: 66 6f 72 20 69 6e 74 65 72 6e 61 6c 20 75 73 65  for internal use
1000: 20 6f 6e 6c 79 29 20 6c 6f 63 61 74 65 73 20 61   only) locates a
1010: 6e 20 65 6c 65 6d 65 6e 74 20 69 6e 20 61 6e 0a  n element in an.
1020: 2a 2a 20 68 61 73 68 20 74 61 62 6c 65 20 74 68  ** hash table th
1030: 61 74 20 6d 61 74 63 68 65 73 20 74 68 65 20 67  at matches the g
1040: 69 76 65 6e 20 6b 65 79 2e 20 20 54 68 65 20 68  iven key.  The h
1050: 61 73 68 20 66 6f 72 20 74 68 69 73 20 6b 65 79  ash for this key
1060: 20 68 61 73 0a 2a 2a 20 61 6c 72 65 61 64 79 20   has.** already 
1070: 62 65 65 6e 20 63 6f 6d 70 75 74 65 64 20 61 6e  been computed an
1080: 64 20 69 73 20 70 61 73 73 65 64 20 61 73 20 74  d is passed as t
1090: 68 65 20 34 74 68 20 70 61 72 61 6d 65 74 65 72  he 4th parameter
10a0: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 48 61 73 68  ..*/.static Hash
10b0: 45 6c 65 6d 20 2a 66 69 6e 64 45 6c 65 6d 65 6e  Elem *findElemen
10c0: 74 47 69 76 65 6e 48 61 73 68 28 0a 20 20 63 6f  tGivenHash(.  co
10d0: 6e 73 74 20 48 61 73 68 20 2a 70 48 2c 20 20 20  nst Hash *pH,   
10e0: 20 20 2f 2a 20 54 68 65 20 70 48 20 74 6f 20 62    /* The pH to b
10f0: 65 20 73 65 61 72 63 68 65 64 20 2a 2f 0a 20 20  e searched */.  
1100: 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79  const void *pKey
1110: 2c 20 20 20 2f 2a 20 54 68 65 20 6b 65 79 20 77  ,   /* The key w
1120: 65 20 61 72 65 20 73 65 61 72 63 68 69 6e 67 20  e are searching 
1130: 66 6f 72 20 2a 2f 0a 20 20 69 6e 74 20 6e 4b 65  for */.  int nKe
1140: 79 2c 0a 20 20 69 6e 74 20 68 20 20 20 20 20 20  y,.  int h      
1150: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20           /* The 
1160: 68 61 73 68 20 66 6f 72 20 74 68 69 73 20 6b 65  hash for this ke
1170: 79 2e 20 2a 2f 0a 29 7b 0a 20 20 48 61 73 68 45  y. */.){.  HashE
1180: 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 20 20  lem *elem;      
1190: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 55 73 65            /* Use
11a0: 64 20 74 6f 20 6c 6f 6f 70 20 74 68 72 75 20 74  d to loop thru t
11b0: 68 65 20 65 6c 65 6d 65 6e 74 20 6c 69 73 74 20  he element list 
11c0: 2a 2f 0a 20 20 69 6e 74 20 63 6f 75 6e 74 3b 20  */.  int count; 
11d0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
11e0: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66      /* Number of
11f0: 20 65 6c 65 6d 65 6e 74 73 20 6c 65 66 74 20 74   elements left t
1200: 6f 20 74 65 73 74 20 2a 2f 0a 0a 20 20 69 66 28  o test */..  if(
1210: 20 70 48 2d 3e 68 74 20 29 7b 0a 20 20 20 20 73   pH->ht ){.    s
1220: 74 72 75 63 74 20 5f 68 74 20 2a 70 45 6e 74 72  truct _ht *pEntr
1230: 79 20 3d 20 26 70 48 2d 3e 68 74 5b 68 5d 3b 0a  y = &pH->ht[h];.
1240: 20 20 20 20 65 6c 65 6d 20 3d 20 70 45 6e 74 72      elem = pEntr
1250: 79 2d 3e 63 68 61 69 6e 3b 0a 20 20 20 20 63 6f  y->chain;.    co
1260: 75 6e 74 20 3d 20 70 45 6e 74 72 79 2d 3e 63 6f  unt = pEntry->co
1270: 75 6e 74 3b 0a 20 20 20 20 77 68 69 6c 65 28 20  unt;.    while( 
1280: 63 6f 75 6e 74 2d 2d 20 26 26 20 65 6c 65 6d 20  count-- && elem 
1290: 29 7b 0a 20 20 20 20 20 20 69 66 28 20 73 74 72  ){.      if( str
12a0: 43 6f 6d 70 61 72 65 28 65 6c 65 6d 2d 3e 70 4b  Compare(elem->pK
12b0: 65 79 2c 65 6c 65 6d 2d 3e 6e 4b 65 79 2c 70 4b  ey,elem->nKey,pK
12c0: 65 79 2c 6e 4b 65 79 29 3d 3d 30 20 29 7b 20 0a  ey,nKey)==0 ){ .
12d0: 20 20 20 20 20 20 20 20 72 65 74 75 72 6e 20 65          return e
12e0: 6c 65 6d 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20  lem;.      }.   
12f0: 20 20 20 65 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e     elem = elem->
1300: 6e 65 78 74 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a  next;.    }.  }.
1310: 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a 0a 2f    return 0;.}../
1320: 2a 20 52 65 6d 6f 76 65 20 61 20 73 69 6e 67 6c  * Remove a singl
1330: 65 20 65 6e 74 72 79 20 66 72 6f 6d 20 74 68 65  e entry from the
1340: 20 68 61 73 68 20 74 61 62 6c 65 20 67 69 76 65   hash table give
1350: 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74  n a pointer to t
1360: 68 61 74 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 61  hat.** element a
1370: 6e 64 20 61 20 68 61 73 68 20 6f 6e 20 74 68 65  nd a hash on the
1380: 20 65 6c 65 6d 65 6e 74 27 73 20 6b 65 79 2e 0a   element's key..
1390: 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 72  */.static void r
13a0: 65 6d 6f 76 65 45 6c 65 6d 65 6e 74 47 69 76 65  emoveElementGive
13b0: 6e 48 61 73 68 28 0a 20 20 48 61 73 68 20 2a 70  nHash(.  Hash *p
13c0: 48 2c 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68  H,         /* Th
13d0: 65 20 70 48 20 63 6f 6e 74 61 69 6e 69 6e 67 20  e pH containing 
13e0: 22 65 6c 65 6d 22 20 2a 2f 0a 20 20 48 61 73 68  "elem" */.  Hash
13f0: 45 6c 65 6d 2a 20 65 6c 65 6d 2c 20 20 20 2f 2a  Elem* elem,   /*
1400: 20 54 68 65 20 65 6c 65 6d 65 6e 74 20 74 6f 20   The element to 
1410: 62 65 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20  be removed from 
1420: 74 68 65 20 70 48 20 2a 2f 0a 20 20 69 6e 74 20  the pH */.  int 
1430: 68 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a  h             /*
1440: 20 48 61 73 68 20 76 61 6c 75 65 20 66 6f 72 20   Hash value for 
1450: 74 68 65 20 65 6c 65 6d 65 6e 74 20 2a 2f 0a 29  the element */.)
1460: 7b 0a 20 20 73 74 72 75 63 74 20 5f 68 74 20 2a  {.  struct _ht *
1470: 70 45 6e 74 72 79 3b 0a 20 20 69 66 28 20 65 6c  pEntry;.  if( el
1480: 65 6d 2d 3e 70 72 65 76 20 29 7b 0a 20 20 20 20  em->prev ){.    
1490: 65 6c 65 6d 2d 3e 70 72 65 76 2d 3e 6e 65 78 74  elem->prev->next
14a0: 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 20 0a   = elem->next; .
14b0: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 70 48 2d    }else{.    pH-
14c0: 3e 66 69 72 73 74 20 3d 20 65 6c 65 6d 2d 3e 6e  >first = elem->n
14d0: 65 78 74 3b 0a 20 20 7d 0a 20 20 69 66 28 20 65  ext;.  }.  if( e
14e0: 6c 65 6d 2d 3e 6e 65 78 74 20 29 7b 0a 20 20 20  lem->next ){.   
14f0: 20 65 6c 65 6d 2d 3e 6e 65 78 74 2d 3e 70 72 65   elem->next->pre
1500: 76 20 3d 20 65 6c 65 6d 2d 3e 70 72 65 76 3b 0a  v = elem->prev;.
1510: 20 20 7d 0a 20 20 70 45 6e 74 72 79 20 3d 20 26    }.  pEntry = &
1520: 70 48 2d 3e 68 74 5b 68 5d 3b 0a 20 20 69 66 28  pH->ht[h];.  if(
1530: 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3d 3d   pEntry->chain==
1540: 65 6c 65 6d 20 29 7b 0a 20 20 20 20 70 45 6e 74  elem ){.    pEnt
1550: 72 79 2d 3e 63 68 61 69 6e 20 3d 20 65 6c 65 6d  ry->chain = elem
1560: 2d 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20 20 70 45  ->next;.  }.  pE
1570: 6e 74 72 79 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a 20  ntry->count--;. 
1580: 20 69 66 28 20 70 45 6e 74 72 79 2d 3e 63 6f 75   if( pEntry->cou
1590: 6e 74 3c 3d 30 20 29 7b 0a 20 20 20 20 70 45 6e  nt<=0 ){.    pEn
15a0: 74 72 79 2d 3e 63 68 61 69 6e 20 3d 20 30 3b 0a  try->chain = 0;.
15b0: 20 20 7d 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f    }.  if( pH->co
15c0: 70 79 4b 65 79 20 29 7b 0a 20 20 20 20 73 71 6c  pyKey ){.    sql
15d0: 69 74 65 33 5f 66 72 65 65 28 65 6c 65 6d 2d 3e  ite3_free(elem->
15e0: 70 4b 65 79 29 3b 0a 20 20 7d 0a 20 20 73 71 6c  pKey);.  }.  sql
15f0: 69 74 65 33 5f 66 72 65 65 28 20 65 6c 65 6d 20  ite3_free( elem 
1600: 29 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 2d 2d  );.  pH->count--
1610: 3b 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f 75 6e  ;.  if( pH->coun
1620: 74 3c 3d 30 20 29 7b 0a 20 20 20 20 61 73 73 65  t<=0 ){.    asse
1630: 72 74 28 20 70 48 2d 3e 66 69 72 73 74 3d 3d 30  rt( pH->first==0
1640: 20 29 3b 0a 20 20 20 20 61 73 73 65 72 74 28 20   );.    assert( 
1650: 70 48 2d 3e 63 6f 75 6e 74 3d 3d 30 20 29 3b 0a  pH->count==0 );.
1660: 20 20 20 20 73 71 6c 69 74 65 33 48 61 73 68 43      sqlite3HashC
1670: 6c 65 61 72 28 70 48 29 3b 0a 20 20 7d 0a 7d 0a  lear(pH);.  }.}.
1680: 0a 2f 2a 20 41 74 74 65 6d 70 74 20 74 6f 20 6c  ./* Attempt to l
1690: 6f 63 61 74 65 20 61 6e 20 65 6c 65 6d 65 6e 74  ocate an element
16a0: 20 6f 66 20 74 68 65 20 68 61 73 68 20 74 61 62   of the hash tab
16b0: 6c 65 20 70 48 20 77 69 74 68 20 61 20 6b 65 79  le pH with a key
16c0: 0a 2a 2a 20 74 68 61 74 20 6d 61 74 63 68 65 73  .** that matches
16d0: 20 70 4b 65 79 2c 6e 4b 65 79 2e 20 20 52 65 74   pKey,nKey.  Ret
16e0: 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f  urn a pointer to
16f0: 20 74 68 65 20 63 6f 72 72 65 73 70 6f 6e 64 69   the correspondi
1700: 6e 67 20 0a 2a 2a 20 48 61 73 68 45 6c 65 6d 20  ng .** HashElem 
1710: 73 74 72 75 63 74 75 72 65 20 66 6f 72 20 74 68  structure for th
1720: 69 73 20 65 6c 65 6d 65 6e 74 20 69 66 20 69 74  is element if it
1730: 20 69 73 20 66 6f 75 6e 64 2c 20 6f 72 20 4e 55   is found, or NU
1740: 4c 4c 0a 2a 2a 20 6f 74 68 65 72 77 69 73 65 2e  LL.** otherwise.
1750: 0a 2a 2f 0a 48 61 73 68 45 6c 65 6d 20 2a 73 71  .*/.HashElem *sq
1760: 6c 69 74 65 33 48 61 73 68 46 69 6e 64 45 6c 65  lite3HashFindEle
1770: 6d 28 63 6f 6e 73 74 20 48 61 73 68 20 2a 70 48  m(const Hash *pH
1780: 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b  , const void *pK
1790: 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20  ey, int nKey){. 
17a0: 20 69 6e 74 20 68 3b 20 20 20 20 20 20 20 20 20   int h;         
17b0: 20 20 20 20 2f 2a 20 41 20 68 61 73 68 20 6f 6e      /* A hash on
17c0: 20 6b 65 79 20 2a 2f 0a 20 20 48 61 73 68 45 6c   key */.  HashEl
17d0: 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 2f 2a 20  em *elem;    /* 
17e0: 54 68 65 20 65 6c 65 6d 65 6e 74 20 74 68 61 74  The element that
17f0: 20 6d 61 74 63 68 65 73 20 6b 65 79 20 2a 2f 0a   matches key */.
1800: 0a 20 20 69 66 28 20 70 48 3d 3d 30 20 7c 7c 20  .  if( pH==0 || 
1810: 70 48 2d 3e 68 74 3d 3d 30 20 29 20 72 65 74 75  pH->ht==0 ) retu
1820: 72 6e 20 30 3b 0a 20 20 68 20 3d 20 73 74 72 48  rn 0;.  h = strH
1830: 61 73 68 28 70 4b 65 79 2c 6e 4b 65 79 29 3b 0a  ash(pKey,nKey);.
1840: 20 20 65 6c 65 6d 20 3d 20 66 69 6e 64 45 6c 65    elem = findEle
1850: 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28 70 48  mentGivenHash(pH
1860: 2c 70 4b 65 79 2c 6e 4b 65 79 2c 20 68 20 25 20  ,pKey,nKey, h % 
1870: 70 48 2d 3e 68 74 73 69 7a 65 29 3b 0a 20 20 72  pH->htsize);.  r
1880: 65 74 75 72 6e 20 65 6c 65 6d 3b 0a 7d 0a 0a 2f  eturn elem;.}../
1890: 2a 20 41 74 74 65 6d 70 74 20 74 6f 20 6c 6f 63  * Attempt to loc
18a0: 61 74 65 20 61 6e 20 65 6c 65 6d 65 6e 74 20 6f  ate an element o
18b0: 66 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65  f the hash table
18c0: 20 70 48 20 77 69 74 68 20 61 20 6b 65 79 0a 2a   pH with a key.*
18d0: 2a 20 74 68 61 74 20 6d 61 74 63 68 65 73 20 70  * that matches p
18e0: 4b 65 79 2c 6e 4b 65 79 2e 20 20 52 65 74 75 72  Key,nKey.  Retur
18f0: 6e 20 74 68 65 20 64 61 74 61 20 66 6f 72 20 74  n the data for t
1900: 68 69 73 20 65 6c 65 6d 65 6e 74 20 69 66 20 69  his element if i
1910: 74 20 69 73 0a 2a 2a 20 66 6f 75 6e 64 2c 20 6f  t is.** found, o
1920: 72 20 4e 55 4c 4c 20 69 66 20 74 68 65 72 65 20  r NULL if there 
1930: 69 73 20 6e 6f 20 6d 61 74 63 68 2e 0a 2a 2f 0a  is no match..*/.
1940: 76 6f 69 64 20 2a 73 71 6c 69 74 65 33 48 61 73  void *sqlite3Has
1950: 68 46 69 6e 64 28 63 6f 6e 73 74 20 48 61 73 68  hFind(const Hash
1960: 20 2a 70 48 2c 20 63 6f 6e 73 74 20 76 6f 69 64   *pH, const void
1970: 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79   *pKey, int nKey
1980: 29 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65  ){.  HashElem *e
1990: 6c 65 6d 3b 20 20 20 20 2f 2a 20 54 68 65 20 65  lem;    /* The e
19a0: 6c 65 6d 65 6e 74 20 74 68 61 74 20 6d 61 74 63  lement that matc
19b0: 68 65 73 20 6b 65 79 20 2a 2f 0a 20 20 65 6c 65  hes key */.  ele
19c0: 6d 20 3d 20 73 71 6c 69 74 65 33 48 61 73 68 46  m = sqlite3HashF
19d0: 69 6e 64 45 6c 65 6d 28 70 48 2c 20 70 4b 65 79  indElem(pH, pKey
19e0: 2c 20 6e 4b 65 79 29 3b 0a 20 20 72 65 74 75 72  , nKey);.  retur
19f0: 6e 20 65 6c 65 6d 20 3f 20 65 6c 65 6d 2d 3e 64  n elem ? elem->d
1a00: 61 74 61 20 3a 20 30 3b 0a 7d 0a 0a 2f 2a 20 49  ata : 0;.}../* I
1a10: 6e 73 65 72 74 20 61 6e 20 65 6c 65 6d 65 6e 74  nsert an element
1a20: 20 69 6e 74 6f 20 74 68 65 20 68 61 73 68 20 74   into the hash t
1a30: 61 62 6c 65 20 70 48 2e 20 20 54 68 65 20 6b 65  able pH.  The ke
1a40: 79 20 69 73 20 70 4b 65 79 2c 6e 4b 65 79 0a 2a  y is pKey,nKey.*
1a50: 2a 20 61 6e 64 20 74 68 65 20 64 61 74 61 20 69  * and the data i
1a60: 73 20 22 64 61 74 61 22 2e 0a 2a 2a 0a 2a 2a 20  s "data"..**.** 
1a70: 49 66 20 6e 6f 20 65 6c 65 6d 65 6e 74 20 65 78  If no element ex
1a80: 69 73 74 73 20 77 69 74 68 20 61 20 6d 61 74 63  ists with a matc
1a90: 68 69 6e 67 20 6b 65 79 2c 20 74 68 65 6e 20 61  hing key, then a
1aa0: 20 6e 65 77 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20   new.** element 
1ab0: 69 73 20 63 72 65 61 74 65 64 2e 20 20 41 20 63  is created.  A c
1ac0: 6f 70 79 20 6f 66 20 74 68 65 20 6b 65 79 20 69  opy of the key i
1ad0: 73 20 6d 61 64 65 20 69 66 20 74 68 65 20 63 6f  s made if the co
1ae0: 70 79 4b 65 79 0a 2a 2a 20 66 6c 61 67 20 69 73  pyKey.** flag is
1af0: 20 73 65 74 2e 20 20 4e 55 4c 4c 20 69 73 20 72   set.  NULL is r
1b00: 65 74 75 72 6e 65 64 2e 0a 2a 2a 0a 2a 2a 20 49  eturned..**.** I
1b10: 66 20 61 6e 6f 74 68 65 72 20 65 6c 65 6d 65 6e  f another elemen
1b20: 74 20 61 6c 72 65 61 64 79 20 65 78 69 73 74 73  t already exists
1b30: 20 77 69 74 68 20 74 68 65 20 73 61 6d 65 20 6b   with the same k
1b40: 65 79 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20  ey, then the.** 
1b50: 6e 65 77 20 64 61 74 61 20 72 65 70 6c 61 63 65  new data replace
1b60: 73 20 74 68 65 20 6f 6c 64 20 64 61 74 61 20 61  s the old data a
1b70: 6e 64 20 74 68 65 20 6f 6c 64 20 64 61 74 61 20  nd the old data 
1b80: 69 73 20 72 65 74 75 72 6e 65 64 2e 0a 2a 2a 20  is returned..** 
1b90: 54 68 65 20 6b 65 79 20 69 73 20 6e 6f 74 20 63  The key is not c
1ba0: 6f 70 69 65 64 20 69 6e 20 74 68 69 73 20 69 6e  opied in this in
1bb0: 73 74 61 6e 63 65 2e 20 20 49 66 20 61 20 6d 61  stance.  If a ma
1bc0: 6c 6c 6f 63 20 66 61 69 6c 73 2c 20 74 68 65 6e  lloc fails, then
1bd0: 0a 2a 2a 20 74 68 65 20 6e 65 77 20 64 61 74 61  .** the new data
1be0: 20 69 73 20 72 65 74 75 72 6e 65 64 20 61 6e 64   is returned and
1bf0: 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20   the hash table 
1c00: 69 73 20 75 6e 63 68 61 6e 67 65 64 2e 0a 2a 2a  is unchanged..**
1c10: 0a 2a 2a 20 49 66 20 74 68 65 20 22 64 61 74 61  .** If the "data
1c20: 22 20 70 61 72 61 6d 65 74 65 72 20 74 6f 20 74  " parameter to t
1c30: 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 69 73 20  his function is 
1c40: 4e 55 4c 4c 2c 20 74 68 65 6e 20 74 68 65 0a 2a  NULL, then the.*
1c50: 2a 20 65 6c 65 6d 65 6e 74 20 63 6f 72 72 65 73  * element corres
1c60: 70 6f 6e 64 69 6e 67 20 74 6f 20 22 6b 65 79 22  ponding to "key"
1c70: 20 69 73 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d   is removed from
1c80: 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 2e   the hash table.
1c90: 0a 2a 2f 0a 76 6f 69 64 20 2a 73 71 6c 69 74 65  .*/.void *sqlite
1ca0: 33 48 61 73 68 49 6e 73 65 72 74 28 48 61 73 68  3HashInsert(Hash
1cb0: 20 2a 70 48 2c 20 63 6f 6e 73 74 20 76 6f 69 64   *pH, const void
1cc0: 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79   *pKey, int nKey
1cd0: 2c 20 76 6f 69 64 20 2a 64 61 74 61 29 7b 0a 20  , void *data){. 
1ce0: 20 69 6e 74 20 68 72 61 77 3b 20 20 20 20 20 20   int hraw;      
1cf0: 20 20 20 20 20 20 20 2f 2a 20 52 61 77 20 68 61         /* Raw ha
1d00: 73 68 20 76 61 6c 75 65 20 6f 66 20 74 68 65 20  sh value of the 
1d10: 6b 65 79 20 2a 2f 0a 20 20 69 6e 74 20 68 3b 20  key */.  int h; 
1d20: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
1d30: 2a 20 74 68 65 20 68 61 73 68 20 6f 66 20 74 68  * the hash of th
1d40: 65 20 6b 65 79 20 6d 6f 64 75 6c 6f 20 68 61 73  e key modulo has
1d50: 68 20 74 61 62 6c 65 20 73 69 7a 65 20 2a 2f 0a  h table size */.
1d60: 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d    HashElem *elem
1d70: 3b 20 20 20 20 20 20 20 2f 2a 20 55 73 65 64 20  ;       /* Used 
1d80: 74 6f 20 6c 6f 6f 70 20 74 68 72 75 20 74 68 65  to loop thru the
1d90: 20 65 6c 65 6d 65 6e 74 20 6c 69 73 74 20 2a 2f   element list */
1da0: 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 6e 65 77  .  HashElem *new
1db0: 5f 65 6c 65 6d 3b 20 20 20 2f 2a 20 4e 65 77 20  _elem;   /* New 
1dc0: 65 6c 65 6d 65 6e 74 20 61 64 64 65 64 20 74 6f  element added to
1dd0: 20 74 68 65 20 70 48 20 2a 2f 0a 0a 20 20 61 73   the pH */..  as
1de0: 73 65 72 74 28 20 70 48 21 3d 30 20 29 3b 0a 20  sert( pH!=0 );. 
1df0: 20 68 72 61 77 20 3d 20 73 74 72 48 61 73 68 28   hraw = strHash(
1e00: 70 4b 65 79 2c 20 6e 4b 65 79 29 3b 0a 20 20 69  pKey, nKey);.  i
1e10: 66 28 20 70 48 2d 3e 68 74 73 69 7a 65 20 29 7b  f( pH->htsize ){
1e20: 0a 20 20 20 20 68 20 3d 20 68 72 61 77 20 25 20  .    h = hraw % 
1e30: 70 48 2d 3e 68 74 73 69 7a 65 3b 0a 20 20 20 20  pH->htsize;.    
1e40: 65 6c 65 6d 20 3d 20 66 69 6e 64 45 6c 65 6d 65  elem = findEleme
1e50: 6e 74 47 69 76 65 6e 48 61 73 68 28 70 48 2c 70  ntGivenHash(pH,p
1e60: 4b 65 79 2c 6e 4b 65 79 2c 68 29 3b 0a 20 20 20  Key,nKey,h);.   
1e70: 20 69 66 28 20 65 6c 65 6d 20 29 7b 0a 20 20 20   if( elem ){.   
1e80: 20 20 20 76 6f 69 64 20 2a 6f 6c 64 5f 64 61 74     void *old_dat
1e90: 61 20 3d 20 65 6c 65 6d 2d 3e 64 61 74 61 3b 0a  a = elem->data;.
1ea0: 20 20 20 20 20 20 69 66 28 20 64 61 74 61 3d 3d        if( data==
1eb0: 30 20 29 7b 0a 20 20 20 20 20 20 20 20 72 65 6d  0 ){.        rem
1ec0: 6f 76 65 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48  oveElementGivenH
1ed0: 61 73 68 28 70 48 2c 65 6c 65 6d 2c 68 29 3b 0a  ash(pH,elem,h);.
1ee0: 20 20 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20        }else{.   
1ef0: 20 20 20 20 20 65 6c 65 6d 2d 3e 64 61 74 61 20       elem->data 
1f00: 3d 20 64 61 74 61 3b 0a 20 20 20 20 20 20 20 20  = data;.        
1f10: 69 66 28 20 21 70 48 2d 3e 63 6f 70 79 4b 65 79  if( !pH->copyKey
1f20: 20 29 7b 0a 20 20 20 20 20 20 20 20 20 20 65 6c   ){.          el
1f30: 65 6d 2d 3e 70 4b 65 79 20 3d 20 28 76 6f 69 64  em->pKey = (void
1f40: 20 2a 29 70 4b 65 79 3b 0a 20 20 20 20 20 20 20   *)pKey;.       
1f50: 20 7d 0a 20 20 20 20 20 20 20 20 61 73 73 65 72   }.        asser
1f60: 74 28 6e 4b 65 79 3d 3d 65 6c 65 6d 2d 3e 6e 4b  t(nKey==elem->nK
1f70: 65 79 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20  ey);.      }.   
1f80: 20 20 20 72 65 74 75 72 6e 20 6f 6c 64 5f 64 61     return old_da
1f90: 74 61 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20  ta;.    }.  }.  
1fa0: 69 66 28 20 64 61 74 61 3d 3d 30 20 29 20 72 65  if( data==0 ) re
1fb0: 74 75 72 6e 20 30 3b 0a 20 20 6e 65 77 5f 65 6c  turn 0;.  new_el
1fc0: 65 6d 20 3d 20 28 48 61 73 68 45 6c 65 6d 2a 29  em = (HashElem*)
1fd0: 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 28 20 73  sqlite3Malloc( s
1fe0: 69 7a 65 6f 66 28 48 61 73 68 45 6c 65 6d 29 20  izeof(HashElem) 
1ff0: 29 3b 0a 20 20 69 66 28 20 6e 65 77 5f 65 6c 65  );.  if( new_ele
2000: 6d 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 64 61  m==0 ) return da
2010: 74 61 3b 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f  ta;.  if( pH->co
2020: 70 79 4b 65 79 20 26 26 20 70 4b 65 79 21 3d 30  pyKey && pKey!=0
2030: 20 29 7b 0a 20 20 20 20 6e 65 77 5f 65 6c 65 6d   ){.    new_elem
2040: 2d 3e 70 4b 65 79 20 3d 20 73 71 6c 69 74 65 33  ->pKey = sqlite3
2050: 4d 61 6c 6c 6f 63 28 20 6e 4b 65 79 20 29 3b 0a  Malloc( nKey );.
2060: 20 20 20 20 69 66 28 20 6e 65 77 5f 65 6c 65 6d      if( new_elem
2070: 2d 3e 70 4b 65 79 3d 3d 30 20 29 7b 0a 20 20 20  ->pKey==0 ){.   
2080: 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28     sqlite3_free(
2090: 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20 20 20 20 20  new_elem);.     
20a0: 20 72 65 74 75 72 6e 20 64 61 74 61 3b 0a 20 20   return data;.  
20b0: 20 20 7d 0a 20 20 20 20 6d 65 6d 63 70 79 28 28    }.    memcpy((
20c0: 76 6f 69 64 2a 29 6e 65 77 5f 65 6c 65 6d 2d 3e  void*)new_elem->
20d0: 70 4b 65 79 2c 20 70 4b 65 79 2c 20 6e 4b 65 79  pKey, pKey, nKey
20e0: 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20  );.  }else{.    
20f0: 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 20 3d  new_elem->pKey =
2100: 20 28 76 6f 69 64 2a 29 70 4b 65 79 3b 0a 20 20   (void*)pKey;.  
2110: 7d 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 6e 4b  }.  new_elem->nK
2120: 65 79 20 3d 20 6e 4b 65 79 3b 0a 20 20 70 48 2d  ey = nKey;.  pH-
2130: 3e 63 6f 75 6e 74 2b 2b 3b 0a 20 20 69 66 28 20  >count++;.  if( 
2140: 70 48 2d 3e 68 74 73 69 7a 65 3d 3d 30 20 29 7b  pH->htsize==0 ){
2150: 0a 20 20 20 20 72 65 68 61 73 68 28 70 48 2c 20  .    rehash(pH, 
2160: 31 32 38 2f 73 69 7a 65 6f 66 28 70 48 2d 3e 68  128/sizeof(pH->h
2170: 74 5b 30 5d 29 29 3b 0a 20 20 20 20 69 66 28 20  t[0]));.    if( 
2180: 70 48 2d 3e 68 74 73 69 7a 65 3d 3d 30 20 29 7b  pH->htsize==0 ){
2190: 0a 20 20 20 20 20 20 70 48 2d 3e 63 6f 75 6e 74  .      pH->count
21a0: 20 3d 20 30 3b 0a 20 20 20 20 20 20 69 66 28 20   = 0;.      if( 
21b0: 70 48 2d 3e 63 6f 70 79 4b 65 79 20 29 7b 0a 20  pH->copyKey ){. 
21c0: 20 20 20 20 20 20 20 73 71 6c 69 74 65 33 5f 66         sqlite3_f
21d0: 72 65 65 28 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b  ree(new_elem->pK
21e0: 65 79 29 3b 0a 20 20 20 20 20 20 7d 0a 20 20 20  ey);.      }.   
21f0: 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28     sqlite3_free(
2200: 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20 20 20 20 20  new_elem);.     
2210: 20 72 65 74 75 72 6e 20 64 61 74 61 3b 0a 20 20   return data;.  
2220: 20 20 7d 0a 20 20 7d 0a 20 20 69 66 28 20 70 48    }.  }.  if( pH
2230: 2d 3e 63 6f 75 6e 74 20 3e 20 70 48 2d 3e 68 74  ->count > pH->ht
2240: 73 69 7a 65 20 29 7b 0a 20 20 20 20 72 65 68 61  size ){.    reha
2250: 73 68 28 70 48 2c 70 48 2d 3e 68 74 73 69 7a 65  sh(pH,pH->htsize
2260: 2a 32 29 3b 0a 20 20 7d 0a 20 20 61 73 73 65 72  *2);.  }.  asser
2270: 74 28 20 70 48 2d 3e 68 74 73 69 7a 65 3e 30 20  t( pH->htsize>0 
2280: 29 3b 0a 20 20 68 20 3d 20 68 72 61 77 20 25 20  );.  h = hraw % 
2290: 70 48 2d 3e 68 74 73 69 7a 65 3b 0a 20 20 69 6e  pH->htsize;.  in
22a0: 73 65 72 74 45 6c 65 6d 65 6e 74 28 70 48 2c 20  sertElement(pH, 
22b0: 26 70 48 2d 3e 68 74 5b 68 5d 2c 20 6e 65 77 5f  &pH->ht[h], new_
22c0: 65 6c 65 6d 29 3b 0a 20 20 6e 65 77 5f 65 6c 65  elem);.  new_ele
22d0: 6d 2d 3e 64 61 74 61 20 3d 20 64 61 74 61 3b 0a  m->data = data;.
22e0: 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a          return 0;.}.