/ Hex Artifact Content
Login

Artifact 458488dcc159c301b8e7686280ab209f1fb915af:


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 0a 20 20 2a 2f 0a 20  a benign..  */. 
0c70: 20 73 71 6c 69 74 65 33 42 65 67 69 6e 42 65 6e   sqlite3BeginBen
0c80: 69 67 6e 4d 61 6c 6c 6f 63 28 29 3b 0a 20 20 6e  ignMalloc();.  n
0c90: 65 77 5f 68 74 20 3d 20 28 73 74 72 75 63 74 20  ew_ht = (struct 
0ca0: 5f 68 74 20 2a 29 73 71 6c 69 74 65 33 4d 61 6c  _ht *)sqlite3Mal
0cb0: 6c 6f 63 28 20 6e 65 77 5f 73 69 7a 65 2a 73 69  loc( new_size*si
0cc0: 7a 65 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29  zeof(struct _ht)
0cd0: 20 29 3b 0a 20 20 73 71 6c 69 74 65 33 45 6e 64   );.  sqlite3End
0ce0: 42 65 6e 69 67 6e 4d 61 6c 6c 6f 63 28 29 3b 0a  BenignMalloc();.
0cf0: 0a 20 20 69 66 28 20 6e 65 77 5f 68 74 3d 3d 30  .  if( new_ht==0
0d00: 20 29 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 73   ) return 0;.  s
0d10: 71 6c 69 74 65 33 5f 66 72 65 65 28 70 48 2d 3e  qlite3_free(pH->
0d20: 68 74 29 3b 0a 20 20 70 48 2d 3e 68 74 20 3d 20  ht);.  pH->ht = 
0d30: 6e 65 77 5f 68 74 3b 0a 20 20 70 48 2d 3e 68 74  new_ht;.  pH->ht
0d40: 73 69 7a 65 20 3d 20 6e 65 77 5f 73 69 7a 65 20  size = new_size 
0d50: 3d 20 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 53  = sqlite3MallocS
0d60: 69 7a 65 28 6e 65 77 5f 68 74 29 2f 73 69 7a 65  ize(new_ht)/size
0d70: 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29 3b 0a  of(struct _ht);.
0d80: 20 20 6d 65 6d 73 65 74 28 6e 65 77 5f 68 74 2c    memset(new_ht,
0d90: 20 30 2c 20 6e 65 77 5f 73 69 7a 65 2a 73 69 7a   0, new_size*siz
0da0: 65 6f 66 28 73 74 72 75 63 74 20 5f 68 74 29 29  eof(struct _ht))
0db0: 3b 0a 20 20 66 6f 72 28 65 6c 65 6d 3d 70 48 2d  ;.  for(elem=pH-
0dc0: 3e 66 69 72 73 74 2c 20 70 48 2d 3e 66 69 72 73  >first, pH->firs
0dd0: 74 3d 30 3b 20 65 6c 65 6d 3b 20 65 6c 65 6d 20  t=0; elem; elem 
0de0: 3d 20 6e 65 78 74 5f 65 6c 65 6d 29 7b 0a 20 20  = next_elem){.  
0df0: 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 68    unsigned int h
0e00: 20 3d 20 73 74 72 48 61 73 68 28 65 6c 65 6d 2d   = strHash(elem-
0e10: 3e 70 4b 65 79 2c 20 65 6c 65 6d 2d 3e 6e 4b 65  >pKey, elem->nKe
0e20: 79 29 20 25 20 6e 65 77 5f 73 69 7a 65 3b 0a 20  y) % new_size;. 
0e30: 20 20 20 6e 65 78 74 5f 65 6c 65 6d 20 3d 20 65     next_elem = e
0e40: 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 69  lem->next;.    i
0e50: 6e 73 65 72 74 45 6c 65 6d 65 6e 74 28 70 48 2c  nsertElement(pH,
0e60: 20 26 6e 65 77 5f 68 74 5b 68 5d 2c 20 65 6c 65   &new_ht[h], ele
0e70: 6d 29 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e  m);.  }.  return
0e80: 20 31 3b 0a 7d 0a 0a 2f 2a 20 54 68 69 73 20 66   1;.}../* This f
0e90: 75 6e 63 74 69 6f 6e 20 28 66 6f 72 20 69 6e 74  unction (for int
0ea0: 65 72 6e 61 6c 20 75 73 65 20 6f 6e 6c 79 29 20  ernal use only) 
0eb0: 6c 6f 63 61 74 65 73 20 61 6e 20 65 6c 65 6d 65  locates an eleme
0ec0: 6e 74 20 69 6e 20 61 6e 0a 2a 2a 20 68 61 73 68  nt in an.** hash
0ed0: 20 74 61 62 6c 65 20 74 68 61 74 20 6d 61 74 63   table that matc
0ee0: 68 65 73 20 74 68 65 20 67 69 76 65 6e 20 6b 65  hes the given ke
0ef0: 79 2e 20 20 54 68 65 20 68 61 73 68 20 66 6f 72  y.  The hash for
0f00: 20 74 68 69 73 20 6b 65 79 20 68 61 73 0a 2a 2a   this key has.**
0f10: 20 61 6c 72 65 61 64 79 20 62 65 65 6e 20 63 6f   already been co
0f20: 6d 70 75 74 65 64 20 61 6e 64 20 69 73 20 70 61  mputed and is pa
0f30: 73 73 65 64 20 61 73 20 74 68 65 20 34 74 68 20  ssed as the 4th 
0f40: 70 61 72 61 6d 65 74 65 72 2e 0a 2a 2f 0a 73 74  parameter..*/.st
0f50: 61 74 69 63 20 48 61 73 68 45 6c 65 6d 20 2a 66  atic HashElem *f
0f60: 69 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48  indElementGivenH
0f70: 61 73 68 28 0a 20 20 63 6f 6e 73 74 20 48 61 73  ash(.  const Has
0f80: 68 20 2a 70 48 2c 20 20 20 20 20 2f 2a 20 54 68  h *pH,     /* Th
0f90: 65 20 70 48 20 74 6f 20 62 65 20 73 65 61 72 63  e pH to be searc
0fa0: 68 65 64 20 2a 2f 0a 20 20 63 6f 6e 73 74 20 63  hed */.  const c
0fb0: 68 61 72 20 2a 70 4b 65 79 2c 20 20 20 2f 2a 20  har *pKey,   /* 
0fc0: 54 68 65 20 6b 65 79 20 77 65 20 61 72 65 20 73  The key we are s
0fd0: 65 61 72 63 68 69 6e 67 20 66 6f 72 20 2a 2f 0a  earching for */.
0fe0: 20 20 69 6e 74 20 6e 4b 65 79 2c 20 20 20 20 20    int nKey,     
0ff0: 20 20 20 20 20 20 2f 2a 20 42 79 74 65 73 20 69        /* Bytes i
1000: 6e 20 6b 65 79 20 28 6e 6f 74 20 63 6f 75 6e 74  n key (not count
1010: 69 6e 67 20 7a 65 72 6f 20 74 65 72 6d 69 6e 61  ing zero termina
1020: 74 6f 72 29 20 2a 2f 0a 20 20 75 6e 73 69 67 6e  tor) */.  unsign
1030: 65 64 20 69 6e 74 20 68 20 20 20 20 20 20 2f 2a  ed int h      /*
1040: 20 54 68 65 20 68 61 73 68 20 66 6f 72 20 74 68   The hash for th
1050: 69 73 20 6b 65 79 2e 20 2a 2f 0a 29 7b 0a 20 20  is key. */.){.  
1060: 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20  HashElem *elem; 
1070: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2f                 /
1080: 2a 20 55 73 65 64 20 74 6f 20 6c 6f 6f 70 20 74  * Used to loop t
1090: 68 72 75 20 74 68 65 20 65 6c 65 6d 65 6e 74 20  hru the element 
10a0: 6c 69 73 74 20 2a 2f 0a 20 20 69 6e 74 20 63 6f  list */.  int co
10b0: 75 6e 74 3b 20 20 20 20 20 20 20 20 20 20 20 20  unt;            
10c0: 20 20 20 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62           /* Numb
10d0: 65 72 20 6f 66 20 65 6c 65 6d 65 6e 74 73 20 6c  er of elements l
10e0: 65 66 74 20 74 6f 20 74 65 73 74 20 2a 2f 0a 0a  eft to test */..
10f0: 20 20 69 66 28 20 70 48 2d 3e 68 74 20 29 7b 0a    if( pH->ht ){.
1100: 20 20 20 20 73 74 72 75 63 74 20 5f 68 74 20 2a      struct _ht *
1110: 70 45 6e 74 72 79 20 3d 20 26 70 48 2d 3e 68 74  pEntry = &pH->ht
1120: 5b 68 5d 3b 0a 20 20 20 20 65 6c 65 6d 20 3d 20  [h];.    elem = 
1130: 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3b 0a 20  pEntry->chain;. 
1140: 20 20 20 63 6f 75 6e 74 20 3d 20 70 45 6e 74 72     count = pEntr
1150: 79 2d 3e 63 6f 75 6e 74 3b 0a 20 20 7d 65 6c 73  y->count;.  }els
1160: 65 7b 0a 20 20 20 20 65 6c 65 6d 20 3d 20 70 48  e{.    elem = pH
1170: 2d 3e 66 69 72 73 74 3b 0a 20 20 20 20 63 6f 75  ->first;.    cou
1180: 6e 74 20 3d 20 70 48 2d 3e 63 6f 75 6e 74 3b 0a  nt = pH->count;.
1190: 20 20 7d 0a 20 20 77 68 69 6c 65 28 20 63 6f 75    }.  while( cou
11a0: 6e 74 2d 2d 20 26 26 20 41 4c 57 41 59 53 28 65  nt-- && ALWAYS(e
11b0: 6c 65 6d 29 20 29 7b 0a 20 20 20 20 69 66 28 20  lem) ){.    if( 
11c0: 65 6c 65 6d 2d 3e 6e 4b 65 79 3d 3d 6e 4b 65 79  elem->nKey==nKey
11d0: 20 26 26 20 73 71 6c 69 74 65 33 53 74 72 4e 49   && sqlite3StrNI
11e0: 43 6d 70 28 65 6c 65 6d 2d 3e 70 4b 65 79 2c 70  Cmp(elem->pKey,p
11f0: 4b 65 79 2c 6e 4b 65 79 29 3d 3d 30 20 29 7b 20  Key,nKey)==0 ){ 
1200: 0a 20 20 20 20 20 20 72 65 74 75 72 6e 20 65 6c  .      return el
1210: 65 6d 3b 0a 20 20 20 20 7d 0a 20 20 20 20 65 6c  em;.    }.    el
1220: 65 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b  em = elem->next;
1230: 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b  .  }.  return 0;
1240: 0a 7d 0a 0a 2f 2a 20 52 65 6d 6f 76 65 20 61 20  .}../* Remove a 
1250: 73 69 6e 67 6c 65 20 65 6e 74 72 79 20 66 72 6f  single entry fro
1260: 6d 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65  m the hash table
1270: 20 67 69 76 65 6e 20 61 20 70 6f 69 6e 74 65 72   given a pointer
1280: 20 74 6f 20 74 68 61 74 0a 2a 2a 20 65 6c 65 6d   to that.** elem
1290: 65 6e 74 20 61 6e 64 20 61 20 68 61 73 68 20 6f  ent and a hash o
12a0: 6e 20 74 68 65 20 65 6c 65 6d 65 6e 74 27 73 20  n the element's 
12b0: 6b 65 79 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76  key..*/.static v
12c0: 6f 69 64 20 72 65 6d 6f 76 65 45 6c 65 6d 65 6e  oid removeElemen
12d0: 74 47 69 76 65 6e 48 61 73 68 28 0a 20 20 48 61  tGivenHash(.  Ha
12e0: 73 68 20 2a 70 48 2c 20 20 20 20 20 20 20 20 20  sh *pH,         
12f0: 2f 2a 20 54 68 65 20 70 48 20 63 6f 6e 74 61 69  /* The pH contai
1300: 6e 69 6e 67 20 22 65 6c 65 6d 22 20 2a 2f 0a 20  ning "elem" */. 
1310: 20 48 61 73 68 45 6c 65 6d 2a 20 65 6c 65 6d 2c   HashElem* elem,
1320: 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e     /* The elemen
1330: 74 20 74 6f 20 62 65 20 72 65 6d 6f 76 65 64 20  t to be removed 
1340: 66 72 6f 6d 20 74 68 65 20 70 48 20 2a 2f 0a 20  from the pH */. 
1350: 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20 68 20   unsigned int h 
1360: 20 20 20 2f 2a 20 48 61 73 68 20 76 61 6c 75 65     /* Hash value
1370: 20 66 6f 72 20 74 68 65 20 65 6c 65 6d 65 6e 74   for the element
1380: 20 2a 2f 0a 29 7b 0a 20 20 73 74 72 75 63 74 20   */.){.  struct 
1390: 5f 68 74 20 2a 70 45 6e 74 72 79 3b 0a 20 20 69  _ht *pEntry;.  i
13a0: 66 28 20 65 6c 65 6d 2d 3e 70 72 65 76 20 29 7b  f( elem->prev ){
13b0: 0a 20 20 20 20 65 6c 65 6d 2d 3e 70 72 65 76 2d  .    elem->prev-
13c0: 3e 6e 65 78 74 20 3d 20 65 6c 65 6d 2d 3e 6e 65  >next = elem->ne
13d0: 78 74 3b 20 0a 20 20 7d 65 6c 73 65 7b 0a 20 20  xt; .  }else{.  
13e0: 20 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 65 6c    pH->first = el
13f0: 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20 20  em->next;.  }.  
1400: 69 66 28 20 65 6c 65 6d 2d 3e 6e 65 78 74 20 29  if( elem->next )
1410: 7b 0a 20 20 20 20 65 6c 65 6d 2d 3e 6e 65 78 74  {.    elem->next
1420: 2d 3e 70 72 65 76 20 3d 20 65 6c 65 6d 2d 3e 70  ->prev = elem->p
1430: 72 65 76 3b 0a 20 20 7d 0a 20 20 69 66 28 20 70  rev;.  }.  if( p
1440: 48 2d 3e 68 74 20 29 7b 0a 20 20 20 20 70 45 6e  H->ht ){.    pEn
1450: 74 72 79 20 3d 20 26 70 48 2d 3e 68 74 5b 68 5d  try = &pH->ht[h]
1460: 3b 0a 20 20 20 20 69 66 28 20 70 45 6e 74 72 79  ;.    if( pEntry
1470: 2d 3e 63 68 61 69 6e 3d 3d 65 6c 65 6d 20 29 7b  ->chain==elem ){
1480: 0a 20 20 20 20 20 20 70 45 6e 74 72 79 2d 3e 63  .      pEntry->c
1490: 68 61 69 6e 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78  hain = elem->nex
14a0: 74 3b 0a 20 20 20 20 7d 0a 20 20 20 20 70 45 6e  t;.    }.    pEn
14b0: 74 72 79 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a 20 20  try->count--;.  
14c0: 20 20 61 73 73 65 72 74 28 20 70 45 6e 74 72 79    assert( pEntry
14d0: 2d 3e 63 6f 75 6e 74 3e 3d 30 20 29 3b 0a 20 20  ->count>=0 );.  
14e0: 7d 0a 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65  }.  sqlite3_free
14f0: 28 20 65 6c 65 6d 20 29 3b 0a 20 20 70 48 2d 3e  ( elem );.  pH->
1500: 63 6f 75 6e 74 2d 2d 3b 0a 20 20 69 66 28 20 70  count--;.  if( p
1510: 48 2d 3e 63 6f 75 6e 74 3c 3d 30 20 29 7b 0a 20  H->count<=0 ){. 
1520: 20 20 20 61 73 73 65 72 74 28 20 70 48 2d 3e 66     assert( pH->f
1530: 69 72 73 74 3d 3d 30 20 29 3b 0a 20 20 20 20 61  irst==0 );.    a
1540: 73 73 65 72 74 28 20 70 48 2d 3e 63 6f 75 6e 74  ssert( pH->count
1550: 3d 3d 30 20 29 3b 0a 20 20 20 20 73 71 6c 69 74  ==0 );.    sqlit
1560: 65 33 48 61 73 68 43 6c 65 61 72 28 70 48 29 3b  e3HashClear(pH);
1570: 0a 20 20 7d 0a 7d 0a 0a 2f 2a 20 41 74 74 65 6d  .  }.}../* Attem
1580: 70 74 20 74 6f 20 6c 6f 63 61 74 65 20 61 6e 20  pt to locate an 
1590: 65 6c 65 6d 65 6e 74 20 6f 66 20 74 68 65 20 68  element of the h
15a0: 61 73 68 20 74 61 62 6c 65 20 70 48 20 77 69 74  ash table pH wit
15b0: 68 20 61 20 6b 65 79 0a 2a 2a 20 74 68 61 74 20  h a key.** that 
15c0: 6d 61 74 63 68 65 73 20 70 4b 65 79 2c 6e 4b 65  matches pKey,nKe
15d0: 79 2e 20 20 52 65 74 75 72 6e 20 74 68 65 20 64  y.  Return the d
15e0: 61 74 61 20 66 6f 72 20 74 68 69 73 20 65 6c 65  ata for this ele
15f0: 6d 65 6e 74 20 69 66 20 69 74 20 69 73 0a 2a 2a  ment if it is.**
1600: 20 66 6f 75 6e 64 2c 20 6f 72 20 4e 55 4c 4c 20   found, or NULL 
1610: 69 66 20 74 68 65 72 65 20 69 73 20 6e 6f 20 6d  if there is no m
1620: 61 74 63 68 2e 0a 2a 2f 0a 76 6f 69 64 20 2a 73  atch..*/.void *s
1630: 71 6c 69 74 65 33 48 61 73 68 46 69 6e 64 28 63  qlite3HashFind(c
1640: 6f 6e 73 74 20 48 61 73 68 20 2a 70 48 2c 20 63  onst Hash *pH, c
1650: 6f 6e 73 74 20 63 68 61 72 20 2a 70 4b 65 79 2c  onst char *pKey,
1660: 20 69 6e 74 20 6e 4b 65 79 29 7b 0a 20 20 48 61   int nKey){.  Ha
1670: 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20  shElem *elem;   
1680: 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65 6e 74 20   /* The element 
1690: 74 68 61 74 20 6d 61 74 63 68 65 73 20 6b 65 79  that matches key
16a0: 20 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64 20 69   */.  unsigned i
16b0: 6e 74 20 68 3b 20 20 20 20 2f 2a 20 41 20 68 61  nt h;    /* A ha
16c0: 73 68 20 6f 6e 20 6b 65 79 20 2a 2f 0a 0a 20 20  sh on key */..  
16d0: 61 73 73 65 72 74 28 20 70 48 21 3d 30 20 29 3b  assert( pH!=0 );
16e0: 0a 20 20 61 73 73 65 72 74 28 20 70 4b 65 79 21  .  assert( pKey!
16f0: 3d 30 20 29 3b 0a 20 20 61 73 73 65 72 74 28 20  =0 );.  assert( 
1700: 6e 4b 65 79 3e 3d 30 20 29 3b 0a 20 20 69 66 28  nKey>=0 );.  if(
1710: 20 70 48 2d 3e 68 74 20 29 7b 0a 20 20 20 20 68   pH->ht ){.    h
1720: 20 3d 20 73 74 72 48 61 73 68 28 70 4b 65 79 2c   = strHash(pKey,
1730: 20 6e 4b 65 79 29 20 25 20 70 48 2d 3e 68 74 73   nKey) % pH->hts
1740: 69 7a 65 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20  ize;.  }else{.  
1750: 20 20 68 20 3d 20 30 3b 0a 20 20 7d 0a 20 20 65    h = 0;.  }.  e
1760: 6c 65 6d 20 3d 20 66 69 6e 64 45 6c 65 6d 65 6e  lem = findElemen
1770: 74 47 69 76 65 6e 48 61 73 68 28 70 48 2c 20 70  tGivenHash(pH, p
1780: 4b 65 79 2c 20 6e 4b 65 79 2c 20 68 29 3b 0a 20  Key, nKey, h);. 
1790: 20 72 65 74 75 72 6e 20 65 6c 65 6d 20 3f 20 65   return elem ? e
17a0: 6c 65 6d 2d 3e 64 61 74 61 20 3a 20 30 3b 0a 7d  lem->data : 0;.}
17b0: 0a 0a 2f 2a 20 49 6e 73 65 72 74 20 61 6e 20 65  ../* Insert an e
17c0: 6c 65 6d 65 6e 74 20 69 6e 74 6f 20 74 68 65 20  lement into the 
17d0: 68 61 73 68 20 74 61 62 6c 65 20 70 48 2e 20 20  hash table pH.  
17e0: 54 68 65 20 6b 65 79 20 69 73 20 70 4b 65 79 2c  The key is pKey,
17f0: 6e 4b 65 79 0a 2a 2a 20 61 6e 64 20 74 68 65 20  nKey.** and the 
1800: 64 61 74 61 20 69 73 20 22 64 61 74 61 22 2e 0a  data is "data"..
1810: 2a 2a 0a 2a 2a 20 49 66 20 6e 6f 20 65 6c 65 6d  **.** If no elem
1820: 65 6e 74 20 65 78 69 73 74 73 20 77 69 74 68 20  ent exists with 
1830: 61 20 6d 61 74 63 68 69 6e 67 20 6b 65 79 2c 20  a matching key, 
1840: 74 68 65 6e 20 61 20 6e 65 77 0a 2a 2a 20 65 6c  then a new.** el
1850: 65 6d 65 6e 74 20 69 73 20 63 72 65 61 74 65 64  ement is created
1860: 20 61 6e 64 20 4e 55 4c 4c 20 69 73 20 72 65 74   and NULL is ret
1870: 75 72 6e 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20  urned..**.** If 
1880: 61 6e 6f 74 68 65 72 20 65 6c 65 6d 65 6e 74 20  another element 
1890: 61 6c 72 65 61 64 79 20 65 78 69 73 74 73 20 77  already exists w
18a0: 69 74 68 20 74 68 65 20 73 61 6d 65 20 6b 65 79  ith the same key
18b0: 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20 6e 65  , then the.** ne
18c0: 77 20 64 61 74 61 20 72 65 70 6c 61 63 65 73 20  w data replaces 
18d0: 74 68 65 20 6f 6c 64 20 64 61 74 61 20 61 6e 64  the old data and
18e0: 20 74 68 65 20 6f 6c 64 20 64 61 74 61 20 69 73   the old data is
18f0: 20 72 65 74 75 72 6e 65 64 2e 0a 2a 2a 20 54 68   returned..** Th
1900: 65 20 6b 65 79 20 69 73 20 6e 6f 74 20 63 6f 70  e key is not cop
1910: 69 65 64 20 69 6e 20 74 68 69 73 20 69 6e 73 74  ied in this inst
1920: 61 6e 63 65 2e 20 20 49 66 20 61 20 6d 61 6c 6c  ance.  If a mall
1930: 6f 63 20 66 61 69 6c 73 2c 20 74 68 65 6e 0a 2a  oc fails, then.*
1940: 2a 20 74 68 65 20 6e 65 77 20 64 61 74 61 20 69  * the new data i
1950: 73 20 72 65 74 75 72 6e 65 64 20 61 6e 64 20 74  s returned and t
1960: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 69 73  he hash table is
1970: 20 75 6e 63 68 61 6e 67 65 64 2e 0a 2a 2a 0a 2a   unchanged..**.*
1980: 2a 20 49 66 20 74 68 65 20 22 64 61 74 61 22 20  * If the "data" 
1990: 70 61 72 61 6d 65 74 65 72 20 74 6f 20 74 68 69  parameter to thi
19a0: 73 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 4e 55  s function is NU
19b0: 4c 4c 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20  LL, then the.** 
19c0: 65 6c 65 6d 65 6e 74 20 63 6f 72 72 65 73 70 6f  element correspo
19d0: 6e 64 69 6e 67 20 74 6f 20 22 6b 65 79 22 20 69  nding to "key" i
19e0: 73 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74  s removed from t
19f0: 68 65 20 68 61 73 68 20 74 61 62 6c 65 2e 0a 2a  he hash table..*
1a00: 2f 0a 76 6f 69 64 20 2a 73 71 6c 69 74 65 33 48  /.void *sqlite3H
1a10: 61 73 68 49 6e 73 65 72 74 28 48 61 73 68 20 2a  ashInsert(Hash *
1a20: 70 48 2c 20 63 6f 6e 73 74 20 63 68 61 72 20 2a  pH, const char *
1a30: 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 2c 20  pKey, int nKey, 
1a40: 76 6f 69 64 20 2a 64 61 74 61 29 7b 0a 20 20 75  void *data){.  u
1a50: 6e 73 69 67 6e 65 64 20 69 6e 74 20 68 3b 20 20  nsigned int h;  
1a60: 20 20 20 20 20 2f 2a 20 74 68 65 20 68 61 73 68       /* the hash
1a70: 20 6f 66 20 74 68 65 20 6b 65 79 20 6d 6f 64 75   of the key modu
1a80: 6c 6f 20 68 61 73 68 20 74 61 62 6c 65 20 73 69  lo hash table si
1a90: 7a 65 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d  ze */.  HashElem
1aa0: 20 2a 65 6c 65 6d 3b 20 20 20 20 20 20 20 2f 2a   *elem;       /*
1ab0: 20 55 73 65 64 20 74 6f 20 6c 6f 6f 70 20 74 68   Used to loop th
1ac0: 72 75 20 74 68 65 20 65 6c 65 6d 65 6e 74 20 6c  ru the element l
1ad0: 69 73 74 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65  ist */.  HashEle
1ae0: 6d 20 2a 6e 65 77 5f 65 6c 65 6d 3b 20 20 20 2f  m *new_elem;   /
1af0: 2a 20 4e 65 77 20 65 6c 65 6d 65 6e 74 20 61 64  * New element ad
1b00: 64 65 64 20 74 6f 20 74 68 65 20 70 48 20 2a 2f  ded to the pH */
1b10: 0a 0a 20 20 61 73 73 65 72 74 28 20 70 48 21 3d  ..  assert( pH!=
1b20: 30 20 29 3b 0a 20 20 61 73 73 65 72 74 28 20 70  0 );.  assert( p
1b30: 4b 65 79 21 3d 30 20 29 3b 0a 20 20 61 73 73 65  Key!=0 );.  asse
1b40: 72 74 28 20 6e 4b 65 79 3e 3d 30 20 29 3b 0a 20  rt( nKey>=0 );. 
1b50: 20 69 66 28 20 70 48 2d 3e 68 74 73 69 7a 65 20   if( pH->htsize 
1b60: 29 7b 0a 20 20 20 20 68 20 3d 20 73 74 72 48 61  ){.    h = strHa
1b70: 73 68 28 70 4b 65 79 2c 20 6e 4b 65 79 29 20 25  sh(pKey, nKey) %
1b80: 20 70 48 2d 3e 68 74 73 69 7a 65 3b 0a 20 20 7d   pH->htsize;.  }
1b90: 65 6c 73 65 7b 0a 20 20 20 20 68 20 3d 20 30 3b  else{.    h = 0;
1ba0: 0a 20 20 7d 0a 20 20 65 6c 65 6d 20 3d 20 66 69  .  }.  elem = fi
1bb0: 6e 64 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61  ndElementGivenHa
1bc0: 73 68 28 70 48 2c 70 4b 65 79 2c 6e 4b 65 79 2c  sh(pH,pKey,nKey,
1bd0: 68 29 3b 0a 20 20 69 66 28 20 65 6c 65 6d 20 29  h);.  if( elem )
1be0: 7b 0a 20 20 20 20 76 6f 69 64 20 2a 6f 6c 64 5f  {.    void *old_
1bf0: 64 61 74 61 20 3d 20 65 6c 65 6d 2d 3e 64 61 74  data = elem->dat
1c00: 61 3b 0a 20 20 20 20 69 66 28 20 64 61 74 61 3d  a;.    if( data=
1c10: 3d 30 20 29 7b 0a 20 20 20 20 20 20 72 65 6d 6f  =0 ){.      remo
1c20: 76 65 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61  veElementGivenHa
1c30: 73 68 28 70 48 2c 65 6c 65 6d 2c 68 29 3b 0a 20  sh(pH,elem,h);. 
1c40: 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20     }else{.      
1c50: 65 6c 65 6d 2d 3e 64 61 74 61 20 3d 20 64 61 74  elem->data = dat
1c60: 61 3b 0a 20 20 20 20 20 20 65 6c 65 6d 2d 3e 70  a;.      elem->p
1c70: 4b 65 79 20 3d 20 70 4b 65 79 3b 0a 20 20 20 20  Key = pKey;.    
1c80: 20 20 61 73 73 65 72 74 28 6e 4b 65 79 3d 3d 65    assert(nKey==e
1c90: 6c 65 6d 2d 3e 6e 4b 65 79 29 3b 0a 20 20 20 20  lem->nKey);.    
1ca0: 7d 0a 20 20 20 20 72 65 74 75 72 6e 20 6f 6c 64  }.    return old
1cb0: 5f 64 61 74 61 3b 0a 20 20 7d 0a 20 20 69 66 28  _data;.  }.  if(
1cc0: 20 64 61 74 61 3d 3d 30 20 29 20 72 65 74 75 72   data==0 ) retur
1cd0: 6e 20 30 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 20  n 0;.  new_elem 
1ce0: 3d 20 28 48 61 73 68 45 6c 65 6d 2a 29 73 71 6c  = (HashElem*)sql
1cf0: 69 74 65 33 4d 61 6c 6c 6f 63 28 20 73 69 7a 65  ite3Malloc( size
1d00: 6f 66 28 48 61 73 68 45 6c 65 6d 29 20 29 3b 0a  of(HashElem) );.
1d10: 20 20 69 66 28 20 6e 65 77 5f 65 6c 65 6d 3d 3d    if( new_elem==
1d20: 30 20 29 20 72 65 74 75 72 6e 20 64 61 74 61 3b  0 ) return data;
1d30: 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65  .  new_elem->pKe
1d40: 79 20 3d 20 70 4b 65 79 3b 0a 20 20 6e 65 77 5f  y = pKey;.  new_
1d50: 65 6c 65 6d 2d 3e 6e 4b 65 79 20 3d 20 6e 4b 65  elem->nKey = nKe
1d60: 79 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 64  y;.  new_elem->d
1d70: 61 74 61 20 3d 20 64 61 74 61 3b 0a 20 20 70 48  ata = data;.  pH
1d80: 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20 20 69 66 28  ->count++;.  if(
1d90: 20 70 48 2d 3e 63 6f 75 6e 74 3e 3d 31 30 20 26   pH->count>=10 &
1da0: 26 20 70 48 2d 3e 63 6f 75 6e 74 20 3e 20 32 2a  & pH->count > 2*
1db0: 70 48 2d 3e 68 74 73 69 7a 65 20 29 7b 0a 20 20  pH->htsize ){.  
1dc0: 20 20 69 66 28 20 72 65 68 61 73 68 28 70 48 2c    if( rehash(pH,
1dd0: 20 70 48 2d 3e 63 6f 75 6e 74 2a 32 29 20 29 7b   pH->count*2) ){
1de0: 0a 20 20 20 20 20 20 61 73 73 65 72 74 28 20 70  .      assert( p
1df0: 48 2d 3e 68 74 73 69 7a 65 3e 30 20 29 3b 0a 20  H->htsize>0 );. 
1e00: 20 20 20 20 20 68 20 3d 20 73 74 72 48 61 73 68       h = strHash
1e10: 28 70 4b 65 79 2c 20 6e 4b 65 79 29 20 25 20 70  (pKey, nKey) % p
1e20: 48 2d 3e 68 74 73 69 7a 65 3b 0a 20 20 20 20 7d  H->htsize;.    }
1e30: 0a 20 20 7d 0a 20 20 69 66 28 20 70 48 2d 3e 68  .  }.  if( pH->h
1e40: 74 20 29 7b 0a 20 20 20 20 69 6e 73 65 72 74 45  t ){.    insertE
1e50: 6c 65 6d 65 6e 74 28 70 48 2c 20 26 70 48 2d 3e  lement(pH, &pH->
1e60: 68 74 5b 68 5d 2c 20 6e 65 77 5f 65 6c 65 6d 29  ht[h], new_elem)
1e70: 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 69  ;.  }else{.    i
1e80: 6e 73 65 72 74 45 6c 65 6d 65 6e 74 28 70 48 2c  nsertElement(pH,
1e90: 20 30 2c 20 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20   0, new_elem);. 
1ea0: 20 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d   }.  return 0;.}
1eb0: 0a                                               .