SQLite
Hex Artifact Content
Not logged in

Artifact 55b5fb474100cee0b901edaf203e26c970940f36:


0000: 2f 2a 0a 2a 2a 20 32 30 30 31 20 53 65 70 74 65  /*.** 2001 Septe
0010: 6d 62 65 72 20 32 32 0a 2a 2a 0a 2a 2a 20 54 68  mber 22.**.** Th
0020: 65 20 61 75 74 68 6f 72 20 64 69 73 63 6c 61 69  e author disclai
0030: 6d 73 20 63 6f 70 79 72 69 67 68 74 20 74 6f 20  ms copyright to 
0040: 74 68 69 73 20 73 6f 75 72 63 65 20 63 6f 64 65  this source code
0050: 2e 20 20 49 6e 20 70 6c 61 63 65 20 6f 66 0a 2a  .  In place of.*
0060: 2a 20 61 20 6c 65 67 61 6c 20 6e 6f 74 69 63 65  * a legal notice
0070: 2c 20 68 65 72 65 20 69 73 20 61 20 62 6c 65 73  , here is a bles
0080: 73 69 6e 67 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 4d  sing:.**.**    M
0090: 61 79 20 79 6f 75 20 64 6f 20 67 6f 6f 64 20 61  ay you do good a
00a0: 6e 64 20 6e 6f 74 20 65 76 69 6c 2e 0a 2a 2a 20  nd not evil..** 
00b0: 20 20 20 4d 61 79 20 79 6f 75 20 66 69 6e 64 20     May you find 
00c0: 66 6f 72 67 69 76 65 6e 65 73 73 20 66 6f 72 20  forgiveness for 
00d0: 79 6f 75 72 73 65 6c 66 20 61 6e 64 20 66 6f 72  yourself and for
00e0: 67 69 76 65 20 6f 74 68 65 72 73 2e 0a 2a 2a 20  give others..** 
00f0: 20 20 20 4d 61 79 20 79 6f 75 20 73 68 61 72 65     May you share
0100: 20 66 72 65 65 6c 79 2c 20 6e 65 76 65 72 20 74   freely, never t
0110: 61 6b 69 6e 67 20 6d 6f 72 65 20 74 68 61 6e 20  aking more than 
0120: 79 6f 75 20 67 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a  you give..**.***
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0170: 2a 2a 2a 2a 2a 2a 0a 2a 2a 20 54 68 69 73 20 69  ******.** This i
0180: 73 20 74 68 65 20 69 6d 70 6c 65 6d 65 6e 74 61  s the implementa
0190: 74 69 6f 6e 20 6f 66 20 67 65 6e 65 72 69 63 20  tion of generic 
01a0: 68 61 73 68 2d 74 61 62 6c 65 73 0a 2a 2a 20 75  hash-tables.** u
01b0: 73 65 64 20 69 6e 20 53 51 4c 69 74 65 2e 0a 2a  sed in SQLite..*
01c0: 2f 0a 23 69 6e 63 6c 75 64 65 20 22 73 71 6c 69  /.#include "sqli
01d0: 74 65 49 6e 74 2e 68 22 0a 23 69 6e 63 6c 75 64  teInt.h".#includ
01e0: 65 20 3c 61 73 73 65 72 74 2e 68 3e 0a 0a 2f 2a  e <assert.h>../*
01f0: 20 54 75 72 6e 20 62 75 6c 6b 20 6d 65 6d 6f 72   Turn bulk memor
0200: 79 20 69 6e 74 6f 20 61 20 68 61 73 68 20 74 61  y into a hash ta
0210: 62 6c 65 20 6f 62 6a 65 63 74 20 62 79 20 69 6e  ble object by in
0220: 69 74 69 61 6c 69 7a 69 6e 67 20 74 68 65 0a 2a  itializing the.*
0230: 2a 20 66 69 65 6c 64 73 20 6f 66 20 74 68 65 20  * fields of the 
0240: 48 61 73 68 20 73 74 72 75 63 74 75 72 65 2e 0a  Hash structure..
0250: 2a 2a 0a 2a 2a 20 22 70 4e 65 77 22 20 69 73 20  **.** "pNew" is 
0260: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65  a pointer to the
0270: 20 68 61 73 68 20 74 61 62 6c 65 20 74 68 61 74   hash table that
0280: 20 69 73 20 74 6f 20 62 65 20 69 6e 69 74 69 61   is to be initia
0290: 6c 69 7a 65 64 2e 0a 2a 2f 0a 76 6f 69 64 20 73  lized..*/.void s
02a0: 71 6c 69 74 65 33 48 61 73 68 49 6e 69 74 28 48  qlite3HashInit(H
02b0: 61 73 68 20 2a 70 4e 65 77 29 7b 0a 20 20 61 73  ash *pNew){.  as
02c0: 73 65 72 74 28 20 70 4e 65 77 21 3d 30 20 29 3b  sert( pNew!=0 );
02d0: 0a 20 20 70 4e 65 77 2d 3e 66 69 72 73 74 20 3d  .  pNew->first =
02e0: 20 30 3b 0a 20 20 70 4e 65 77 2d 3e 63 6f 75 6e   0;.  pNew->coun
02f0: 74 20 3d 20 30 3b 0a 20 20 70 4e 65 77 2d 3e 68  t = 0;.  pNew->h
0300: 74 73 69 7a 65 20 3d 20 30 3b 0a 20 20 70 4e 65  tsize = 0;.  pNe
0310: 77 2d 3e 68 74 20 3d 20 30 3b 0a 7d 0a 0a 2f 2a  w->ht = 0;.}../*
0320: 20 52 65 6d 6f 76 65 20 61 6c 6c 20 65 6e 74 72   Remove all entr
0330: 69 65 73 20 66 72 6f 6d 20 61 20 68 61 73 68 20  ies from a hash 
0340: 74 61 62 6c 65 2e 20 20 52 65 63 6c 61 69 6d 20  table.  Reclaim 
0350: 61 6c 6c 20 6d 65 6d 6f 72 79 2e 0a 2a 2a 20 43  all memory..** C
0360: 61 6c 6c 20 74 68 69 73 20 72 6f 75 74 69 6e 65  all this routine
0370: 20 74 6f 20 64 65 6c 65 74 65 20 61 20 68 61 73   to delete a has
0380: 68 20 74 61 62 6c 65 20 6f 72 20 74 6f 20 72 65  h table or to re
0390: 73 65 74 20 61 20 68 61 73 68 20 74 61 62 6c 65  set a hash table
03a0: 0a 2a 2a 20 74 6f 20 74 68 65 20 65 6d 70 74 79  .** to the empty
03b0: 20 73 74 61 74 65 2e 0a 2a 2f 0a 76 6f 69 64 20   state..*/.void 
03c0: 73 71 6c 69 74 65 33 48 61 73 68 43 6c 65 61 72  sqlite3HashClear
03d0: 28 48 61 73 68 20 2a 70 48 29 7b 0a 20 20 48 61  (Hash *pH){.  Ha
03e0: 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20  shElem *elem;   
03f0: 20 20 20 20 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f        /* For loo
0400: 70 69 6e 67 20 6f 76 65 72 20 61 6c 6c 20 65 6c  ping over all el
0410: 65 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 74 61  ements of the ta
0420: 62 6c 65 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74  ble */..  assert
0430: 28 20 70 48 21 3d 30 20 29 3b 0a 20 20 65 6c 65  ( pH!=0 );.  ele
0440: 6d 20 3d 20 70 48 2d 3e 66 69 72 73 74 3b 0a 20  m = pH->first;. 
0450: 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 30 3b 0a   pH->first = 0;.
0460: 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70    sqlite3_free(p
0470: 48 2d 3e 68 74 29 3b 0a 20 20 70 48 2d 3e 68 74  H->ht);.  pH->ht
0480: 20 3d 20 30 3b 0a 20 20 70 48 2d 3e 68 74 73 69   = 0;.  pH->htsi
0490: 7a 65 20 3d 20 30 3b 0a 20 20 77 68 69 6c 65 28  ze = 0;.  while(
04a0: 20 65 6c 65 6d 20 29 7b 0a 20 20 20 20 48 61 73   elem ){.    Has
04b0: 68 45 6c 65 6d 20 2a 6e 65 78 74 5f 65 6c 65 6d  hElem *next_elem
04c0: 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20   = elem->next;. 
04d0: 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28     sqlite3_free(
04e0: 65 6c 65 6d 29 3b 0a 20 20 20 20 65 6c 65 6d 20  elem);.    elem 
04f0: 3d 20 6e 65 78 74 5f 65 6c 65 6d 3b 0a 20 20 7d  = next_elem;.  }
0500: 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 20 3d 20 30  .  pH->count = 0
0510: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 68  ;.}../*.** The h
0520: 61 73 68 69 6e 67 20 66 75 6e 63 74 69 6f 6e 2e  ashing function.
0530: 0a 2a 2f 0a 73 74 61 74 69 63 20 75 6e 73 69 67  .*/.static unsig
0540: 6e 65 64 20 69 6e 74 20 73 74 72 48 61 73 68 28  ned int strHash(
0550: 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a 29 7b 0a  const char *z){.
0560: 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 68    unsigned int h
0570: 20 3d 20 30 3b 0a 20 20 75 6e 73 69 67 6e 65 64   = 0;.  unsigned
0580: 20 63 68 61 72 20 63 3b 0a 20 20 77 68 69 6c 65   char c;.  while
0590: 28 20 28 63 20 3d 20 28 75 6e 73 69 67 6e 65 64  ( (c = (unsigned
05a0: 20 63 68 61 72 29 2a 7a 2b 2b 29 21 3d 30 20 29   char)*z++)!=0 )
05b0: 7b 20 20 20 20 20 2f 2a 4f 50 54 49 4d 49 5a 41  {     /*OPTIMIZA
05c0: 54 49 4f 4e 2d 49 46 2d 54 52 55 45 2a 2f 0a 20  TION-IF-TRUE*/. 
05d0: 20 20 20 68 20 3d 20 28 68 3c 3c 33 29 20 5e 20     h = (h<<3) ^ 
05e0: 68 20 5e 20 73 71 6c 69 74 65 33 55 70 70 65 72  h ^ sqlite3Upper
05f0: 54 6f 4c 6f 77 65 72 5b 63 5d 3b 0a 20 20 7d 0a  ToLower[c];.  }.
0600: 20 20 72 65 74 75 72 6e 20 68 3b 0a 7d 0a 0a 0a    return h;.}...
0610: 2f 2a 20 4c 69 6e 6b 20 70 4e 65 77 20 65 6c 65  /* Link pNew ele
0620: 6d 65 6e 74 20 69 6e 74 6f 20 74 68 65 20 68 61  ment into the ha
0630: 73 68 20 74 61 62 6c 65 20 70 48 2e 20 20 49 66  sh table pH.  If
0640: 20 70 45 6e 74 72 79 21 3d 30 20 74 68 65 6e 20   pEntry!=0 then 
0650: 61 6c 73 6f 0a 2a 2a 20 69 6e 73 65 72 74 20 70  also.** insert p
0660: 4e 65 77 20 69 6e 74 6f 20 74 68 65 20 70 45 6e  New into the pEn
0670: 74 72 79 20 68 61 73 68 20 62 75 63 6b 65 74 2e  try hash bucket.
0680: 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64 20  .*/.static void 
0690: 69 6e 73 65 72 74 45 6c 65 6d 65 6e 74 28 0a 20  insertElement(. 
06a0: 20 48 61 73 68 20 2a 70 48 2c 20 20 20 20 20 20   Hash *pH,      
06b0: 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 63          /* The c
06c0: 6f 6d 70 6c 65 74 65 20 68 61 73 68 20 74 61 62  omplete hash tab
06d0: 6c 65 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 5f  le */.  struct _
06e0: 68 74 20 2a 70 45 6e 74 72 79 2c 20 20 20 20 2f  ht *pEntry,    /
06f0: 2a 20 54 68 65 20 65 6e 74 72 79 20 69 6e 74 6f  * The entry into
0700: 20 77 68 69 63 68 20 70 4e 65 77 20 69 73 20 69   which pNew is i
0710: 6e 73 65 72 74 65 64 20 2a 2f 0a 20 20 48 61 73  nserted */.  Has
0720: 68 45 6c 65 6d 20 2a 70 4e 65 77 20 20 20 20 20  hElem *pNew     
0730: 20 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65      /* The eleme
0740: 6e 74 20 74 6f 20 62 65 20 69 6e 73 65 72 74 65  nt to be inserte
0750: 64 20 2a 2f 0a 29 7b 0a 20 20 48 61 73 68 45 6c  d */.){.  HashEl
0760: 65 6d 20 2a 70 48 65 61 64 3b 20 20 20 20 20 20  em *pHead;      
0770: 20 2f 2a 20 46 69 72 73 74 20 65 6c 65 6d 65 6e   /* First elemen
0780: 74 20 61 6c 72 65 61 64 79 20 69 6e 20 70 45 6e  t already in pEn
0790: 74 72 79 20 2a 2f 0a 20 20 69 66 28 20 70 45 6e  try */.  if( pEn
07a0: 74 72 79 20 29 7b 0a 20 20 20 20 70 48 65 61 64  try ){.    pHead
07b0: 20 3d 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74   = pEntry->count
07c0: 20 3f 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e   ? pEntry->chain
07d0: 20 3a 20 30 3b 0a 20 20 20 20 70 45 6e 74 72 79   : 0;.    pEntry
07e0: 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20 20 20 20 70  ->count++;.    p
07f0: 45 6e 74 72 79 2d 3e 63 68 61 69 6e 20 3d 20 70  Entry->chain = p
0800: 4e 65 77 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20  New;.  }else{.  
0810: 20 20 70 48 65 61 64 20 3d 20 30 3b 0a 20 20 7d    pHead = 0;.  }
0820: 0a 20 20 69 66 28 20 70 48 65 61 64 20 29 7b 0a  .  if( pHead ){.
0830: 20 20 20 20 70 4e 65 77 2d 3e 6e 65 78 74 20 3d      pNew->next =
0840: 20 70 48 65 61 64 3b 0a 20 20 20 20 70 4e 65 77   pHead;.    pNew
0850: 2d 3e 70 72 65 76 20 3d 20 70 48 65 61 64 2d 3e  ->prev = pHead->
0860: 70 72 65 76 3b 0a 20 20 20 20 69 66 28 20 70 48  prev;.    if( pH
0870: 65 61 64 2d 3e 70 72 65 76 20 29 7b 20 70 48 65  ead->prev ){ pHe
0880: 61 64 2d 3e 70 72 65 76 2d 3e 6e 65 78 74 20 3d  ad->prev->next =
0890: 20 70 4e 65 77 3b 20 7d 0a 20 20 20 20 65 6c 73   pNew; }.    els
08a0: 65 20 20 20 20 20 20 20 20 20 20 20 20 20 7b 20  e             { 
08b0: 70 48 2d 3e 66 69 72 73 74 20 3d 20 70 4e 65 77  pH->first = pNew
08c0: 3b 20 7d 0a 20 20 20 20 70 48 65 61 64 2d 3e 70  ; }.    pHead->p
08d0: 72 65 76 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 65  rev = pNew;.  }e
08e0: 6c 73 65 7b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e  lse{.    pNew->n
08f0: 65 78 74 20 3d 20 70 48 2d 3e 66 69 72 73 74 3b  ext = pH->first;
0900: 0a 20 20 20 20 69 66 28 20 70 48 2d 3e 66 69 72  .    if( pH->fir
0910: 73 74 20 29 7b 20 70 48 2d 3e 66 69 72 73 74 2d  st ){ pH->first-
0920: 3e 70 72 65 76 20 3d 20 70 4e 65 77 3b 20 7d 0a  >prev = pNew; }.
0930: 20 20 20 20 70 4e 65 77 2d 3e 70 72 65 76 20 3d      pNew->prev =
0940: 20 30 3b 0a 20 20 20 20 70 48 2d 3e 66 69 72 73   0;.    pH->firs
0950: 74 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 0a 7d 0a  t = pNew;.  }.}.
0960: 0a 0a 2f 2a 20 52 65 73 69 7a 65 20 74 68 65 20  ../* Resize the 
0970: 68 61 73 68 20 74 61 62 6c 65 20 73 6f 20 74 68  hash table so th
0980: 61 74 20 69 74 20 63 61 6e 74 61 69 6e 73 20 22  at it cantains "
0990: 6e 65 77 5f 73 69 7a 65 22 20 62 75 63 6b 65 74  new_size" bucket
09a0: 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 68 61 73  s..**.** The has
09b0: 68 20 74 61 62 6c 65 20 6d 69 67 68 74 20 66 61  h table might fa
09c0: 69 6c 20 74 6f 20 72 65 73 69 7a 65 20 69 66 20  il to resize if 
09d0: 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 29  sqlite3_malloc()
09e0: 20 66 61 69 6c 73 20 6f 72 0a 2a 2a 20 69 66 20   fails or.** if 
09f0: 74 68 65 20 6e 65 77 20 73 69 7a 65 20 69 73 20  the new size is 
0a00: 74 68 65 20 73 61 6d 65 20 61 73 20 74 68 65 20  the same as the 
0a10: 70 72 69 6f 72 20 73 69 7a 65 2e 0a 2a 2a 20 52  prior size..** R
0a20: 65 74 75 72 6e 20 54 52 55 45 20 69 66 20 74 68  eturn TRUE if th
0a30: 65 20 72 65 73 69 7a 65 20 6f 63 63 75 72 73 20  e resize occurs 
0a40: 61 6e 64 20 66 61 6c 73 65 20 69 66 20 6e 6f 74  and false if not
0a50: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20  ..*/.static int 
0a60: 72 65 68 61 73 68 28 48 61 73 68 20 2a 70 48 2c  rehash(Hash *pH,
0a70: 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 6e 65   unsigned int ne
0a80: 77 5f 73 69 7a 65 29 7b 0a 20 20 73 74 72 75 63  w_size){.  struc
0a90: 74 20 5f 68 74 20 2a 6e 65 77 5f 68 74 3b 20 20  t _ht *new_ht;  
0aa0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65            /* The
0ab0: 20 6e 65 77 20 68 61 73 68 20 74 61 62 6c 65 20   new hash table 
0ac0: 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65  */.  HashElem *e
0ad0: 6c 65 6d 2c 20 2a 6e 65 78 74 5f 65 6c 65 6d 3b  lem, *next_elem;
0ae0: 20 20 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f 70 69      /* For loopi
0af0: 6e 67 20 6f 76 65 72 20 65 78 69 73 74 69 6e 67  ng over existing
0b00: 20 65 6c 65 6d 65 6e 74 73 20 2a 2f 0a 0a 23 69   elements */..#i
0b10: 66 20 53 51 4c 49 54 45 5f 4d 41 4c 4c 4f 43 5f  f SQLITE_MALLOC_
0b20: 53 4f 46 54 5f 4c 49 4d 49 54 3e 30 0a 20 20 69  SOFT_LIMIT>0.  i
0b30: 66 28 20 6e 65 77 5f 73 69 7a 65 2a 73 69 7a 65  f( new_size*size
0b40: 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29 3e 53  of(struct _ht)>S
0b50: 51 4c 49 54 45 5f 4d 41 4c 4c 4f 43 5f 53 4f 46  QLITE_MALLOC_SOF
0b60: 54 5f 4c 49 4d 49 54 20 29 7b 0a 20 20 20 20 6e  T_LIMIT ){.    n
0b70: 65 77 5f 73 69 7a 65 20 3d 20 53 51 4c 49 54 45  ew_size = SQLITE
0b80: 5f 4d 41 4c 4c 4f 43 5f 53 4f 46 54 5f 4c 49 4d  _MALLOC_SOFT_LIM
0b90: 49 54 2f 73 69 7a 65 6f 66 28 73 74 72 75 63 74  IT/sizeof(struct
0ba0: 20 5f 68 74 29 3b 0a 20 20 7d 0a 20 20 69 66 28   _ht);.  }.  if(
0bb0: 20 6e 65 77 5f 73 69 7a 65 3d 3d 70 48 2d 3e 68   new_size==pH->h
0bc0: 74 73 69 7a 65 20 29 20 72 65 74 75 72 6e 20 30  tsize ) return 0
0bd0: 3b 0a 23 65 6e 64 69 66 0a 0a 20 20 2f 2a 20 54  ;.#endif..  /* T
0be0: 68 65 20 69 6e 61 62 69 6c 69 74 79 20 74 6f 20  he inability to 
0bf0: 61 6c 6c 6f 63 61 74 65 73 20 73 70 61 63 65 20  allocates space 
0c00: 66 6f 72 20 61 20 6c 61 72 67 65 72 20 68 61 73  for a larger has
0c10: 68 20 74 61 62 6c 65 20 69 73 0a 20 20 2a 2a 20  h table is.  ** 
0c20: 61 20 70 65 72 66 6f 72 6d 61 6e 63 65 20 68 69  a performance hi
0c30: 74 20 62 75 74 20 69 74 20 69 73 20 6e 6f 74 20  t but it is not 
0c40: 61 20 66 61 74 61 6c 20 65 72 72 6f 72 2e 20 20  a fatal error.  
0c50: 53 6f 20 6d 61 72 6b 20 74 68 65 0a 20 20 2a 2a  So mark the.  **
0c60: 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 61 73 20 61   allocation as a
0c70: 20 62 65 6e 69 67 6e 2e 20 55 73 65 20 73 71 6c   benign. Use sql
0c80: 69 74 65 33 4d 61 6c 6c 6f 63 28 29 2f 6d 65 6d  ite3Malloc()/mem
0c90: 73 65 74 28 30 29 20 69 6e 73 74 65 61 64 20 6f  set(0) instead o
0ca0: 66 20 0a 20 20 2a 2a 20 73 71 6c 69 74 65 33 4d  f .  ** sqlite3M
0cb0: 61 6c 6c 6f 63 5a 65 72 6f 28 29 20 74 6f 20 6d  allocZero() to m
0cc0: 61 6b 65 20 74 68 65 20 61 6c 6c 6f 63 61 74 69  ake the allocati
0cd0: 6f 6e 2c 20 61 73 20 73 71 6c 69 74 65 33 4d 61  on, as sqlite3Ma
0ce0: 6c 6c 6f 63 5a 65 72 6f 28 29 0a 20 20 2a 2a 20  llocZero().  ** 
0cf0: 6f 6e 6c 79 20 7a 65 72 6f 65 73 20 74 68 65 20  only zeroes the 
0d00: 72 65 71 75 65 73 74 65 64 20 6e 75 6d 62 65 72  requested number
0d10: 20 6f 66 20 62 79 74 65 73 20 77 68 65 72 65 61   of bytes wherea
0d20: 73 20 74 68 69 73 20 6d 6f 64 75 6c 65 20 77 69  s this module wi
0d30: 6c 6c 0a 20 20 2a 2a 20 75 73 65 20 74 68 65 20  ll.  ** use the 
0d40: 61 63 74 75 61 6c 20 61 6d 6f 75 6e 74 20 6f 66  actual amount of
0d50: 20 73 70 61 63 65 20 61 6c 6c 6f 63 61 74 65 64   space allocated
0d60: 20 66 6f 72 20 74 68 65 20 68 61 73 68 20 74 61   for the hash ta
0d70: 62 6c 65 20 28 77 68 69 63 68 0a 20 20 2a 2a 20  ble (which.  ** 
0d80: 6d 61 79 20 62 65 20 6c 61 72 67 65 72 20 74 68  may be larger th
0d90: 61 6e 20 74 68 65 20 72 65 71 75 65 73 74 65 64  an the requested
0da0: 20 61 6d 6f 75 6e 74 29 2e 0a 20 20 2a 2f 0a 20   amount)..  */. 
0db0: 20 73 71 6c 69 74 65 33 42 65 67 69 6e 42 65 6e   sqlite3BeginBen
0dc0: 69 67 6e 4d 61 6c 6c 6f 63 28 29 3b 0a 20 20 6e  ignMalloc();.  n
0dd0: 65 77 5f 68 74 20 3d 20 28 73 74 72 75 63 74 20  ew_ht = (struct 
0de0: 5f 68 74 20 2a 29 73 71 6c 69 74 65 33 4d 61 6c  _ht *)sqlite3Mal
0df0: 6c 6f 63 28 20 6e 65 77 5f 73 69 7a 65 2a 73 69  loc( new_size*si
0e00: 7a 65 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29  zeof(struct _ht)
0e10: 20 29 3b 0a 20 20 73 71 6c 69 74 65 33 45 6e 64   );.  sqlite3End
0e20: 42 65 6e 69 67 6e 4d 61 6c 6c 6f 63 28 29 3b 0a  BenignMalloc();.
0e30: 0a 20 20 69 66 28 20 6e 65 77 5f 68 74 3d 3d 30  .  if( new_ht==0
0e40: 20 29 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 73   ) return 0;.  s
0e50: 71 6c 69 74 65 33 5f 66 72 65 65 28 70 48 2d 3e  qlite3_free(pH->
0e60: 68 74 29 3b 0a 20 20 70 48 2d 3e 68 74 20 3d 20  ht);.  pH->ht = 
0e70: 6e 65 77 5f 68 74 3b 0a 20 20 70 48 2d 3e 68 74  new_ht;.  pH->ht
0e80: 73 69 7a 65 20 3d 20 6e 65 77 5f 73 69 7a 65 20  size = new_size 
0e90: 3d 20 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 53  = sqlite3MallocS
0ea0: 69 7a 65 28 6e 65 77 5f 68 74 29 2f 73 69 7a 65  ize(new_ht)/size
0eb0: 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29 3b 0a  of(struct _ht);.
0ec0: 20 20 6d 65 6d 73 65 74 28 6e 65 77 5f 68 74 2c    memset(new_ht,
0ed0: 20 30 2c 20 6e 65 77 5f 73 69 7a 65 2a 73 69 7a   0, new_size*siz
0ee0: 65 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29 29  eof(struct _ht))
0ef0: 3b 0a 20 20 66 6f 72 28 65 6c 65 6d 3d 70 48 2d  ;.  for(elem=pH-
0f00: 3e 66 69 72 73 74 2c 20 70 48 2d 3e 66 69 72 73  >first, pH->firs
0f10: 74 3d 30 3b 20 65 6c 65 6d 3b 20 65 6c 65 6d 20  t=0; elem; elem 
0f20: 3d 20 6e 65 78 74 5f 65 6c 65 6d 29 7b 0a 20 20  = next_elem){.  
0f30: 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 68    unsigned int h
0f40: 20 3d 20 73 74 72 48 61 73 68 28 65 6c 65 6d 2d   = strHash(elem-
0f50: 3e 70 4b 65 79 29 20 25 20 6e 65 77 5f 73 69 7a  >pKey) % new_siz
0f60: 65 3b 0a 20 20 20 20 6e 65 78 74 5f 65 6c 65 6d  e;.    next_elem
0f70: 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20   = elem->next;. 
0f80: 20 20 20 69 6e 73 65 72 74 45 6c 65 6d 65 6e 74     insertElement
0f90: 28 70 48 2c 20 26 6e 65 77 5f 68 74 5b 68 5d 2c  (pH, &new_ht[h],
0fa0: 20 65 6c 65 6d 29 3b 0a 20 20 7d 0a 20 20 72 65   elem);.  }.  re
0fb0: 74 75 72 6e 20 31 3b 0a 7d 0a 0a 2f 2a 20 54 68  turn 1;.}../* Th
0fc0: 69 73 20 66 75 6e 63 74 69 6f 6e 20 28 66 6f 72  is function (for
0fd0: 20 69 6e 74 65 72 6e 61 6c 20 75 73 65 20 6f 6e   internal use on
0fe0: 6c 79 29 20 6c 6f 63 61 74 65 73 20 61 6e 20 65  ly) locates an e
0ff0: 6c 65 6d 65 6e 74 20 69 6e 20 61 6e 0a 2a 2a 20  lement in an.** 
1000: 68 61 73 68 20 74 61 62 6c 65 20 74 68 61 74 20  hash table that 
1010: 6d 61 74 63 68 65 73 20 74 68 65 20 67 69 76 65  matches the give
1020: 6e 20 6b 65 79 2e 20 20 54 68 65 20 68 61 73 68  n key.  The hash
1030: 20 66 6f 72 20 74 68 69 73 20 6b 65 79 20 69 73   for this key is
1040: 0a 2a 2a 20 61 6c 73 6f 20 63 6f 6d 70 75 74 65  .** also compute
1050: 64 20 61 6e 64 20 72 65 74 75 72 6e 65 64 20 69  d and returned i
1060: 6e 20 74 68 65 20 2a 70 48 20 70 61 72 61 6d 65  n the *pH parame
1070: 74 65 72 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 48  ter..*/.static H
1080: 61 73 68 45 6c 65 6d 20 2a 66 69 6e 64 45 6c 65  ashElem *findEle
1090: 6d 65 6e 74 57 69 74 68 48 61 73 68 28 0a 20 20  mentWithHash(.  
10a0: 63 6f 6e 73 74 20 48 61 73 68 20 2a 70 48 2c 20  const Hash *pH, 
10b0: 20 20 20 20 2f 2a 20 54 68 65 20 70 48 20 74 6f      /* The pH to
10c0: 20 62 65 20 73 65 61 72 63 68 65 64 20 2a 2f 0a   be searched */.
10d0: 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 4b    const char *pK
10e0: 65 79 2c 20 20 20 2f 2a 20 54 68 65 20 6b 65 79  ey,   /* The key
10f0: 20 77 65 20 61 72 65 20 73 65 61 72 63 68 69 6e   we are searchin
1100: 67 20 66 6f 72 20 2a 2f 0a 20 20 75 6e 73 69 67  g for */.  unsig
1110: 6e 65 64 20 69 6e 74 20 2a 70 48 61 73 68 20 2f  ned int *pHash /
1120: 2a 20 57 72 69 74 65 20 74 68 65 20 68 61 73 68  * Write the hash
1130: 20 76 61 6c 75 65 20 68 65 72 65 20 2a 2f 0a 29   value here */.)
1140: 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c  {.  HashElem *el
1150: 65 6d 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  em;             
1160: 20 20 20 2f 2a 20 55 73 65 64 20 74 6f 20 6c 6f     /* Used to lo
1170: 6f 70 20 74 68 72 75 20 74 68 65 20 65 6c 65 6d  op thru the elem
1180: 65 6e 74 20 6c 69 73 74 20 2a 2f 0a 20 20 69 6e  ent list */.  in
1190: 74 20 63 6f 75 6e 74 3b 20 20 20 20 20 20 20 20  t count;        
11a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
11b0: 4e 75 6d 62 65 72 20 6f 66 20 65 6c 65 6d 65 6e  Number of elemen
11c0: 74 73 20 6c 65 66 74 20 74 6f 20 74 65 73 74 20  ts left to test 
11d0: 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64 20 69 6e  */.  unsigned in
11e0: 74 20 68 3b 20 20 20 20 20 20 20 20 20 20 20 20  t h;            
11f0: 20 20 20 20 2f 2a 20 54 68 65 20 63 6f 6d 70 75      /* The compu
1200: 74 65 64 20 68 61 73 68 20 2a 2f 0a 0a 20 20 69  ted hash */..  i
1210: 66 28 20 70 48 2d 3e 68 74 20 29 7b 20 20 20 2f  f( pH->ht ){   /
1220: 2a 4f 50 54 49 4d 49 5a 41 54 49 4f 4e 2d 49 46  *OPTIMIZATION-IF
1230: 2d 54 52 55 45 2a 2f 0a 20 20 20 20 73 74 72 75  -TRUE*/.    stru
1240: 63 74 20 5f 68 74 20 2a 70 45 6e 74 72 79 3b 0a  ct _ht *pEntry;.
1250: 20 20 20 20 68 20 3d 20 73 74 72 48 61 73 68 28      h = strHash(
1260: 70 4b 65 79 29 20 25 20 70 48 2d 3e 68 74 73 69  pKey) % pH->htsi
1270: 7a 65 3b 0a 20 20 20 20 70 45 6e 74 72 79 20 3d  ze;.    pEntry =
1280: 20 26 70 48 2d 3e 68 74 5b 68 5d 3b 0a 20 20 20   &pH->ht[h];.   
1290: 20 65 6c 65 6d 20 3d 20 70 45 6e 74 72 79 2d 3e   elem = pEntry->
12a0: 63 68 61 69 6e 3b 0a 20 20 20 20 63 6f 75 6e 74  chain;.    count
12b0: 20 3d 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74   = pEntry->count
12c0: 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 68  ;.  }else{.    h
12d0: 20 3d 20 30 3b 0a 20 20 20 20 65 6c 65 6d 20 3d   = 0;.    elem =
12e0: 20 70 48 2d 3e 66 69 72 73 74 3b 0a 20 20 20 20   pH->first;.    
12f0: 63 6f 75 6e 74 20 3d 20 70 48 2d 3e 63 6f 75 6e  count = pH->coun
1300: 74 3b 0a 20 20 7d 0a 20 20 2a 70 48 61 73 68 20  t;.  }.  *pHash 
1310: 3d 20 68 3b 0a 20 20 77 68 69 6c 65 28 20 63 6f  = h;.  while( co
1320: 75 6e 74 2d 2d 20 29 7b 0a 20 20 20 20 61 73 73  unt-- ){.    ass
1330: 65 72 74 28 20 65 6c 65 6d 21 3d 30 20 29 3b 0a  ert( elem!=0 );.
1340: 20 20 20 20 69 66 28 20 73 71 6c 69 74 65 33 53      if( sqlite3S
1350: 74 72 49 43 6d 70 28 65 6c 65 6d 2d 3e 70 4b 65  trICmp(elem->pKe
1360: 79 2c 70 4b 65 79 29 3d 3d 30 20 29 7b 20 0a 20  y,pKey)==0 ){ . 
1370: 20 20 20 20 20 72 65 74 75 72 6e 20 65 6c 65 6d       return elem
1380: 3b 0a 20 20 20 20 7d 0a 20 20 20 20 65 6c 65 6d  ;.    }.    elem
1390: 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20   = elem->next;. 
13a0: 20 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d   }.  return 0;.}
13b0: 0a 0a 2f 2a 20 52 65 6d 6f 76 65 20 61 20 73 69  ../* Remove a si
13c0: 6e 67 6c 65 20 65 6e 74 72 79 20 66 72 6f 6d 20  ngle entry from 
13d0: 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 67  the hash table g
13e0: 69 76 65 6e 20 61 20 70 6f 69 6e 74 65 72 20 74  iven a pointer t
13f0: 6f 20 74 68 61 74 0a 2a 2a 20 65 6c 65 6d 65 6e  o that.** elemen
1400: 74 20 61 6e 64 20 61 20 68 61 73 68 20 6f 6e 20  t and a hash on 
1410: 74 68 65 20 65 6c 65 6d 65 6e 74 27 73 20 6b 65  the element's ke
1420: 79 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69  y..*/.static voi
1430: 64 20 72 65 6d 6f 76 65 45 6c 65 6d 65 6e 74 47  d removeElementG
1440: 69 76 65 6e 48 61 73 68 28 0a 20 20 48 61 73 68  ivenHash(.  Hash
1450: 20 2a 70 48 2c 20 20 20 20 20 20 20 20 20 2f 2a   *pH,         /*
1460: 20 54 68 65 20 70 48 20 63 6f 6e 74 61 69 6e 69   The pH containi
1470: 6e 67 20 22 65 6c 65 6d 22 20 2a 2f 0a 20 20 48  ng "elem" */.  H
1480: 61 73 68 45 6c 65 6d 2a 20 65 6c 65 6d 2c 20 20  ashElem* elem,  
1490: 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e 74 20   /* The element 
14a0: 74 6f 20 62 65 20 72 65 6d 6f 76 65 64 20 66 72  to be removed fr
14b0: 6f 6d 20 74 68 65 20 70 48 20 2a 2f 0a 20 20 75  om the pH */.  u
14c0: 6e 73 69 67 6e 65 64 20 69 6e 74 20 68 20 20 20  nsigned int h   
14d0: 20 2f 2a 20 48 61 73 68 20 76 61 6c 75 65 20 66   /* Hash value f
14e0: 6f 72 20 74 68 65 20 65 6c 65 6d 65 6e 74 20 2a  or the element *
14f0: 2f 0a 29 7b 0a 20 20 73 74 72 75 63 74 20 5f 68  /.){.  struct _h
1500: 74 20 2a 70 45 6e 74 72 79 3b 0a 20 20 69 66 28  t *pEntry;.  if(
1510: 20 65 6c 65 6d 2d 3e 70 72 65 76 20 29 7b 0a 20   elem->prev ){. 
1520: 20 20 20 65 6c 65 6d 2d 3e 70 72 65 76 2d 3e 6e     elem->prev->n
1530: 65 78 74 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74  ext = elem->next
1540: 3b 20 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20  ; .  }else{.    
1550: 70 48 2d 3e 66 69 72 73 74 20 3d 20 65 6c 65 6d  pH->first = elem
1560: 2d 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20 20 69 66  ->next;.  }.  if
1570: 28 20 65 6c 65 6d 2d 3e 6e 65 78 74 20 29 7b 0a  ( elem->next ){.
1580: 20 20 20 20 65 6c 65 6d 2d 3e 6e 65 78 74 2d 3e      elem->next->
1590: 70 72 65 76 20 3d 20 65 6c 65 6d 2d 3e 70 72 65  prev = elem->pre
15a0: 76 3b 0a 20 20 7d 0a 20 20 69 66 28 20 70 48 2d  v;.  }.  if( pH-
15b0: 3e 68 74 20 29 7b 0a 20 20 20 20 70 45 6e 74 72  >ht ){.    pEntr
15c0: 79 20 3d 20 26 70 48 2d 3e 68 74 5b 68 5d 3b 0a  y = &pH->ht[h];.
15d0: 20 20 20 20 69 66 28 20 70 45 6e 74 72 79 2d 3e      if( pEntry->
15e0: 63 68 61 69 6e 3d 3d 65 6c 65 6d 20 29 7b 0a 20  chain==elem ){. 
15f0: 20 20 20 20 20 70 45 6e 74 72 79 2d 3e 63 68 61       pEntry->cha
1600: 69 6e 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b  in = elem->next;
1610: 0a 20 20 20 20 7d 0a 20 20 20 20 70 45 6e 74 72  .    }.    pEntr
1620: 79 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a 20 20 20 20  y->count--;.    
1630: 61 73 73 65 72 74 28 20 70 45 6e 74 72 79 2d 3e  assert( pEntry->
1640: 63 6f 75 6e 74 3e 3d 30 20 29 3b 0a 20 20 7d 0a  count>=0 );.  }.
1650: 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 20    sqlite3_free( 
1660: 65 6c 65 6d 20 29 3b 0a 20 20 70 48 2d 3e 63 6f  elem );.  pH->co
1670: 75 6e 74 2d 2d 3b 0a 20 20 69 66 28 20 70 48 2d  unt--;.  if( pH-
1680: 3e 63 6f 75 6e 74 3d 3d 30 20 29 7b 0a 20 20 20  >count==0 ){.   
1690: 20 61 73 73 65 72 74 28 20 70 48 2d 3e 66 69 72   assert( pH->fir
16a0: 73 74 3d 3d 30 20 29 3b 0a 20 20 20 20 61 73 73  st==0 );.    ass
16b0: 65 72 74 28 20 70 48 2d 3e 63 6f 75 6e 74 3d 3d  ert( pH->count==
16c0: 30 20 29 3b 0a 20 20 20 20 73 71 6c 69 74 65 33  0 );.    sqlite3
16d0: 48 61 73 68 43 6c 65 61 72 28 70 48 29 3b 0a 20  HashClear(pH);. 
16e0: 20 7d 0a 7d 0a 0a 2f 2a 20 41 74 74 65 6d 70 74   }.}../* Attempt
16f0: 20 74 6f 20 6c 6f 63 61 74 65 20 61 6e 20 65 6c   to locate an el
1700: 65 6d 65 6e 74 20 6f 66 20 74 68 65 20 68 61 73  ement of the has
1710: 68 20 74 61 62 6c 65 20 70 48 20 77 69 74 68 20  h table pH with 
1720: 61 20 6b 65 79 0a 2a 2a 20 74 68 61 74 20 6d 61  a key.** that ma
1730: 74 63 68 65 73 20 70 4b 65 79 2e 20 20 52 65 74  tches pKey.  Ret
1740: 75 72 6e 20 74 68 65 20 64 61 74 61 20 66 6f 72  urn the data for
1750: 20 74 68 69 73 20 65 6c 65 6d 65 6e 74 20 69 66   this element if
1760: 20 69 74 20 69 73 0a 2a 2a 20 66 6f 75 6e 64 2c   it is.** found,
1770: 20 6f 72 20 4e 55 4c 4c 20 69 66 20 74 68 65 72   or NULL if ther
1780: 65 20 69 73 20 6e 6f 20 6d 61 74 63 68 2e 0a 2a  e is no match..*
1790: 2f 0a 76 6f 69 64 20 2a 73 71 6c 69 74 65 33 48  /.void *sqlite3H
17a0: 61 73 68 46 69 6e 64 28 63 6f 6e 73 74 20 48 61  ashFind(const Ha
17b0: 73 68 20 2a 70 48 2c 20 63 6f 6e 73 74 20 63 68  sh *pH, const ch
17c0: 61 72 20 2a 70 4b 65 79 29 7b 0a 20 20 48 61 73  ar *pKey){.  Has
17d0: 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20  hElem *elem;    
17e0: 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e 74 20 74  /* The element t
17f0: 68 61 74 20 6d 61 74 63 68 65 73 20 6b 65 79 20  hat matches key 
1800: 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64 20 69 6e  */.  unsigned in
1810: 74 20 68 3b 20 20 20 20 2f 2a 20 41 20 68 61 73  t h;    /* A has
1820: 68 20 6f 6e 20 6b 65 79 20 2a 2f 0a 0a 20 20 61  h on key */..  a
1830: 73 73 65 72 74 28 20 70 48 21 3d 30 20 29 3b 0a  ssert( pH!=0 );.
1840: 20 20 61 73 73 65 72 74 28 20 70 4b 65 79 21 3d    assert( pKey!=
1850: 30 20 29 3b 0a 20 20 65 6c 65 6d 20 3d 20 66 69  0 );.  elem = fi
1860: 6e 64 45 6c 65 6d 65 6e 74 57 69 74 68 48 61 73  ndElementWithHas
1870: 68 28 70 48 2c 20 70 4b 65 79 2c 20 26 68 29 3b  h(pH, pKey, &h);
1880: 0a 20 20 72 65 74 75 72 6e 20 65 6c 65 6d 20 3f  .  return elem ?
1890: 20 65 6c 65 6d 2d 3e 64 61 74 61 20 3a 20 30 3b   elem->data : 0;
18a0: 0a 7d 0a 0a 2f 2a 20 49 6e 73 65 72 74 20 61 6e  .}../* Insert an
18b0: 20 65 6c 65 6d 65 6e 74 20 69 6e 74 6f 20 74 68   element into th
18c0: 65 20 68 61 73 68 20 74 61 62 6c 65 20 70 48 2e  e hash table pH.
18d0: 20 20 54 68 65 20 6b 65 79 20 69 73 20 70 4b 65    The key is pKe
18e0: 79 0a 2a 2a 20 61 6e 64 20 74 68 65 20 64 61 74  y.** and the dat
18f0: 61 20 69 73 20 22 64 61 74 61 22 2e 0a 2a 2a 0a  a is "data"..**.
1900: 2a 2a 20 49 66 20 6e 6f 20 65 6c 65 6d 65 6e 74  ** If no element
1910: 20 65 78 69 73 74 73 20 77 69 74 68 20 61 20 6d   exists with a m
1920: 61 74 63 68 69 6e 67 20 6b 65 79 2c 20 74 68 65  atching key, the
1930: 6e 20 61 20 6e 65 77 0a 2a 2a 20 65 6c 65 6d 65  n a new.** eleme
1940: 6e 74 20 69 73 20 63 72 65 61 74 65 64 20 61 6e  nt is created an
1950: 64 20 4e 55 4c 4c 20 69 73 20 72 65 74 75 72 6e  d NULL is return
1960: 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 61 6e 6f  ed..**.** If ano
1970: 74 68 65 72 20 65 6c 65 6d 65 6e 74 20 61 6c 72  ther element alr
1980: 65 61 64 79 20 65 78 69 73 74 73 20 77 69 74 68  eady exists with
1990: 20 74 68 65 20 73 61 6d 65 20 6b 65 79 2c 20 74   the same key, t
19a0: 68 65 6e 20 74 68 65 0a 2a 2a 20 6e 65 77 20 64  hen the.** new d
19b0: 61 74 61 20 72 65 70 6c 61 63 65 73 20 74 68 65  ata replaces the
19c0: 20 6f 6c 64 20 64 61 74 61 20 61 6e 64 20 74 68   old data and th
19d0: 65 20 6f 6c 64 20 64 61 74 61 20 69 73 20 72 65  e old data is re
19e0: 74 75 72 6e 65 64 2e 0a 2a 2a 20 54 68 65 20 6b  turned..** The k
19f0: 65 79 20 69 73 20 6e 6f 74 20 63 6f 70 69 65 64  ey is not copied
1a00: 20 69 6e 20 74 68 69 73 20 69 6e 73 74 61 6e 63   in this instanc
1a10: 65 2e 20 20 49 66 20 61 20 6d 61 6c 6c 6f 63 20  e.  If a malloc 
1a20: 66 61 69 6c 73 2c 20 74 68 65 6e 0a 2a 2a 20 74  fails, then.** t
1a30: 68 65 20 6e 65 77 20 64 61 74 61 20 69 73 20 72  he new data is r
1a40: 65 74 75 72 6e 65 64 20 61 6e 64 20 74 68 65 20  eturned and the 
1a50: 68 61 73 68 20 74 61 62 6c 65 20 69 73 20 75 6e  hash table is un
1a60: 63 68 61 6e 67 65 64 2e 0a 2a 2a 0a 2a 2a 20 49  changed..**.** I
1a70: 66 20 74 68 65 20 22 64 61 74 61 22 20 70 61 72  f the "data" par
1a80: 61 6d 65 74 65 72 20 74 6f 20 74 68 69 73 20 66  ameter to this f
1a90: 75 6e 63 74 69 6f 6e 20 69 73 20 4e 55 4c 4c 2c  unction is NULL,
1aa0: 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20 65 6c 65   then the.** ele
1ab0: 6d 65 6e 74 20 63 6f 72 72 65 73 70 6f 6e 64 69  ment correspondi
1ac0: 6e 67 20 74 6f 20 22 6b 65 79 22 20 69 73 20 72  ng to "key" is r
1ad0: 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74 68 65 20  emoved from the 
1ae0: 68 61 73 68 20 74 61 62 6c 65 2e 0a 2a 2f 0a 76  hash table..*/.v
1af0: 6f 69 64 20 2a 73 71 6c 69 74 65 33 48 61 73 68  oid *sqlite3Hash
1b00: 49 6e 73 65 72 74 28 48 61 73 68 20 2a 70 48 2c  Insert(Hash *pH,
1b10: 20 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 4b 65   const char *pKe
1b20: 79 2c 20 76 6f 69 64 20 2a 64 61 74 61 29 7b 0a  y, void *data){.
1b30: 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 68    unsigned int h
1b40: 3b 20 20 20 20 20 20 20 2f 2a 20 74 68 65 20 68  ;       /* the h
1b50: 61 73 68 20 6f 66 20 74 68 65 20 6b 65 79 20 6d  ash of the key m
1b60: 6f 64 75 6c 6f 20 68 61 73 68 20 74 61 62 6c 65  odulo hash table
1b70: 20 73 69 7a 65 20 2a 2f 0a 20 20 48 61 73 68 45   size */.  HashE
1b80: 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 20 20  lem *elem;      
1b90: 20 2f 2a 20 55 73 65 64 20 74 6f 20 6c 6f 6f 70   /* Used to loop
1ba0: 20 74 68 72 75 20 74 68 65 20 65 6c 65 6d 65 6e   thru the elemen
1bb0: 74 20 6c 69 73 74 20 2a 2f 0a 20 20 48 61 73 68  t list */.  Hash
1bc0: 45 6c 65 6d 20 2a 6e 65 77 5f 65 6c 65 6d 3b 20  Elem *new_elem; 
1bd0: 20 20 2f 2a 20 4e 65 77 20 65 6c 65 6d 65 6e 74    /* New element
1be0: 20 61 64 64 65 64 20 74 6f 20 74 68 65 20 70 48   added to the pH
1bf0: 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 70   */..  assert( p
1c00: 48 21 3d 30 20 29 3b 0a 20 20 61 73 73 65 72 74  H!=0 );.  assert
1c10: 28 20 70 4b 65 79 21 3d 30 20 29 3b 0a 20 20 65  ( pKey!=0 );.  e
1c20: 6c 65 6d 20 3d 20 66 69 6e 64 45 6c 65 6d 65 6e  lem = findElemen
1c30: 74 57 69 74 68 48 61 73 68 28 70 48 2c 70 4b 65  tWithHash(pH,pKe
1c40: 79 2c 26 68 29 3b 0a 20 20 69 66 28 20 65 6c 65  y,&h);.  if( ele
1c50: 6d 20 29 7b 0a 20 20 20 20 76 6f 69 64 20 2a 6f  m ){.    void *o
1c60: 6c 64 5f 64 61 74 61 20 3d 20 65 6c 65 6d 2d 3e  ld_data = elem->
1c70: 64 61 74 61 3b 0a 20 20 20 20 69 66 28 20 64 61  data;.    if( da
1c80: 74 61 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 72  ta==0 ){.      r
1c90: 65 6d 6f 76 65 45 6c 65 6d 65 6e 74 47 69 76 65  emoveElementGive
1ca0: 6e 48 61 73 68 28 70 48 2c 65 6c 65 6d 2c 68 29  nHash(pH,elem,h)
1cb0: 3b 0a 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20  ;.    }else{.   
1cc0: 20 20 20 65 6c 65 6d 2d 3e 64 61 74 61 20 3d 20     elem->data = 
1cd0: 64 61 74 61 3b 0a 20 20 20 20 20 20 65 6c 65 6d  data;.      elem
1ce0: 2d 3e 70 4b 65 79 20 3d 20 70 4b 65 79 3b 0a 20  ->pKey = pKey;. 
1cf0: 20 20 20 7d 0a 20 20 20 20 72 65 74 75 72 6e 20     }.    return 
1d00: 6f 6c 64 5f 64 61 74 61 3b 0a 20 20 7d 0a 20 20  old_data;.  }.  
1d10: 69 66 28 20 64 61 74 61 3d 3d 30 20 29 20 72 65  if( data==0 ) re
1d20: 74 75 72 6e 20 30 3b 0a 20 20 6e 65 77 5f 65 6c  turn 0;.  new_el
1d30: 65 6d 20 3d 20 28 48 61 73 68 45 6c 65 6d 2a 29  em = (HashElem*)
1d40: 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 28 20 73  sqlite3Malloc( s
1d50: 69 7a 65 6f 66 28 48 61 73 68 45 6c 65 6d 29 20  izeof(HashElem) 
1d60: 29 3b 0a 20 20 69 66 28 20 6e 65 77 5f 65 6c 65  );.  if( new_ele
1d70: 6d 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 64 61  m==0 ) return da
1d80: 74 61 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e  ta;.  new_elem->
1d90: 70 4b 65 79 20 3d 20 70 4b 65 79 3b 0a 20 20 6e  pKey = pKey;.  n
1da0: 65 77 5f 65 6c 65 6d 2d 3e 64 61 74 61 20 3d 20  ew_elem->data = 
1db0: 64 61 74 61 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e  data;.  pH->coun
1dc0: 74 2b 2b 3b 0a 20 20 69 66 28 20 70 48 2d 3e 63  t++;.  if( pH->c
1dd0: 6f 75 6e 74 3e 3d 31 30 20 26 26 20 70 48 2d 3e  ount>=10 && pH->
1de0: 63 6f 75 6e 74 20 3e 20 32 2a 70 48 2d 3e 68 74  count > 2*pH->ht
1df0: 73 69 7a 65 20 29 7b 0a 20 20 20 20 69 66 28 20  size ){.    if( 
1e00: 72 65 68 61 73 68 28 70 48 2c 20 70 48 2d 3e 63  rehash(pH, pH->c
1e10: 6f 75 6e 74 2a 32 29 20 29 7b 0a 20 20 20 20 20  ount*2) ){.     
1e20: 20 61 73 73 65 72 74 28 20 70 48 2d 3e 68 74 73   assert( pH->hts
1e30: 69 7a 65 3e 30 20 29 3b 0a 20 20 20 20 20 20 68  ize>0 );.      h
1e40: 20 3d 20 73 74 72 48 61 73 68 28 70 4b 65 79 29   = strHash(pKey)
1e50: 20 25 20 70 48 2d 3e 68 74 73 69 7a 65 3b 0a 20   % pH->htsize;. 
1e60: 20 20 20 7d 0a 20 20 7d 0a 20 20 69 6e 73 65 72     }.  }.  inser
1e70: 74 45 6c 65 6d 65 6e 74 28 70 48 2c 20 70 48 2d  tElement(pH, pH-
1e80: 3e 68 74 20 3f 20 26 70 48 2d 3e 68 74 5b 68 5d  >ht ? &pH->ht[h]
1e90: 20 3a 20 30 2c 20 6e 65 77 5f 65 6c 65 6d 29 3b   : 0, new_elem);
1ea0: 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a     .  return 0;.}.