/ Hex Artifact Content
Login

Artifact 3c8f6387a4a7f5305588b203fa7c887d753e1f1c:


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 20 75 73 65 64  hash-tables used
01b0: 20 69 6e 20 53 51 4c 69 74 65 2e 0a 2a 2a 20 57   in SQLite..** W
01c0: 65 27 76 65 20 6d 6f 64 69 66 69 65 64 20 69 74  e've modified it
01d0: 20 73 6c 69 67 68 74 6c 79 20 74 6f 20 73 65 72   slightly to ser
01e0: 76 65 20 61 73 20 61 20 73 74 61 6e 64 61 6c 6f  ve as a standalo
01f0: 6e 65 20 68 61 73 68 20 74 61 62 6c 65 0a 2a 2a  ne hash table.**
0200: 20 69 6d 70 6c 65 6d 65 6e 74 61 74 69 6f 6e 20   implementation 
0210: 66 6f 72 20 74 68 65 20 66 75 6c 6c 2d 74 65 78  for the full-tex
0220: 74 20 69 6e 64 65 78 69 6e 67 20 6d 6f 64 75 6c  t indexing modul
0230: 65 2e 0a 2a 2f 0a 0a 2f 2a 0a 2a 2a 20 54 68 65  e..*/../*.** The
0240: 20 63 6f 64 65 20 69 6e 20 74 68 69 73 20 66 69   code in this fi
0250: 6c 65 20 69 73 20 6f 6e 6c 79 20 63 6f 6d 70 69  le is only compi
0260: 6c 65 64 20 69 66 3a 0a 2a 2a 0a 2a 2a 20 20 20  led if:.**.**   
0270: 20 20 2a 20 54 68 65 20 46 54 53 33 20 6d 6f 64    * The FTS3 mod
0280: 75 6c 65 20 69 73 20 62 65 69 6e 67 20 62 75 69  ule is being bui
0290: 6c 74 20 61 73 20 61 6e 20 65 78 74 65 6e 73 69  lt as an extensi
02a0: 6f 6e 0a 2a 2a 20 20 20 20 20 20 20 28 69 6e 20  on.**       (in 
02b0: 77 68 69 63 68 20 63 61 73 65 20 53 51 4c 49 54  which case SQLIT
02c0: 45 5f 43 4f 52 45 20 69 73 20 6e 6f 74 20 64 65  E_CORE is not de
02d0: 66 69 6e 65 64 29 2c 20 6f 72 0a 2a 2a 0a 2a 2a  fined), or.**.**
02e0: 20 20 20 20 20 2a 20 54 68 65 20 46 54 53 33 20       * The FTS3 
02f0: 6d 6f 64 75 6c 65 20 69 73 20 62 65 69 6e 67 20  module is being 
0300: 62 75 69 6c 74 20 69 6e 74 6f 20 74 68 65 20 63  built into the c
0310: 6f 72 65 20 6f 66 0a 2a 2a 20 20 20 20 20 20 20  ore of.**       
0320: 53 51 4c 69 74 65 20 28 69 6e 20 77 68 69 63 68  SQLite (in which
0330: 20 63 61 73 65 20 53 51 4c 49 54 45 5f 45 4e 41   case SQLITE_ENA
0340: 42 4c 45 5f 46 54 53 33 20 69 73 20 64 65 66 69  BLE_FTS3 is defi
0350: 6e 65 64 29 2e 0a 2a 2f 0a 23 69 66 20 21 64 65  ned)..*/.#if !de
0360: 66 69 6e 65 64 28 53 51 4c 49 54 45 5f 43 4f 52  fined(SQLITE_COR
0370: 45 29 20 7c 7c 20 64 65 66 69 6e 65 64 28 53 51  E) || defined(SQ
0380: 4c 49 54 45 5f 45 4e 41 42 4c 45 5f 46 54 53 33  LITE_ENABLE_FTS3
0390: 29 0a 0a 23 69 6e 63 6c 75 64 65 20 3c 61 73 73  )..#include <ass
03a0: 65 72 74 2e 68 3e 0a 23 69 6e 63 6c 75 64 65 20  ert.h>.#include 
03b0: 3c 73 74 64 6c 69 62 2e 68 3e 0a 23 69 6e 63 6c  <stdlib.h>.#incl
03c0: 75 64 65 20 3c 73 74 72 69 6e 67 2e 68 3e 0a 0a  ude <string.h>..
03d0: 23 69 6e 63 6c 75 64 65 20 22 73 71 6c 69 74 65  #include "sqlite
03e0: 33 2e 68 22 0a 23 69 6e 63 6c 75 64 65 20 22 66  3.h".#include "f
03f0: 74 73 33 5f 68 61 73 68 2e 68 22 0a 0a 2f 2a 0a  ts3_hash.h"../*.
0400: 2a 2a 20 4d 61 6c 6c 6f 63 20 61 6e 64 20 46 72  ** Malloc and Fr
0410: 65 65 20 66 75 6e 63 74 69 6f 6e 73 0a 2a 2f 0a  ee functions.*/.
0420: 73 74 61 74 69 63 20 76 6f 69 64 20 2a 66 74 73  static void *fts
0430: 33 48 61 73 68 4d 61 6c 6c 6f 63 28 69 6e 74 20  3HashMalloc(int 
0440: 6e 29 7b 0a 20 20 76 6f 69 64 20 2a 70 20 3d 20  n){.  void *p = 
0450: 73 71 6c 69 74 65 33 5f 6d 61 6c 6c 6f 63 28 6e  sqlite3_malloc(n
0460: 29 3b 0a 20 20 69 66 28 20 70 20 29 7b 0a 20 20  );.  if( p ){.  
0470: 20 20 6d 65 6d 73 65 74 28 70 2c 20 30 2c 20 6e    memset(p, 0, n
0480: 29 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20  );.  }.  return 
0490: 70 3b 0a 7d 0a 73 74 61 74 69 63 20 76 6f 69 64  p;.}.static void
04a0: 20 66 74 73 33 48 61 73 68 46 72 65 65 28 76 6f   fts3HashFree(vo
04b0: 69 64 20 2a 70 29 7b 0a 20 20 73 71 6c 69 74 65  id *p){.  sqlite
04c0: 33 5f 66 72 65 65 28 70 29 3b 0a 7d 0a 0a 2f 2a  3_free(p);.}../*
04d0: 20 54 75 72 6e 20 62 75 6c 6b 20 6d 65 6d 6f 72   Turn bulk memor
04e0: 79 20 69 6e 74 6f 20 61 20 68 61 73 68 20 74 61  y into a hash ta
04f0: 62 6c 65 20 6f 62 6a 65 63 74 20 62 79 20 69 6e  ble object by in
0500: 69 74 69 61 6c 69 7a 69 6e 67 20 74 68 65 0a 2a  itializing the.*
0510: 2a 20 66 69 65 6c 64 73 20 6f 66 20 74 68 65 20  * fields of the 
0520: 48 61 73 68 20 73 74 72 75 63 74 75 72 65 2e 0a  Hash structure..
0530: 2a 2a 0a 2a 2a 20 22 70 4e 65 77 22 20 69 73 20  **.** "pNew" is 
0540: 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68 65  a pointer to the
0550: 20 68 61 73 68 20 74 61 62 6c 65 20 74 68 61 74   hash table that
0560: 20 69 73 20 74 6f 20 62 65 20 69 6e 69 74 69 61   is to be initia
0570: 6c 69 7a 65 64 2e 0a 2a 2a 20 6b 65 79 43 6c 61  lized..** keyCla
0580: 73 73 20 69 73 20 6f 6e 65 20 6f 66 20 74 68 65  ss is one of the
0590: 20 63 6f 6e 73 74 61 6e 74 73 20 0a 2a 2a 20 46   constants .** F
05a0: 54 53 33 5f 48 41 53 48 5f 42 49 4e 41 52 59 20  TS3_HASH_BINARY 
05b0: 6f 72 20 46 54 53 33 5f 48 41 53 48 5f 53 54 52  or FTS3_HASH_STR
05c0: 49 4e 47 2e 20 20 54 68 65 20 76 61 6c 75 65 20  ING.  The value 
05d0: 6f 66 20 6b 65 79 43 6c 61 73 73 20 0a 2a 2a 20  of keyClass .** 
05e0: 64 65 74 65 72 6d 69 6e 65 73 20 77 68 61 74 20  determines what 
05f0: 6b 69 6e 64 20 6f 66 20 6b 65 79 20 74 68 65 20  kind of key the 
0600: 68 61 73 68 20 74 61 62 6c 65 20 77 69 6c 6c 20  hash table will 
0610: 75 73 65 2e 20 20 22 63 6f 70 79 4b 65 79 22 20  use.  "copyKey" 
0620: 69 73 0a 2a 2a 20 74 72 75 65 20 69 66 20 74 68  is.** true if th
0630: 65 20 68 61 73 68 20 74 61 62 6c 65 20 73 68 6f  e hash table sho
0640: 75 6c 64 20 6d 61 6b 65 20 69 74 73 20 6f 77 6e  uld make its own
0650: 20 70 72 69 76 61 74 65 20 63 6f 70 79 20 6f 66   private copy of
0660: 20 6b 65 79 73 20 61 6e 64 0a 2a 2a 20 66 61 6c   keys and.** fal
0670: 73 65 20 69 66 20 69 74 20 73 68 6f 75 6c 64 20  se if it should 
0680: 6a 75 73 74 20 75 73 65 20 74 68 65 20 73 75 70  just use the sup
0690: 70 6c 69 65 64 20 70 6f 69 6e 74 65 72 2e 0a 2a  plied pointer..*
06a0: 2f 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 46 74  /.void sqlite3Ft
06b0: 73 33 48 61 73 68 49 6e 69 74 28 46 74 73 33 48  s3HashInit(Fts3H
06c0: 61 73 68 20 2a 70 4e 65 77 2c 20 63 68 61 72 20  ash *pNew, char 
06d0: 6b 65 79 43 6c 61 73 73 2c 20 63 68 61 72 20 63  keyClass, char c
06e0: 6f 70 79 4b 65 79 29 7b 0a 20 20 61 73 73 65 72  opyKey){.  asser
06f0: 74 28 20 70 4e 65 77 21 3d 30 20 29 3b 0a 20 20  t( pNew!=0 );.  
0700: 61 73 73 65 72 74 28 20 6b 65 79 43 6c 61 73 73  assert( keyClass
0710: 3e 3d 46 54 53 33 5f 48 41 53 48 5f 53 54 52 49  >=FTS3_HASH_STRI
0720: 4e 47 20 26 26 20 6b 65 79 43 6c 61 73 73 3c 3d  NG && keyClass<=
0730: 46 54 53 33 5f 48 41 53 48 5f 42 49 4e 41 52 59  FTS3_HASH_BINARY
0740: 20 29 3b 0a 20 20 70 4e 65 77 2d 3e 6b 65 79 43   );.  pNew->keyC
0750: 6c 61 73 73 20 3d 20 6b 65 79 43 6c 61 73 73 3b  lass = keyClass;
0760: 0a 20 20 70 4e 65 77 2d 3e 63 6f 70 79 4b 65 79  .  pNew->copyKey
0770: 20 3d 20 63 6f 70 79 4b 65 79 3b 0a 20 20 70 4e   = copyKey;.  pN
0780: 65 77 2d 3e 66 69 72 73 74 20 3d 20 30 3b 0a 20  ew->first = 0;. 
0790: 20 70 4e 65 77 2d 3e 63 6f 75 6e 74 20 3d 20 30   pNew->count = 0
07a0: 3b 0a 20 20 70 4e 65 77 2d 3e 68 74 73 69 7a 65  ;.  pNew->htsize
07b0: 20 3d 20 30 3b 0a 20 20 70 4e 65 77 2d 3e 68 74   = 0;.  pNew->ht
07c0: 20 3d 20 30 3b 0a 7d 0a 0a 2f 2a 20 52 65 6d 6f   = 0;.}../* Remo
07d0: 76 65 20 61 6c 6c 20 65 6e 74 72 69 65 73 20 66  ve all entries f
07e0: 72 6f 6d 20 61 20 68 61 73 68 20 74 61 62 6c 65  rom a hash table
07f0: 2e 20 20 52 65 63 6c 61 69 6d 20 61 6c 6c 20 6d  .  Reclaim all m
0800: 65 6d 6f 72 79 2e 0a 2a 2a 20 43 61 6c 6c 20 74  emory..** Call t
0810: 68 69 73 20 72 6f 75 74 69 6e 65 20 74 6f 20 64  his routine to d
0820: 65 6c 65 74 65 20 61 20 68 61 73 68 20 74 61 62  elete a hash tab
0830: 6c 65 20 6f 72 20 74 6f 20 72 65 73 65 74 20 61  le or to reset a
0840: 20 68 61 73 68 20 74 61 62 6c 65 0a 2a 2a 20 74   hash table.** t
0850: 6f 20 74 68 65 20 65 6d 70 74 79 20 73 74 61 74  o the empty stat
0860: 65 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74  e..*/.void sqlit
0870: 65 33 46 74 73 33 48 61 73 68 43 6c 65 61 72 28  e3Fts3HashClear(
0880: 46 74 73 33 48 61 73 68 20 2a 70 48 29 7b 0a 20  Fts3Hash *pH){. 
0890: 20 46 74 73 33 48 61 73 68 45 6c 65 6d 20 2a 65   Fts3HashElem *e
08a0: 6c 65 6d 3b 20 20 20 20 20 20 20 20 20 2f 2a 20  lem;         /* 
08b0: 46 6f 72 20 6c 6f 6f 70 69 6e 67 20 6f 76 65 72  For looping over
08c0: 20 61 6c 6c 20 65 6c 65 6d 65 6e 74 73 20 6f 66   all elements of
08d0: 20 74 68 65 20 74 61 62 6c 65 20 2a 2f 0a 0a 20   the table */.. 
08e0: 20 61 73 73 65 72 74 28 20 70 48 21 3d 30 20 29   assert( pH!=0 )
08f0: 3b 0a 20 20 65 6c 65 6d 20 3d 20 70 48 2d 3e 66  ;.  elem = pH->f
0900: 69 72 73 74 3b 0a 20 20 70 48 2d 3e 66 69 72 73  irst;.  pH->firs
0910: 74 20 3d 20 30 3b 0a 20 20 66 74 73 33 48 61 73  t = 0;.  fts3Has
0920: 68 46 72 65 65 28 70 48 2d 3e 68 74 29 3b 0a 20  hFree(pH->ht);. 
0930: 20 70 48 2d 3e 68 74 20 3d 20 30 3b 0a 20 20 70   pH->ht = 0;.  p
0940: 48 2d 3e 68 74 73 69 7a 65 20 3d 20 30 3b 0a 20  H->htsize = 0;. 
0950: 20 77 68 69 6c 65 28 20 65 6c 65 6d 20 29 7b 0a   while( elem ){.
0960: 20 20 20 20 46 74 73 33 48 61 73 68 45 6c 65 6d      Fts3HashElem
0970: 20 2a 6e 65 78 74 5f 65 6c 65 6d 20 3d 20 65 6c   *next_elem = el
0980: 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 69 66  em->next;.    if
0990: 28 20 70 48 2d 3e 63 6f 70 79 4b 65 79 20 26 26  ( pH->copyKey &&
09a0: 20 65 6c 65 6d 2d 3e 70 4b 65 79 20 29 7b 0a 20   elem->pKey ){. 
09b0: 20 20 20 20 20 66 74 73 33 48 61 73 68 46 72 65       fts3HashFre
09c0: 65 28 65 6c 65 6d 2d 3e 70 4b 65 79 29 3b 0a 20  e(elem->pKey);. 
09d0: 20 20 20 7d 0a 20 20 20 20 66 74 73 33 48 61 73     }.    fts3Has
09e0: 68 46 72 65 65 28 65 6c 65 6d 29 3b 0a 20 20 20  hFree(elem);.   
09f0: 20 65 6c 65 6d 20 3d 20 6e 65 78 74 5f 65 6c 65   elem = next_ele
0a00: 6d 3b 0a 20 20 7d 0a 20 20 70 48 2d 3e 63 6f 75  m;.  }.  pH->cou
0a10: 6e 74 20 3d 20 30 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a  nt = 0;.}../*.**
0a20: 20 48 61 73 68 20 61 6e 64 20 63 6f 6d 70 61 72   Hash and compar
0a30: 69 73 6f 6e 20 66 75 6e 63 74 69 6f 6e 73 20 77  ison functions w
0a40: 68 65 6e 20 74 68 65 20 6d 6f 64 65 20 69 73 20  hen the mode is 
0a50: 46 54 53 33 5f 48 41 53 48 5f 53 54 52 49 4e 47  FTS3_HASH_STRING
0a60: 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 66  .*/.static int f
0a70: 74 73 33 53 74 72 48 61 73 68 28 63 6f 6e 73 74  ts3StrHash(const
0a80: 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74   void *pKey, int
0a90: 20 6e 4b 65 79 29 7b 0a 20 20 63 6f 6e 73 74 20   nKey){.  const 
0aa0: 63 68 61 72 20 2a 7a 20 3d 20 28 63 6f 6e 73 74  char *z = (const
0ab0: 20 63 68 61 72 20 2a 29 70 4b 65 79 3b 0a 20 20   char *)pKey;.  
0ac0: 69 6e 74 20 68 20 3d 20 30 3b 0a 20 20 69 66 28  int h = 0;.  if(
0ad0: 20 6e 4b 65 79 3c 3d 30 20 29 20 6e 4b 65 79 20   nKey<=0 ) nKey 
0ae0: 3d 20 28 69 6e 74 29 20 73 74 72 6c 65 6e 28 7a  = (int) strlen(z
0af0: 29 3b 0a 20 20 77 68 69 6c 65 28 20 6e 4b 65 79  );.  while( nKey
0b00: 20 3e 20 30 20 20 29 7b 0a 20 20 20 20 68 20 3d   > 0  ){.    h =
0b10: 20 28 68 3c 3c 33 29 20 5e 20 68 20 5e 20 2a 7a   (h<<3) ^ h ^ *z
0b20: 2b 2b 3b 0a 20 20 20 20 6e 4b 65 79 2d 2d 3b 0a  ++;.    nKey--;.
0b30: 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 68 20 26    }.  return h &
0b40: 20 30 78 37 66 66 66 66 66 66 66 3b 0a 7d 0a 73   0x7fffffff;.}.s
0b50: 74 61 74 69 63 20 69 6e 74 20 66 74 73 33 53 74  tatic int fts3St
0b60: 72 43 6f 6d 70 61 72 65 28 63 6f 6e 73 74 20 76  rCompare(const v
0b70: 6f 69 64 20 2a 70 4b 65 79 31 2c 20 69 6e 74 20  oid *pKey1, int 
0b80: 6e 31 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a  n1, const void *
0b90: 70 4b 65 79 32 2c 20 69 6e 74 20 6e 32 29 7b 0a  pKey2, int n2){.
0ba0: 20 20 69 66 28 20 6e 31 21 3d 6e 32 20 29 20 72    if( n1!=n2 ) r
0bb0: 65 74 75 72 6e 20 31 3b 0a 20 20 72 65 74 75 72  eturn 1;.  retur
0bc0: 6e 20 73 74 72 6e 63 6d 70 28 28 63 6f 6e 73 74  n strncmp((const
0bd0: 20 63 68 61 72 2a 29 70 4b 65 79 31 2c 28 63 6f   char*)pKey1,(co
0be0: 6e 73 74 20 63 68 61 72 2a 29 70 4b 65 79 32 2c  nst char*)pKey2,
0bf0: 6e 31 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 48 61  n1);.}../*.** Ha
0c00: 73 68 20 61 6e 64 20 63 6f 6d 70 61 72 69 73 6f  sh and compariso
0c10: 6e 20 66 75 6e 63 74 69 6f 6e 73 20 77 68 65 6e  n functions when
0c20: 20 74 68 65 20 6d 6f 64 65 20 69 73 20 46 54 53   the mode is FTS
0c30: 33 5f 48 41 53 48 5f 42 49 4e 41 52 59 0a 2a 2f  3_HASH_BINARY.*/
0c40: 0a 73 74 61 74 69 63 20 69 6e 74 20 66 74 73 33  .static int fts3
0c50: 42 69 6e 48 61 73 68 28 63 6f 6e 73 74 20 76 6f  BinHash(const vo
0c60: 69 64 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b  id *pKey, int nK
0c70: 65 79 29 7b 0a 20 20 69 6e 74 20 68 20 3d 20 30  ey){.  int h = 0
0c80: 3b 0a 20 20 63 6f 6e 73 74 20 63 68 61 72 20 2a  ;.  const char *
0c90: 7a 20 3d 20 28 63 6f 6e 73 74 20 63 68 61 72 20  z = (const char 
0ca0: 2a 29 70 4b 65 79 3b 0a 20 20 77 68 69 6c 65 28  *)pKey;.  while(
0cb0: 20 6e 4b 65 79 2d 2d 20 3e 20 30 20 29 7b 0a 20   nKey-- > 0 ){. 
0cc0: 20 20 20 68 20 3d 20 28 68 3c 3c 33 29 20 5e 20     h = (h<<3) ^ 
0cd0: 68 20 5e 20 2a 28 7a 2b 2b 29 3b 0a 20 20 7d 0a  h ^ *(z++);.  }.
0ce0: 20 20 72 65 74 75 72 6e 20 68 20 26 20 30 78 37    return h & 0x7
0cf0: 66 66 66 66 66 66 66 3b 0a 7d 0a 73 74 61 74 69  fffffff;.}.stati
0d00: 63 20 69 6e 74 20 66 74 73 33 42 69 6e 43 6f 6d  c int fts3BinCom
0d10: 70 61 72 65 28 63 6f 6e 73 74 20 76 6f 69 64 20  pare(const void 
0d20: 2a 70 4b 65 79 31 2c 20 69 6e 74 20 6e 31 2c 20  *pKey1, int n1, 
0d30: 63 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79  const void *pKey
0d40: 32 2c 20 69 6e 74 20 6e 32 29 7b 0a 20 20 69 66  2, int n2){.  if
0d50: 28 20 6e 31 21 3d 6e 32 20 29 20 72 65 74 75 72  ( n1!=n2 ) retur
0d60: 6e 20 31 3b 0a 20 20 72 65 74 75 72 6e 20 6d 65  n 1;.  return me
0d70: 6d 63 6d 70 28 70 4b 65 79 31 2c 70 4b 65 79 32  mcmp(pKey1,pKey2
0d80: 2c 6e 31 29 3b 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52  ,n1);.}../*.** R
0d90: 65 74 75 72 6e 20 61 20 70 6f 69 6e 74 65 72 20  eturn a pointer 
0da0: 74 6f 20 74 68 65 20 61 70 70 72 6f 70 72 69 61  to the appropria
0db0: 74 65 20 68 61 73 68 20 66 75 6e 63 74 69 6f 6e  te hash function
0dc0: 20 67 69 76 65 6e 20 74 68 65 20 6b 65 79 20 63   given the key c
0dd0: 6c 61 73 73 2e 0a 2a 2a 0a 2a 2a 20 54 68 65 20  lass..**.** The 
0de0: 43 20 73 79 6e 74 61 78 20 69 6e 20 74 68 69 73  C syntax in this
0df0: 20 66 75 6e 63 74 69 6f 6e 20 64 65 66 69 6e 69   function defini
0e00: 74 69 6f 6e 20 6d 61 79 20 62 65 20 75 6e 66 61  tion may be unfa
0e10: 6d 69 6c 61 72 20 74 6f 20 73 6f 6d 65 20 0a 2a  milar to some .*
0e20: 2a 20 70 72 6f 67 72 61 6d 6d 65 72 73 2c 20 73  * programmers, s
0e30: 6f 20 77 65 20 70 72 6f 76 69 64 65 20 74 68 65  o we provide the
0e40: 20 66 6f 6c 6c 6f 77 69 6e 67 20 61 64 64 69 74   following addit
0e50: 69 6f 6e 61 6c 20 65 78 70 6c 61 6e 61 74 69 6f  ional explanatio
0e60: 6e 3a 0a 2a 2a 0a 2a 2a 20 54 68 65 20 6e 61 6d  n:.**.** The nam
0e70: 65 20 6f 66 20 74 68 65 20 66 75 6e 63 74 69 6f  e of the functio
0e80: 6e 20 69 73 20 22 66 74 73 48 61 73 68 46 75 6e  n is "ftsHashFun
0e90: 63 74 69 6f 6e 22 2e 20 20 54 68 65 20 66 75 6e  ction".  The fun
0ea0: 63 74 69 6f 6e 20 74 61 6b 65 73 20 61 0a 2a 2a  ction takes a.**
0eb0: 20 73 69 6e 67 6c 65 20 70 61 72 61 6d 65 74 65   single paramete
0ec0: 72 20 22 6b 65 79 43 6c 61 73 73 22 2e 20 20 54  r "keyClass".  T
0ed0: 68 65 20 72 65 74 75 72 6e 20 76 61 6c 75 65 20  he return value 
0ee0: 6f 66 20 66 74 73 48 61 73 68 46 75 6e 63 74 69  of ftsHashFuncti
0ef0: 6f 6e 28 29 0a 2a 2a 20 69 73 20 61 20 70 6f 69  on().** is a poi
0f00: 6e 74 65 72 20 74 6f 20 61 6e 6f 74 68 65 72 20  nter to another 
0f10: 66 75 6e 63 74 69 6f 6e 2e 20 20 53 70 65 63 69  function.  Speci
0f20: 66 69 63 61 6c 6c 79 2c 20 74 68 65 20 72 65 74  fically, the ret
0f30: 75 72 6e 20 76 61 6c 75 65 0a 2a 2a 20 6f 66 20  urn value.** of 
0f40: 66 74 73 48 61 73 68 46 75 6e 63 74 69 6f 6e 28  ftsHashFunction(
0f50: 29 20 69 73 20 61 20 70 6f 69 6e 74 65 72 20 74  ) is a pointer t
0f60: 6f 20 61 20 66 75 6e 63 74 69 6f 6e 20 74 68 61  o a function tha
0f70: 74 20 74 61 6b 65 73 20 74 77 6f 20 70 61 72 61  t takes two para
0f80: 6d 65 74 65 72 73 0a 2a 2a 20 77 69 74 68 20 74  meters.** with t
0f90: 79 70 65 73 20 22 63 6f 6e 73 74 20 76 6f 69 64  ypes "const void
0fa0: 2a 22 20 61 6e 64 20 22 69 6e 74 22 20 61 6e 64  *" and "int" and
0fb0: 20 72 65 74 75 72 6e 73 20 61 6e 20 22 69 6e 74   returns an "int
0fc0: 22 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74  "..*/.static int
0fd0: 20 28 2a 66 74 73 48 61 73 68 46 75 6e 63 74 69   (*ftsHashFuncti
0fe0: 6f 6e 28 69 6e 74 20 6b 65 79 43 6c 61 73 73 29  on(int keyClass)
0ff0: 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c 69 6e  )(const void*,in
1000: 74 29 7b 0a 20 20 69 66 28 20 6b 65 79 43 6c 61  t){.  if( keyCla
1010: 73 73 3d 3d 46 54 53 33 5f 48 41 53 48 5f 53 54  ss==FTS3_HASH_ST
1020: 52 49 4e 47 20 29 7b 0a 20 20 20 20 72 65 74 75  RING ){.    retu
1030: 72 6e 20 26 66 74 73 33 53 74 72 48 61 73 68 3b  rn &fts3StrHash;
1040: 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 61 73  .  }else{.    as
1050: 73 65 72 74 28 20 6b 65 79 43 6c 61 73 73 3d 3d  sert( keyClass==
1060: 46 54 53 33 5f 48 41 53 48 5f 42 49 4e 41 52 59  FTS3_HASH_BINARY
1070: 20 29 3b 0a 20 20 20 20 72 65 74 75 72 6e 20 26   );.    return &
1080: 66 74 73 33 42 69 6e 48 61 73 68 3b 0a 20 20 7d  fts3BinHash;.  }
1090: 0a 7d 0a 0a 2f 2a 0a 2a 2a 20 52 65 74 75 72 6e  .}../*.** Return
10a0: 20 61 20 70 6f 69 6e 74 65 72 20 74 6f 20 74 68   a pointer to th
10b0: 65 20 61 70 70 72 6f 70 72 69 61 74 65 20 68 61  e appropriate ha
10c0: 73 68 20 66 75 6e 63 74 69 6f 6e 20 67 69 76 65  sh function give
10d0: 6e 20 74 68 65 20 6b 65 79 20 63 6c 61 73 73 2e  n the key class.
10e0: 0a 2a 2a 0a 2a 2a 20 46 6f 72 20 68 65 6c 70 20  .**.** For help 
10f0: 69 6e 20 69 6e 74 65 72 70 72 65 74 65 64 20 74  in interpreted t
1100: 68 65 20 6f 62 73 63 75 72 65 20 43 20 63 6f 64  he obscure C cod
1110: 65 20 69 6e 20 74 68 65 20 66 75 6e 63 74 69 6f  e in the functio
1120: 6e 20 64 65 66 69 6e 69 74 69 6f 6e 2c 0a 2a 2a  n definition,.**
1130: 20 73 65 65 20 74 68 65 20 68 65 61 64 65 72 20   see the header 
1140: 63 6f 6d 6d 65 6e 74 20 6f 6e 20 74 68 65 20 70  comment on the p
1150: 72 65 76 69 6f 75 73 20 66 75 6e 63 74 69 6f 6e  revious function
1160: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20  ..*/.static int 
1170: 28 2a 66 74 73 43 6f 6d 70 61 72 65 46 75 6e 63  (*ftsCompareFunc
1180: 74 69 6f 6e 28 69 6e 74 20 6b 65 79 43 6c 61 73  tion(int keyClas
1190: 73 29 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a 2c  s))(const void*,
11a0: 69 6e 74 2c 63 6f 6e 73 74 20 76 6f 69 64 2a 2c  int,const void*,
11b0: 69 6e 74 29 7b 0a 20 20 69 66 28 20 6b 65 79 43  int){.  if( keyC
11c0: 6c 61 73 73 3d 3d 46 54 53 33 5f 48 41 53 48 5f  lass==FTS3_HASH_
11d0: 53 54 52 49 4e 47 20 29 7b 0a 20 20 20 20 72 65  STRING ){.    re
11e0: 74 75 72 6e 20 26 66 74 73 33 53 74 72 43 6f 6d  turn &fts3StrCom
11f0: 70 61 72 65 3b 0a 20 20 7d 65 6c 73 65 7b 0a 20  pare;.  }else{. 
1200: 20 20 20 61 73 73 65 72 74 28 20 6b 65 79 43 6c     assert( keyCl
1210: 61 73 73 3d 3d 46 54 53 33 5f 48 41 53 48 5f 42  ass==FTS3_HASH_B
1220: 49 4e 41 52 59 20 29 3b 0a 20 20 20 20 72 65 74  INARY );.    ret
1230: 75 72 6e 20 26 66 74 73 33 42 69 6e 43 6f 6d 70  urn &fts3BinComp
1240: 61 72 65 3b 0a 20 20 7d 0a 7d 0a 0a 2f 2a 20 4c  are;.  }.}../* L
1250: 69 6e 6b 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69  ink an element i
1260: 6e 74 6f 20 74 68 65 20 68 61 73 68 20 74 61 62  nto the hash tab
1270: 6c 65 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69  le.*/.static voi
1280: 64 20 66 74 73 33 48 61 73 68 49 6e 73 65 72 74  d fts3HashInsert
1290: 45 6c 65 6d 65 6e 74 28 0a 20 20 46 74 73 33 48  Element(.  Fts3H
12a0: 61 73 68 20 2a 70 48 2c 20 20 20 20 20 20 20 20  ash *pH,        
12b0: 20 20 20 20 2f 2a 20 54 68 65 20 63 6f 6d 70 6c      /* The compl
12c0: 65 74 65 20 68 61 73 68 20 74 61 62 6c 65 20 2a  ete hash table *
12d0: 2f 0a 20 20 73 74 72 75 63 74 20 5f 66 74 73 33  /.  struct _fts3
12e0: 68 74 20 2a 70 45 6e 74 72 79 2c 20 20 2f 2a 20  ht *pEntry,  /* 
12f0: 54 68 65 20 65 6e 74 72 79 20 69 6e 74 6f 20 77  The entry into w
1300: 68 69 63 68 20 70 4e 65 77 20 69 73 20 69 6e 73  hich pNew is ins
1310: 65 72 74 65 64 20 2a 2f 0a 20 20 46 74 73 33 48  erted */.  Fts3H
1320: 61 73 68 45 6c 65 6d 20 2a 70 4e 65 77 20 20 20  ashElem *pNew   
1330: 20 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d 65      /* The eleme
1340: 6e 74 20 74 6f 20 62 65 20 69 6e 73 65 72 74 65  nt to be inserte
1350: 64 20 2a 2f 0a 29 7b 0a 20 20 46 74 73 33 48 61  d */.){.  Fts3Ha
1360: 73 68 45 6c 65 6d 20 2a 70 48 65 61 64 3b 20 20  shElem *pHead;  
1370: 20 20 20 2f 2a 20 46 69 72 73 74 20 65 6c 65 6d     /* First elem
1380: 65 6e 74 20 61 6c 72 65 61 64 79 20 69 6e 20 70  ent already in p
1390: 45 6e 74 72 79 20 2a 2f 0a 20 20 70 48 65 61 64  Entry */.  pHead
13a0: 20 3d 20 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e   = pEntry->chain
13b0: 3b 0a 20 20 69 66 28 20 70 48 65 61 64 20 29 7b  ;.  if( pHead ){
13c0: 0a 20 20 20 20 70 4e 65 77 2d 3e 6e 65 78 74 20  .    pNew->next 
13d0: 3d 20 70 48 65 61 64 3b 0a 20 20 20 20 70 4e 65  = pHead;.    pNe
13e0: 77 2d 3e 70 72 65 76 20 3d 20 70 48 65 61 64 2d  w->prev = pHead-
13f0: 3e 70 72 65 76 3b 0a 20 20 20 20 69 66 28 20 70  >prev;.    if( p
1400: 48 65 61 64 2d 3e 70 72 65 76 20 29 7b 20 70 48  Head->prev ){ pH
1410: 65 61 64 2d 3e 70 72 65 76 2d 3e 6e 65 78 74 20  ead->prev->next 
1420: 3d 20 70 4e 65 77 3b 20 7d 0a 20 20 20 20 65 6c  = pNew; }.    el
1430: 73 65 20 20 20 20 20 20 20 20 20 20 20 20 20 7b  se             {
1440: 20 70 48 2d 3e 66 69 72 73 74 20 3d 20 70 4e 65   pH->first = pNe
1450: 77 3b 20 7d 0a 20 20 20 20 70 48 65 61 64 2d 3e  w; }.    pHead->
1460: 70 72 65 76 20 3d 20 70 4e 65 77 3b 0a 20 20 7d  prev = pNew;.  }
1470: 65 6c 73 65 7b 0a 20 20 20 20 70 4e 65 77 2d 3e  else{.    pNew->
1480: 6e 65 78 74 20 3d 20 70 48 2d 3e 66 69 72 73 74  next = pH->first
1490: 3b 0a 20 20 20 20 69 66 28 20 70 48 2d 3e 66 69  ;.    if( pH->fi
14a0: 72 73 74 20 29 7b 20 70 48 2d 3e 66 69 72 73 74  rst ){ pH->first
14b0: 2d 3e 70 72 65 76 20 3d 20 70 4e 65 77 3b 20 7d  ->prev = pNew; }
14c0: 0a 20 20 20 20 70 4e 65 77 2d 3e 70 72 65 76 20  .    pNew->prev 
14d0: 3d 20 30 3b 0a 20 20 20 20 70 48 2d 3e 66 69 72  = 0;.    pH->fir
14e0: 73 74 20 3d 20 70 4e 65 77 3b 0a 20 20 7d 0a 20  st = pNew;.  }. 
14f0: 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 2b 2b   pEntry->count++
1500: 3b 0a 20 20 70 45 6e 74 72 79 2d 3e 63 68 61 69  ;.  pEntry->chai
1510: 6e 20 3d 20 70 4e 65 77 3b 0a 7d 0a 0a 0a 2f 2a  n = pNew;.}.../*
1520: 20 52 65 73 69 7a 65 20 74 68 65 20 68 61 73 68   Resize the hash
1530: 20 74 61 62 6c 65 20 73 6f 20 74 68 61 74 20 69   table so that i
1540: 74 20 63 61 6e 74 61 69 6e 73 20 22 6e 65 77 5f  t cantains "new_
1550: 73 69 7a 65 22 20 62 75 63 6b 65 74 73 2e 0a 2a  size" buckets..*
1560: 2a 20 22 6e 65 77 5f 73 69 7a 65 22 20 6d 75 73  * "new_size" mus
1570: 74 20 62 65 20 61 20 70 6f 77 65 72 20 6f 66 20  t be a power of 
1580: 32 2e 20 20 54 68 65 20 68 61 73 68 20 74 61 62  2.  The hash tab
1590: 6c 65 20 6d 69 67 68 74 20 66 61 69 6c 20 0a 2a  le might fail .*
15a0: 2a 20 74 6f 20 72 65 73 69 7a 65 20 69 66 20 73  * to resize if s
15b0: 71 6c 69 74 65 4d 61 6c 6c 6f 63 28 29 20 66 61  qliteMalloc() fa
15c0: 69 6c 73 2e 0a 2a 2a 0a 2a 2a 20 52 65 74 75 72  ils..**.** Retur
15d0: 6e 20 6e 6f 6e 2d 7a 65 72 6f 20 69 66 20 61 20  n non-zero if a 
15e0: 6d 65 6d 6f 72 79 20 61 6c 6c 6f 63 61 74 69 6f  memory allocatio
15f0: 6e 20 65 72 72 6f 72 20 6f 63 63 75 72 73 2e 0a  n error occurs..
1600: 2a 2f 0a 73 74 61 74 69 63 20 69 6e 74 20 66 74  */.static int ft
1610: 73 33 52 65 68 61 73 68 28 46 74 73 33 48 61 73  s3Rehash(Fts3Has
1620: 68 20 2a 70 48 2c 20 69 6e 74 20 6e 65 77 5f 73  h *pH, int new_s
1630: 69 7a 65 29 7b 0a 20 20 73 74 72 75 63 74 20 5f  ize){.  struct _
1640: 66 74 73 33 68 74 20 2a 6e 65 77 5f 68 74 3b 20  fts3ht *new_ht; 
1650: 20 20 20 20 20 20 20 20 20 2f 2a 20 54 68 65 20           /* The 
1660: 6e 65 77 20 68 61 73 68 20 74 61 62 6c 65 20 2a  new hash table *
1670: 2f 0a 20 20 46 74 73 33 48 61 73 68 45 6c 65 6d  /.  Fts3HashElem
1680: 20 2a 65 6c 65 6d 2c 20 2a 6e 65 78 74 5f 65 6c   *elem, *next_el
1690: 65 6d 3b 20 20 2f 2a 20 46 6f 72 20 6c 6f 6f 70  em;  /* For loop
16a0: 69 6e 67 20 6f 76 65 72 20 65 78 69 73 74 69 6e  ing over existin
16b0: 67 20 65 6c 65 6d 65 6e 74 73 20 2a 2f 0a 20 20  g elements */.  
16c0: 69 6e 74 20 28 2a 78 48 61 73 68 29 28 63 6f 6e  int (*xHash)(con
16d0: 73 74 20 76 6f 69 64 2a 2c 69 6e 74 29 3b 20 20  st void*,int);  
16e0: 20 2f 2a 20 54 68 65 20 68 61 73 68 20 66 75 6e   /* The hash fun
16f0: 63 74 69 6f 6e 20 2a 2f 0a 0a 20 20 61 73 73 65  ction */..  asse
1700: 72 74 28 20 28 6e 65 77 5f 73 69 7a 65 20 26 20  rt( (new_size & 
1710: 28 6e 65 77 5f 73 69 7a 65 2d 31 29 29 3d 3d 30  (new_size-1))==0
1720: 20 29 3b 0a 20 20 6e 65 77 5f 68 74 20 3d 20 28   );.  new_ht = (
1730: 73 74 72 75 63 74 20 5f 66 74 73 33 68 74 20 2a  struct _fts3ht *
1740: 29 66 74 73 33 48 61 73 68 4d 61 6c 6c 6f 63 28  )fts3HashMalloc(
1750: 20 6e 65 77 5f 73 69 7a 65 2a 73 69 7a 65 6f 66   new_size*sizeof
1760: 28 73 74 72 75 63 74 20 5f 66 74 73 33 68 74 29  (struct _fts3ht)
1770: 20 29 3b 0a 20 20 69 66 28 20 6e 65 77 5f 68 74   );.  if( new_ht
1780: 3d 3d 30 20 29 20 72 65 74 75 72 6e 20 31 3b 0a  ==0 ) return 1;.
1790: 20 20 66 74 73 33 48 61 73 68 46 72 65 65 28 70    fts3HashFree(p
17a0: 48 2d 3e 68 74 29 3b 0a 20 20 70 48 2d 3e 68 74  H->ht);.  pH->ht
17b0: 20 3d 20 6e 65 77 5f 68 74 3b 0a 20 20 70 48 2d   = new_ht;.  pH-
17c0: 3e 68 74 73 69 7a 65 20 3d 20 6e 65 77 5f 73 69  >htsize = new_si
17d0: 7a 65 3b 0a 20 20 78 48 61 73 68 20 3d 20 66 74  ze;.  xHash = ft
17e0: 73 48 61 73 68 46 75 6e 63 74 69 6f 6e 28 70 48  sHashFunction(pH
17f0: 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20 20 66  ->keyClass);.  f
1800: 6f 72 28 65 6c 65 6d 3d 70 48 2d 3e 66 69 72 73  or(elem=pH->firs
1810: 74 2c 20 70 48 2d 3e 66 69 72 73 74 3d 30 3b 20  t, pH->first=0; 
1820: 65 6c 65 6d 3b 20 65 6c 65 6d 20 3d 20 6e 65 78  elem; elem = nex
1830: 74 5f 65 6c 65 6d 29 7b 0a 20 20 20 20 69 6e 74  t_elem){.    int
1840: 20 68 20 3d 20 28 2a 78 48 61 73 68 29 28 65 6c   h = (*xHash)(el
1850: 65 6d 2d 3e 70 4b 65 79 2c 20 65 6c 65 6d 2d 3e  em->pKey, elem->
1860: 6e 4b 65 79 29 20 26 20 28 6e 65 77 5f 73 69 7a  nKey) & (new_siz
1870: 65 2d 31 29 3b 0a 20 20 20 20 6e 65 78 74 5f 65  e-1);.    next_e
1880: 6c 65 6d 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74  lem = elem->next
1890: 3b 0a 20 20 20 20 66 74 73 33 48 61 73 68 49 6e  ;.    fts3HashIn
18a0: 73 65 72 74 45 6c 65 6d 65 6e 74 28 70 48 2c 20  sertElement(pH, 
18b0: 26 6e 65 77 5f 68 74 5b 68 5d 2c 20 65 6c 65 6d  &new_ht[h], elem
18c0: 29 3b 0a 20 20 7d 0a 20 20 72 65 74 75 72 6e 20  );.  }.  return 
18d0: 30 3b 0a 7d 0a 0a 2f 2a 20 54 68 69 73 20 66 75  0;.}../* This fu
18e0: 6e 63 74 69 6f 6e 20 28 66 6f 72 20 69 6e 74 65  nction (for inte
18f0: 72 6e 61 6c 20 75 73 65 20 6f 6e 6c 79 29 20 6c  rnal use only) l
1900: 6f 63 61 74 65 73 20 61 6e 20 65 6c 65 6d 65 6e  ocates an elemen
1910: 74 20 69 6e 20 61 6e 0a 2a 2a 20 68 61 73 68 20  t in an.** hash 
1920: 74 61 62 6c 65 20 74 68 61 74 20 6d 61 74 63 68  table that match
1930: 65 73 20 74 68 65 20 67 69 76 65 6e 20 6b 65 79  es the given key
1940: 2e 20 20 54 68 65 20 68 61 73 68 20 66 6f 72 20  .  The hash for 
1950: 74 68 69 73 20 6b 65 79 20 68 61 73 0a 2a 2a 20  this key has.** 
1960: 61 6c 72 65 61 64 79 20 62 65 65 6e 20 63 6f 6d  already been com
1970: 70 75 74 65 64 20 61 6e 64 20 69 73 20 70 61 73  puted and is pas
1980: 73 65 64 20 61 73 20 74 68 65 20 34 74 68 20 70  sed as the 4th p
1990: 61 72 61 6d 65 74 65 72 2e 0a 2a 2f 0a 73 74 61  arameter..*/.sta
19a0: 74 69 63 20 46 74 73 33 48 61 73 68 45 6c 65 6d  tic Fts3HashElem
19b0: 20 2a 66 74 73 33 46 69 6e 64 45 6c 65 6d 65 6e   *fts3FindElemen
19c0: 74 42 79 48 61 73 68 28 0a 20 20 63 6f 6e 73 74  tByHash(.  const
19d0: 20 46 74 73 33 48 61 73 68 20 2a 70 48 2c 20 2f   Fts3Hash *pH, /
19e0: 2a 20 54 68 65 20 70 48 20 74 6f 20 62 65 20 73  * The pH to be s
19f0: 65 61 72 63 68 65 64 20 2a 2f 0a 20 20 63 6f 6e  earched */.  con
1a00: 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 20  st void *pKey,  
1a10: 20 2f 2a 20 54 68 65 20 6b 65 79 20 77 65 20 61   /* The key we a
1a20: 72 65 20 73 65 61 72 63 68 69 6e 67 20 66 6f 72  re searching for
1a30: 20 2a 2f 0a 20 20 69 6e 74 20 6e 4b 65 79 2c 0a   */.  int nKey,.
1a40: 20 20 69 6e 74 20 68 20 20 20 20 20 20 20 20 20    int h         
1a50: 20 20 20 20 20 20 2f 2a 20 54 68 65 20 68 61 73        /* The has
1a60: 68 20 66 6f 72 20 74 68 69 73 20 6b 65 79 2e 20  h for this key. 
1a70: 2a 2f 0a 29 7b 0a 20 20 46 74 73 33 48 61 73 68  */.){.  Fts3Hash
1a80: 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20 20 20 20  Elem *elem;     
1a90: 20 20 20 20 20 20 20 2f 2a 20 55 73 65 64 20 74         /* Used t
1aa0: 6f 20 6c 6f 6f 70 20 74 68 72 75 20 74 68 65 20  o loop thru the 
1ab0: 65 6c 65 6d 65 6e 74 20 6c 69 73 74 20 2a 2f 0a  element list */.
1ac0: 20 20 69 6e 74 20 63 6f 75 6e 74 3b 20 20 20 20    int count;    
1ad0: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
1ae0: 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66 20 65 6c   /* Number of el
1af0: 65 6d 65 6e 74 73 20 6c 65 66 74 20 74 6f 20 74  ements left to t
1b00: 65 73 74 20 2a 2f 0a 20 20 69 6e 74 20 28 2a 78  est */.  int (*x
1b10: 43 6f 6d 70 61 72 65 29 28 63 6f 6e 73 74 20 76  Compare)(const v
1b20: 6f 69 64 2a 2c 69 6e 74 2c 63 6f 6e 73 74 20 76  oid*,int,const v
1b30: 6f 69 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a 20 63  oid*,int);  /* c
1b40: 6f 6d 70 61 72 69 73 6f 6e 20 66 75 6e 63 74 69  omparison functi
1b50: 6f 6e 20 2a 2f 0a 0a 20 20 69 66 28 20 70 48 2d  on */..  if( pH-
1b60: 3e 68 74 20 29 7b 0a 20 20 20 20 73 74 72 75 63  >ht ){.    struc
1b70: 74 20 5f 66 74 73 33 68 74 20 2a 70 45 6e 74 72  t _fts3ht *pEntr
1b80: 79 20 3d 20 26 70 48 2d 3e 68 74 5b 68 5d 3b 0a  y = &pH->ht[h];.
1b90: 20 20 20 20 65 6c 65 6d 20 3d 20 70 45 6e 74 72      elem = pEntr
1ba0: 79 2d 3e 63 68 61 69 6e 3b 0a 20 20 20 20 63 6f  y->chain;.    co
1bb0: 75 6e 74 20 3d 20 70 45 6e 74 72 79 2d 3e 63 6f  unt = pEntry->co
1bc0: 75 6e 74 3b 0a 20 20 20 20 78 43 6f 6d 70 61 72  unt;.    xCompar
1bd0: 65 20 3d 20 66 74 73 43 6f 6d 70 61 72 65 46 75  e = ftsCompareFu
1be0: 6e 63 74 69 6f 6e 28 70 48 2d 3e 6b 65 79 43 6c  nction(pH->keyCl
1bf0: 61 73 73 29 3b 0a 20 20 20 20 77 68 69 6c 65 28  ass);.    while(
1c00: 20 63 6f 75 6e 74 2d 2d 20 26 26 20 65 6c 65 6d   count-- && elem
1c10: 20 29 7b 0a 20 20 20 20 20 20 69 66 28 20 28 2a   ){.      if( (*
1c20: 78 43 6f 6d 70 61 72 65 29 28 65 6c 65 6d 2d 3e  xCompare)(elem->
1c30: 70 4b 65 79 2c 65 6c 65 6d 2d 3e 6e 4b 65 79 2c  pKey,elem->nKey,
1c40: 70 4b 65 79 2c 6e 4b 65 79 29 3d 3d 30 20 29 7b  pKey,nKey)==0 ){
1c50: 20 0a 20 20 20 20 20 20 20 20 72 65 74 75 72 6e   .        return
1c60: 20 65 6c 65 6d 3b 0a 20 20 20 20 20 20 7d 0a 20   elem;.      }. 
1c70: 20 20 20 20 20 65 6c 65 6d 20 3d 20 65 6c 65 6d       elem = elem
1c80: 2d 3e 6e 65 78 74 3b 0a 20 20 20 20 7d 0a 20 20  ->next;.    }.  
1c90: 7d 0a 20 20 72 65 74 75 72 6e 20 30 3b 0a 7d 0a  }.  return 0;.}.
1ca0: 0a 2f 2a 20 52 65 6d 6f 76 65 20 61 20 73 69 6e  ./* Remove a sin
1cb0: 67 6c 65 20 65 6e 74 72 79 20 66 72 6f 6d 20 74  gle entry from t
1cc0: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 67 69  he hash table gi
1cd0: 76 65 6e 20 61 20 70 6f 69 6e 74 65 72 20 74 6f  ven a pointer to
1ce0: 20 74 68 61 74 0a 2a 2a 20 65 6c 65 6d 65 6e 74   that.** element
1cf0: 20 61 6e 64 20 61 20 68 61 73 68 20 6f 6e 20 74   and a hash on t
1d00: 68 65 20 65 6c 65 6d 65 6e 74 27 73 20 6b 65 79  he element's key
1d10: 2e 0a 2a 2f 0a 73 74 61 74 69 63 20 76 6f 69 64  ..*/.static void
1d20: 20 66 74 73 33 52 65 6d 6f 76 65 45 6c 65 6d 65   fts3RemoveEleme
1d30: 6e 74 42 79 48 61 73 68 28 0a 20 20 46 74 73 33  ntByHash(.  Fts3
1d40: 48 61 73 68 20 2a 70 48 2c 20 20 20 20 20 20 20  Hash *pH,       
1d50: 20 20 2f 2a 20 54 68 65 20 70 48 20 63 6f 6e 74    /* The pH cont
1d60: 61 69 6e 69 6e 67 20 22 65 6c 65 6d 22 20 2a 2f  aining "elem" */
1d70: 0a 20 20 46 74 73 33 48 61 73 68 45 6c 65 6d 2a  .  Fts3HashElem*
1d80: 20 65 6c 65 6d 2c 20 20 20 2f 2a 20 54 68 65 20   elem,   /* The 
1d90: 65 6c 65 6d 65 6e 74 20 74 6f 20 62 65 20 72 65  element to be re
1da0: 6d 6f 76 65 64 20 66 72 6f 6d 20 74 68 65 20 70  moved from the p
1db0: 48 20 2a 2f 0a 20 20 69 6e 74 20 68 20 20 20 20  H */.  int h    
1dc0: 20 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20               /* 
1dd0: 48 61 73 68 20 76 61 6c 75 65 20 66 6f 72 20 74  Hash value for t
1de0: 68 65 20 65 6c 65 6d 65 6e 74 20 2a 2f 0a 29 7b  he element */.){
1df0: 0a 20 20 73 74 72 75 63 74 20 5f 66 74 73 33 68  .  struct _fts3h
1e00: 74 20 2a 70 45 6e 74 72 79 3b 0a 20 20 69 66 28  t *pEntry;.  if(
1e10: 20 65 6c 65 6d 2d 3e 70 72 65 76 20 29 7b 0a 20   elem->prev ){. 
1e20: 20 20 20 65 6c 65 6d 2d 3e 70 72 65 76 2d 3e 6e     elem->prev->n
1e30: 65 78 74 20 3d 20 65 6c 65 6d 2d 3e 6e 65 78 74  ext = elem->next
1e40: 3b 20 0a 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20  ; .  }else{.    
1e50: 70 48 2d 3e 66 69 72 73 74 20 3d 20 65 6c 65 6d  pH->first = elem
1e60: 2d 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20 20 69 66  ->next;.  }.  if
1e70: 28 20 65 6c 65 6d 2d 3e 6e 65 78 74 20 29 7b 0a  ( elem->next ){.
1e80: 20 20 20 20 65 6c 65 6d 2d 3e 6e 65 78 74 2d 3e      elem->next->
1e90: 70 72 65 76 20 3d 20 65 6c 65 6d 2d 3e 70 72 65  prev = elem->pre
1ea0: 76 3b 0a 20 20 7d 0a 20 20 70 45 6e 74 72 79 20  v;.  }.  pEntry 
1eb0: 3d 20 26 70 48 2d 3e 68 74 5b 68 5d 3b 0a 20 20  = &pH->ht[h];.  
1ec0: 69 66 28 20 70 45 6e 74 72 79 2d 3e 63 68 61 69  if( pEntry->chai
1ed0: 6e 3d 3d 65 6c 65 6d 20 29 7b 0a 20 20 20 20 70  n==elem ){.    p
1ee0: 45 6e 74 72 79 2d 3e 63 68 61 69 6e 20 3d 20 65  Entry->chain = e
1ef0: 6c 65 6d 2d 3e 6e 65 78 74 3b 0a 20 20 7d 0a 20  lem->next;.  }. 
1f00: 20 70 45 6e 74 72 79 2d 3e 63 6f 75 6e 74 2d 2d   pEntry->count--
1f10: 3b 0a 20 20 69 66 28 20 70 45 6e 74 72 79 2d 3e  ;.  if( pEntry->
1f20: 63 6f 75 6e 74 3c 3d 30 20 29 7b 0a 20 20 20 20  count<=0 ){.    
1f30: 70 45 6e 74 72 79 2d 3e 63 68 61 69 6e 20 3d 20  pEntry->chain = 
1f40: 30 3b 0a 20 20 7d 0a 20 20 69 66 28 20 70 48 2d  0;.  }.  if( pH-
1f50: 3e 63 6f 70 79 4b 65 79 20 26 26 20 65 6c 65 6d  >copyKey && elem
1f60: 2d 3e 70 4b 65 79 20 29 7b 0a 20 20 20 20 66 74  ->pKey ){.    ft
1f70: 73 33 48 61 73 68 46 72 65 65 28 65 6c 65 6d 2d  s3HashFree(elem-
1f80: 3e 70 4b 65 79 29 3b 0a 20 20 7d 0a 20 20 66 74  >pKey);.  }.  ft
1f90: 73 33 48 61 73 68 46 72 65 65 28 20 65 6c 65 6d  s3HashFree( elem
1fa0: 20 29 3b 0a 20 20 70 48 2d 3e 63 6f 75 6e 74 2d   );.  pH->count-
1fb0: 2d 3b 0a 20 20 69 66 28 20 70 48 2d 3e 63 6f 75  -;.  if( pH->cou
1fc0: 6e 74 3c 3d 30 20 29 7b 0a 20 20 20 20 61 73 73  nt<=0 ){.    ass
1fd0: 65 72 74 28 20 70 48 2d 3e 66 69 72 73 74 3d 3d  ert( pH->first==
1fe0: 30 20 29 3b 0a 20 20 20 20 61 73 73 65 72 74 28  0 );.    assert(
1ff0: 20 70 48 2d 3e 63 6f 75 6e 74 3d 3d 30 20 29 3b   pH->count==0 );
2000: 0a 20 20 20 20 66 74 73 33 48 61 73 68 43 6c 65  .    fts3HashCle
2010: 61 72 28 70 48 29 3b 0a 20 20 7d 0a 7d 0a 0a 46  ar(pH);.  }.}..F
2020: 74 73 33 48 61 73 68 45 6c 65 6d 20 2a 73 71 6c  ts3HashElem *sql
2030: 69 74 65 33 46 74 73 33 48 61 73 68 46 69 6e 64  ite3Fts3HashFind
2040: 45 6c 65 6d 28 0a 20 20 63 6f 6e 73 74 20 46 74  Elem(.  const Ft
2050: 73 33 48 61 73 68 20 2a 70 48 2c 20 0a 20 20 63  s3Hash *pH, .  c
2060: 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c  onst void *pKey,
2070: 20 0a 20 20 69 6e 74 20 6e 4b 65 79 0a 29 7b 0a   .  int nKey.){.
2080: 20 20 69 6e 74 20 68 3b 20 20 20 20 20 20 20 20    int h;        
2090: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20                  
20a0: 20 20 2f 2a 20 41 20 68 61 73 68 20 6f 6e 20 6b    /* A hash on k
20b0: 65 79 20 2a 2f 0a 20 20 69 6e 74 20 28 2a 78 48  ey */.  int (*xH
20c0: 61 73 68 29 28 63 6f 6e 73 74 20 76 6f 69 64 2a  ash)(const void*
20d0: 2c 69 6e 74 29 3b 20 20 2f 2a 20 54 68 65 20 68  ,int);  /* The h
20e0: 61 73 68 20 66 75 6e 63 74 69 6f 6e 20 2a 2f 0a  ash function */.
20f0: 0a 20 20 69 66 28 20 70 48 3d 3d 30 20 7c 7c 20  .  if( pH==0 || 
2100: 70 48 2d 3e 68 74 3d 3d 30 20 29 20 72 65 74 75  pH->ht==0 ) retu
2110: 72 6e 20 30 3b 0a 20 20 78 48 61 73 68 20 3d 20  rn 0;.  xHash = 
2120: 66 74 73 48 61 73 68 46 75 6e 63 74 69 6f 6e 28  ftsHashFunction(
2130: 70 48 2d 3e 6b 65 79 43 6c 61 73 73 29 3b 0a 20  pH->keyClass);. 
2140: 20 61 73 73 65 72 74 28 20 78 48 61 73 68 21 3d   assert( xHash!=
2150: 30 20 29 3b 0a 20 20 68 20 3d 20 28 2a 78 48 61  0 );.  h = (*xHa
2160: 73 68 29 28 70 4b 65 79 2c 6e 4b 65 79 29 3b 0a  sh)(pKey,nKey);.
2170: 20 20 61 73 73 65 72 74 28 20 28 70 48 2d 3e 68    assert( (pH->h
2180: 74 73 69 7a 65 20 26 20 28 70 48 2d 3e 68 74 73  tsize & (pH->hts
2190: 69 7a 65 2d 31 29 29 3d 3d 30 20 29 3b 0a 20 20  ize-1))==0 );.  
21a0: 72 65 74 75 72 6e 20 66 74 73 33 46 69 6e 64 45  return fts3FindE
21b0: 6c 65 6d 65 6e 74 42 79 48 61 73 68 28 70 48 2c  lementByHash(pH,
21c0: 70 4b 65 79 2c 6e 4b 65 79 2c 20 68 20 26 20 28  pKey,nKey, h & (
21d0: 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29 29 3b 0a  pH->htsize-1));.
21e0: 7d 0a 0a 2f 2a 20 0a 2a 2a 20 41 74 74 65 6d 70  }../* .** Attemp
21f0: 74 20 74 6f 20 6c 6f 63 61 74 65 20 61 6e 20 65  t to locate an e
2200: 6c 65 6d 65 6e 74 20 6f 66 20 74 68 65 20 68 61  lement of the ha
2210: 73 68 20 74 61 62 6c 65 20 70 48 20 77 69 74 68  sh table pH with
2220: 20 61 20 6b 65 79 0a 2a 2a 20 74 68 61 74 20 6d   a key.** that m
2230: 61 74 63 68 65 73 20 70 4b 65 79 2c 6e 4b 65 79  atches pKey,nKey
2240: 2e 20 20 52 65 74 75 72 6e 20 74 68 65 20 64 61  .  Return the da
2250: 74 61 20 66 6f 72 20 74 68 69 73 20 65 6c 65 6d  ta for this elem
2260: 65 6e 74 20 69 66 20 69 74 20 69 73 0a 2a 2a 20  ent if it is.** 
2270: 66 6f 75 6e 64 2c 20 6f 72 20 4e 55 4c 4c 20 69  found, or NULL i
2280: 66 20 74 68 65 72 65 20 69 73 20 6e 6f 20 6d 61  f there is no ma
2290: 74 63 68 2e 0a 2a 2f 0a 76 6f 69 64 20 2a 73 71  tch..*/.void *sq
22a0: 6c 69 74 65 33 46 74 73 33 48 61 73 68 46 69 6e  lite3Fts3HashFin
22b0: 64 28 63 6f 6e 73 74 20 46 74 73 33 48 61 73 68  d(const Fts3Hash
22c0: 20 2a 70 48 2c 20 63 6f 6e 73 74 20 76 6f 69 64   *pH, const void
22d0: 20 2a 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79   *pKey, int nKey
22e0: 29 7b 0a 20 20 46 74 73 33 48 61 73 68 45 6c 65  ){.  Fts3HashEle
22f0: 6d 20 2a 70 45 6c 65 6d 3b 20 20 20 20 20 20 20  m *pElem;       
2300: 20 20 20 20 20 2f 2a 20 54 68 65 20 65 6c 65 6d       /* The elem
2310: 65 6e 74 20 74 68 61 74 20 6d 61 74 63 68 65 73  ent that matches
2320: 20 6b 65 79 20 28 69 66 20 61 6e 79 29 20 2a 2f   key (if any) */
2330: 0a 0a 20 20 70 45 6c 65 6d 20 3d 20 73 71 6c 69  ..  pElem = sqli
2340: 74 65 33 46 74 73 33 48 61 73 68 46 69 6e 64 45  te3Fts3HashFindE
2350: 6c 65 6d 28 70 48 2c 20 70 4b 65 79 2c 20 6e 4b  lem(pH, pKey, nK
2360: 65 79 29 3b 0a 20 20 72 65 74 75 72 6e 20 70 45  ey);.  return pE
2370: 6c 65 6d 20 3f 20 70 45 6c 65 6d 2d 3e 64 61 74  lem ? pElem->dat
2380: 61 20 3a 20 30 3b 0a 7d 0a 0a 2f 2a 20 49 6e 73  a : 0;.}../* Ins
2390: 65 72 74 20 61 6e 20 65 6c 65 6d 65 6e 74 20 69  ert an element i
23a0: 6e 74 6f 20 74 68 65 20 68 61 73 68 20 74 61 62  nto the hash tab
23b0: 6c 65 20 70 48 2e 20 20 54 68 65 20 6b 65 79 20  le pH.  The key 
23c0: 69 73 20 70 4b 65 79 2c 6e 4b 65 79 0a 2a 2a 20  is pKey,nKey.** 
23d0: 61 6e 64 20 74 68 65 20 64 61 74 61 20 69 73 20  and the data is 
23e0: 22 64 61 74 61 22 2e 0a 2a 2a 0a 2a 2a 20 49 66  "data"..**.** If
23f0: 20 6e 6f 20 65 6c 65 6d 65 6e 74 20 65 78 69 73   no element exis
2400: 74 73 20 77 69 74 68 20 61 20 6d 61 74 63 68 69  ts with a matchi
2410: 6e 67 20 6b 65 79 2c 20 74 68 65 6e 20 61 20 6e  ng key, then a n
2420: 65 77 0a 2a 2a 20 65 6c 65 6d 65 6e 74 20 69 73  ew.** element is
2430: 20 63 72 65 61 74 65 64 2e 20 20 41 20 63 6f 70   created.  A cop
2440: 79 20 6f 66 20 74 68 65 20 6b 65 79 20 69 73 20  y of the key is 
2450: 6d 61 64 65 20 69 66 20 74 68 65 20 63 6f 70 79  made if the copy
2460: 4b 65 79 0a 2a 2a 20 66 6c 61 67 20 69 73 20 73  Key.** flag is s
2470: 65 74 2e 20 20 4e 55 4c 4c 20 69 73 20 72 65 74  et.  NULL is ret
2480: 75 72 6e 65 64 2e 0a 2a 2a 0a 2a 2a 20 49 66 20  urned..**.** If 
2490: 61 6e 6f 74 68 65 72 20 65 6c 65 6d 65 6e 74 20  another element 
24a0: 61 6c 72 65 61 64 79 20 65 78 69 73 74 73 20 77  already exists w
24b0: 69 74 68 20 74 68 65 20 73 61 6d 65 20 6b 65 79  ith the same key
24c0: 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20 6e 65  , then the.** ne
24d0: 77 20 64 61 74 61 20 72 65 70 6c 61 63 65 73 20  w data replaces 
24e0: 74 68 65 20 6f 6c 64 20 64 61 74 61 20 61 6e 64  the old data and
24f0: 20 74 68 65 20 6f 6c 64 20 64 61 74 61 20 69 73   the old data is
2500: 20 72 65 74 75 72 6e 65 64 2e 0a 2a 2a 20 54 68   returned..** Th
2510: 65 20 6b 65 79 20 69 73 20 6e 6f 74 20 63 6f 70  e key is not cop
2520: 69 65 64 20 69 6e 20 74 68 69 73 20 69 6e 73 74  ied in this inst
2530: 61 6e 63 65 2e 20 20 49 66 20 61 20 6d 61 6c 6c  ance.  If a mall
2540: 6f 63 20 66 61 69 6c 73 2c 20 74 68 65 6e 0a 2a  oc fails, then.*
2550: 2a 20 74 68 65 20 6e 65 77 20 64 61 74 61 20 69  * the new data i
2560: 73 20 72 65 74 75 72 6e 65 64 20 61 6e 64 20 74  s returned and t
2570: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 69 73  he hash table is
2580: 20 75 6e 63 68 61 6e 67 65 64 2e 0a 2a 2a 0a 2a   unchanged..**.*
2590: 2a 20 49 66 20 74 68 65 20 22 64 61 74 61 22 20  * If the "data" 
25a0: 70 61 72 61 6d 65 74 65 72 20 74 6f 20 74 68 69  parameter to thi
25b0: 73 20 66 75 6e 63 74 69 6f 6e 20 69 73 20 4e 55  s function is NU
25c0: 4c 4c 2c 20 74 68 65 6e 20 74 68 65 0a 2a 2a 20  LL, then the.** 
25d0: 65 6c 65 6d 65 6e 74 20 63 6f 72 72 65 73 70 6f  element correspo
25e0: 6e 64 69 6e 67 20 74 6f 20 22 6b 65 79 22 20 69  nding to "key" i
25f0: 73 20 72 65 6d 6f 76 65 64 20 66 72 6f 6d 20 74  s removed from t
2600: 68 65 20 68 61 73 68 20 74 61 62 6c 65 2e 0a 2a  he hash table..*
2610: 2f 0a 76 6f 69 64 20 2a 73 71 6c 69 74 65 33 46  /.void *sqlite3F
2620: 74 73 33 48 61 73 68 49 6e 73 65 72 74 28 0a 20  ts3HashInsert(. 
2630: 20 46 74 73 33 48 61 73 68 20 2a 70 48 2c 20 20   Fts3Hash *pH,  
2640: 20 20 20 20 20 20 2f 2a 20 54 68 65 20 68 61 73        /* The has
2650: 68 20 74 61 62 6c 65 20 74 6f 20 69 6e 73 65 72  h table to inser
2660: 74 20 69 6e 74 6f 20 2a 2f 0a 20 20 63 6f 6e 73  t into */.  cons
2670: 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 20 20  t void *pKey,   
2680: 20 2f 2a 20 54 68 65 20 6b 65 79 20 2a 2f 0a 20   /* The key */. 
2690: 20 69 6e 74 20 6e 4b 65 79 2c 20 20 20 20 20 20   int nKey,      
26a0: 20 20 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20        /* Number 
26b0: 6f 66 20 62 79 74 65 73 20 69 6e 20 74 68 65 20  of bytes in the 
26c0: 6b 65 79 20 2a 2f 0a 20 20 76 6f 69 64 20 2a 64  key */.  void *d
26d0: 61 74 61 20 20 20 20 20 20 20 20 20 20 20 2f 2a  ata           /*
26e0: 20 54 68 65 20 64 61 74 61 20 2a 2f 0a 29 7b 0a   The data */.){.
26f0: 20 20 69 6e 74 20 68 72 61 77 3b 20 20 20 20 20    int hraw;     
2700: 20 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 52              /* R
2710: 61 77 20 68 61 73 68 20 76 61 6c 75 65 20 6f 66  aw hash value of
2720: 20 74 68 65 20 6b 65 79 20 2a 2f 0a 20 20 69 6e   the key */.  in
2730: 74 20 68 3b 20 20 20 20 20 20 20 20 20 20 20 20  t h;            
2740: 20 20 20 20 20 20 20 20 2f 2a 20 74 68 65 20 68          /* the h
2750: 61 73 68 20 6f 66 20 74 68 65 20 6b 65 79 20 6d  ash of the key m
2760: 6f 64 75 6c 6f 20 68 61 73 68 20 74 61 62 6c 65  odulo hash table
2770: 20 73 69 7a 65 20 2a 2f 0a 20 20 46 74 73 33 48   size */.  Fts3H
2780: 61 73 68 45 6c 65 6d 20 2a 65 6c 65 6d 3b 20 20  ashElem *elem;  
2790: 20 20 20 20 20 2f 2a 20 55 73 65 64 20 74 6f 20       /* Used to 
27a0: 6c 6f 6f 70 20 74 68 72 75 20 74 68 65 20 65 6c  loop thru the el
27b0: 65 6d 65 6e 74 20 6c 69 73 74 20 2a 2f 0a 20 20  ement list */.  
27c0: 46 74 73 33 48 61 73 68 45 6c 65 6d 20 2a 6e 65  Fts3HashElem *ne
27d0: 77 5f 65 6c 65 6d 3b 20 20 20 2f 2a 20 4e 65 77  w_elem;   /* New
27e0: 20 65 6c 65 6d 65 6e 74 20 61 64 64 65 64 20 74   element added t
27f0: 6f 20 74 68 65 20 70 48 20 2a 2f 0a 20 20 69 6e  o the pH */.  in
2800: 74 20 28 2a 78 48 61 73 68 29 28 63 6f 6e 73 74  t (*xHash)(const
2810: 20 76 6f 69 64 2a 2c 69 6e 74 29 3b 20 20 2f 2a   void*,int);  /*
2820: 20 54 68 65 20 68 61 73 68 20 66 75 6e 63 74 69   The hash functi
2830: 6f 6e 20 2a 2f 0a 0a 20 20 61 73 73 65 72 74 28  on */..  assert(
2840: 20 70 48 21 3d 30 20 29 3b 0a 20 20 78 48 61 73   pH!=0 );.  xHas
2850: 68 20 3d 20 66 74 73 48 61 73 68 46 75 6e 63 74  h = ftsHashFunct
2860: 69 6f 6e 28 70 48 2d 3e 6b 65 79 43 6c 61 73 73  ion(pH->keyClass
2870: 29 3b 0a 20 20 61 73 73 65 72 74 28 20 78 48 61  );.  assert( xHa
2880: 73 68 21 3d 30 20 29 3b 0a 20 20 68 72 61 77 20  sh!=0 );.  hraw 
2890: 3d 20 28 2a 78 48 61 73 68 29 28 70 4b 65 79 2c  = (*xHash)(pKey,
28a0: 20 6e 4b 65 79 29 3b 0a 20 20 61 73 73 65 72 74   nKey);.  assert
28b0: 28 20 28 70 48 2d 3e 68 74 73 69 7a 65 20 26 20  ( (pH->htsize & 
28c0: 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31 29 29 3d  (pH->htsize-1))=
28d0: 3d 30 20 29 3b 0a 20 20 68 20 3d 20 68 72 61 77  =0 );.  h = hraw
28e0: 20 26 20 28 70 48 2d 3e 68 74 73 69 7a 65 2d 31   & (pH->htsize-1
28f0: 29 3b 0a 20 20 65 6c 65 6d 20 3d 20 66 74 73 33  );.  elem = fts3
2900: 46 69 6e 64 45 6c 65 6d 65 6e 74 42 79 48 61 73  FindElementByHas
2910: 68 28 70 48 2c 70 4b 65 79 2c 6e 4b 65 79 2c 68  h(pH,pKey,nKey,h
2920: 29 3b 0a 20 20 69 66 28 20 65 6c 65 6d 20 29 7b  );.  if( elem ){
2930: 0a 20 20 20 20 76 6f 69 64 20 2a 6f 6c 64 5f 64  .    void *old_d
2940: 61 74 61 20 3d 20 65 6c 65 6d 2d 3e 64 61 74 61  ata = elem->data
2950: 3b 0a 20 20 20 20 69 66 28 20 64 61 74 61 3d 3d  ;.    if( data==
2960: 30 20 29 7b 0a 20 20 20 20 20 20 66 74 73 33 52  0 ){.      fts3R
2970: 65 6d 6f 76 65 45 6c 65 6d 65 6e 74 42 79 48 61  emoveElementByHa
2980: 73 68 28 70 48 2c 65 6c 65 6d 2c 68 29 3b 0a 20  sh(pH,elem,h);. 
2990: 20 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 20 20     }else{.      
29a0: 65 6c 65 6d 2d 3e 64 61 74 61 20 3d 20 64 61 74  elem->data = dat
29b0: 61 3b 0a 20 20 20 20 7d 0a 20 20 20 20 72 65 74  a;.    }.    ret
29c0: 75 72 6e 20 6f 6c 64 5f 64 61 74 61 3b 0a 20 20  urn old_data;.  
29d0: 7d 0a 20 20 69 66 28 20 64 61 74 61 3d 3d 30 20  }.  if( data==0 
29e0: 29 20 72 65 74 75 72 6e 20 30 3b 0a 20 20 69 66  ) return 0;.  if
29f0: 28 20 28 70 48 2d 3e 68 74 73 69 7a 65 3d 3d 30  ( (pH->htsize==0
2a00: 20 26 26 20 66 74 73 33 52 65 68 61 73 68 28 70   && fts3Rehash(p
2a10: 48 2c 38 29 29 0a 20 20 20 7c 7c 20 28 70 48 2d  H,8)).   || (pH-
2a20: 3e 63 6f 75 6e 74 3e 3d 70 48 2d 3e 68 74 73 69  >count>=pH->htsi
2a30: 7a 65 20 26 26 20 66 74 73 33 52 65 68 61 73 68  ze && fts3Rehash
2a40: 28 70 48 2c 20 70 48 2d 3e 68 74 73 69 7a 65 2a  (pH, pH->htsize*
2a50: 32 29 29 0a 20 20 29 7b 0a 20 20 20 20 70 48 2d  2)).  ){.    pH-
2a60: 3e 63 6f 75 6e 74 20 3d 20 30 3b 0a 20 20 20 20  >count = 0;.    
2a70: 72 65 74 75 72 6e 20 64 61 74 61 3b 0a 20 20 7d  return data;.  }
2a80: 0a 20 20 61 73 73 65 72 74 28 20 70 48 2d 3e 68  .  assert( pH->h
2a90: 74 73 69 7a 65 3e 30 20 29 3b 0a 20 20 6e 65 77  tsize>0 );.  new
2aa0: 5f 65 6c 65 6d 20 3d 20 28 46 74 73 33 48 61 73  _elem = (Fts3Has
2ab0: 68 45 6c 65 6d 2a 29 66 74 73 33 48 61 73 68 4d  hElem*)fts3HashM
2ac0: 61 6c 6c 6f 63 28 20 73 69 7a 65 6f 66 28 46 74  alloc( sizeof(Ft
2ad0: 73 33 48 61 73 68 45 6c 65 6d 29 20 29 3b 0a 20  s3HashElem) );. 
2ae0: 20 69 66 28 20 6e 65 77 5f 65 6c 65 6d 3d 3d 30   if( new_elem==0
2af0: 20 29 20 72 65 74 75 72 6e 20 64 61 74 61 3b 0a   ) return data;.
2b00: 20 20 69 66 28 20 70 48 2d 3e 63 6f 70 79 4b 65    if( pH->copyKe
2b10: 79 20 26 26 20 70 4b 65 79 21 3d 30 20 29 7b 0a  y && pKey!=0 ){.
2b20: 20 20 20 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b      new_elem->pK
2b30: 65 79 20 3d 20 66 74 73 33 48 61 73 68 4d 61 6c  ey = fts3HashMal
2b40: 6c 6f 63 28 20 6e 4b 65 79 20 29 3b 0a 20 20 20  loc( nKey );.   
2b50: 20 69 66 28 20 6e 65 77 5f 65 6c 65 6d 2d 3e 70   if( new_elem->p
2b60: 4b 65 79 3d 3d 30 20 29 7b 0a 20 20 20 20 20 20  Key==0 ){.      
2b70: 66 74 73 33 48 61 73 68 46 72 65 65 28 6e 65 77  fts3HashFree(new
2b80: 5f 65 6c 65 6d 29 3b 0a 20 20 20 20 20 20 72 65  _elem);.      re
2b90: 74 75 72 6e 20 64 61 74 61 3b 0a 20 20 20 20 7d  turn data;.    }
2ba0: 0a 20 20 20 20 6d 65 6d 63 70 79 28 28 76 6f 69  .    memcpy((voi
2bb0: 64 2a 29 6e 65 77 5f 65 6c 65 6d 2d 3e 70 4b 65  d*)new_elem->pKe
2bc0: 79 2c 20 70 4b 65 79 2c 20 6e 4b 65 79 29 3b 0a  y, pKey, nKey);.
2bd0: 20 20 7d 65 6c 73 65 7b 0a 20 20 20 20 6e 65 77    }else{.    new
2be0: 5f 65 6c 65 6d 2d 3e 70 4b 65 79 20 3d 20 28 76  _elem->pKey = (v
2bf0: 6f 69 64 2a 29 70 4b 65 79 3b 0a 20 20 7d 0a 20  oid*)pKey;.  }. 
2c00: 20 6e 65 77 5f 65 6c 65 6d 2d 3e 6e 4b 65 79 20   new_elem->nKey 
2c10: 3d 20 6e 4b 65 79 3b 0a 20 20 70 48 2d 3e 63 6f  = nKey;.  pH->co
2c20: 75 6e 74 2b 2b 3b 0a 20 20 61 73 73 65 72 74 28  unt++;.  assert(
2c30: 20 70 48 2d 3e 68 74 73 69 7a 65 3e 30 20 29 3b   pH->htsize>0 );
2c40: 0a 20 20 61 73 73 65 72 74 28 20 28 70 48 2d 3e  .  assert( (pH->
2c50: 68 74 73 69 7a 65 20 26 20 28 70 48 2d 3e 68 74  htsize & (pH->ht
2c60: 73 69 7a 65 2d 31 29 29 3d 3d 30 20 29 3b 0a 20  size-1))==0 );. 
2c70: 20 68 20 3d 20 68 72 61 77 20 26 20 28 70 48 2d   h = hraw & (pH-
2c80: 3e 68 74 73 69 7a 65 2d 31 29 3b 0a 20 20 66 74  >htsize-1);.  ft
2c90: 73 33 48 61 73 68 49 6e 73 65 72 74 45 6c 65 6d  s3HashInsertElem
2ca0: 65 6e 74 28 70 48 2c 20 26 70 48 2d 3e 68 74 5b  ent(pH, &pH->ht[
2cb0: 68 5d 2c 20 6e 65 77 5f 65 6c 65 6d 29 3b 0a 20  h], new_elem);. 
2cc0: 20 6e 65 77 5f 65 6c 65 6d 2d 3e 64 61 74 61 20   new_elem->data 
2cd0: 3d 20 64 61 74 61 3b 0a 20 20 72 65 74 75 72 6e  = data;.  return
2ce0: 20 30 3b 0a 7d 0a 0a 23 65 6e 64 69 66 20 2f 2a   0;.}..#endif /*
2cf0: 20 21 64 65 66 69 6e 65 64 28 53 51 4c 49 54 45   !defined(SQLITE
2d00: 5f 43 4f 52 45 29 20 7c 7c 20 64 65 66 69 6e 65  _CORE) || define
2d10: 64 28 53 51 4c 49 54 45 5f 45 4e 41 42 4c 45 5f  d(SQLITE_ENABLE_
2d20: 46 54 53 33 29 20 2a 2f 0a                       FTS3) */.