/ Hex Artifact Content
Login

Artifact 582c00618efe2051785e66ba1b6430d5a129de3f:


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 31 20 32 30 30 38 2f 31 30 2f  ,v 1.31 2008/10/
01e0: 31 30 20 31 37 3a 34 31 3a 32 39 20 64 72 68 20  10 17:41:29 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 26 26  ( pH->copyKey &&
05d0: 20 65 6c 65 6d 2d 3e 70 4b 65 79 20 29 7b 0a 20   elem->pKey ){. 
05e0: 20 20 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65       sqlite3_fre
05f0: 65 28 65 6c 65 6d 2d 3e 70 4b 65 79 29 3b 0a 20  e(elem->pKey);. 
0600: 20 20 20 7d 0a 20 20 20 20 73 71 6c 69 74 65 33     }.    sqlite3
0610: 5f 66 72 65 65 28 65 6c 65 6d 29 3b 0a 20 20 20  _free(elem);.   
0620: 20 65 6c 65 6d 20 3d 20 6e 65 78 74 5f 65 6c 65   elem = next_ele
0630: 6d 3b 0a 20 20 7d 0a 20 20 70 48 2d 3e 63 6f 75  m;.  }.  pH->cou
0640: 6e 74 20 3d 20 30 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  nt = 0;.}../*.**
0650: 20 48 61 73 68 20 61 6e 64 20 63 6f 6d 70 61 72   Hash and compar
0660: 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 20 77  ison functions w
0670: 68 65 6e 20 74 68 65 20 6d 6f 64 65 20 69 73 20  hen the mode is 
0680: 53 51 4c 49 54 45 5f 48 41 53 48 5f 53 54 52 49  SQLITE_HASH_STRI
0690: 4e 47 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74  NG.*/.static int
06a0: 20 73 74 72 48 61 73 68 28 63 6f 6e 73 74 20 76   strHash(const v
06b0: 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e  oid *pKey, int n
06c0: 4b 65 79 29 7b 0a 20 20 63 6f 6e 73 74 20 63 68  Key){.  const ch
06d0: 61 72 20 2a 7a 20 3d 20 28 63 6f 6e 73 74 20 63  ar *z = (const c
06e0: 68 61 72 20 2a 29 70 4b 65 79 3b 0a 20 20 69 6e  har *)pKey;.  in
06f0: 74 20 68 20 3d 20 30 3b 0a 20 20 69 66 28 20 6e  t h = 0;.  if( n
0700: 4b 65 79 3c 3d 30 20 29 20 6e 4b 65 79 20 3d 20  Key<=0 ) nKey = 
0710: 73 74 72 6c 65 6e 28 7a 29 3b 0a 20 20 77 68 69  strlen(z);.  whi
0720: 6c 65 28 20 6e 4b 65 79 20 3e 20 30 20 20 29 7b  le( nKey > 0  ){
0730: 0a 20 20 20 20 68 20 3d 20 28 68 3c 3c 33 29 20  .    h = (h<<3) 
0740: 5e 20 68 20 5e 20 73 71 6c 69 74 65 33 55 70 70  ^ h ^ sqlite3Upp
0750: 65 72 54 6f 4c 6f 77 65 72 5b 28 75 6e 73 69 67  erToLower[(unsig
0760: 6e 65 64 20 63 68 61 72 29 2a 7a 2b 2b 5d 3b 0a  ned char)*z++];.
0770: 20 20 20 20 6e 4b 65 79 2d 2d 3b 0a 20 20 7d 0a      nKey--;.  }.
0780: 20 20 72 65 74 75 72 6e 20 68 20 26 20 30 78 37    return h & 0x7
0790: 66 66 66 66 66 66 66 3b 0a 7d 0a 73 74 61 74 69  fffffff;.}.stati
07a0: 63 20 69 6e 74 20 73 74 72 43 6f 6d 70 61 72 65  c int strCompare
07b0: 28 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65  (const void *pKe
07c0: 79 31 2c 20 69 6e 74 20 6e 31 2c 20 63 6f 6e 73  y1, int n1, cons
07d0: 74 20 76 6f 69 64 20 2a 70 4b 65 79 32 2c 20 69  t void *pKey2, i
07e0: 6e 74 20 6e 32 29 7b 0a 20 20 69 66 28 20 6e 31  nt n2){.  if( n1
07f0: 21 3d 6e 32 20 29 20 72 65 74 75 72 6e 20 31 3b  !=n2 ) return 1;
0800: 0a 20 20 72 65 74 75 72 6e 20 73 71 6c 69 74 65  .  return sqlite
0810: 33 53 74 72 4e 49 43 6d 70 28 28 63 6f 6e 73 74  3StrNICmp((const
0820: 20 63 68 61 72 2a 29 70 4b 65 79 31 2c 28 63 6f   char*)pKey1,(co
0830: 6e 73 74 20 63 68 61 72 2a 29 70 4b 65 79 32 2c  nst char*)pKey2,
0840: 6e 31 29 3b 0a 7d 0a 0a 0a 2f 2a 20 4c 69 6e 6b  n1);.}.../* Link
0850: 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69 6e 74 6f   an element into
0860: 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 0a   the hash table.
0870: 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20 69  */.static void i
0880: 6e 73 65 72 74 45 6c 65 6d 65 6e 74 28 0a 20 20  nsertElement(.  
0890: 48 61 73 68 20 2a 70 48 2c 20 20 20 20 20 20 20  Hash *pH,       
08a0: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 63 6f         /* The co
08b0: 6d 70 6c 65 74 65 20 68 61 73 68 20 74 61 62 6c  mplete hash tabl
08c0: 65 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 5f 68  e */.  struct _h
08d0: 74 20 2a 70 45 6e 74 72 79 2c 20 20 20 20 2f 2a  t *pEntry,    /*
08e0: 20 54 68 65 20 65 6e 74 72 79 20 69 6e 74 6f 20   The entry into 
08f0: 77 68 69 63 68 20 70 4e 65 77 20 69 73 20 69 6e  which pNew is in
0900: 73 65 72 74 65 64 20 2a 2f 0a 20 20 48 61 73 68  serted */.  Hash
0910: 45 6c 65 6d 20 2a 70 4e 65 77 20 20 20 20 20 20  Elem *pNew      
0920: 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e     /* The elemen
0930: 74 20 74 6f 20 62 65 20 69 6e 73 65 72 74 65 64  t to be inserted
0940: 20 2a 2f 0a 29 7b 0a 20 20 48 61 73 68 45 6c 65   */.){.  HashEle
0950: 6d 20 2a 70 48 65 61 64 3b 20 20 20 20 20 20 20  m *pHead;       
0960: 2f 2a 20 46 69 72 73 74 20 65 6c 65 6d 65 6e 74  /* First element
0970: 20 61 6c 72 65 61 64 79 20 69 6e 20 70 45 6e 74   already in pEnt
0980: 72 79 20 2a 2f 0a 20 20 70 48 65 61 64 20 3d 20  ry */.  pHead = 
0990: 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3b 0a 20  pEntry->chain;. 
09a0: 20 69 66 28 20 70 48 65 61 64 20 29 7b 0a 20 20   if( pHead ){.  
09b0: 20 20 70 4e 65 77 2d 3e 6e 65 78 74 20 3d 20 70    pNew->next = p
09c0: 48 65 61 64 3b 0a 20 20 20 20 70 4e 65 77 2d 3e  Head;.    pNew->
09d0: 70 72 65 76 20 3d 20 70 48 65 61 64 2d 3e 70 72  prev = pHead->pr
09e0: 65 76 3b 0a 20 20 20 20 69 66 28 20 70 48 65 61  ev;.    if( pHea
09f0: 64 2d 3e 70 72 65 76 20 29 7b 20 70 48 65 61 64  d->prev ){ pHead
0a00: 2d 3e 70 72 65 76 2d 3e 6e 65 78 74 20 3d 20 70  ->prev->next = p
0a10: 4e 65 77 3b 20 7d 0a 20 20 20 20 65 6c 73 65 20  New; }.    else 
0a20: 20 20 20 20 20 20 20 20 20 20 20 20 7b 20 70 48              { pH
0a30: 2d 3e 66 69 72 73 74 20 3d 20 70 4e 65 77 3b 20  ->first = pNew; 
0a40: 7d 0a 20 20 20 20 70 48 65 61 64 2d 3e 70 72 65  }.    pHead->pre
0a50: 76 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 65 6c 73  v = pNew;.  }els
0a60: 65 7b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 65 78  e{.    pNew->nex
0a70: 74 20 3d 20 70 48 2d 3e 66 69 72 73 74 3b 0a 20  t = pH->first;. 
0a80: 20 20 20 69 66 28 20 70 48 2d 3e 66 69 72 73 74     if( pH->first
0a90: 20 29 7b 20 70 48 2d 3e 66 69 72 73 74 2d 3e 70   ){ pH->first->p
0aa0: 72 65 76 20 3d 20 70 4e 65 77 3b 20 7d 0a 20 20  rev = pNew; }.  
0ab0: 20 20 70 4e 65 77 2d 3e 70 72 65 76 20 3d 20 30    pNew->prev = 0
0ac0: 3b 0a 20 20 20 20 70 48 2d 3e 66 69 72 73 74 20  ;.    pH->first 
0ad0: 3d 20 70 4e 65 77 3b 0a 20 20 7d 0a 20 20 70 45  = pNew;.  }.  pE
0ae0: 6e 74 72 79 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20  ntry->count++;. 
0af0: 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 20 3d   pEntry->chain =
0b00: 20 70 4e 65 77 3b 0a 7d 0a 0a 0a 2f 2a 20 52 65   pNew;.}.../* Re
0b10: 73 69 7a 65 20 74 68 65 20 68 61 73 68 20 74 61  size the hash ta
0b20: 62 6c 65 20 73 6f 20 74 68 61 74 20 69 74 20 63  ble so that it c
0b30: 61 6e 74 61 69 6e 73 20 22 6e 65 77 5f 73 69 7a  antains "new_siz
0b40: 65 22 20 62 75 63 6b 65 74 73 2e 0a 2a 2a 20 22  e" buckets..** "
0b50: 6e 65 77 5f 73 69 7a 65 22 20 6d 75 73 74 20 62  new_size" must b
0b60: 65 20 61 20 70 6f 77 65 72 20 6f 66 20 32 2e 20  e a power of 2. 
0b70: 20 54 68 65 20 68 61 73 68 20 74 61 62 6c 65 20   The hash table 
0b80: 6d 69 67 68 74 20 66 61 69 6c 20 0a 2a 2a 20 74  might fail .** t
0b90: 6f 20 72 65 73 69 7a 65 20 69 66 20 73 71 6c 69  o resize if sqli
0ba0: 74 65 33 5f 6d 61 6c 6c 6f 63 28 29 20 66 61 69  te3_malloc() fai
0bb0: 6c 73 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f  ls..*/.static vo
0bc0: 69 64 20 72 65 68 61 73 68 28 48 61 73 68 20 2a  id rehash(Hash *
0bd0: 70 48 2c 20 69 6e 74 20 6e 65 77 5f 73 69 7a 65  pH, int new_size
0be0: 29 7b 0a 20 20 73 74 72 75 63 74 20 5f 68 74 20  ){.  struct _ht 
0bf0: 2a 6e 65 77 5f 68 74 3b 20 20 20 20 20 20 20 20  *new_ht;        
0c00: 20 20 20 20 2f 2a 20 54 68 65 20 6e 65 77 20 68      /* The new h
0c10: 61 73 68 20 74 61 62 6c 65 20 2a 2f 0a 20 20 48  ash table */.  H
0c20: 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 2c 20 2a  ashElem *elem, *
0c30: 6e 65 78 74 5f 65 6c 65 6d 3b 20 20 20 20 2f 2a  next_elem;    /*
0c40: 20 46 6f 72 20 6c 6f 6f 70 69 6e 67 20 6f 76 65   For looping ove
0c50: 72 20 65 78 69 73 74 69 6e 67 20 65 6c 65 6d 65  r existing eleme
0c60: 6e 74 73 20 2a 2f 0a 0a 23 69 66 64 65 66 20 53  nts */..#ifdef S
0c70: 51 4c 49 54 45 5f 4d 41 4c 4c 4f 43 5f 53 4f 46  QLITE_MALLOC_SOF
0c80: 54 5f 4c 49 4d 49 54 0a 20 20 69 66 28 20 6e 65  T_LIMIT.  if( ne
0c90: 77 5f 73 69 7a 65 2a 73 69 7a 65 6f 66 28 73 74  w_size*sizeof(st
0ca0: 72 75 63 74 20 5f 68 74 29 3e 53 51 4c 49 54 45  ruct _ht)>SQLITE
0cb0: 5f 4d 41 4c 4c 4f 43 5f 53 4f 46 54 5f 4c 49 4d  _MALLOC_SOFT_LIM
0cc0: 49 54 20 29 7b 0a 20 20 20 20 6e 65 77 5f 73 69  IT ){.    new_si
0cd0: 7a 65 20 3d 20 53 51 4c 49 54 45 5f 4d 41 4c 4c  ze = SQLITE_MALL
0ce0: 4f 43 5f 53 4f 46 54 5f 4c 49 4d 49 54 2f 73 69  OC_SOFT_LIMIT/si
0cf0: 7a 65 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29  zeof(struct _ht)
0d00: 3b 0a 20 20 7d 0a 20 20 69 66 28 20 6e 65 77 5f  ;.  }.  if( new_
0d10: 73 69 7a 65 3d 3d 70 48 2d 3e 68 74 73 69 7a 65  size==pH->htsize
0d20: 20 29 20 72 65 74 75 72 6e 3b 0a 23 65 6e 64 69   ) return;.#endi
0d30: 66 0a 0a 20 20 2f 2a 20 54 68 65 72 65 20 69 73  f..  /* There is
0d40: 20 61 20 63 61 6c 6c 20 74 6f 20 73 71 6c 69 74   a call to sqlit
0d50: 65 33 5f 6d 61 6c 6c 6f 63 28 29 20 69 6e 73 69  e3_malloc() insi
0d60: 64 65 20 72 65 68 61 73 68 28 29 2e 20 49 66 20  de rehash(). If 
0d70: 74 68 65 72 65 20 69 73 0a 20 20 2a 2a 20 61 6c  there is.  ** al
0d80: 72 65 61 64 79 20 61 6e 20 61 6c 6c 6f 63 61 74  ready an allocat
0d90: 69 6f 6e 20 61 74 20 70 48 2d 3e 68 74 2c 20 74  ion at pH->ht, t
0da0: 68 65 6e 20 69 66 20 74 68 69 73 20 6d 61 6c 6c  hen if this mall
0db0: 6f 63 28 29 20 66 61 69 6c 73 20 69 74 0a 20 20  oc() fails it.  
0dc0: 2a 2a 20 69 73 20 62 65 6e 69 67 6e 20 28 73 69  ** is benign (si
0dd0: 6e 63 65 20 66 61 69 6c 69 6e 67 20 74 6f 20 72  nce failing to r
0de0: 65 73 69 7a 65 20 61 20 68 61 73 68 20 74 61 62  esize a hash tab
0df0: 6c 65 20 69 73 20 61 20 70 65 72 66 6f 72 6d 61  le is a performa
0e00: 6e 63 65 0a 20 20 2a 2a 20 68 69 74 20 6f 6e 6c  nce.  ** hit onl
0e10: 79 2c 20 6e 6f 74 20 61 20 66 61 74 61 6c 20 65  y, not a fatal e
0e20: 72 72 6f 72 29 2e 0a 20 20 2a 2f 0a 20 20 69 66  rror)..  */.  if
0e30: 28 20 70 48 2d 3e 68 74 73 69 7a 65 3e 30 20 29  ( pH->htsize>0 )
0e40: 20 73 71 6c 69 74 65 33 42 65 67 69 6e 42 65 6e   sqlite3BeginBen
0e50: 69 67 6e 4d 61 6c 6c 6f 63 28 29 3b 0a 20 20 6e  ignMalloc();.  n
0e60: 65 77 5f 68 74 20 3d 20 28 73 74 72 75 63 74 20  ew_ht = (struct 
0e70: 5f 68 74 20 2a 29 73 71 6c 69 74 65 33 4d 61 6c  _ht *)sqlite3Mal
0e80: 6c 6f 63 5a 65 72 6f 28 20 6e 65 77 5f 73 69 7a  locZero( new_siz
0e90: 65 2a 73 69 7a 65 6f 66 28 73 74 72 75 63 74 20  e*sizeof(struct 
0ea0: 5f 68 74 29 20 29 3b 0a 20 20 69 66 28 20 70 48  _ht) );.  if( pH
0eb0: 2d 3e 68 74 73 69 7a 65 3e 30 20 29 20 73 71 6c  ->htsize>0 ) sql
0ec0: 69 74 65 33 45 6e 64 42 65 6e 69 67 6e 4d 61 6c  ite3EndBenignMal
0ed0: 6c 6f 63 28 29 3b 0a 0a 20 20 69 66 28 20 6e 65  loc();..  if( ne
0ee0: 77 5f 68 74 3d 3d 30 20 29 20 72 65 74 75 72 6e  w_ht==0 ) return
0ef0: 3b 0a 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65  ;.  sqlite3_free
0f00: 28 70 48 2d 3e 68 74 29 3b 0a 20 20 70 48 2d 3e  (pH->ht);.  pH->
0f10: 68 74 20 3d 20 6e 65 77 5f 68 74 3b 0a 20 20 70  ht = new_ht;.  p
0f20: 48 2d 3e 68 74 73 69 7a 65 20 3d 20 6e 65 77 5f  H->htsize = new_
0f30: 73 69 7a 65 3b 0a 20 20 66 6f 72 28 65 6c 65 6d  size;.  for(elem
0f40: 3d 70 48 2d 3e 66 69 72 73 74 2c 20 70 48 2d 3e  =pH->first, pH->
0f50: 66 69 72 73 74 3d 30 3b 20 65 6c 65 6d 3b 20 65  first=0; elem; e
0f60: 6c 65 6d 20 3d 20 6e 65 78 74 5f 65 6c 65 6d 29  lem = next_elem)
0f70: 7b 0a 20 20 20 20 69 6e 74 20 68 20 3d 20 73 74  {.    int h = st
0f80: 72 48 61 73 68 28 65 6c 65 6d 2d 3e 70 4b 65 79  rHash(elem->pKey
0f90: 2c 20 65 6c 65 6d 2d 3e 6e 4b 65 79 29 20 26 20  , elem->nKey) & 
0fa0: 28 6e 65 77 5f 73 69 7a 65 2d 31 29 3b 0a 20 20  (new_size-1);.  
0fb0: 20 20 6e 65 78 74 5f 65 6c 65 6d 20 3d 20 65 6c    next_elem = el
0fc0: 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 69 6e  em->next;.    in
0fd0: 73 65 72 74 45 6c 65 6d 65 6e 74 28 70 48 2c 20  sertElement(pH, 
0fe0: 26 6e 65 77 5f 68 74 5b 68 5d 2c 20 65 6c 65 6d  &new_ht[h], elem
0ff0: 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 20 54 68 69  );.  }.}../* Thi
1000: 73 20 66 75 6e 63 74 69 6f 6e 20 28 66 6f 72 20  s function (for 
1010: 69 6e 74 65 72 6e 61 6c 20 75 73 65 20 6f 6e 6c  internal use onl
1020: 79 29 20 6c 6f 63 61 74 65 73 20 61 6e 20 65 6c  y) locates an el
1030: 65 6d 65 6e 74 20 69 6e 20 61 6e 0a 2a 2a 20 68  ement in an.** h
1040: 61 73 68 20 74 61 62 6c 65 20 74 68 61 74 20 6d  ash table that m
1050: 61 74 63 68 65 73 20 74 68 65 20 67 69 76 65 6e  atches the given
1060: 20 6b 65 79 2e 20 20 54 68 65 20 68 61 73 68 20   key.  The hash 
1070: 66 6f 72 20 74 68 69 73 20 6b 65 79 20 68 61 73  for this key has
1080: 0a 2a 2a 20 61 6c 72 65 61 64 79 20 62 65 65 6e  .** already been
1090: 20 63 6f 6d 70 75 74 65 64 20 61 6e 64 20 69 73   computed and is
10a0: 20 70 61 73 73 65 64 20 61 73 20 74 68 65 20 34   passed as the 4
10b0: 74 68 20 70 61 72 61 6d 65 74 65 72 2e 0a 2a 2f  th parameter..*/
10c0: 0a 73 74 61 74 69 63 20 48 61 73 68 45 6c 65 6d  .static HashElem
10d0: 20 2a 66 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76   *findElementGiv
10e0: 65 6e 48 61 73 68 28 0a 20 20 63 6f 6e 73 74 20  enHash(.  const 
10f0: 48 61 73 68 20 2a 70 48 2c 20 20 20 20 20 2f 2a  Hash *pH,     /*
1100: 20 54 68 65 20 70 48 20 74 6f 20 62 65 20 73 65   The pH to be se
1110: 61 72 63 68 65 64 20 2a 2f 0a 20 20 63 6f 6e 73  arched */.  cons
1120: 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 20 20  t void *pKey,   
1130: 2f 2a 20 54 68 65 20 6b 65 79 20 77 65 20 61 72  /* The key we ar
1140: 65 20 73 65 61 72 63 68 69 6e 67 20 66 6f 72 20  e searching for 
1150: 2a 2f 0a 20 20 69 6e 74 20 6e 4b 65 79 2c 0a 20  */.  int nKey,. 
1160: 20 69 6e 74 20 68 20 20 20 20 20 20 20 20 20 20   int h          
1170: 20 20 20 20 20 2f 2a 20 54 68 65 20 68 61 73 68       /* The hash
1180: 20 66 6f 72 20 74 68 69 73 20 6b 65 79 2e 20 2a   for this key. *
1190: 2f 0a 29 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20  /.){.  HashElem 
11a0: 2a 65 6c 65 6d 3b 20 20 20 20 20 20 20 20 20 20  *elem;          
11b0: 20 20 20 20 20 20 2f 2a 20 55 73 65 64 20 74 6f        /* Used to
11c0: 20 6c 6f 6f 70 20 74 68 72 75 20 74 68 65 20 65   loop thru the e
11d0: 6c 65 6d 65 6e 74 20 6c 69 73 74 20 2a 2f 0a 20  lement list */. 
11e0: 20 69 6e 74 20 63 6f 75 6e 74 3b 20 20 20 20 20   int count;     
11f0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1200: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65 6c 65  /* Number of ele
1210: 6d 65 6e 74 73 20 6c 65 66 74 20 74 6f 20 74 65  ments left to te
1220: 73 74 20 2a 2f 0a 0a 20 20 69 66 28 20 70 48 2d  st */..  if( pH-
1230: 3e 68 74 20 29 7b 0a 20 20 20 20 73 74 72 75 63  >ht ){.    struc
1240: 74 20 5f 68 74 20 2a 70 45 6e 74 72 79 20 3d 20  t _ht *pEntry = 
1250: 26 70 48 2d 3e 68 74 5b 68 5d 3b 0a 20 20 20 20  &pH->ht[h];.    
1260: 65 6c 65 6d 20 3d 20 70 45 6e 74 72 79 2d 3e 63  elem = pEntry->c
1270: 68 61 69 6e 3b 0a 20 20 20 20 63 6f 75 6e 74 20  hain;.    count 
1280: 3d 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 3b  = pEntry->count;
1290: 0a 20 20 20 20 77 68 69 6c 65 28 20 63 6f 75 6e  .    while( coun
12a0: 74 2d 2d 20 26 26 20 65 6c 65 6d 20 29 7b 0a 20  t-- && elem ){. 
12b0: 20 20 20 20 20 69 66 28 20 73 74 72 43 6f 6d 70       if( strComp
12c0: 61 72 65 28 65 6c 65 6d 2d 3e 70 4b 65 79 2c 65  are(elem->pKey,e
12d0: 6c 65 6d 2d 3e 6e 4b 65 79 2c 70 4b 65 79 2c 6e  lem->nKey,pKey,n
12e0: 4b 65 79 29 3d 3d 30 20 29 7b 20 0a 20 20 20 20  Key)==0 ){ .    
12f0: 20 20 20 20 72 65 74 75 72 6e 20 65 6c 65 6d 3b      return elem;
1300: 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 65  .      }.      e
1310: 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74  lem = elem->next
1320: 3b 0a 20 20 20 20 7d 0a 20 20 7d 0a 20 20 72 65  ;.    }.  }.  re
1330: 74 75 72 6e 20 30 3b 0a 7d 0a 0a 2f 2a 20 52 65  turn 0;.}../* Re
1340: 6d 6f 76 65 20 61 20 73 69 6e 67 6c 65 20 65 6e  move a single en
1350: 74 72 79 20 66 72 6f 6d 20 74 68 65 20 68 61 73  try from the has
1360: 68 20 74 61 62 6c 65 20 67 69 76 65 6e 20 61 20  h table given a 
1370: 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 61 74 0a  pointer to that.
1380: 2a 2a 20 65 6c 65 6d 65 6e 74 20 61 6e 64 20 61  ** element and a
1390: 20 68 61 73 68 20 6f 6e 20 74 68 65 20 65 6c 65   hash on the ele
13a0: 6d 65 6e 74 27 73 20 6b 65 79 2e 0a 2a 2f 0a 73  ment's key..*/.s
13b0: 74 61 74 69 63 20 76 6f 69 64 20 72 65 6d 6f 76  tatic void remov
13c0: 65 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61 73  eElementGivenHas
13d0: 68 28 0a 20 20 48 61 73 68 20 2a 70 48 2c 20 20  h(.  Hash *pH,  
13e0: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 70 48         /* The pH
13f0: 20 63 6f 6e 74 61 69 6e 69 6e 67 20 22 65 6c 65   containing "ele
1400: 6d 22 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d  m" */.  HashElem
1410: 2a 20 65 6c 65 6d 2c 20 20 20 2f 2a 20 54 68 65  * elem,   /* The
1420: 20 65 6c 65 6d 65 6e 74 20 74 6f 20 62 65 20 72   element to be r
1430: 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74 68 65 20  emoved from the 
1440: 70 48 20 2a 2f 0a 20 20 69 6e 74 20 68 20 20 20  pH */.  int h   
1450: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 48 61 73            /* Has
1460: 68 20 76 61 6c 75 65 20 66 6f 72 20 74 68 65 20  h value for the 
1470: 65 6c 65 6d 65 6e 74 20 2a 2f 0a 29 7b 0a 20 20  element */.){.  
1480: 73 74 72 75 63 74 20 5f 68 74 20 2a 70 45 6e 74  struct _ht *pEnt
1490: 72 79 3b 0a 20 20 69 66 28 20 65 6c 65 6d 2d 3e  ry;.  if( elem->
14a0: 70 72 65 76 20 29 7b 0a 20 20 20 20 65 6c 65 6d  prev ){.    elem
14b0: 2d 3e 70 72 65 76 2d 3e 6e 65 78 74 20 3d 20 65  ->prev->next = e
14c0: 6c 65 6d 2d 3e 6e 65 78 74 3b 20 0a 20 20 7d 65  lem->next; .  }e
14d0: 6c 73 65 7b 0a 20 20 20 20 70 48 2d 3e 66 69 72  lse{.    pH->fir
14e0: 73 74 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b  st = elem->next;
14f0: 0a 20 20 7d 0a 20 20 69 66 28 20 65 6c 65 6d 2d  .  }.  if( elem-
1500: 3e 6e 65 78 74 20 29 7b 0a 20 20 20 20 65 6c 65  >next ){.    ele
1510: 6d 2d 3e 6e 65 78 74 2d 3e 70 72 65 76 20 3d 20  m->next->prev = 
1520: 65 6c 65 6d 2d 3e 70 72 65 76 3b 0a 20 20 7d 0a  elem->prev;.  }.
1530: 20 20 70 45 6e 74 72 79 20 3d 20 26 70 48 2d 3e    pEntry = &pH->
1540: 68 74 5b 68 5d 3b 0a 20 20 69 66 28 20 70 45 6e  ht[h];.  if( pEn
1550: 74 72 79 2d 3e 63 68 61 69 6e 3d 3d 65 6c 65 6d  try->chain==elem
1560: 20 29 7b 0a 20 20 20 20 70 45 6e 74 72 79 2d 3e   ){.    pEntry->
1570: 63 68 61 69 6e 20 3d 20 65 6c 65 6d 2d 3e 6e 65  chain = elem->ne
1580: 78 74 3b 0a 20 20 7d 0a 20 20 70 45 6e 74 72 79  xt;.  }.  pEntry
1590: 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a 20 20 69 66 28  ->count--;.  if(
15a0: 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 3c 3d   pEntry->count<=
15b0: 30 20 29 7b 0a 20 20 20 20 70 45 6e 74 72 79 2d  0 ){.    pEntry-
15c0: 3e 63 68 61 69 6e 20 3d 20 30 3b 0a 20 20 7d 0a  >chain = 0;.  }.
15d0: 20 20 69 66 28 20 70 48 2d 3e 63 6f 70 79 4b 65    if( pH->copyKe
15e0: 79 20 29 7b 0a 20 20 20 20 73 71 6c 69 74 65 33  y ){.    sqlite3
15f0: 5f 66 72 65 65 28 65 6c 65 6d 2d 3e 70 4b 65 79  _free(elem->pKey
1600: 29 3b 0a 20 20 7d 0a 20 20 73 71 6c 69 74 65 33  );.  }.  sqlite3
1610: 5f 66 72 65 65 28 20 65 6c 65 6d 20 29 3b 0a 20  _free( elem );. 
1620: 20 70 48 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a 20 20   pH->count--;.  
1630: 69 66 28 20 70 48 2d 3e 63 6f 75 6e 74 3c 3d 30  if( pH->count<=0
1640: 20 29 7b 0a 20 20 20 20 61 73 73 65 72 74 28 20   ){.    assert( 
1650: 70 48 2d 3e 66 69 72 73 74 3d 3d 30 20 29 3b 0a  pH->first==0 );.
1660: 20 20 20 20 61 73 73 65 72 74 28 20 70 48 2d 3e      assert( pH->
1670: 63 6f 75 6e 74 3d 3d 30 20 29 3b 0a 20 20 20 20  count==0 );.    
1680: 73 71 6c 69 74 65 33 48 61 73 68 43 6c 65 61 72  sqlite3HashClear
1690: 28 70 48 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 20  (pH);.  }.}../* 
16a0: 41 74 74 65 6d 70 74 20 74 6f 20 6c 6f 63 61 74  Attempt to locat
16b0: 65 20 61 6e 20 65 6c 65 6d 65 6e 74 20 6f 66 20  e an element of 
16c0: 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 70  the hash table p
16d0: 48 20 77 69 74 68 20 61 20 6b 65 79 0a 2a 2a 20  H with a key.** 
16e0: 74 68 61 74 20 6d 61 74 63 68 65 73 20 70 4b 65  that matches pKe
16f0: 79 2c 6e 4b 65 79 2e 20 20 52 65 74 75 72 6e 20  y,nKey.  Return 
1700: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65  a pointer to the
1710: 20 63 6f 72 72 65 73 70 6f 6e 64 69 6e 67 20 0a   corresponding .
1720: 2a 2a 20 48 61 73 68 45 6c 65 6d 20 73 74 72 75  ** HashElem stru
1730: 63 74 75 72 65 20 66 6f 72 20 74 68 69 73 20 65  cture for this e
1740: 6c 65 6d 65 6e 74 20 69 66 20 69 74 20 69 73 20  lement if it is 
1750: 66 6f 75 6e 64 2c 20 6f 72 20 4e 55 4c 4c 0a 2a  found, or NULL.*
1760: 2a 20 6f 74 68 65 72 77 69 73 65 2e 0a 2a 2f 0a  * otherwise..*/.
1770: 48 61 73 68 45 6c 65 6d 20 2a 73 71 6c 69 74 65  HashElem *sqlite
1780: 33 48 61 73 68 46 69 6e 64 45 6c 65 6d 28 63 6f  3HashFindElem(co
1790: 6e 73 74 20 48 61 73 68 20 2a 70 48 2c 20 63 6f  nst Hash *pH, co
17a0: 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20  nst void *pKey, 
17b0: 69 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 69 6e 74  int nKey){.  int
17c0: 20 68 3b 20 20 20 20 20 20 20 20 20 20 20 20 20   h;             
17d0: 2f 2a 20 41 20 68 61 73 68 20 6f 6e 20 6b 65 79  /* A hash on key
17e0: 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a   */.  HashElem *
17f0: 65 6c 65 6d 3b 20 20 20 20 2f 2a 20 54 68 65 20  elem;    /* The 
1800: 65 6c 65 6d 65 6e 74 20 74 68 61 74 20 6d 61 74  element that mat
1810: 63 68 65 73 20 6b 65 79 20 2a 2f 0a 0a 20 20 69  ches key */..  i
1820: 66 28 20 70 48 3d 3d 30 20 7c 7c 20 70 48 2d 3e  f( pH==0 || pH->
1830: 68 74 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 30  ht==0 ) return 0
1840: 3b 0a 20 20 68 20 3d 20 73 74 72 48 61 73 68 28  ;.  h = strHash(
1850: 70 4b 65 79 2c 6e 4b 65 79 29 3b 0a 20 20 65 6c  pKey,nKey);.  el
1860: 65 6d 20 3d 20 66 69 6e 64 45 6c 65 6d 65 6e 74  em = findElement
1870: 47 69 76 65 6e 48 61 73 68 28 70 48 2c 70 4b 65  GivenHash(pH,pKe
1880: 79 2c 6e 4b 65 79 2c 20 68 20 25 20 70 48 2d 3e  y,nKey, h % pH->
1890: 68 74 73 69 7a 65 29 3b 0a 20 20 72 65 74 75 72  htsize);.  retur
18a0: 6e 20 65 6c 65 6d 3b 0a 7d 0a 0a 2f 2a 20 41 74  n elem;.}../* At
18b0: 74 65 6d 70 74 20 74 6f 20 6c 6f 63 61 74 65 20  tempt to locate 
18c0: 61 6e 20 65 6c 65 6d 65 6e 74 20 6f 66 20 74 68  an element of th
18d0: 65 20 68 61 73 68 20 74 61 62 6c 65 20 70 48 20  e hash table pH 
18e0: 77 69 74 68 20 61 20 6b 65 79 0a 2a 2a 20 74 68  with a key.** th
18f0: 61 74 20 6d 61 74 63 68 65 73 20 70 4b 65 79 2c  at matches pKey,
1900: 6e 4b 65 79 2e 20 20 52 65 74 75 72 6e 20 74 68  nKey.  Return th
1910: 65 20 64 61 74 61 20 66 6f 72 20 74 68 69 73 20  e data for this 
1920: 65 6c 65 6d 65 6e 74 20 69 66 20 69 74 20 69 73  element if it is
1930: 0a 2a 2a 20 66 6f 75 6e 64 2c 20 6f 72 20 4e 55  .** found, or NU
1940: 4c 4c 20 69 66 20 74 68 65 72 65 20 69 73 20 6e  LL if there is n
1950: 6f 20 6d 61 74 63 68 2e 0a 2a 2f 0a 76 6f 69 64  o match..*/.void
1960: 20 2a 73 71 6c 69 74 65 33 48 61 73 68 46 69 6e   *sqlite3HashFin
1970: 64 28 63 6f 6e 73 74 20 48 61 73 68 20 2a 70 48  d(const Hash *pH
1980: 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b  , const void *pK
1990: 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20  ey, int nKey){. 
19a0: 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b   HashElem *elem;
19b0: 20 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65      /* The eleme
19c0: 6e 74 20 74 68 61 74 20 6d 61 74 63 68 65 73 20  nt that matches 
19d0: 6b 65 79 20 2a 2f 0a 20 20 65 6c 65 6d 20 3d 20  key */.  elem = 
19e0: 73 71 6c 69 74 65 33 48 61 73 68 46 69 6e 64 45  sqlite3HashFindE
19f0: 6c 65 6d 28 70 48 2c 20 70 4b 65 79 2c 20 6e 4b  lem(pH, pKey, nK
1a00: 65 79 29 3b 0a 20 20 72 65 74 75 72 6e 20 65 6c  ey);.  return el
1a10: 65 6d 20 3f 20 65 6c 65 6d 2d 3e 64 61 74 61 20  em ? elem->data 
1a20: 3a 20 30 3b 0a 7d 0a 0a 2f 2a 20 49 6e 73 65 72  : 0;.}../* Inser
1a30: 74 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69 6e 74  t an element int
1a40: 6f 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65  o the hash table
1a50: 20 70 48 2e 20 20 54 68 65 20 6b 65 79 20 69 73   pH.  The key is
1a60: 20 70 4b 65 79 2c 6e 4b 65 79 0a 2a 2a 20 61 6e   pKey,nKey.** an
1a70: 64 20 74 68 65 20 64 61 74 61 20 69 73 20 22 64  d the data is "d
1a80: 61 74 61 22 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 6e  ata"..**.** If n
1a90: 6f 20 65 6c 65 6d 65 6e 74 20 65 78 69 73 74 73  o element exists
1aa0: 20 77 69 74 68 20 61 20 6d 61 74 63 68 69 6e 67   with a matching
1ab0: 20 6b 65 79 2c 20 74 68 65 6e 20 61 20 6e 65 77   key, then a new
1ac0: 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 69 73 20 63  .** element is c
1ad0: 72 65 61 74 65 64 2e 20 20 41 20 63 6f 70 79 20  reated.  A copy 
1ae0: 6f 66 20 74 68 65 20 6b 65 79 20 69 73 20 6d 61  of the key is ma
1af0: 64 65 20 69 66 20 74 68 65 20 63 6f 70 79 4b 65  de if the copyKe
1b00: 79 0a 2a 2a 20 66 6c 61 67 20 69 73 20 73 65 74  y.** flag is set
1b10: 2e 20 20 4e 55 4c 4c 20 69 73 20 72 65 74 75 72  .  NULL is retur
1b20: 6e 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 61 6e  ned..**.** If an
1b30: 6f 74 68 65 72 20 65 6c 65 6d 65 6e 74 20 61 6c  other element al
1b40: 72 65 61 64 79 20 65 78 69 73 74 73 20 77 69 74  ready exists wit
1b50: 68 20 74 68 65 20 73 61 6d 65 20 6b 65 79 2c 20  h the same key, 
1b60: 74 68 65 6e 20 74 68 65 0a 2a 2a 20 6e 65 77 20  then the.** new 
1b70: 64 61 74 61 20 72 65 70 6c 61 63 65 73 20 74 68  data replaces th
1b80: 65 20 6f 6c 64 20 64 61 74 61 20 61 6e 64 20 74  e old data and t
1b90: 68 65 20 6f 6c 64 20 64 61 74 61 20 69 73 20 72  he old data is r
1ba0: 65 74 75 72 6e 65 64 2e 0a 2a 2a 20 54 68 65 20  eturned..** The 
1bb0: 6b 65 79 20 69 73 20 6e 6f 74 20 63 6f 70 69 65  key is not copie
1bc0: 64 20 69 6e 20 74 68 69 73 20 69 6e 73 74 61 6e  d in this instan
1bd0: 63 65 2e 20 20 49 66 20 61 20 6d 61 6c 6c 6f 63  ce.  If a malloc
1be0: 20 66 61 69 6c 73 2c 20 74 68 65 6e 0a 2a 2a 20   fails, then.** 
1bf0: 74 68 65 20 6e 65 77 20 64 61 74 61 20 69 73 20  the new data is 
1c00: 72 65 74 75 72 6e 65 64 20 61 6e 64 20 74 68 65  returned and the
1c10: 20 68 61 73 68 20 74 61 62 6c 65 20 69 73 20 75   hash table is u
1c20: 6e 63 68 61 6e 67 65 64 2e 0a 2a 2a 0a 2a 2a 20  nchanged..**.** 
1c30: 49 66 20 74 68 65 20 22 64 61 74 61 22 20 70 61  If the "data" pa
1c40: 72 61 6d 65 74 65 72 20 74 6f 20 74 68 69 73 20  rameter to this 
1c50: 66 75 6e 63 74 69 6f 6e 20 69 73 20 4e 55 4c 4c  function is NULL
1c60: 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20 65 6c  , then the.** el
1c70: 65 6d 65 6e 74 20 63 6f 72 72 65 73 70 6f 6e 64  ement correspond
1c80: 69 6e 67 20 74 6f 20 22 6b 65 79 22 20 69 73 20  ing to "key" is 
1c90: 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74 68 65  removed from the
1ca0: 20 68 61 73 68 20 74 61 62 6c 65 2e 0a 2a 2f 0a   hash table..*/.
1cb0: 76 6f 69 64 20 2a 73 71 6c 69 74 65 33 48 61 73  void *sqlite3Has
1cc0: 68 49 6e 73 65 72 74 28 48 61 73 68 20 2a 70 48  hInsert(Hash *pH
1cd0: 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b  , const void *pK
1ce0: 65 79 2c 20 69 6e 74 20 6e 4b 65 79 2c 20 76 6f  ey, int nKey, vo
1cf0: 69 64 20 2a 64 61 74 61 29 7b 0a 20 20 69 6e 74  id *data){.  int
1d00: 20 68 72 61 77 3b 20 20 20 20 20 20 20 20 20 20   hraw;          
1d10: 20 20 20 2f 2a 20 52 61 77 20 68 61 73 68 20 76     /* Raw hash v
1d20: 61 6c 75 65 20 6f 66 20 74 68 65 20 6b 65 79 20  alue of the key 
1d30: 2a 2f 0a 20 20 69 6e 74 20 68 3b 20 20 20 20 20  */.  int h;     
1d40: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 74 68             /* th
1d50: 65 20 68 61 73 68 20 6f 66 20 74 68 65 20 6b 65  e hash of the ke
1d60: 79 20 6d 6f 64 75 6c 6f 20 68 61 73 68 20 74 61  y modulo hash ta
1d70: 62 6c 65 20 73 69 7a 65 20 2a 2f 0a 20 20 48 61  ble size */.  Ha
1d80: 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20  shElem *elem;   
1d90: 20 20 20 20 2f 2a 20 55 73 65 64 20 74 6f 20 6c      /* Used to l
1da0: 6f 6f 70 20 74 68 72 75 20 74 68 65 20 65 6c 65  oop thru the ele
1db0: 6d 65 6e 74 20 6c 69 73 74 20 2a 2f 0a 20 20 48  ment list */.  H
1dc0: 61 73 68 45 6c 65 6d 20 2a 6e 65 77 5f 65 6c 65  ashElem *new_ele
1dd0: 6d 3b 20 20 20 2f 2a 20 4e 65 77 20 65 6c 65 6d  m;   /* New elem
1de0: 65 6e 74 20 61 64 64 65 64 20 74 6f 20 74 68 65  ent added to the
1df0: 20 70 48 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74   pH */..  assert
1e00: 28 20 70 48 21 3d 30 20 29 3b 0a 20 20 68 72 61  ( pH!=0 );.  hra
1e10: 77 20 3d 20 73 74 72 48 61 73 68 28 70 4b 65 79  w = strHash(pKey
1e20: 2c 20 6e 4b 65 79 29 3b 0a 20 20 69 66 28 20 70  , nKey);.  if( p
1e30: 48 2d 3e 68 74 73 69 7a 65 20 29 7b 0a 20 20 20  H->htsize ){.   
1e40: 20 68 20 3d 20 68 72 61 77 20 25 20 70 48 2d 3e   h = hraw % pH->
1e50: 68 74 73 69 7a 65 3b 0a 20 20 20 20 65 6c 65 6d  htsize;.    elem
1e60: 20 3d 20 66 69 6e 64 45 6c 65 6d 65 6e 74 47 69   = findElementGi
1e70: 76 65 6e 48 61 73 68 28 70 48 2c 70 4b 65 79 2c  venHash(pH,pKey,
1e80: 6e 4b 65 79 2c 68 29 3b 0a 20 20 20 20 69 66 28  nKey,h);.    if(
1e90: 20 65 6c 65 6d 20 29 7b 0a 20 20 20 20 20 20 76   elem ){.      v
1ea0: 6f 69 64 20 2a 6f 6c 64 5f 64 61 74 61 20 3d 20  oid *old_data = 
1eb0: 65 6c 65 6d 2d 3e 64 61 74 61 3b 0a 20 20 20 20  elem->data;.    
1ec0: 20 20 69 66 28 20 64 61 74 61 3d 3d 30 20 29 7b    if( data==0 ){
1ed0: 0a 20 20 20 20 20 20 20 20 72 65 6d 6f 76 65 45  .        removeE
1ee0: 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28  lementGivenHash(
1ef0: 70 48 2c 65 6c 65 6d 2c 68 29 3b 0a 20 20 20 20  pH,elem,h);.    
1f00: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20 20    }else{.       
1f10: 20 65 6c 65 6d 2d 3e 64 61 74 61 20 3d 20 64 61   elem->data = da
1f20: 74 61 3b 0a 20 20 20 20 20 20 20 20 69 66 28 20  ta;.        if( 
1f30: 21 70 48 2d 3e 63 6f 70 79 4b 65 79 20 29 7b 0a  !pH->copyKey ){.
1f40: 20 20 20 20 20 20 20 20 20 20 65 6c 65 6d 2d 3e            elem->
1f50: 70 4b 65 79 20 3d 20 28 76 6f 69 64 20 2a 29 70  pKey = (void *)p
1f60: 4b 65 79 3b 0a 20 20 20 20 20 20 20 20 7d 0a 20  Key;.        }. 
1f70: 20 20 20 20 20 20 20 61 73 73 65 72 74 28 6e 4b         assert(nK
1f80: 65 79 3d 3d 65 6c 65 6d 2d 3e 6e 4b 65 79 29 3b  ey==elem->nKey);
1f90: 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 72  .      }.      r
1fa0: 65 74 75 72 6e 20 6f 6c 64 5f 64 61 74 61 3b 0a  eturn old_data;.
1fb0: 20 20 20 20 7d 0a 20 20 7d 0a 20 20 69 66 28 20      }.  }.  if( 
1fc0: 64 61 74 61 3d 3d 30 20 29 20 72 65 74 75 72 6e  data==0 ) return
1fd0: 20 30 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 20 3d   0;.  new_elem =
1fe0: 20 28 48 61 73 68 45 6c 65 6d 2a 29 73 71 6c 69   (HashElem*)sqli
1ff0: 74 65 33 4d 61 6c 6c 6f 63 28 20 73 69 7a 65 6f  te3Malloc( sizeo
2000: 66 28 48 61 73 68 45 6c 65 6d 29 20 29 3b 0a 20  f(HashElem) );. 
2010: 20 69 66 28 20 6e 65 77 5f 65 6c 65 6d 3d 3d 30   if( new_elem==0
2020: 20 29 20 72 65 74 75 72 6e 20 64 61 74 61 3b 0a   ) return data;.
2030: 20 20 69 66 28 20 70 48 2d 3e 63 6f 70 79 4b 65    if( pH->copyKe
2040: 79 20 26 26 20 70 4b 65 79 21 3d 30 20 29 7b 0a  y && pKey!=0 ){.
2050: 20 20 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b      new_elem->pK
2060: 65 79 20 3d 20 73 71 6c 69 74 65 33 4d 61 6c 6c  ey = sqlite3Mall
2070: 6f 63 28 20 6e 4b 65 79 20 29 3b 0a 20 20 20 20  oc( nKey );.    
2080: 69 66 28 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b  if( new_elem->pK
2090: 65 79 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 73  ey==0 ){.      s
20a0: 71 6c 69 74 65 33 5f 66 72 65 65 28 6e 65 77 5f  qlite3_free(new_
20b0: 65 6c 65 6d 29 3b 0a 20 20 20 20 20 20 72 65 74  elem);.      ret
20c0: 75 72 6e 20 64 61 74 61 3b 0a 20 20 20 20 7d 0a  urn data;.    }.
20d0: 20 20 20 20 6d 65 6d 63 70 79 28 28 76 6f 69 64      memcpy((void
20e0: 2a 29 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79  *)new_elem->pKey
20f0: 2c 20 70 4b 65 79 2c 20 6e 4b 65 79 29 3b 0a 20  , pKey, nKey);. 
2100: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 6e 65 77 5f   }else{.    new_
2110: 65 6c 65 6d 2d 3e 70 4b 65 79 20 3d 20 28 76 6f  elem->pKey = (vo
2120: 69 64 2a 29 70 4b 65 79 3b 0a 20 20 7d 0a 20 20  id*)pKey;.  }.  
2130: 6e 65 77 5f 65 6c 65 6d 2d 3e 6e 4b 65 79 20 3d  new_elem->nKey =
2140: 20 6e 4b 65 79 3b 0a 20 20 70 48 2d 3e 63 6f 75   nKey;.  pH->cou
2150: 6e 74 2b 2b 3b 0a 20 20 69 66 28 20 70 48 2d 3e  nt++;.  if( pH->
2160: 68 74 73 69 7a 65 3d 3d 30 20 29 7b 0a 20 20 20  htsize==0 ){.   
2170: 20 72 65 68 61 73 68 28 70 48 2c 20 31 32 38 2f   rehash(pH, 128/
2180: 73 69 7a 65 6f 66 28 70 48 2d 3e 68 74 5b 30 5d  sizeof(pH->ht[0]
2190: 29 29 3b 0a 20 20 20 20 69 66 28 20 70 48 2d 3e  ));.    if( pH->
21a0: 68 74 73 69 7a 65 3d 3d 30 20 29 7b 0a 20 20 20  htsize==0 ){.   
21b0: 20 20 20 70 48 2d 3e 63 6f 75 6e 74 20 3d 20 30     pH->count = 0
21c0: 3b 0a 20 20 20 20 20 20 69 66 28 20 70 48 2d 3e  ;.      if( pH->
21d0: 63 6f 70 79 4b 65 79 20 29 7b 0a 20 20 20 20 20  copyKey ){.     
21e0: 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28     sqlite3_free(
21f0: 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 29 3b  new_elem->pKey);
2200: 0a 20 20 20 20 20 20 7d 0a 20 20 20 20 20 20 73  .      }.      s
2210: 71 6c 69 74 65 33 5f 66 72 65 65 28 6e 65 77 5f  qlite3_free(new_
2220: 65 6c 65 6d 29 3b 0a 20 20 20 20 20 20 72 65 74  elem);.      ret
2230: 75 72 6e 20 64 61 74 61 3b 0a 20 20 20 20 7d 0a  urn data;.    }.
2240: 20 20 7d 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f    }.  if( pH->co
2250: 75 6e 74 20 3e 20 70 48 2d 3e 68 74 73 69 7a 65  unt > pH->htsize
2260: 20 29 7b 0a 20 20 20 20 72 65 68 61 73 68 28 70   ){.    rehash(p
2270: 48 2c 70 48 2d 3e 68 74 73 69 7a 65 2a 32 29 3b  H,pH->htsize*2);
2280: 0a 20 20 7d 0a 20 20 61 73 73 65 72 74 28 20 70  .  }.  assert( p
2290: 48 2d 3e 68 74 73 69 7a 65 3e 30 20 29 3b 0a 20  H->htsize>0 );. 
22a0: 20 68 20 3d 20 68 72 61 77 20 25 20 70 48 2d 3e   h = hraw % pH->
22b0: 68 74 73 69 7a 65 3b 0a 20 20 69 6e 73 65 72 74  htsize;.  insert
22c0: 45 6c 65 6d 65 6e 74 28 70 48 2c 20 26 70 48 2d  Element(pH, &pH-
22d0: 3e 68 74 5b 68 5d 2c 20 6e 65 77 5f 65 6c 65 6d  >ht[h], new_elem
22e0: 29 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 64  );.  new_elem->d
22f0: 61 74 61 20 3d 20 64 61 74 61 3b 0a 20 20 72 65  ata = data;.  re
2300: 74 75 72 6e 20 30 3b 0a 7d 0a                    turn 0;.}.