/ Hex Artifact Content
Login

Artifact 4263fbc955f26c2e8cdc0cf214bc42435aa4e4f5:


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 0a 20 20 20 20 68 20 3d 20 28 68 3c 3c 33 29  {.    h = (h<<3)
05c0: 20 5e 20 68 20 5e 20 73 71 6c 69 74 65 33 55 70   ^ h ^ sqlite3Up
05d0: 70 65 72 54 6f 4c 6f 77 65 72 5b 63 5d 3b 0a 20  perToLower[c];. 
05e0: 20 7d 0a 20 20 72 65 74 75 72 6e 20 68 3b 0a 7d   }.  return h;.}
05f0: 0a 0a 0a 2f 2a 20 4c 69 6e 6b 20 70 4e 65 77 20  .../* Link pNew 
0600: 65 6c 65 6d 65 6e 74 20 69 6e 74 6f 20 74 68 65  element into the
0610: 20 68 61 73 68 20 74 61 62 6c 65 20 70 48 2e 20   hash table pH. 
0620: 20 49 66 20 70 45 6e 74 72 79 21 3d 30 20 74 68   If pEntry!=0 th
0630: 65 6e 20 61 6c 73 6f 0a 2a 2a 20 69 6e 73 65 72  en also.** inser
0640: 74 20 70 4e 65 77 20 69 6e 74 6f 20 74 68 65 20  t pNew into the 
0650: 70 45 6e 74 72 79 20 68 61 73 68 20 62 75 63 6b  pEntry hash buck
0660: 65 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f  et..*/.static vo
0670: 69 64 20 69 6e 73 65 72 74 45 6c 65 6d 65 6e 74  id insertElement
0680: 28 0a 20 20 48 61 73 68 20 2a 70 48 2c 20 20 20  (.  Hash *pH,   
0690: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68             /* Th
06a0: 65 20 63 6f 6d 70 6c 65 74 65 20 68 61 73 68 20  e complete hash 
06b0: 74 61 62 6c 65 20 2a 2f 0a 20 20 73 74 72 75 63  table */.  struc
06c0: 74 20 5f 68 74 20 2a 70 45 6e 74 72 79 2c 20 20  t _ht *pEntry,  
06d0: 20 20 2f 2a 20 54 68 65 20 65 6e 74 72 79 20 69    /* The entry i
06e0: 6e 74 6f 20 77 68 69 63 68 20 70 4e 65 77 20 69  nto which pNew i
06f0: 73 20 69 6e 73 65 72 74 65 64 20 2a 2f 0a 20 20  s inserted */.  
0700: 48 61 73 68 45 6c 65 6d 20 2a 70 4e 65 77 20 20  HashElem *pNew  
0710: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 65 6c         /* The el
0720: 65 6d 65 6e 74 20 74 6f 20 62 65 20 69 6e 73 65  ement to be inse
0730: 72 74 65 64 20 2a 2f 0a 29 7b 0a 20 20 48 61 73  rted */.){.  Has
0740: 68 45 6c 65 6d 20 2a 70 48 65 61 64 3b 20 20 20  hElem *pHead;   
0750: 20 20 20 20 2f 2a 20 46 69 72 73 74 20 65 6c 65      /* First ele
0760: 6d 65 6e 74 20 61 6c 72 65 61 64 79 20 69 6e 20  ment already in 
0770: 70 45 6e 74 72 79 20 2a 2f 0a 20 20 69 66 28 20  pEntry */.  if( 
0780: 70 45 6e 74 72 79 20 29 7b 0a 20 20 20 20 70 48  pEntry ){.    pH
0790: 65 61 64 20 3d 20 70 45 6e 74 72 79 2d 3e 63 6f  ead = pEntry->co
07a0: 75 6e 74 20 3f 20 70 45 6e 74 72 79 2d 3e 63 68  unt ? pEntry->ch
07b0: 61 69 6e 20 3a 20 30 3b 0a 20 20 20 20 70 45 6e  ain : 0;.    pEn
07c0: 74 72 79 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20 20  try->count++;.  
07d0: 20 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 20    pEntry->chain 
07e0: 3d 20 70 4e 65 77 3b 0a 20 20 7d 65 6c 73 65 7b  = pNew;.  }else{
07f0: 0a 20 20 20 20 70 48 65 61 64 20 3d 20 30 3b 0a  .    pHead = 0;.
0800: 20 20 7d 0a 20 20 69 66 28 20 70 48 65 61 64 20    }.  if( pHead 
0810: 29 7b 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 65 78  ){.    pNew->nex
0820: 74 20 3d 20 70 48 65 61 64 3b 0a 20 20 20 20 70  t = pHead;.    p
0830: 4e 65 77 2d 3e 70 72 65 76 20 3d 20 70 48 65 61  New->prev = pHea
0840: 64 2d 3e 70 72 65 76 3b 0a 20 20 20 20 69 66 28  d->prev;.    if(
0850: 20 70 48 65 61 64 2d 3e 70 72 65 76 20 29 7b 20   pHead->prev ){ 
0860: 70 48 65 61 64 2d 3e 70 72 65 76 2d 3e 6e 65 78  pHead->prev->nex
0870: 74 20 3d 20 70 4e 65 77 3b 20 7d 0a 20 20 20 20  t = pNew; }.    
0880: 65 6c 73 65 20 20 20 20 20 20 20 20 20 20 20 20  else            
0890: 20 7b 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 70   { pH->first = p
08a0: 4e 65 77 3b 20 7d 0a 20 20 20 20 70 48 65 61 64  New; }.    pHead
08b0: 2d 3e 70 72 65 76 20 3d 20 70 4e 65 77 3b 0a 20  ->prev = pNew;. 
08c0: 20 7d 65 6c 73 65 7b 0a 20 20 20 20 70 4e 65 77   }else{.    pNew
08d0: 2d 3e 6e 65 78 74 20 3d 20 70 48 2d 3e 66 69 72  ->next = pH->fir
08e0: 73 74 3b 0a 20 20 20 20 69 66 28 20 70 48 2d 3e  st;.    if( pH->
08f0: 66 69 72 73 74 20 29 7b 20 70 48 2d 3e 66 69 72  first ){ pH->fir
0900: 73 74 2d 3e 70 72 65 76 20 3d 20 70 4e 65 77 3b  st->prev = pNew;
0910: 20 7d 0a 20 20 20 20 70 4e 65 77 2d 3e 70 72 65   }.    pNew->pre
0920: 76 20 3d 20 30 3b 0a 20 20 20 20 70 48 2d 3e 66  v = 0;.    pH->f
0930: 69 72 73 74 20 3d 20 70 4e 65 77 3b 0a 20 20 7d  irst = pNew;.  }
0940: 0a 7d 0a 0a 0a 2f 2a 20 52 65 73 69 7a 65 20 74  .}.../* Resize t
0950: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 73 6f  he hash table so
0960: 20 74 68 61 74 20 69 74 20 63 61 6e 74 61 69 6e   that it cantain
0970: 73 20 22 6e 65 77 5f 73 69 7a 65 22 20 62 75 63  s "new_size" buc
0980: 6b 65 74 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20  kets..**.** The 
0990: 68 61 73 68 20 74 61 62 6c 65 20 6d 69 67 68 74  hash table might
09a0: 20 66 61 69 6c 20 74 6f 20 72 65 73 69 7a 65 20   fail to resize 
09b0: 69 66 20 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f  if sqlite3_mallo
09c0: 63 28 29 20 66 61 69 6c 73 20 6f 72 0a 2a 2a 20  c() fails or.** 
09d0: 69 66 20 74 68 65 20 6e 65 77 20 73 69 7a 65 20  if the new size 
09e0: 69 73 20 74 68 65 20 73 61 6d 65 20 61 73 20 74  is the same as t
09f0: 68 65 20 70 72 69 6f 72 20 73 69 7a 65 2e 0a 2a  he prior size..*
0a00: 2a 20 52 65 74 75 72 6e 20 54 52 55 45 20 69 66  * Return TRUE if
0a10: 20 74 68 65 20 72 65 73 69 7a 65 20 6f 63 63 75   the resize occu
0a20: 72 73 20 61 6e 64 20 66 61 6c 73 65 20 69 66 20  rs and false if 
0a30: 6e 6f 74 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69  not..*/.static i
0a40: 6e 74 20 72 65 68 61 73 68 28 48 61 73 68 20 2a  nt rehash(Hash *
0a50: 70 48 2c 20 75 6e 73 69 67 6e 65 64 20 69 6e 74  pH, unsigned int
0a60: 20 6e 65 77 5f 73 69 7a 65 29 7b 0a 20 20 73 74   new_size){.  st
0a70: 72 75 63 74 20 5f 68 74 20 2a 6e 65 77 5f 68 74  ruct _ht *new_ht
0a80: 3b 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20  ;            /* 
0a90: 54 68 65 20 6e 65 77 20 68 61 73 68 20 74 61 62  The new hash tab
0aa0: 6c 65 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d  le */.  HashElem
0ab0: 20 2a 65 6c 65 6d 2c 20 2a 6e 65 78 74 5f 65 6c   *elem, *next_el
0ac0: 65 6d 3b 20 20 20 20 2f 2a 20 46 6f 72 20 6c 6f  em;    /* For lo
0ad0: 6f 70 69 6e 67 20 6f 76 65 72 20 65 78 69 73 74  oping over exist
0ae0: 69 6e 67 20 65 6c 65 6d 65 6e 74 73 20 2a 2f 0a  ing elements */.
0af0: 0a 23 69 66 20 53 51 4c 49 54 45 5f 4d 41 4c 4c  .#if SQLITE_MALL
0b00: 4f 43 5f 53 4f 46 54 5f 4c 49 4d 49 54 3e 30 0a  OC_SOFT_LIMIT>0.
0b10: 20 20 69 66 28 20 6e 65 77 5f 73 69 7a 65 2a 73    if( new_size*s
0b20: 69 7a 65 6f 66 28 73 74 72 75 63 74 20 5f 68 74  izeof(struct _ht
0b30: 29 3e 53 51 4c 49 54 45 5f 4d 41 4c 4c 4f 43 5f  )>SQLITE_MALLOC_
0b40: 53 4f 46 54 5f 4c 49 4d 49 54 20 29 7b 0a 20 20  SOFT_LIMIT ){.  
0b50: 20 20 6e 65 77 5f 73 69 7a 65 20 3d 20 53 51 4c    new_size = SQL
0b60: 49 54 45 5f 4d 41 4c 4c 4f 43 5f 53 4f 46 54 5f  ITE_MALLOC_SOFT_
0b70: 4c 49 4d 49 54 2f 73 69 7a 65 6f 66 28 73 74 72  LIMIT/sizeof(str
0b80: 75 63 74 20 5f 68 74 29 3b 0a 20 20 7d 0a 20 20  uct _ht);.  }.  
0b90: 69 66 28 20 6e 65 77 5f 73 69 7a 65 3d 3d 70 48  if( new_size==pH
0ba0: 2d 3e 68 74 73 69 7a 65 20 29 20 72 65 74 75 72  ->htsize ) retur
0bb0: 6e 20 30 3b 0a 23 65 6e 64 69 66 0a 0a 20 20 2f  n 0;.#endif..  /
0bc0: 2a 20 54 68 65 20 69 6e 61 62 69 6c 69 74 79 20  * The inability 
0bd0: 74 6f 20 61 6c 6c 6f 63 61 74 65 73 20 73 70 61  to allocates spa
0be0: 63 65 20 66 6f 72 20 61 20 6c 61 72 67 65 72 20  ce for a larger 
0bf0: 68 61 73 68 20 74 61 62 6c 65 20 69 73 0a 20 20  hash table is.  
0c00: 2a 2a 20 61 20 70 65 72 66 6f 72 6d 61 6e 63 65  ** a performance
0c10: 20 68 69 74 20 62 75 74 20 69 74 20 69 73 20 6e   hit but it is n
0c20: 6f 74 20 61 20 66 61 74 61 6c 20 65 72 72 6f 72  ot a fatal error
0c30: 2e 20 20 53 6f 20 6d 61 72 6b 20 74 68 65 0a 20  .  So mark the. 
0c40: 20 2a 2a 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 61   ** allocation a
0c50: 73 20 61 20 62 65 6e 69 67 6e 2e 20 55 73 65 20  s a benign. Use 
0c60: 73 71 6c 69 74 65 33 4d 61 6c 6c 6f 63 28 29 2f  sqlite3Malloc()/
0c70: 6d 65 6d 73 65 74 28 30 29 20 69 6e 73 74 65 61  memset(0) instea
0c80: 64 20 6f 66 20 0a 20 20 2a 2a 20 73 71 6c 69 74  d of .  ** sqlit
0c90: 65 33 4d 61 6c 6c 6f 63 5a 65 72 6f 28 29 20 74  e3MallocZero() t
0ca0: 6f 20 6d 61 6b 65 20 74 68 65 20 61 6c 6c 6f 63  o make the alloc
0cb0: 61 74 69 6f 6e 2c 20 61 73 20 73 71 6c 69 74 65  ation, as sqlite
0cc0: 33 4d 61 6c 6c 6f 63 5a 65 72 6f 28 29 0a 20 20  3MallocZero().  
0cd0: 2a 2a 20 6f 6e 6c 79 20 7a 65 72 6f 65 73 20 74  ** only zeroes t
0ce0: 68 65 20 72 65 71 75 65 73 74 65 64 20 6e 75 6d  he requested num
0cf0: 62 65 72 20 6f 66 20 62 79 74 65 73 20 77 68 65  ber of bytes whe
0d00: 72 65 61 73 20 74 68 69 73 20 6d 6f 64 75 6c 65  reas this module
0d10: 20 77 69 6c 6c 0a 20 20 2a 2a 20 75 73 65 20 74   will.  ** use t
0d20: 68 65 20 61 63 74 75 61 6c 20 61 6d 6f 75 6e 74  he actual amount
0d30: 20 6f 66 20 73 70 61 63 65 20 61 6c 6c 6f 63 61   of space alloca
0d40: 74 65 64 20 66 6f 72 20 74 68 65 20 68 61 73 68  ted for the hash
0d50: 20 74 61 62 6c 65 20 28 77 68 69 63 68 0a 20 20   table (which.  
0d60: 2a 2a 20 6d 61 79 20 62 65 20 6c 61 72 67 65 72  ** may be larger
0d70: 20 74 68 61 6e 20 74 68 65 20 72 65 71 75 65 73   than the reques
0d80: 74 65 64 20 61 6d 6f 75 6e 74 29 2e 0a 20 20 2a  ted amount)..  *
0d90: 2f 0a 20 20 73 71 6c 69 74 65 33 42 65 67 69 6e  /.  sqlite3Begin
0da0: 42 65 6e 69 67 6e 4d 61 6c 6c 6f 63 28 29 3b 0a  BenignMalloc();.
0db0: 20 20 6e 65 77 5f 68 74 20 3d 20 28 73 74 72 75    new_ht = (stru
0dc0: 63 74 20 5f 68 74 20 2a 29 73 71 6c 69 74 65 33  ct _ht *)sqlite3
0dd0: 4d 61 6c 6c 6f 63 28 20 6e 65 77 5f 73 69 7a 65  Malloc( new_size
0de0: 2a 73 69 7a 65 6f 66 28 73 74 72 75 63 74 20 5f  *sizeof(struct _
0df0: 68 74 29 20 29 3b 0a 20 20 73 71 6c 69 74 65 33  ht) );.  sqlite3
0e00: 45 6e 64 42 65 6e 69 67 6e 4d 61 6c 6c 6f 63 28  EndBenignMalloc(
0e10: 29 3b 0a 0a 20 20 69 66 28 20 6e 65 77 5f 68 74  );..  if( new_ht
0e20: 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 30 3b 0a  ==0 ) return 0;.
0e30: 20 20 73 71 6c 69 74 65 33 5f 66 72 65 65 28 70    sqlite3_free(p
0e40: 48 2d 3e 68 74 29 3b 0a 20 20 70 48 2d 3e 68 74  H->ht);.  pH->ht
0e50: 20 3d 20 6e 65 77 5f 68 74 3b 0a 20 20 70 48 2d   = new_ht;.  pH-
0e60: 3e 68 74 73 69 7a 65 20 3d 20 6e 65 77 5f 73 69  >htsize = new_si
0e70: 7a 65 20 3d 20 73 71 6c 69 74 65 33 4d 61 6c 6c  ze = sqlite3Mall
0e80: 6f 63 53 69 7a 65 28 6e 65 77 5f 68 74 29 2f 73  ocSize(new_ht)/s
0e90: 69 7a 65 6f 66 28 73 74 72 75 63 74 20 5f 68 74  izeof(struct _ht
0ea0: 29 3b 0a 20 20 6d 65 6d 73 65 74 28 6e 65 77 5f  );.  memset(new_
0eb0: 68 74 2c 20 30 2c 20 6e 65 77 5f 73 69 7a 65 2a  ht, 0, new_size*
0ec0: 73 69 7a 65 6f 66 28 73 74 72 75 63 74 20 5f 68  sizeof(struct _h
0ed0: 74 29 29 3b 0a 20 20 66 6f 72 28 65 6c 65 6d 3d  t));.  for(elem=
0ee0: 70 48 2d 3e 66 69 72 73 74 2c 20 70 48 2d 3e 66  pH->first, pH->f
0ef0: 69 72 73 74 3d 30 3b 20 65 6c 65 6d 3b 20 65 6c  irst=0; elem; el
0f00: 65 6d 20 3d 20 6e 65 78 74 5f 65 6c 65 6d 29 7b  em = next_elem){
0f10: 0a 20 20 20 20 75 6e 73 69 67 6e 65 64 20 69 6e  .    unsigned in
0f20: 74 20 68 20 3d 20 73 74 72 48 61 73 68 28 65 6c  t h = strHash(el
0f30: 65 6d 2d 3e 70 4b 65 79 29 20 25 20 6e 65 77 5f  em->pKey) % new_
0f40: 73 69 7a 65 3b 0a 20 20 20 20 6e 65 78 74 5f 65  size;.    next_e
0f50: 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74  lem = elem->next
0f60: 3b 0a 20 20 20 20 69 6e 73 65 72 74 45 6c 65 6d  ;.    insertElem
0f70: 65 6e 74 28 70 48 2c 20 26 6e 65 77 5f 68 74 5b  ent(pH, &new_ht[
0f80: 68 5d 2c 20 65 6c 65 6d 29 3b 0a 20 20 7d 0a 20  h], elem);.  }. 
0f90: 20 72 65 74 75 72 6e 20 31 3b 0a 7d 0a 0a 2f 2a   return 1;.}../*
0fa0: 20 54 68 69 73 20 66 75 6e 63 74 69 6f 6e 20 28   This function (
0fb0: 66 6f 72 20 69 6e 74 65 72 6e 61 6c 20 75 73 65  for internal use
0fc0: 20 6f 6e 6c 79 29 20 6c 6f 63 61 74 65 73 20 61   only) locates a
0fd0: 6e 20 65 6c 65 6d 65 6e 74 20 69 6e 20 61 6e 0a  n element in an.
0fe0: 2a 2a 20 68 61 73 68 20 74 61 62 6c 65 20 74 68  ** hash table th
0ff0: 61 74 20 6d 61 74 63 68 65 73 20 74 68 65 20 67  at matches the g
1000: 69 76 65 6e 20 6b 65 79 2e 20 20 54 68 65 20 68  iven key.  The h
1010: 61 73 68 20 66 6f 72 20 74 68 69 73 20 6b 65 79  ash for this key
1020: 20 69 73 0a 2a 2a 20 61 6c 73 6f 20 63 6f 6d 70   is.** also comp
1030: 75 74 65 64 20 61 6e 64 20 72 65 74 75 72 6e 65  uted and returne
1040: 64 20 69 6e 20 74 68 65 20 2a 70 48 20 70 61 72  d in the *pH par
1050: 61 6d 65 74 65 72 2e 0a 2a 2f 0a 73 74 61 74 69  ameter..*/.stati
1060: 63 20 48 61 73 68 45 6c 65 6d 20 2a 66 69 6e 64  c HashElem *find
1070: 45 6c 65 6d 65 6e 74 57 69 74 68 48 61 73 68 28  ElementWithHash(
1080: 0a 20 20 63 6f 6e 73 74 20 48 61 73 68 20 2a 70  .  const Hash *p
1090: 48 2c 20 20 20 20 20 2f 2a 20 54 68 65 20 70 48  H,     /* The pH
10a0: 20 74 6f 20 62 65 20 73 65 61 72 63 68 65 64 20   to be searched 
10b0: 2a 2f 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20  */.  const char 
10c0: 2a 70 4b 65 79 2c 20 20 20 2f 2a 20 54 68 65 20  *pKey,   /* The 
10d0: 6b 65 79 20 77 65 20 61 72 65 20 73 65 61 72 63  key we are searc
10e0: 68 69 6e 67 20 66 6f 72 20 2a 2f 0a 20 20 75 6e  hing for */.  un
10f0: 73 69 67 6e 65 64 20 69 6e 74 20 2a 70 48 61 73  signed int *pHas
1100: 68 20 2f 2a 20 57 72 69 74 65 20 74 68 65 20 68  h /* Write the h
1110: 61 73 68 20 76 61 6c 75 65 20 68 65 72 65 20 2a  ash value here *
1120: 2f 0a 29 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20  /.){.  HashElem 
1130: 2a 65 6c 65 6d 3b 20 20 20 20 20 20 20 20 20 20  *elem;          
1140: 20 20 20 20 20 20 2f 2a 20 55 73 65 64 20 74 6f        /* Used to
1150: 20 6c 6f 6f 70 20 74 68 72 75 20 74 68 65 20 65   loop thru the e
1160: 6c 65 6d 65 6e 74 20 6c 69 73 74 20 2a 2f 0a 20  lement list */. 
1170: 20 69 6e 74 20 63 6f 75 6e 74 3b 20 20 20 20 20   int count;     
1180: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1190: 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65 6c 65  /* Number of ele
11a0: 6d 65 6e 74 73 20 6c 65 66 74 20 74 6f 20 74 65  ments left to te
11b0: 73 74 20 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64  st */.  unsigned
11c0: 20 69 6e 74 20 68 3b 20 20 20 20 20 20 20 20 20   int h;         
11d0: 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20 63 6f         /* The co
11e0: 6d 70 75 74 65 64 20 68 61 73 68 20 2a 2f 0a 0a  mputed hash */..
11f0: 20 20 69 66 28 20 70 48 2d 3e 68 74 20 29 7b 0a    if( pH->ht ){.
1200: 20 20 20 20 73 74 72 75 63 74 20 5f 68 74 20 2a      struct _ht *
1210: 70 45 6e 74 72 79 3b 0a 20 20 20 20 68 20 3d 20  pEntry;.    h = 
1220: 73 74 72 48 61 73 68 28 70 4b 65 79 29 20 25 20  strHash(pKey) % 
1230: 70 48 2d 3e 68 74 73 69 7a 65 3b 0a 20 20 20 20  pH->htsize;.    
1240: 70 45 6e 74 72 79 20 3d 20 26 70 48 2d 3e 68 74  pEntry = &pH->ht
1250: 5b 68 5d 3b 0a 20 20 20 20 65 6c 65 6d 20 3d 20  [h];.    elem = 
1260: 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3b 0a 20  pEntry->chain;. 
1270: 20 20 20 63 6f 75 6e 74 20 3d 20 70 45 6e 74 72     count = pEntr
1280: 79 2d 3e 63 6f 75 6e 74 3b 0a 20 20 7d 65 6c 73  y->count;.  }els
1290: 65 7b 0a 20 20 20 20 68 20 3d 20 30 3b 0a 20 20  e{.    h = 0;.  
12a0: 20 20 65 6c 65 6d 20 3d 20 70 48 2d 3e 66 69 72    elem = pH->fir
12b0: 73 74 3b 0a 20 20 20 20 63 6f 75 6e 74 20 3d 20  st;.    count = 
12c0: 70 48 2d 3e 63 6f 75 6e 74 3b 0a 20 20 7d 0a 20  pH->count;.  }. 
12d0: 20 2a 70 48 61 73 68 20 3d 20 68 3b 0a 20 20 77   *pHash = h;.  w
12e0: 68 69 6c 65 28 20 63 6f 75 6e 74 2d 2d 20 29 7b  hile( count-- ){
12f0: 0a 20 20 20 20 61 73 73 65 72 74 28 20 65 6c 65  .    assert( ele
1300: 6d 21 3d 30 20 29 3b 0a 20 20 20 20 69 66 28 20  m!=0 );.    if( 
1310: 73 71 6c 69 74 65 33 53 74 72 49 43 6d 70 28 65  sqlite3StrICmp(e
1320: 6c 65 6d 2d 3e 70 4b 65 79 2c 70 4b 65 79 29 3d  lem->pKey,pKey)=
1330: 3d 30 20 29 7b 20 0a 20 20 20 20 20 20 72 65 74  =0 ){ .      ret
1340: 75 72 6e 20 65 6c 65 6d 3b 0a 20 20 20 20 7d 0a  urn elem;.    }.
1350: 20 20 20 20 65 6c 65 6d 20 3d 20 65 6c 65 6d 2d      elem = elem-
1360: 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20 20 72 65 74  >next;.  }.  ret
1370: 75 72 6e 20 30 3b 0a 7d 0a 0a 2f 2a 20 52 65 6d  urn 0;.}../* Rem
1380: 6f 76 65 20 61 20 73 69 6e 67 6c 65 20 65 6e 74  ove a single ent
1390: 72 79 20 66 72 6f 6d 20 74 68 65 20 68 61 73 68  ry from the hash
13a0: 20 74 61 62 6c 65 20 67 69 76 65 6e 20 61 20 70   table given a p
13b0: 6f 69 6e 74 65 72 20 74 6f 20 74 68 61 74 0a 2a  ointer to that.*
13c0: 2a 20 65 6c 65 6d 65 6e 74 20 61 6e 64 20 61 20  * element and a 
13d0: 68 61 73 68 20 6f 6e 20 74 68 65 20 65 6c 65 6d  hash on the elem
13e0: 65 6e 74 27 73 20 6b 65 79 2e 0a 2a 2f 0a 73 74  ent's key..*/.st
13f0: 61 74 69 63 20 76 6f 69 64 20 72 65 6d 6f 76 65  atic void remove
1400: 45 6c 65 6d 65 6e 74 47 69 76 65 6e 48 61 73 68  ElementGivenHash
1410: 28 0a 20 20 48 61 73 68 20 2a 70 48 2c 20 20 20  (.  Hash *pH,   
1420: 20 20 20 20 20 20 2f 2a 20 54 68 65 20 70 48 20        /* The pH 
1430: 63 6f 6e 74 61 69 6e 69 6e 67 20 22 65 6c 65 6d  containing "elem
1440: 22 20 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 2a  " */.  HashElem*
1450: 20 65 6c 65 6d 2c 20 20 20 2f 2a 20 54 68 65 20   elem,   /* The 
1460: 65 6c 65 6d 65 6e 74 20 74 6f 20 62 65 20 72 65  element to be re
1470: 6d 6f 76 65 64 20 66 72 6f 6d 20 74 68 65 20 70  moved from the p
1480: 48 20 2a 2f 0a 20 20 75 6e 73 69 67 6e 65 64 20  H */.  unsigned 
1490: 69 6e 74 20 68 20 20 20 20 2f 2a 20 48 61 73 68  int h    /* Hash
14a0: 20 76 61 6c 75 65 20 66 6f 72 20 74 68 65 20 65   value for the e
14b0: 6c 65 6d 65 6e 74 20 2a 2f 0a 29 7b 0a 20 20 73  lement */.){.  s
14c0: 74 72 75 63 74 20 5f 68 74 20 2a 70 45 6e 74 72  truct _ht *pEntr
14d0: 79 3b 0a 20 20 69 66 28 20 65 6c 65 6d 2d 3e 70  y;.  if( elem->p
14e0: 72 65 76 20 29 7b 0a 20 20 20 20 65 6c 65 6d 2d  rev ){.    elem-
14f0: 3e 70 72 65 76 2d 3e 6e 65 78 74 20 3d 20 65 6c  >prev->next = el
1500: 65 6d 2d 3e 6e 65 78 74 3b 20 0a 20 20 7d 65 6c  em->next; .  }el
1510: 73 65 7b 0a 20 20 20 20 70 48 2d 3e 66 69 72 73  se{.    pH->firs
1520: 74 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74 3b 0a  t = elem->next;.
1530: 20 20 7d 0a 20 20 69 66 28 20 65 6c 65 6d 2d 3e    }.  if( elem->
1540: 6e 65 78 74 20 29 7b 0a 20 20 20 20 65 6c 65 6d  next ){.    elem
1550: 2d 3e 6e 65 78 74 2d 3e 70 72 65 76 20 3d 20 65  ->next->prev = e
1560: 6c 65 6d 2d 3e 70 72 65 76 3b 0a 20 20 7d 0a 20  lem->prev;.  }. 
1570: 20 69 66 28 20 70 48 2d 3e 68 74 20 29 7b 0a 20   if( pH->ht ){. 
1580: 20 20 20 70 45 6e 74 72 79 20 3d 20 26 70 48 2d     pEntry = &pH-
1590: 3e 68 74 5b 68 5d 3b 0a 20 20 20 20 69 66 28 20  >ht[h];.    if( 
15a0: 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 3d 3d 65  pEntry->chain==e
15b0: 6c 65 6d 20 29 7b 0a 20 20 20 20 20 20 70 45 6e  lem ){.      pEn
15c0: 74 72 79 2d 3e 63 68 61 69 6e 20 3d 20 65 6c 65  try->chain = ele
15d0: 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 7d 0a 20  m->next;.    }. 
15e0: 20 20 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74     pEntry->count
15f0: 2d 2d 3b 0a 20 20 20 20 61 73 73 65 72 74 28 20  --;.    assert( 
1600: 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 3e 3d 30  pEntry->count>=0
1610: 20 29 3b 0a 20 20 7d 0a 20 20 73 71 6c 69 74 65   );.  }.  sqlite
1620: 33 5f 66 72 65 65 28 20 65 6c 65 6d 20 29 3b 0a  3_free( elem );.
1630: 20 20 70 48 2d 3e 63 6f 75 6e 74 2d 2d 3b 0a 20    pH->count--;. 
1640: 20 69 66 28 20 70 48 2d 3e 63 6f 75 6e 74 3d 3d   if( pH->count==
1650: 30 20 29 7b 0a 20 20 20 20 61 73 73 65 72 74 28  0 ){.    assert(
1660: 20 70 48 2d 3e 66 69 72 73 74 3d 3d 30 20 29 3b   pH->first==0 );
1670: 0a 20 20 20 20 61 73 73 65 72 74 28 20 70 48 2d  .    assert( pH-
1680: 3e 63 6f 75 6e 74 3d 3d 30 20 29 3b 0a 20 20 20  >count==0 );.   
1690: 20 73 71 6c 69 74 65 33 48 61 73 68 43 6c 65 61   sqlite3HashClea
16a0: 72 28 70 48 29 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a  r(pH);.  }.}../*
16b0: 20 41 74 74 65 6d 70 74 20 74 6f 20 6c 6f 63 61   Attempt to loca
16c0: 74 65 20 61 6e 20 65 6c 65 6d 65 6e 74 20 6f 66  te an element of
16d0: 20 74 68 65 20 68 61 73 68 20 74 61 62 6c 65 20   the hash table 
16e0: 70 48 20 77 69 74 68 20 61 20 6b 65 79 0a 2a 2a  pH with a key.**
16f0: 20 74 68 61 74 20 6d 61 74 63 68 65 73 20 70 4b   that matches pK
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: 29 7b 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65  ){.  HashElem *e
17a0: 6c 65 6d 3b 20 20 20 20 2f 2a 20 54 68 65 20 65  lem;    /* The e
17b0: 6c 65 6d 65 6e 74 20 74 68 61 74 20 6d 61 74 63  lement that matc
17c0: 68 65 73 20 6b 65 79 20 2a 2f 0a 20 20 75 6e 73  hes key */.  uns
17d0: 69 67 6e 65 64 20 69 6e 74 20 68 3b 20 20 20 20  igned int h;    
17e0: 2f 2a 20 41 20 68 61 73 68 20 6f 6e 20 6b 65 79  /* A hash on key
17f0: 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28 20 70   */..  assert( p
1800: 48 21 3d 30 20 29 3b 0a 20 20 61 73 73 65 72 74  H!=0 );.  assert
1810: 28 20 70 4b 65 79 21 3d 30 20 29 3b 0a 20 20 65  ( pKey!=0 );.  e
1820: 6c 65 6d 20 3d 20 66 69 6e 64 45 6c 65 6d 65 6e  lem = findElemen
1830: 74 57 69 74 68 48 61 73 68 28 70 48 2c 20 70 4b  tWithHash(pH, pK
1840: 65 79 2c 20 26 68 29 3b 0a 20 20 72 65 74 75 72  ey, &h);.  retur
1850: 6e 20 65 6c 65 6d 20 3f 20 65 6c 65 6d 2d 3e 64  n elem ? elem->d
1860: 61 74 61 20 3a 20 30 3b 0a 7d 0a 0a 2f 2a 20 49  ata : 0;.}../* I
1870: 6e 73 65 72 74 20 61 6e 20 65 6c 65 6d 65 6e 74  nsert an element
1880: 20 69 6e 74 6f 20 74 68 65 20 68 61 73 68 20 74   into the hash t
1890: 61 62 6c 65 20 70 48 2e 20 20 54 68 65 20 6b 65  able pH.  The ke
18a0: 79 20 69 73 20 70 4b 65 79 0a 2a 2a 20 61 6e 64  y is pKey.** and
18b0: 20 74 68 65 20 64 61 74 61 20 69 73 20 22 64 61   the data is "da
18c0: 74 61 22 2e 0a 2a 2a 0a 2a 2a 20 49 66 20 6e 6f  ta"..**.** If no
18d0: 20 65 6c 65 6d 65 6e 74 20 65 78 69 73 74 73 20   element exists 
18e0: 77 69 74 68 20 61 20 6d 61 74 63 68 69 6e 67 20  with a matching 
18f0: 6b 65 79 2c 20 74 68 65 6e 20 61 20 6e 65 77 0a  key, then a new.
1900: 2a 2a 20 65 6c 65 6d 65 6e 74 20 69 73 20 63 72  ** element is cr
1910: 65 61 74 65 64 20 61 6e 64 20 4e 55 4c 4c 20 69  eated and NULL i
1920: 73 20 72 65 74 75 72 6e 65 64 2e 0a 2a 2a 0a 2a  s returned..**.*
1930: 2a 20 49 66 20 61 6e 6f 74 68 65 72 20 65 6c 65  * If another ele
1940: 6d 65 6e 74 20 61 6c 72 65 61 64 79 20 65 78 69  ment already exi
1950: 73 74 73 20 77 69 74 68 20 74 68 65 20 73 61 6d  sts with the sam
1960: 65 20 6b 65 79 2c 20 74 68 65 6e 20 74 68 65 0a  e key, then the.
1970: 2a 2a 20 6e 65 77 20 64 61 74 61 20 72 65 70 6c  ** new data repl
1980: 61 63 65 73 20 74 68 65 20 6f 6c 64 20 64 61 74  aces the old dat
1990: 61 20 61 6e 64 20 74 68 65 20 6f 6c 64 20 64 61  a and the old da
19a0: 74 61 20 69 73 20 72 65 74 75 72 6e 65 64 2e 0a  ta is returned..
19b0: 2a 2a 20 54 68 65 20 6b 65 79 20 69 73 20 6e 6f  ** The key is no
19c0: 74 20 63 6f 70 69 65 64 20 69 6e 20 74 68 69 73  t copied in this
19d0: 20 69 6e 73 74 61 6e 63 65 2e 20 20 49 66 20 61   instance.  If a
19e0: 20 6d 61 6c 6c 6f 63 20 66 61 69 6c 73 2c 20 74   malloc fails, t
19f0: 68 65 6e 0a 2a 2a 20 74 68 65 20 6e 65 77 20 64  hen.** the new d
1a00: 61 74 61 20 69 73 20 72 65 74 75 72 6e 65 64 20  ata is returned 
1a10: 61 6e 64 20 74 68 65 20 68 61 73 68 20 74 61 62  and the hash tab
1a20: 6c 65 20 69 73 20 75 6e 63 68 61 6e 67 65 64 2e  le is unchanged.
1a30: 0a 2a 2a 0a 2a 2a 20 49 66 20 74 68 65 20 22 64  .**.** If the "d
1a40: 61 74 61 22 20 70 61 72 61 6d 65 74 65 72 20 74  ata" parameter t
1a50: 6f 20 74 68 69 73 20 66 75 6e 63 74 69 6f 6e 20  o this function 
1a60: 69 73 20 4e 55 4c 4c 2c 20 74 68 65 6e 20 74 68  is NULL, then th
1a70: 65 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 63 6f 72  e.** element cor
1a80: 72 65 73 70 6f 6e 64 69 6e 67 20 74 6f 20 22 6b  responding to "k
1a90: 65 79 22 20 69 73 20 72 65 6d 6f 76 65 64 20 66  ey" is removed f
1aa0: 72 6f 6d 20 74 68 65 20 68 61 73 68 20 74 61 62  rom the hash tab
1ab0: 6c 65 2e 0a 2a 2f 0a 76 6f 69 64 20 2a 73 71 6c  le..*/.void *sql
1ac0: 69 74 65 33 48 61 73 68 49 6e 73 65 72 74 28 48  ite3HashInsert(H
1ad0: 61 73 68 20 2a 70 48 2c 20 63 6f 6e 73 74 20 63  ash *pH, const c
1ae0: 68 61 72 20 2a 70 4b 65 79 2c 20 76 6f 69 64 20  har *pKey, void 
1af0: 2a 64 61 74 61 29 7b 0a 20 20 75 6e 73 69 67 6e  *data){.  unsign
1b00: 65 64 20 69 6e 74 20 68 3b 20 20 20 20 20 20 20  ed int h;       
1b10: 2f 2a 20 74 68 65 20 68 61 73 68 20 6f 66 20 74  /* the hash of t
1b20: 68 65 20 6b 65 79 20 6d 6f 64 75 6c 6f 20 68 61  he key modulo ha
1b30: 73 68 20 74 61 62 6c 65 20 73 69 7a 65 20 2a 2f  sh table size */
1b40: 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 65 6c 65  .  HashElem *ele
1b50: 6d 3b 20 20 20 20 20 20 20 2f 2a 20 55 73 65 64  m;       /* Used
1b60: 20 74 6f 20 6c 6f 6f 70 20 74 68 72 75 20 74 68   to loop thru th
1b70: 65 20 65 6c 65 6d 65 6e 74 20 6c 69 73 74 20 2a  e element list *
1b80: 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 6e 65  /.  HashElem *ne
1b90: 77 5f 65 6c 65 6d 3b 20 20 20 2f 2a 20 4e 65 77  w_elem;   /* New
1ba0: 20 65 6c 65 6d 65 6e 74 20 61 64 64 65 64 20 74   element added t
1bb0: 6f 20 74 68 65 20 70 48 20 2a 2f 0a 0a 20 20 61  o the pH */..  a
1bc0: 73 73 65 72 74 28 20 70 48 21 3d 30 20 29 3b 0a  ssert( pH!=0 );.
1bd0: 20 20 61 73 73 65 72 74 28 20 70 4b 65 79 21 3d    assert( pKey!=
1be0: 30 20 29 3b 0a 20 20 65 6c 65 6d 20 3d 20 66 69  0 );.  elem = fi
1bf0: 6e 64 45 6c 65 6d 65 6e 74 57 69 74 68 48 61 73  ndElementWithHas
1c00: 68 28 70 48 2c 70 4b 65 79 2c 26 68 29 3b 0a 20  h(pH,pKey,&h);. 
1c10: 20 69 66 28 20 65 6c 65 6d 20 29 7b 0a 20 20 20   if( elem ){.   
1c20: 20 76 6f 69 64 20 2a 6f 6c 64 5f 64 61 74 61 20   void *old_data 
1c30: 3d 20 65 6c 65 6d 2d 3e 64 61 74 61 3b 0a 20 20  = elem->data;.  
1c40: 20 20 69 66 28 20 64 61 74 61 3d 3d 30 20 29 7b    if( data==0 ){
1c50: 0a 20 20 20 20 20 20 72 65 6d 6f 76 65 45 6c 65  .      removeEle
1c60: 6d 65 6e 74 47 69 76 65 6e 48 61 73 68 28 70 48  mentGivenHash(pH
1c70: 2c 65 6c 65 6d 2c 68 29 3b 0a 20 20 20 20 7d 65  ,elem,h);.    }e
1c80: 6c 73 65 7b 0a 20 20 20 20 20 20 65 6c 65 6d 2d  lse{.      elem-
1c90: 3e 64 61 74 61 20 3d 20 64 61 74 61 3b 0a 20 20  >data = data;.  
1ca0: 20 20 20 20 65 6c 65 6d 2d 3e 70 4b 65 79 20 3d      elem->pKey =
1cb0: 20 70 4b 65 79 3b 0a 20 20 20 20 7d 0a 20 20 20   pKey;.    }.   
1cc0: 20 72 65 74 75 72 6e 20 6f 6c 64 5f 64 61 74 61   return old_data
1cd0: 3b 0a 20 20 7d 0a 20 20 69 66 28 20 64 61 74 61  ;.  }.  if( data
1ce0: 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 30 3b 0a  ==0 ) return 0;.
1cf0: 20 20 6e 65 77 5f 65 6c 65 6d 20 3d 20 28 48 61    new_elem = (Ha
1d00: 73 68 45 6c 65 6d 2a 29 73 71 6c 69 74 65 33 4d  shElem*)sqlite3M
1d10: 61 6c 6c 6f 63 28 20 73 69 7a 65 6f 66 28 48 61  alloc( sizeof(Ha
1d20: 73 68 45 6c 65 6d 29 20 29 3b 0a 20 20 69 66 28  shElem) );.  if(
1d30: 20 6e 65 77 5f 65 6c 65 6d 3d 3d 30 20 29 20 72   new_elem==0 ) r
1d40: 65 74 75 72 6e 20 64 61 74 61 3b 0a 20 20 6e 65  eturn data;.  ne
1d50: 77 5f 65 6c 65 6d 2d 3e 70 4b 65 79 20 3d 20 70  w_elem->pKey = p
1d60: 4b 65 79 3b 0a 20 20 6e 65 77 5f 65 6c 65 6d 2d  Key;.  new_elem-
1d70: 3e 64 61 74 61 20 3d 20 64 61 74 61 3b 0a 20 20  >data = data;.  
1d80: 70 48 2d 3e 63 6f 75 6e 74 2b 2b 3b 0a 20 20 69  pH->count++;.  i
1d90: 66 28 20 70 48 2d 3e 63 6f 75 6e 74 3e 3d 31 30  f( pH->count>=10
1da0: 20 26 26 20 70 48 2d 3e 63 6f 75 6e 74 20 3e 20   && pH->count > 
1db0: 32 2a 70 48 2d 3e 68 74 73 69 7a 65 20 29 7b 0a  2*pH->htsize ){.
1dc0: 20 20 20 20 69 66 28 20 72 65 68 61 73 68 28 70      if( rehash(p
1dd0: 48 2c 20 70 48 2d 3e 63 6f 75 6e 74 2a 32 29 20  H, pH->count*2) 
1de0: 29 7b 0a 20 20 20 20 20 20 61 73 73 65 72 74 28  ){.      assert(
1df0: 20 70 48 2d 3e 68 74 73 69 7a 65 3e 30 20 29 3b   pH->htsize>0 );
1e00: 0a 20 20 20 20 20 20 68 20 3d 20 73 74 72 48 61  .      h = strHa
1e10: 73 68 28 70 4b 65 79 29 20 25 20 70 48 2d 3e 68  sh(pKey) % pH->h
1e20: 74 73 69 7a 65 3b 0a 20 20 20 20 7d 0a 20 20 7d  tsize;.    }.  }
1e30: 0a 20 20 69 6e 73 65 72 74 45 6c 65 6d 65 6e 74  .  insertElement
1e40: 28 70 48 2c 20 70 48 2d 3e 68 74 20 3f 20 26 70  (pH, pH->ht ? &p
1e50: 48 2d 3e 68 74 5b 68 5d 20 3a 20 30 2c 20 6e 65  H->ht[h] : 0, ne
1e60: 77 5f 65 6c 65 6d 29 3b 0a 20 20 72 65 74 75 72  w_elem);.  retur
1e70: 6e 20 30 3b 0a 7d 0a                             n 0;.}.