/ Hex Artifact Content
Login

Artifact ac3470bbf1ca4ae4e306a8ecb0fdf1731810ffe4:


0000: 2f 2a 0a 2a 2a 20 32 30 30 31 20 53 65 70 74 65  /*.** 2001 Septe
0010: 6d 62 65 72 20 32 32 0a 2a 2a 0a 2a 2a 20 54 68  mber 22.**.** Th
0020: 65 20 61 75 74 68 6f 72 20 64 69 73 63 6c 61 69  e author disclai
0030: 6d 73 20 63 6f 70 79 72 69 67 68 74 20 74 6f 20  ms copyright to 
0040: 74 68 69 73 20 73 6f 75 72 63 65 20 63 6f 64 65  this source code
0050: 2e 20 20 49 6e 20 70 6c 61 63 65 20 6f 66 0a 2a  .  In place of.*
0060: 2a 20 61 20 6c 65 67 61 6c 20 6e 6f 74 69 63 65  * a legal notice
0070: 2c 20 68 65 72 65 20 69 73 20 61 20 62 6c 65 73  , here is a bles
0080: 73 69 6e 67 3a 0a 2a 2a 0a 2a 2a 20 20 20 20 4d  sing:.**.**    M
0090: 61 79 20 79 6f 75 20 64 6f 20 67 6f 6f 64 20 61  ay you do good a
00a0: 6e 64 20 6e 6f 74 20 65 76 69 6c 2e 0a 2a 2a 20  nd not evil..** 
00b0: 20 20 20 4d 61 79 20 79 6f 75 20 66 69 6e 64 20     May you find 
00c0: 66 6f 72 67 69 76 65 6e 65 73 73 20 66 6f 72 20  forgiveness for 
00d0: 79 6f 75 72 73 65 6c 66 20 61 6e 64 20 66 6f 72  yourself and for
00e0: 67 69 76 65 20 6f 74 68 65 72 73 2e 0a 2a 2a 20  give others..** 
00f0: 20 20 20 4d 61 79 20 79 6f 75 20 73 68 61 72 65     May you share
0100: 20 66 72 65 65 6c 79 2c 20 6e 65 76 65 72 20 74   freely, never t
0110: 61 6b 69 6e 67 20 6d 6f 72 65 20 74 68 61 6e 20  aking more than 
0120: 79 6f 75 20 67 69 76 65 2e 0a 2a 2a 0a 2a 2a 2a  you give..**.***
0130: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0140: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0150: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0160: 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a 2a  ****************
0170: 2a 2a 2a 2a 2a 2a 0a 2a 2a 20 54 68 69 73 20 69  ******.** This i
0180: 73 20 74 68 65 20 69 6d 70 6c 65 6d 65 6e 74 61  s the implementa
0190: 74 69 6f 6e 20 6f 66 20 67 65 6e 65 72 69 63 20  tion of generic 
01a0: 68 61 73 68 2d 74 61 62 6c 65 73 0a 2a 2a 20 75  hash-tables.** u
01b0: 73 65 64 20 69 6e 20 53 51 4c 69 74 65 2e 0a 2a  sed in SQLite..*
01c0: 2f 0a 23 69 6e 63 6c 75 64 65 20 22 73 71 6c 69  /.#include "sqli
01d0: 74 65 49 6e 74 2e 68 22 0a 23 69 6e 63 6c 75 64  teInt.h".#includ
01e0: 65 20 3c 61 73 73 65 72 74 2e 68 3e 0a 0a 2f 2a  e <assert.h>../*
01f0: 20 54 75 72 6e 20 62 75 6c 6b 20 6d 65 6d 6f 72   Turn bulk memor
0200: 79 20 69 6e 74 6f 20 61 20 68 61 73 68 20 74 61  y into a hash ta
0210: 62 6c 65 20 6f 62 6a 65 63 74 20 62 79 20 69 6e  ble object by in
0220: 69 74 69 61 6c 69 7a 69 6e 67 20 74 68 65 0a 2a  itializing the.*
0230: 2a 20 66 69 65 6c 64 73 20 6f 66 20 74 68 65 20  * fields of the 
0240: 48 61 73 68 20 73 74 72 75 63 74 75 72 65 2e 0a  Hash structure..
0250: 2a 2a 0a 2a 2a 20 22 70 4e 65 77 22 20 69 73 20  **.** "pNew" is 
0260: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65  a pointer to the
0270: 20 68 61 73 68 20 74 61 62 6c 65 20 74 68 61 74   hash table that
0280: 20 69 73 20 74 6f 20 62 65 20 69 6e 69 74 69 61   is to be initia
0290: 6c 69 7a 65 64 2e 0a 2a 2f 0a 76 6f 69 64 20 73  lized..*/.void s
02a0: 71 6c 69 74 65 33 48 61 73 68 49 6e 69 74 28 48  qlite3HashInit(H
02b0: 61 73 68 20 2a 70 4e 65 77 29 7b 0a 20 20 61 73  ash *pNew){.  as
02c0: 73 65 72 74 28 20 70 4e 65 77 21 3d 30 20 29 3b  sert( pNew!=0 );
02d0: 0a 20 20 70 4e 65 77 2d 3e 66 69 72 73 74 20 3d  .  pNew->first =
02e0: 20 30 3b 0a 20 20 70 4e 65 77 2d 3e 63 6f 75 6e   0;.  pNew->coun
02f0: 74 20 3d 20 30 3b 0a 20 20 70 4e 65 77 2d 3e 68  t = 0;.  pNew->h
0300: 74 73 69 7a 65 20 3d 20 30 3b 0a 20 20 70 4e 65  tsize = 0;.  pNe
0310: 77 2d 3e 68 74 20 3d 20 30 3b 0a 7d 0a 0a 2f 2a  w->ht = 0;.}../*
0320: 20 52 65 6d 6f 76 65 20 61 6c 6c 20 65 6e 74 72   Remove all entr
0330: 69 65 73 20 66 72 6f 6d 20 61 20 68 61 73 68 20  ies from a hash 
0340: 74 61 62 6c 65 2e 20 20 52 65 63 6c 61 69 6d 20  table.  Reclaim 
0350: 61 6c 6c 20 6d 65 6d 6f 72 79 2e 0a 2a 2a 20 43  all memory..** C
0360: 61 6c 6c 20 74 68 69 73 20 72 6f 75 74 69 6e 65  all this routine
0370: 20 74 6f 20 64 65 6c 65 74 65 20 61 20 68 61 73   to delete a has
0380: 68 20 74 61 62 6c 65 20 6f 72 20 74 6f 20 72 65  h table or to re
0390: 73 65 74 20 61 20 68 61 73 68 20 74 61 62 6c 65  set a hash table
03a0: 0a 2a 2a 20 74 6f 20 74 68 65 20 65 6d 70 74 79  .** to the empty
03b0: 20 73 74 61 74 65 2e 0a 2a 2f 0a 76 6f 69 64 20   state..*/.void 
03c0: 73 71 6c 69 74 65 33 48 61 73 68 43 6c 65 61 72  sqlite3HashClear
03d0: 28 48 61 73 68 20 2a 70 48 29 7b 0a 20 20 48 61  (Hash *pH){.  Ha
03e0: 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20  shElem *elem;   
03f0: 20 20 20 20 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f        /* For loo
0400: 70 69 6e 67 20 6f 76 65 72 20 61 6c 6c 20 65 6c  ping over all el
0410: 65 6d 65 6e 74 73 20 6f 66 20 74 68 65 20 74 61  ements of the ta
0420: 62 6c 65 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74  ble */..  assert
0430: 28 20 70 48 21 3d 30 20 29 3b 0a 20 20 65 6c 65  ( pH!=0 );.  ele
0440: 6d 20 3d 20 70 48 2d 3e 66 69 72 73 74 3b 0a 20  m = pH->first;. 
0450: 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 30 3b 0a   pH->first = 0;.
0460: 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70    sqlite3_free(p
0470: 48 2d 3e 68 74 29 3b 0a 20 20 70 48 2d 3e 68 74  H->ht);.  pH->ht
0480: 20 3d 20 30 3b 0a 20 20 70 48 2d 3e 68 74 73 69   = 0;.  pH->htsi
0490: 7a 65 20 3d 20 30 3b 0a 20 20 77 68 69 6c 65 28  ze = 0;.  while(
04a0: 20 65 6c 65 6d 20 29 7b 0a 20 20 20 20 48 61 73   elem ){.    Has
04b0: 68 45 6c 65 6d 20 2a 6e 65 78 74 5f 65 6c 65 6d  hElem *next_elem
04c0: 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20   = elem->next;. 
04d0: 20 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28     sqlite3_free(
04e0: 65 6c 65 6d 29 3b 0a 20 20 20 20 65 6c 65 6d 20  elem);.    elem 
04f0: 3d 20 6e 65 78 74 5f 65 6c 65 6d 3b 0a 20 20 7d  = next_elem;.  }
0500: 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 20 3d 20 30  .  pH->count = 0
0510: 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 54 68 65 20 68  ;.}../*.** The h
0520: 61 73 68 69 6e 67 20 66 75 6e 63 74 69 6f 6e 2e  ashing function.
0530: 0a 2a 2f 0a 73 74 61 74 69 63 20 75 6e 73 69 67  .*/.static unsig
0540: 6e 65 64 20 69 6e 74 20 73 74 72 48 61 73 68 28  ned int strHash(
0550: 63 6f 6e 73 74 20 63 68 61 72 20 2a 7a 2c 20 69  const char *z, i
0560: 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 69 6e 74 20  nt nKey){.  int 
0570: 68 20 3d 20 30 3b 0a 20 20 61 73 73 65 72 74 28  h = 0;.  assert(
0580: 20 6e 4b 65 79 3e 3d 30 20 29 3b 0a 20 20 77 68   nKey>=0 );.  wh
0590: 69 6c 65 28 20 6e 4b 65 79 20 3e 20 30 20 20 29  ile( nKey > 0  )
05a0: 7b 0a 20 20 20 20 68 20 3d 20 28 68 3c 3c 33 29  {.    h = (h<<3)
05b0: 20 5e 20 68 20 5e 20 73 71 6c 69 74 65 33 55 70   ^ h ^ sqlite3Up
05c0: 70 65 72 54 6f 4c 6f 77 65 72 5b 28 75 6e 73 69  perToLower[(unsi
05d0: 67 6e 65 64 20 63 68 61 72 29 2a 7a 2b 2b 5d 3b  gned char)*z++];
05e0: 0a 20 20 20 20 6e 4b 65 79 2d 2d 3b 0a 20 20 7d  .    nKey--;.  }
05f0: 0a 20 20 72 65 74 75 72 6e 20 68 3b 0a 7d 0a 0a  .  return h;.}..
0600: 0a 2f 2a 20 4c 69 6e 6b 20 70 4e 65 77 20 65 6c  ./* Link pNew el
0610: 65 6d 65 6e 74 20 69 6e 74 6f 20 74 68 65 20 68  ement into the h
0620: 61 73 68 20 74 61 62 6c 65 20 70 48 2e 20 20 49  ash table pH.  I
0630: 66 20 70 45 6e 74 72 79 21 3d 30 20 74 68 65 6e  f pEntry!=0 then
0640: 20 61 6c 73 6f 0a 2a 2a 20 69 6e 73 65 72 74 20   also.** insert 
0650: 70 4e 65 77 20 69 6e 74 6f 20 74 68 65 20 70 45  pNew into the pE
0660: 6e 74 72 79 20 68 61 73 68 20 62 75 63 6b 65 74  ntry hash bucket
0670: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64  ..*/.static void
0680: 20 69 6e 73 65 72 74 45 6c 65 6d 65 6e 74 28 0a   insertElement(.
0690: 20 20 48 61 73 68 20 2a 70 48 2c 20 20 20 20 20    Hash *pH,     
06a0: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20           /* The 
06b0: 63 6f 6d 70 6c 65 74 65 20 68 61 73 68 20 74 61  complete hash ta
06c0: 62 6c 65 20 2a 2f 0a 20 20 73 74 72 75 63 74 20  ble */.  struct 
06d0: 5f 68 74 20 2a 70 45 6e 74 72 79 2c 20 20 20 20  _ht *pEntry,    
06e0: 2f 2a 20 54 68 65 20 65 6e 74 72 79 20 69 6e 74  /* The entry int
06f0: 6f 20 77 68 69 63 68 20 70 4e 65 77 20 69 73 20  o which pNew is 
0700: 69 6e 73 65 72 74 65 64 20 2a 2f 0a 20 20 48 61  inserted */.  Ha
0710: 73 68 45 6c 65 6d 20 2a 70 4e 65 77 20 20 20 20  shElem *pNew    
0720: 20 20 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d       /* The elem
0730: 65 6e 74 20 74 6f 20 62 65 20 69 6e 73 65 72 74  ent to be insert
0740: 65 64 20 2a 2f 0a 29 7b 0a 20 20 48 61 73 68 45  ed */.){.  HashE
0750: 6c 65 6d 20 2a 70 48 65 61 64 3b 20 20 20 20 20  lem *pHead;     
0760: 20 20 2f 2a 20 46 69 72 73 74 20 65 6c 65 6d 65    /* First eleme
0770: 6e 74 20 61 6c 72 65 61 64 79 20 69 6e 20 70 45  nt already in pE
0780: 6e 74 72 79 20 2a 2f 0a 20 20 69 66 28 20 70 45  ntry */.  if( pE
0790: 6e 74 72 79 20 29 7b 0a 20 20 20 20 70 48 65 61  ntry ){.    pHea
07a0: 64 20 3d 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e  d = pEntry->coun
07b0: 74 20 3f 20 70 45 6e 74 72 79 2d 3e 63 68 61 69  t ? pEntry->chai
07c0: 6e 20 3a 20 30 3b 0a 20 20 20 20 70 45 6e 74 72  n : 0;.    pEntr
07d0: 79 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20 20 20 20  y->count++;.    
07e0: 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 20 3d 20  pEntry->chain = 
07f0: 70 4e 65 77 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20  pNew;.  }else{. 
0800: 20 20 20 70 48 65 61 64 20 3d 20 30 3b 0a 20 20     pHead = 0;.  
0810: 7d 0a 20 20 69 66 28 20 70 48 65 61 64 20 29 7b  }.  if( pHead ){
0820: 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 65 78 74 20  .    pNew->next 
0830: 3d 20 70 48 65 61 64 3b 0a 20 20 20 20 70 4e 65  = pHead;.    pNe
0840: 77 2d 3e 70 72 65 76 20 3d 20 70 48 65 61 64 2d  w->prev = pHead-
0850: 3e 70 72 65 76 3b 0a 20 20 20 20 69 66 28 20 70  >prev;.    if( p
0860: 48 65 61 64 2d 3e 70 72 65 76 20 29 7b 20 70 48  Head->prev ){ pH
0870: 65 61 64 2d 3e 70 72 65 76 2d 3e 6e 65 78 74 20  ead->prev->next 
0880: 3d 20 70 4e 65 77 3b 20 7d 0a 20 20 20 20 65 6c  = pNew; }.    el
0890: 73 65 20 20 20 20 20 20 20 20 20 20 20 20 20 7b  se             {
08a0: 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 70 4e 65   pH->first = pNe
08b0: 77 3b 20 7d 0a 20 20 20 20 70 48 65 61 64 2d 3e  w; }.    pHead->
08c0: 70 72 65 76 20 3d 20 70 4e 65 77 3b 0a 20 20 7d  prev = pNew;.  }
08d0: 65 6c 73 65 7b 0a 20 20 20 20 70 4e 65 77 2d 3e  else{.    pNew->
08e0: 6e 65 78 74 20 3d 20 70 48 2d 3e 66 69 72 73 74  next = pH->first
08f0: 3b 0a 20 20 20 20 69 66 28 20 70 48 2d 3e 66 69  ;.    if( pH->fi
0900: 72 73 74 20 29 7b 20 70 48 2d 3e 66 69 72 73 74  rst ){ pH->first
0910: 2d 3e 70 72 65 76 20 3d 20 70 4e 65 77 3b 20 7d  ->prev = pNew; }
0920: 0a 20 20 20 20 70 4e 65 77 2d 3e 70 72 65 76 20  .    pNew->prev 
0930: 3d 20 30 3b 0a 20 20 20 20 70 48 2d 3e 66 69 72  = 0;.    pH->fir
0940: 73 74 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 0a 7d  st = pNew;.  }.}
0950: 0a 0a 0a 2f 2a 20 52 65 73 69 7a 65 20 74 68 65  .../* Resize the
0960: 20 68 61 73 68 20 74 61 62 6c 65 20 73 6f 20 74   hash table so t
0970: 68 61 74 20 69 74 20 63 61 6e 74 61 69 6e 73 20  hat it cantains 
0980: 22 6e 65 77 5f 73 69 7a 65 22 20 62 75 63 6b 65  "new_size" bucke
0990: 74 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20 68 61  ts..**.** The ha
09a0: 73 68 20 74 61 62 6c 65 20 6d 69 67 68 74 20 66  sh table might f
09b0: 61 69 6c 20 74 6f 20 72 65 73 69 7a 65 20 69 66  ail to resize if
09c0: 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28   sqlite3_malloc(
09d0: 29 20 66 61 69 6c 73 20 6f 72 0a 2a 2a 20 69 66  ) fails or.** if
09e0: 20 74 68 65 20 6e 65 77 20 73 69 7a 65 20 69 73   the new size is
09f0: 20 74 68 65 20 73 61 6d 65 20 61 73 20 74 68 65   the same as the
0a00: 20 70 72 69 6f 72 20 73 69 7a 65 2e 0a 2a 2a 20   prior size..** 
0a10: 52 65 74 75 72 6e 20 54 52 55 45 20 69 66 20 74  Return TRUE if t
0a20: 68 65 20 72 65 73 69 7a 65 20 6f 63 63 75 72 73  he resize occurs
0a30: 20 61 6e 64 20 66 61 6c 73 65 20 69 66 20 6e 6f   and false if no
0a40: 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74  t..*/.static int
0a50: 20 72 65 68 61 73 68 28 48 61 73 68 20 2a 70 48   rehash(Hash *pH
0a60: 2c 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 6e  , unsigned int n
0a70: 65 77 5f 73 69 7a 65 29 7b 0a 20 20 73 74 72 75  ew_size){.  stru
0a80: 63 74 20 5f 68 74 20 2a 6e 65 77 5f 68 74 3b 20  ct _ht *new_ht; 
0a90: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68             /* Th
0aa0: 65 20 6e 65 77 20 68 61 73 68 20 74 61 62 6c 65  e new hash table
0ab0: 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a   */.  HashElem *
0ac0: 65 6c 65 6d 2c 20 2a 6e 65 78 74 5f 65 6c 65 6d  elem, *next_elem
0ad0: 3b 20 20 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f 70  ;    /* For loop
0ae0: 69 6e 67 20 6f 76 65 72 20 65 78 69 73 74 69 6e  ing over existin
0af0: 67 20 65 6c 65 6d 65 6e 74 73 20 2a 2f 0a 0a 23  g elements */..#
0b00: 69 66 20 53 51 4c 49 54 45 5f 4d 41 4c 4c 4f 43  if SQLITE_MALLOC
0b10: 5f 53 4f 46 54 5f 4c 49 4d 49 54 3e 30 0a 20 20  _SOFT_LIMIT>0.  
0b20: 69 66 28 20 6e 65 77 5f 73 69 7a 65 2a 73 69 7a  if( new_size*siz
0b30: 65 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29 3e  eof(struct _ht)>
0b40: 53 51 4c 49 54 45 5f 4d 41 4c 4c 4f 43 5f 53 4f  SQLITE_MALLOC_SO
0b50: 46 54 5f 4c 49 4d 49 54 20 29 7b 0a 20 20 20 20  FT_LIMIT ){.    
0b60: 6e 65 77 5f 73 69 7a 65 20 3d 20 53 51 4c 49 54  new_size = SQLIT
0b70: 45 5f 4d 41 4c 4c 4f 43 5f 53 4f 46 54 5f 4c 49  E_MALLOC_SOFT_LI
0b80: 4d 49 54 2f 73 69 7a 65 6f 66 28 73 74 72 75 63  MIT/sizeof(struc
0b90: 74 20 5f 68 74 29 3b 0a 20 20 7d 0a 20 20 69 66  t _ht);.  }.  if
0ba0: 28 20 6e 65 77 5f 73 69 7a 65 3d 3d 70 48 2d 3e  ( new_size==pH->
0bb0: 68 74 73 69 7a 65 20 29 20 72 65 74 75 72 6e 20  htsize ) return 
0bc0: 30 3b 0a 23 65 6e 64 69 66 0a 0a 20 20 2f 2a 20  0;.#endif..  /* 
0bd0: 54 68 65 20 69 6e 61 62 69 6c 69 74 79 20 74 6f  The inability to
0be0: 20 61 6c 6c 6f 63 61 74 65 73 20 73 70 61 63 65   allocates space
0bf0: 20 66 6f 72 20 61 20 6c 61 72 67 65 72 20 68 61   for a larger ha
0c00: 73 68 20 74 61 62 6c 65 20 69 73 0a 20 20 2a 2a  sh table is.  **
0c10: 20 61 20 70 65 72 66 6f 72 6d 61 6e 63 65 20 68   a performance h
0c20: 69 74 20 62 75 74 20 69 74 20 69 73 20 6e 6f 74  it but it is not
0c30: 20 61 20 66 61 74 61 6c 20 65 72 72 6f 72 2e 20   a fatal error. 
0c40: 20 53 6f 20 6d 61 72 6b 20 74 68 65 0a 20 20 2a   So mark the.  *
0c50: 2a 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 61 73 20  * allocation as 
0c60: 61 20 62 65 6e 69 67 6e 2e 20 55 73 65 20 73 71  a benign. Use sq
0c70: 6c 69 74 65 33 4d 61 6c 6c 6f 63 28 29 2f 6d 65  lite3Malloc()/me
0c80: 6d 73 65 74 28 30 29 20 69 6e 73 74 65 61 64 20  mset(0) instead 
0c90: 6f 66 20 0a 20 20 2a 2a 20 73 71 6c 69 74 65 33  of .  ** sqlite3
0ca0: 4d 61 6c 6c 6f 63 5a 65 72 6f 28 29 20 74 6f 20  MallocZero() to 
0cb0: 6d 61 6b 65 20 74 68 65 20 61 6c 6c 6f 63 61 74  make the allocat
0cc0: 69 6f 6e 2c 20 61 73 20 73 71 6c 69 74 65 33 4d  ion, as sqlite3M
0cd0: 61 6c 6c 6f 63 5a 65 72 6f 28 29 0a 20 20 2a 2a  allocZero().  **
0ce0: 20 6f 6e 6c 79 20 7a 65 72 6f 65 73 20 74 68 65   only zeroes the
0cf0: 20 72 65 71 75 65 73 74 65 64 20 6e 75 6d 62 65   requested numbe
0d00: 72 20 6f 66 20 62 79 74 65 73 20 77 68 65 72 65  r of bytes where
0d10: 61 73 20 74 68 69 73 20 6d 6f 64 75 6c 65 20 77  as this module w
0d20: 69 6c 6c 0a 20 20 2a 2a 20 75 73 65 20 74 68 65  ill.  ** use the
0d30: 20 61 63 74 75 61 6c 20 61 6d 6f 75 6e 74 20 6f   actual amount o
0d40: 66 20 73 70 61 63 65 20 61 6c 6c 6f 63 61 74 65  f space allocate
0d50: 64 20 66 6f 72 20 74 68 65 20 68 61 73 68 20 74  d for the hash t
0d60: 61 62 6c 65 20 28 77 68 69 63 68 0a 20 20 2a 2a  able (which.  **
0d70: 20 6d 61 79 20 62 65 20 6c 61 72 67 65 72 20 74   may be larger t
0d80: 68 61 6e 20 74 68 65 20 72 65 71 75 65 73 74 65  han the requeste
0d90: 64 20 61 6d 6f 75 6e 74 29 2e 0a 20 20 2a 2f 0a  d amount)..  */.
0da0: 20 20 73 71 6c 69 74 65 33 42 65 67 69 6e 42 65    sqlite3BeginBe
0db0: 6e 69 67 6e 4d 61 6c 6c 6f 63 28 29 3b 0a 20 20  nignMalloc();.  
0dc0: 6e 65 77 5f 68 74 20 3d 20 28 73 74 72 75 63 74  new_ht = (struct
0dd0: 20 5f 68 74 20 2a 29 73 71 6c 69 74 65 33 4d 61   _ht *)sqlite3Ma
0de0: 6c 6c 6f 63 28 20 6e 65 77 5f 73 69 7a 65 2a 73  lloc( new_size*s
0df0: 69 7a 65 6f 66 28 73 74 72 75 63 74 20 5f 68 74  izeof(struct _ht
0e00: 29 20 29 3b 0a 20 20 73 71 6c 69 74 65 33 45 6e  ) );.  sqlite3En
0e10: 64 42 65 6e 69 67 6e 4d 61 6c 6c 6f 63 28 29 3b  dBenignMalloc();
0e20: 0a 0a 20 20 69 66 28 20 6e 65 77 5f 68 74 3d 3d  ..  if( new_ht==
0e30: 30 20 29 20 72 65 74 75 72 6e 20 30 3b 0a 20 20  0 ) return 0;.  
0e40: 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70 48 2d  sqlite3_free(pH-
0e50: 3e 68 74 29 3b 0a 20 20 70 48 2d 3e 68 74 20 3d  >ht);.  pH->ht =
0e60: 20 6e 65 77 5f 68 74 3b 0a 20 20 70 48 2d 3e 68   new_ht;.  pH->h
0e70: 74 73 69 7a 65 20 3d 20 6e 65 77 5f 73 69 7a 65  tsize = new_size
0e80: 20 3d 20 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63   = sqlite3Malloc
0e90: 53 69 7a 65 28 6e 65 77 5f 68 74 29 2f 73 69 7a  Size(new_ht)/siz
0ea0: 65 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29 3b  eof(struct _ht);
0eb0: 0a 20 20 6d 65 6d 73 65 74 28 6e 65 77 5f 68 74  .  memset(new_ht
0ec0: 2c 20 30 2c 20 6e 65 77 5f 73 69 7a 65 2a 73 69  , 0, new_size*si
0ed0: 7a 65 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29  zeof(struct _ht)
0ee0: 29 3b 0a 20 20 66 6f 72 28 65 6c 65 6d 3d 70 48  );.  for(elem=pH
0ef0: 2d 3e 66 69 72 73 74 2c 20 70 48 2d 3e 66 69 72  ->first, pH->fir
0f00: 73 74 3d 30 3b 20 65 6c 65 6d 3b 20 65 6c 65 6d  st=0; elem; elem
0f10: 20 3d 20 6e 65 78 74 5f 65 6c 65 6d 29 7b 0a 20   = next_elem){. 
0f20: 20 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20     unsigned int 
0f30: 68 20 3d 20 73 74 72 48 61 73 68 28 65 6c 65 6d  h = strHash(elem
0f40: 2d 3e 70 4b 65 79 2c 20 65 6c 65 6d 2d 3e 6e 4b  ->pKey, elem->nK
0f50: 65 79 29 20 25 20 6e 65 77 5f 73 69 7a 65 3b 0a  ey) % new_size;.
0f60: 20 20 20 20 6e 65 78 74 5f 65 6c 65 6d 20 3d 20      next_elem = 
0f70: 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20 20  elem->next;.    
0f80: 69 6e 73 65 72 74 45 6c 65 6d 65 6e 74 28 70 48  insertElement(pH
0f90: 2c 20 26 6e 65 77 5f 68 74 5b 68 5d 2c 20 65 6c  , &new_ht[h], el
0fa0: 65 6d 29 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72  em);.  }.  retur
0fb0: 6e 20 31 3b 0a 7d 0a 0a 2f 2a 20 54 68 69 73 20  n 1;.}../* This 
0fc0: 66 75 6e 63 74 69 6f 6e 20 28 66 6f 72 20 69 6e  function (for in
0fd0: 74 65 72 6e 61 6c 20 75 73 65 20 6f 6e 6c 79 29  ternal use only)
0fe0: 20 6c 6f 63 61 74 65 73 20 61 6e 20 65 6c 65 6d   locates an elem
0ff0: 65 6e 74 20 69 6e 20 61 6e 0a 2a 2a 20 68 61 73  ent in an.** has
1000: 68 20 74 61 62 6c 65 20 74 68 61 74 20 6d 61 74  h table that mat
1010: 63 68 65 73 20 74 68 65 20 67 69 76 65 6e 20 6b  ches the given k
1020: 65 79 2e 20 20 54 68 65 20 68 61 73 68 20 66 6f  ey.  The hash fo
1030: 72 20 74 68 69 73 20 6b 65 79 20 68 61 73 0a 2a  r this key has.*
1040: 2a 20 61 6c 72 65 61 64 79 20 62 65 65 6e 20 63  * already been c
1050: 6f 6d 70 75 74 65 64 20 61 6e 64 20 69 73 20 70  omputed and is p
1060: 61 73 73 65 64 20 61 73 20 74 68 65 20 34 74 68  assed as the 4th
1070: 20 70 61 72 61 6d 65 74 65 72 2e 0a 2a 2f 0a 73   parameter..*/.s
1080: 74 61 74 69 63 20 48 61 73 68 45 6c 65 6d 20 2a  tatic HashElem *
1090: 66 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65 6e  findElementGiven
10a0: 48 61 73 68 28 0a 20 20 63 6f 6e 73 74 20 48 61  Hash(.  const Ha
10b0: 73 68 20 2a 70 48 2c 20 20 20 20 20 2f 2a 20 54  sh *pH,     /* T
10c0: 68 65 20 70 48 20 74 6f 20 62 65 20 73 65 61 72  he pH to be sear
10d0: 63 68 65 64 20 2a 2f 0a 20 20 63 6f 6e 73 74 20  ched */.  const 
10e0: 63 68 61 72 20 2a 70 4b 65 79 2c 20 20 20 2f 2a  char *pKey,   /*
10f0: 20 54 68 65 20 6b 65 79 20 77 65 20 61 72 65 20   The key we are 
1100: 73 65 61 72 63 68 69 6e 67 20 66 6f 72 20 2a 2f  searching for */
1110: 0a 20 20 69 6e 74 20 6e 4b 65 79 2c 20 20 20 20  .  int nKey,    
1120: 20 20 20 20 20 20 20 2f 2a 20 42 79 74 65 73 20         /* Bytes 
1130: 69 6e 20 6b 65 79 20 28 6e 6f 74 20 63 6f 75 6e  in key (not coun
1140: 74 69 6e 67 20 7a 65 72 6f 20 74 65 72 6d 69 6e  ting zero termin
1150: 61 74 6f 72 29 20 2a 2f 0a 20 20 75 6e 73 69 67  ator) */.  unsig
1160: 6e 65 64 20 69 6e 74 20 68 20 20 20 20 20 20 2f  ned int h      /
1170: 2a 20 54 68 65 20 68 61 73 68 20 66 6f 72 20 74  * The hash for t
1180: 68 69 73 20 6b 65 79 2e 20 2a 2f 0a 29 7b 0a 20  his key. */.){. 
1190: 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b   HashElem *elem;
11a0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
11b0: 2f 2a 20 55 73 65 64 20 74 6f 20 6c 6f 6f 70 20  /* Used to loop 
11c0: 74 68 72 75 20 74 68 65 20 65 6c 65 6d 65 6e 74  thru the element
11d0: 20 6c 69 73 74 20 2a 2f 0a 20 20 69 6e 74 20 63   list */.  int c
11e0: 6f 75 6e 74 3b 20 20 20 20 20 20 20 20 20 20 20  ount;           
11f0: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d            /* Num
1200: 62 65 72 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20  ber of elements 
1210: 6c 65 66 74 20 74 6f 20 74 65 73 74 20 2a 2f 0a  left to test */.
1220: 0a 20 20 69 66 28 20 70 48 2d 3e 68 74 20 29 7b  .  if( pH->ht ){
1230: 0a 20 20 20 20 73 74 72 75 63 74 20 5f 68 74 20  .    struct _ht 
1240: 2a 70 45 6e 74 72 79 20 3d 20 26 70 48 2d 3e 68  *pEntry = &pH->h
1250: 74 5b 68 5d 3b 0a 20 20 20 20 65 6c 65 6d 20 3d  t[h];.    elem =
1260: 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3b 0a   pEntry->chain;.
1270: 20 20 20 20 63 6f 75 6e 74 20 3d 20 70 45 6e 74      count = pEnt
1280: 72 79 2d 3e 63 6f 75 6e 74 3b 0a 20 20 7d 65 6c  ry->count;.  }el
1290: 73 65 7b 0a 20 20 20 20 65 6c 65 6d 20 3d 20 70  se{.    elem = p
12a0: 48 2d 3e 66 69 72 73 74 3b 0a 20 20 20 20 63 6f  H->first;.    co
12b0: 75 6e 74 20 3d 20 70 48 2d 3e 63 6f 75 6e 74 3b  unt = pH->count;
12c0: 0a 20 20 7d 0a 20 20 77 68 69 6c 65 28 20 63 6f  .  }.  while( co
12d0: 75 6e 74 2d 2d 20 26 26 20 41 4c 57 41 59 53 28  unt-- && ALWAYS(
12e0: 65 6c 65 6d 29 20 29 7b 0a 20 20 20 20 69 66 28  elem) ){.    if(
12f0: 20 65 6c 65 6d 2d 3e 6e 4b 65 79 3d 3d 6e 4b 65   elem->nKey==nKe
1300: 79 20 26 26 20 73 71 6c 69 74 65 33 53 74 72 4e  y && sqlite3StrN
1310: 49 43 6d 70 28 65 6c 65 6d 2d 3e 70 4b 65 79 2c  ICmp(elem->pKey,
1320: 70 4b 65 79 2c 6e 4b 65 79 29 3d 3d 30 20 29 7b  pKey,nKey)==0 ){
1330: 20 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 65   .      return e
1340: 6c 65 6d 3b 0a 20 20 20 20 7d 0a 20 20 20 20 65  lem;.    }.    e
1350: 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74  lem = elem->next
1360: 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 30  ;.  }.  return 0
1370: 3b 0a 7d 0a 0a 2f 2a 20 52 65 6d 6f 76 65 20 61  ;.}../* Remove a
1380: 20 73 69 6e 67 6c 65 20 65 6e 74 72 79 20 66 72   single entry fr
1390: 6f 6d 20 74 68 65 20 68 61 73 68 20 74 61 62 6c  om the hash tabl
13a0: 65 20 67 69 76 65 6e 20 61 20 70 6f 69 6e 74 65  e given a pointe
13b0: 72 20 74 6f 20 74 68 61 74 0a 2a 2a 20 65 6c 65  r to that.** ele
13c0: 6d 65 6e 74 20 61 6e 64 20 61 20 68 61 73 68 20  ment and a hash 
13d0: 6f 6e 20 74 68 65 20 65 6c 65 6d 65 6e 74 27 73  on the element's
13e0: 20 6b 65 79 2e 0a 2a 2f 0a 73 74 61 74 69 63 20   key..*/.static 
13f0: 76 6f 69 64 20 72 65 6d 6f 76 65 45 6c 65 6d 65  void removeEleme
1400: 6e 74 47 69 76 65 6e 48 61 73 68 28 0a 20 20 48  ntGivenHash(.  H
1410: 61 73 68 20 2a 70 48 2c 20 20 20 20 20 20 20 20  ash *pH,        
1420: 20 2f 2a 20 54 68 65 20 70 48 20 63 6f 6e 74 61   /* The pH conta
1430: 69 6e 69 6e 67 20 22 65 6c 65 6d 22 20 2a 2f 0a  ining "elem" */.
1440: 20 20 48 61 73 68 45 6c 65 6d 2a 20 65 6c 65 6d    HashElem* elem
1450: 2c 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65  ,   /* The eleme
1460: 6e 74 20 74 6f 20 62 65 20 72 65 6d 6f 76 65 64  nt to be removed
1470: 20 66 72 6f 6d 20 74 68 65 20 70 48 20 2a 2f 0a   from the pH */.
1480: 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 68    unsigned int h
1490: 20 20 20 20 2f 2a 20 48 61 73 68 20 76 61 6c 75      /* Hash valu
14a0: 65 20 66 6f 72 20 74 68 65 20 65 6c 65 6d 65 6e  e for the elemen
14b0: 74 20 2a 2f 0a 29 7b 0a 20 20 73 74 72 75 63 74  t */.){.  struct
14c0: 20 5f 68 74 20 2a 70 45 6e 74 72 79 3b 0a 20 20   _ht *pEntry;.  
14d0: 69 66 28 20 65 6c 65 6d 2d 3e 70 72 65 76 20 29  if( elem->prev )
14e0: 7b 0a 20 20 20 20 65 6c 65 6d 2d 3e 70 72 65 76  {.    elem->prev
14f0: 2d 3e 6e 65 78 74 20 3d 20 65 6c 65 6d 2d 3e 6e  ->next = elem->n
1500: 65 78 74 3b 20 0a 20 20 7d 65 6c 73 65 7b 0a 20  ext; .  }else{. 
1510: 20 20 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 65     pH->first = e
1520: 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20  lem->next;.  }. 
1530: 20 69 66 28 20 65 6c 65 6d 2d 3e 6e 65 78 74 20   if( elem->next 
1540: 29 7b 0a 20 20 20 20 65 6c 65 6d 2d 3e 6e 65 78  ){.    elem->nex
1550: 74 2d 3e 70 72 65 76 20 3d 20 65 6c 65 6d 2d 3e  t->prev = elem->
1560: 70 72 65 76 3b 0a 20 20 7d 0a 20 20 69 66 28 20  prev;.  }.  if( 
1570: 70 48 2d 3e 68 74 20 29 7b 0a 20 20 20 20 70 45  pH->ht ){.    pE
1580: 6e 74 72 79 20 3d 20 26 70 48 2d 3e 68 74 5b 68  ntry = &pH->ht[h
1590: 5d 3b 0a 20 20 20 20 69 66 28 20 70 45 6e 74 72  ];.    if( pEntr
15a0: 79 2d 3e 63 68 61 69 6e 3d 3d 65 6c 65 6d 20 29  y->chain==elem )
15b0: 7b 0a 20 20 20 20 20 20 70 45 6e 74 72 79 2d 3e  {.      pEntry->
15c0: 63 68 61 69 6e 20 3d 20 65 6c 65 6d 2d 3e 6e 65  chain = elem->ne
15d0: 78 74 3b 0a 20 20 20 20 7d 0a 20 20 20 20 70 45  xt;.    }.    pE
15e0: 6e 74 72 79 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a 20  ntry->count--;. 
15f0: 20 20 20 61 73 73 65 72 74 28 20 70 45 6e 74 72     assert( pEntr
1600: 79 2d 3e 63 6f 75 6e 74 3e 3d 30 20 29 3b 0a 20  y->count>=0 );. 
1610: 20 7d 0a 20 20 73 71 6c 69 74 65 33 5f 66 72 65   }.  sqlite3_fre
1620: 65 28 20 65 6c 65 6d 20 29 3b 0a 20 20 70 48 2d  e( elem );.  pH-
1630: 3e 63 6f 75 6e 74 2d 2d 3b 0a 20 20 69 66 28 20  >count--;.  if( 
1640: 70 48 2d 3e 63 6f 75 6e 74 3d 3d 30 20 29 7b 0a  pH->count==0 ){.
1650: 20 20 20 20 61 73 73 65 72 74 28 20 70 48 2d 3e      assert( pH->
1660: 66 69 72 73 74 3d 3d 30 20 29 3b 0a 20 20 20 20  first==0 );.    
1670: 61 73 73 65 72 74 28 20 70 48 2d 3e 63 6f 75 6e  assert( pH->coun
1680: 74 3d 3d 30 20 29 3b 0a 20 20 20 20 73 71 6c 69  t==0 );.    sqli
1690: 74 65 33 48 61 73 68 43 6c 65 61 72 28 70 48 29  te3HashClear(pH)
16a0: 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 20 41 74 74 65  ;.  }.}../* Atte
16b0: 6d 70 74 20 74 6f 20 6c 6f 63 61 74 65 20 61 6e  mpt to locate an
16c0: 20 65 6c 65 6d 65 6e 74 20 6f 66 20 74 68 65 20   element of the 
16d0: 68 61 73 68 20 74 61 62 6c 65 20 70 48 20 77 69  hash table pH wi
16e0: 74 68 20 61 20 6b 65 79 0a 2a 2a 20 74 68 61 74  th a key.** that
16f0: 20 6d 61 74 63 68 65 73 20 70 4b 65 79 2c 6e 4b   matches pKey,nK
1700: 65 79 2e 20 20 52 65 74 75 72 6e 20 74 68 65 20  ey.  Return the 
1710: 64 61 74 61 20 66 6f 72 20 74 68 69 73 20 65 6c  data for this el
1720: 65 6d 65 6e 74 20 69 66 20 69 74 20 69 73 0a 2a  ement if it is.*
1730: 2a 20 66 6f 75 6e 64 2c 20 6f 72 20 4e 55 4c 4c  * found, or NULL
1740: 20 69 66 20 74 68 65 72 65 20 69 73 20 6e 6f 20   if there is no 
1750: 6d 61 74 63 68 2e 0a 2a 2f 0a 76 6f 69 64 20 2a  match..*/.void *
1760: 73 71 6c 69 74 65 33 48 61 73 68 46 69 6e 64 28  sqlite3HashFind(
1770: 63 6f 6e 73 74 20 48 61 73 68 20 2a 70 48 2c 20  const Hash *pH, 
1780: 63 6f 6e 73 74 20 63 68 61 72 20 2a 70 4b 65 79  const char *pKey
1790: 2c 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 48  , int nKey){.  H
17a0: 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20  ashElem *elem;  
17b0: 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e 74    /* The element
17c0: 20 74 68 61 74 20 6d 61 74 63 68 65 73 20 6b 65   that matches ke
17d0: 79 20 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64 20  y */.  unsigned 
17e0: 69 6e 74 20 68 3b 20 20 20 20 2f 2a 20 41 20 68  int h;    /* A h
17f0: 61 73 68 20 6f 6e 20 6b 65 79 20 2a 2f 0a 0a 20  ash on key */.. 
1800: 20 61 73 73 65 72 74 28 20 70 48 21 3d 30 20 29   assert( pH!=0 )
1810: 3b 0a 20 20 61 73 73 65 72 74 28 20 70 4b 65 79  ;.  assert( pKey
1820: 21 3d 30 20 29 3b 0a 20 20 61 73 73 65 72 74 28  !=0 );.  assert(
1830: 20 6e 4b 65 79 3e 3d 30 20 29 3b 0a 20 20 69 66   nKey>=0 );.  if
1840: 28 20 70 48 2d 3e 68 74 20 29 7b 0a 20 20 20 20  ( pH->ht ){.    
1850: 68 20 3d 20 73 74 72 48 61 73 68 28 70 4b 65 79  h = strHash(pKey
1860: 2c 20 6e 4b 65 79 29 20 25 20 70 48 2d 3e 68 74  , nKey) % pH->ht
1870: 73 69 7a 65 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20  size;.  }else{. 
1880: 20 20 20 68 20 3d 20 30 3b 0a 20 20 7d 0a 20 20     h = 0;.  }.  
1890: 65 6c 65 6d 20 3d 20 66 69 6e 64 45 6c 65 6d 65  elem = findEleme
18a0: 6e 74 47 69 76 65 6e 48 61 73 68 28 70 48 2c 20  ntGivenHash(pH, 
18b0: 70 4b 65 79 2c 20 6e 4b 65 79 2c 20 68 29 3b 0a  pKey, nKey, h);.
18c0: 20 20 72 65 74 75 72 6e 20 65 6c 65 6d 20 3f 20    return elem ? 
18d0: 65 6c 65 6d 2d 3e 64 61 74 61 20 3a 20 30 3b 0a  elem->data : 0;.
18e0: 7d 0a 0a 2f 2a 20 49 6e 73 65 72 74 20 61 6e 20  }../* Insert an 
18f0: 65 6c 65 6d 65 6e 74 20 69 6e 74 6f 20 74 68 65  element into the
1900: 20 68 61 73 68 20 74 61 62 6c 65 20 70 48 2e 20   hash table pH. 
1910: 20 54 68 65 20 6b 65 79 20 69 73 20 70 4b 65 79   The key is pKey
1920: 2c 6e 4b 65 79 0a 2a 2a 20 61 6e 64 20 74 68 65  ,nKey.** and the
1930: 20 64 61 74 61 20 69 73 20 22 64 61 74 61 22 2e   data is "data".
1940: 0a 2a 2a 0a 2a 2a 20 49 66 20 6e 6f 20 65 6c 65  .**.** If no ele
1950: 6d 65 6e 74 20 65 78 69 73 74 73 20 77 69 74 68  ment exists with
1960: 20 61 20 6d 61 74 63 68 69 6e 67 20 6b 65 79 2c   a matching key,
1970: 20 74 68 65 6e 20 61 20 6e 65 77 0a 2a 2a 20 65   then a new.** e
1980: 6c 65 6d 65 6e 74 20 69 73 20 63 72 65 61 74 65  lement is create
1990: 64 20 61 6e 64 20 4e 55 4c 4c 20 69 73 20 72 65  d and NULL is re
19a0: 74 75 72 6e 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66  turned..**.** If
19b0: 20 61 6e 6f 74 68 65 72 20 65 6c 65 6d 65 6e 74   another element
19c0: 20 61 6c 72 65 61 64 79 20 65 78 69 73 74 73 20   already exists 
19d0: 77 69 74 68 20 74 68 65 20 73 61 6d 65 20 6b 65  with the same ke
19e0: 79 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20 6e  y, then the.** n
19f0: 65 77 20 64 61 74 61 20 72 65 70 6c 61 63 65 73  ew data replaces
1a00: 20 74 68 65 20 6f 6c 64 20 64 61 74 61 20 61 6e   the old data an
1a10: 64 20 74 68 65 20 6f 6c 64 20 64 61 74 61 20 69  d the old data i
1a20: 73 20 72 65 74 75 72 6e 65 64 2e 0a 2a 2a 20 54  s returned..** T
1a30: 68 65 20 6b 65 79 20 69 73 20 6e 6f 74 20 63 6f  he key is not co
1a40: 70 69 65 64 20 69 6e 20 74 68 69 73 20 69 6e 73  pied in this ins
1a50: 74 61 6e 63 65 2e 20 20 49 66 20 61 20 6d 61 6c  tance.  If a mal
1a60: 6c 6f 63 20 66 61 69 6c 73 2c 20 74 68 65 6e 0a  loc fails, then.
1a70: 2a 2a 20 74 68 65 20 6e 65 77 20 64 61 74 61 20  ** the new data 
1a80: 69 73 20 72 65 74 75 72 6e 65 64 20 61 6e 64 20  is returned and 
1a90: 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 69  the hash table i
1aa0: 73 20 75 6e 63 68 61 6e 67 65 64 2e 0a 2a 2a 0a  s unchanged..**.
1ab0: 2a 2a 20 49 66 20 74 68 65 20 22 64 61 74 61 22  ** If the "data"
1ac0: 20 70 61 72 61 6d 65 74 65 72 20 74 6f 20 74 68   parameter to th
1ad0: 69 73 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 4e  is function is N
1ae0: 55 4c 4c 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a  ULL, then the.**
1af0: 20 65 6c 65 6d 65 6e 74 20 63 6f 72 72 65 73 70   element corresp
1b00: 6f 6e 64 69 6e 67 20 74 6f 20 22 6b 65 79 22 20  onding to "key" 
1b10: 69 73 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20  is removed from 
1b20: 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 2e 0a  the hash table..
1b30: 2a 2f 0a 76 6f 69 64 20 2a 73 71 6c 69 74 65 33  */.void *sqlite3
1b40: 48 61 73 68 49 6e 73 65 72 74 28 48 61 73 68 20  HashInsert(Hash 
1b50: 2a 70 48 2c 20 63 6f 6e 73 74 20 63 68 61 72 20  *pH, const char 
1b60: 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 2c  *pKey, int nKey,
1b70: 20 76 6f 69 64 20 2a 64 61 74 61 29 7b 0a 20 20   void *data){.  
1b80: 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 68 3b 20  unsigned int h; 
1b90: 20 20 20 20 20 20 2f 2a 20 74 68 65 20 68 61 73        /* the has
1ba0: 68 20 6f 66 20 74 68 65 20 6b 65 79 20 6d 6f 64  h of the key mod
1bb0: 75 6c 6f 20 68 61 73 68 20 74 61 62 6c 65 20 73  ulo hash table s
1bc0: 69 7a 65 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65  ize */.  HashEle
1bd0: 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 20 20 20 2f  m *elem;       /
1be0: 2a 20 55 73 65 64 20 74 6f 20 6c 6f 6f 70 20 74  * Used to loop t
1bf0: 68 72 75 20 74 68 65 20 65 6c 65 6d 65 6e 74 20  hru the element 
1c00: 6c 69 73 74 20 2a 2f 0a 20 20 48 61 73 68 45 6c  list */.  HashEl
1c10: 65 6d 20 2a 6e 65 77 5f 65 6c 65 6d 3b 20 20 20  em *new_elem;   
1c20: 2f 2a 20 4e 65 77 20 65 6c 65 6d 65 6e 74 20 61  /* New element a
1c30: 64 64 65 64 20 74 6f 20 74 68 65 20 70 48 20 2a  dded to the pH *
1c40: 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 70 48 21  /..  assert( pH!
1c50: 3d 30 20 29 3b 0a 20 20 61 73 73 65 72 74 28 20  =0 );.  assert( 
1c60: 70 4b 65 79 21 3d 30 20 29 3b 0a 20 20 61 73 73  pKey!=0 );.  ass
1c70: 65 72 74 28 20 6e 4b 65 79 3e 3d 30 20 29 3b 0a  ert( nKey>=0 );.
1c80: 20 20 69 66 28 20 70 48 2d 3e 68 74 73 69 7a 65    if( pH->htsize
1c90: 20 29 7b 0a 20 20 20 20 68 20 3d 20 73 74 72 48   ){.    h = strH
1ca0: 61 73 68 28 70 4b 65 79 2c 20 6e 4b 65 79 29 20  ash(pKey, nKey) 
1cb0: 25 20 70 48 2d 3e 68 74 73 69 7a 65 3b 0a 20 20  % pH->htsize;.  
1cc0: 7d 65 6c 73 65 7b 0a 20 20 20 20 68 20 3d 20 30  }else{.    h = 0
1cd0: 3b 0a 20 20 7d 0a 20 20 65 6c 65 6d 20 3d 20 66  ;.  }.  elem = f
1ce0: 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48  indElementGivenH
1cf0: 61 73 68 28 70 48 2c 70 4b 65 79 2c 6e 4b 65 79  ash(pH,pKey,nKey
1d00: 2c 68 29 3b 0a 20 20 69 66 28 20 65 6c 65 6d 20  ,h);.  if( elem 
1d10: 29 7b 0a 20 20 20 20 76 6f 69 64 20 2a 6f 6c 64  ){.    void *old
1d20: 5f 64 61 74 61 20 3d 20 65 6c 65 6d 2d 3e 64 61  _data = elem->da
1d30: 74 61 3b 0a 20 20 20 20 69 66 28 20 64 61 74 61  ta;.    if( data
1d40: 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20 72 65 6d  ==0 ){.      rem
1d50: 6f 76 65 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48  oveElementGivenH
1d60: 61 73 68 28 70 48 2c 65 6c 65 6d 2c 68 29 3b 0a  ash(pH,elem,h);.
1d70: 20 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20      }else{.     
1d80: 20 65 6c 65 6d 2d 3e 64 61 74 61 20 3d 20 64 61   elem->data = da
1d90: 74 61 3b 0a 20 20 20 20 20 20 65 6c 65 6d 2d 3e  ta;.      elem->
1da0: 70 4b 65 79 20 3d 20 70 4b 65 79 3b 0a 20 20 20  pKey = pKey;.   
1db0: 20 20 20 61 73 73 65 72 74 28 6e 4b 65 79 3d 3d     assert(nKey==
1dc0: 65 6c 65 6d 2d 3e 6e 4b 65 79 29 3b 0a 20 20 20  elem->nKey);.   
1dd0: 20 7d 0a 20 20 20 20 72 65 74 75 72 6e 20 6f 6c   }.    return ol
1de0: 64 5f 64 61 74 61 3b 0a 20 20 7d 0a 20 20 69 66  d_data;.  }.  if
1df0: 28 20 64 61 74 61 3d 3d 30 20 29 20 72 65 74 75  ( data==0 ) retu
1e00: 72 6e 20 30 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d  rn 0;.  new_elem
1e10: 20 3d 20 28 48 61 73 68 45 6c 65 6d 2a 29 73 71   = (HashElem*)sq
1e20: 6c 69 74 65 33 4d 61 6c 6c 6f 63 28 20 73 69 7a  lite3Malloc( siz
1e30: 65 6f 66 28 48 61 73 68 45 6c 65 6d 29 20 29 3b  eof(HashElem) );
1e40: 0a 20 20 69 66 28 20 6e 65 77 5f 65 6c 65 6d 3d  .  if( new_elem=
1e50: 3d 30 20 29 20 72 65 74 75 72 6e 20 64 61 74 61  =0 ) return data
1e60: 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b  ;.  new_elem->pK
1e70: 65 79 20 3d 20 70 4b 65 79 3b 0a 20 20 6e 65 77  ey = pKey;.  new
1e80: 5f 65 6c 65 6d 2d 3e 6e 4b 65 79 20 3d 20 6e 4b  _elem->nKey = nK
1e90: 65 79 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e  ey;.  new_elem->
1ea0: 64 61 74 61 20 3d 20 64 61 74 61 3b 0a 20 20 70  data = data;.  p
1eb0: 48 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20 20 69 66  H->count++;.  if
1ec0: 28 20 70 48 2d 3e 63 6f 75 6e 74 3e 3d 31 30 20  ( pH->count>=10 
1ed0: 26 26 20 70 48 2d 3e 63 6f 75 6e 74 20 3e 20 32  && pH->count > 2
1ee0: 2a 70 48 2d 3e 68 74 73 69 7a 65 20 29 7b 0a 20  *pH->htsize ){. 
1ef0: 20 20 20 69 66 28 20 72 65 68 61 73 68 28 70 48     if( rehash(pH
1f00: 2c 20 70 48 2d 3e 63 6f 75 6e 74 2a 32 29 20 29  , pH->count*2) )
1f10: 7b 0a 20 20 20 20 20 20 61 73 73 65 72 74 28 20  {.      assert( 
1f20: 70 48 2d 3e 68 74 73 69 7a 65 3e 30 20 29 3b 0a  pH->htsize>0 );.
1f30: 20 20 20 20 20 20 68 20 3d 20 73 74 72 48 61 73        h = strHas
1f40: 68 28 70 4b 65 79 2c 20 6e 4b 65 79 29 20 25 20  h(pKey, nKey) % 
1f50: 70 48 2d 3e 68 74 73 69 7a 65 3b 0a 20 20 20 20  pH->htsize;.    
1f60: 7d 0a 20 20 7d 0a 20 20 69 66 28 20 70 48 2d 3e  }.  }.  if( pH->
1f70: 68 74 20 29 7b 0a 20 20 20 20 69 6e 73 65 72 74  ht ){.    insert
1f80: 45 6c 65 6d 65 6e 74 28 70 48 2c 20 26 70 48 2d  Element(pH, &pH-
1f90: 3e 68 74 5b 68 5d 2c 20 6e 65 77 5f 65 6c 65 6d  >ht[h], new_elem
1fa0: 29 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20  );.  }else{.    
1fb0: 69 6e 73 65 72 74 45 6c 65 6d 65 6e 74 28 70 48  insertElement(pH
1fc0: 2c 20 30 2c 20 6e 65 77 5f 65 6c 65 6d 29 3b 0a  , 0, new_elem);.
1fd0: 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a    }.  return 0;.
1fe0: 7d 0a                                            }.