/ Hex Artifact Content
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

Artifact 28f38ebb1006a5beedcb013bcdfe31befe7437ae:


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 68 65 61 64 65 72 20 66 69 6c  s the header fil
0190: 65 20 66 6f 72 20 74 68 65 20 67 65 6e 65 72 69  e for the generi
01a0: 63 20 68 61 73 68 2d 74 61 62 6c 65 20 69 6d 70  c hash-table imp
01b0: 6c 65 6d 65 6e 61 74 69 6f 6e 0a 2a 2a 20 75 73  lemenation.** us
01c0: 65 64 20 69 6e 20 53 51 4c 69 74 65 2e 0a 2a 2a  ed in SQLite..**
01d0: 0a 2a 2a 20 24 49 64 3a 20 68 61 73 68 2e 68 2c  .** $Id: hash.h,
01e0: 76 20 31 2e 31 32 20 32 30 30 38 2f 31 30 2f 31  v 1.12 2008/10/1
01f0: 30 20 31 37 3a 34 31 3a 32 39 20 64 72 68 20 45  0 17:41:29 drh E
0200: 78 70 20 24 0a 2a 2f 0a 23 69 66 6e 64 65 66 20  xp $.*/.#ifndef 
0210: 5f 53 51 4c 49 54 45 5f 48 41 53 48 5f 48 5f 0a  _SQLITE_HASH_H_.
0220: 23 64 65 66 69 6e 65 20 5f 53 51 4c 49 54 45 5f  #define _SQLITE_
0230: 48 41 53 48 5f 48 5f 0a 0a 2f 2a 20 46 6f 72 77  HASH_H_../* Forw
0240: 61 72 64 20 64 65 63 6c 61 72 61 74 69 6f 6e 73  ard declarations
0250: 20 6f 66 20 73 74 72 75 63 74 75 72 65 73 2e 20   of structures. 
0260: 2a 2f 0a 74 79 70 65 64 65 66 20 73 74 72 75 63  */.typedef struc
0270: 74 20 48 61 73 68 20 48 61 73 68 3b 0a 74 79 70  t Hash Hash;.typ
0280: 65 64 65 66 20 73 74 72 75 63 74 20 48 61 73 68  edef struct Hash
0290: 45 6c 65 6d 20 48 61 73 68 45 6c 65 6d 3b 0a 0a  Elem HashElem;..
02a0: 2f 2a 20 41 20 63 6f 6d 70 6c 65 74 65 20 68 61  /* A complete ha
02b0: 73 68 20 74 61 62 6c 65 20 69 73 20 61 6e 20 69  sh table is an i
02c0: 6e 73 74 61 6e 63 65 20 6f 66 20 74 68 65 20 66  nstance of the f
02d0: 6f 6c 6c 6f 77 69 6e 67 20 73 74 72 75 63 74 75  ollowing structu
02e0: 72 65 2e 0a 2a 2a 20 54 68 65 20 69 6e 74 65 72  re..** The inter
02f0: 6e 61 6c 73 20 6f 66 20 74 68 69 73 20 73 74 72  nals of this str
0300: 75 63 74 75 72 65 20 61 72 65 20 69 6e 74 65 6e  ucture are inten
0310: 64 65 64 20 74 6f 20 62 65 20 6f 70 61 71 75 65  ded to be opaque
0320: 20 2d 2d 20 63 6c 69 65 6e 74 0a 2a 2a 20 63 6f   -- client.** co
0330: 64 65 20 73 68 6f 75 6c 64 20 6e 6f 74 20 61 74  de should not at
0340: 74 65 6d 70 74 20 74 6f 20 61 63 63 65 73 73 20  tempt to access 
0350: 6f 72 20 6d 6f 64 69 66 79 20 74 68 65 20 66 69  or modify the fi
0360: 65 6c 64 73 20 6f 66 20 74 68 69 73 20 73 74 72  elds of this str
0370: 75 63 74 75 72 65 0a 2a 2a 20 64 69 72 65 63 74  ucture.** direct
0380: 6c 79 2e 20 20 43 68 61 6e 67 65 20 74 68 69 73  ly.  Change this
0390: 20 73 74 72 75 63 74 75 72 65 20 6f 6e 6c 79 20   structure only 
03a0: 62 79 20 75 73 69 6e 67 20 74 68 65 20 72 6f 75  by using the rou
03b0: 74 69 6e 65 73 20 62 65 6c 6f 77 2e 0a 2a 2a 20  tines below..** 
03c0: 48 6f 77 65 76 65 72 2c 20 6d 61 6e 79 20 6f 66  However, many of
03d0: 20 74 68 65 20 22 70 72 6f 63 65 64 75 72 65 73   the "procedures
03e0: 22 20 61 6e 64 20 22 66 75 6e 63 74 69 6f 6e 73  " and "functions
03f0: 22 20 66 6f 72 20 6d 6f 64 69 66 79 69 6e 67 20  " for modifying 
0400: 61 6e 64 0a 2a 2a 20 61 63 63 65 73 73 69 6e 67  and.** accessing
0410: 20 74 68 69 73 20 73 74 72 75 63 74 75 72 65 20   this structure 
0420: 61 72 65 20 72 65 61 6c 6c 79 20 6d 61 63 72 6f  are really macro
0430: 73 2c 20 73 6f 20 77 65 20 63 61 6e 27 74 20 72  s, so we can't r
0440: 65 61 6c 6c 79 20 6d 61 6b 65 0a 2a 2a 20 74 68  eally make.** th
0450: 69 73 20 73 74 72 75 63 74 75 72 65 20 6f 70 61  is structure opa
0460: 71 75 65 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 48  que..*/.struct H
0470: 61 73 68 20 7b 0a 20 20 75 6e 73 69 67 6e 65 64  ash {.  unsigned
0480: 20 69 6e 74 20 63 6f 70 79 4b 65 79 3a 20 31 3b   int copyKey: 1;
0490: 20 20 2f 2a 20 54 72 75 65 20 69 66 20 63 6f 70    /* True if cop
04a0: 79 20 6f 66 20 6b 65 79 20 6d 61 64 65 20 6f 6e  y of key made on
04b0: 20 69 6e 73 65 72 74 20 2a 2f 0a 20 20 75 6e 73   insert */.  uns
04c0: 69 67 6e 65 64 20 69 6e 74 20 68 74 73 69 7a 65  igned int htsize
04d0: 20 3a 20 33 31 3b 20 2f 2a 20 4e 75 6d 62 65 72   : 31; /* Number
04e0: 20 6f 66 20 62 75 63 6b 65 74 73 20 69 6e 20 74   of buckets in t
04f0: 68 65 20 68 61 73 68 20 74 61 62 6c 65 20 2a 2f  he hash table */
0500: 0a 20 20 75 6e 73 69 67 6e 65 64 20 69 6e 74 20  .  unsigned int 
0510: 63 6f 75 6e 74 3b 20 20 20 20 20 20 20 2f 2a 20  count;       /* 
0520: 4e 75 6d 62 65 72 20 6f 66 20 65 6e 74 72 69 65  Number of entrie
0530: 73 20 69 6e 20 74 68 69 73 20 74 61 62 6c 65 20  s in this table 
0540: 2a 2f 0a 20 20 48 61 73 68 45 6c 65 6d 20 2a 66  */.  HashElem *f
0550: 69 72 73 74 3b 20 20 20 20 20 20 20 20 20 20 2f  irst;          /
0560: 2a 20 54 68 65 20 66 69 72 73 74 20 65 6c 65 6d  * The first elem
0570: 65 6e 74 20 6f 66 20 74 68 65 20 61 72 72 61 79  ent of the array
0580: 20 2a 2f 0a 20 20 73 74 72 75 63 74 20 5f 68 74   */.  struct _ht
0590: 20 7b 20 20 20 20 20 20 20 20 20 20 20 20 20 20   {              
05a0: 2f 2a 20 74 68 65 20 68 61 73 68 20 74 61 62 6c  /* the hash tabl
05b0: 65 20 2a 2f 0a 20 20 20 20 69 6e 74 20 63 6f 75  e */.    int cou
05c0: 6e 74 3b 20 20 20 20 20 20 20 20 20 20 20 20 20  nt;             
05d0: 20 20 20 20 2f 2a 20 4e 75 6d 62 65 72 20 6f 66      /* Number of
05e0: 20 65 6e 74 72 69 65 73 20 77 69 74 68 20 74 68   entries with th
05f0: 69 73 20 68 61 73 68 20 2a 2f 0a 20 20 20 20 48  is hash */.    H
0600: 61 73 68 45 6c 65 6d 20 2a 63 68 61 69 6e 3b 20  ashElem *chain; 
0610: 20 20 20 20 20 20 20 20 20 20 2f 2a 20 50 6f 69            /* Poi
0620: 6e 74 65 72 20 74 6f 20 66 69 72 73 74 20 65 6e  nter to first en
0630: 74 72 79 20 77 69 74 68 20 74 68 69 73 20 68 61  try with this ha
0640: 73 68 20 2a 2f 0a 20 20 7d 20 2a 68 74 3b 0a 7d  sh */.  } *ht;.}
0650: 3b 0a 0a 2f 2a 20 45 61 63 68 20 65 6c 65 6d 65  ;../* Each eleme
0660: 6e 74 20 69 6e 20 74 68 65 20 68 61 73 68 20 74  nt in the hash t
0670: 61 62 6c 65 20 69 73 20 61 6e 20 69 6e 73 74 61  able is an insta
0680: 6e 63 65 20 6f 66 20 74 68 65 20 66 6f 6c 6c 6f  nce of the follo
0690: 77 69 6e 67 20 0a 2a 2a 20 73 74 72 75 63 74 75  wing .** structu
06a0: 72 65 2e 20 20 41 6c 6c 20 65 6c 65 6d 65 6e 74  re.  All element
06b0: 73 20 61 72 65 20 73 74 6f 72 65 64 20 6f 6e 20  s are stored on 
06c0: 61 20 73 69 6e 67 6c 65 20 64 6f 75 62 6c 79 2d  a single doubly-
06d0: 6c 69 6e 6b 65 64 20 6c 69 73 74 2e 0a 2a 2a 0a  linked list..**.
06e0: 2a 2a 20 41 67 61 69 6e 2c 20 74 68 69 73 20 73  ** Again, this s
06f0: 74 72 75 63 74 75 72 65 20 69 73 20 69 6e 74 65  tructure is inte
0700: 6e 64 65 64 20 74 6f 20 62 65 20 6f 70 61 71 75  nded to be opaqu
0710: 65 2c 20 62 75 74 20 69 74 20 63 61 6e 27 74 20  e, but it can't 
0720: 72 65 61 6c 6c 79 0a 2a 2a 20 62 65 20 6f 70 61  really.** be opa
0730: 71 75 65 20 62 65 63 61 75 73 65 20 69 74 20 69  que because it i
0740: 73 20 75 73 65 64 20 62 79 20 6d 61 63 72 6f 73  s used by macros
0750: 2e 0a 2a 2f 0a 73 74 72 75 63 74 20 48 61 73 68  ..*/.struct Hash
0760: 45 6c 65 6d 20 7b 0a 20 20 48 61 73 68 45 6c 65  Elem {.  HashEle
0770: 6d 20 2a 6e 65 78 74 2c 20 2a 70 72 65 76 3b 20  m *next, *prev; 
0780: 20 20 2f 2a 20 4e 65 78 74 20 61 6e 64 20 70 72    /* Next and pr
0790: 65 76 69 6f 75 73 20 65 6c 65 6d 65 6e 74 73 20  evious elements 
07a0: 69 6e 20 74 68 65 20 74 61 62 6c 65 20 2a 2f 0a  in the table */.
07b0: 20 20 76 6f 69 64 20 2a 64 61 74 61 3b 20 20 20    void *data;   
07c0: 20 20 20 20 20 20 20 20 20 20 20 2f 2a 20 44 61             /* Da
07d0: 74 61 20 61 73 73 6f 63 69 61 74 65 64 20 77 69  ta associated wi
07e0: 74 68 20 74 68 69 73 20 65 6c 65 6d 65 6e 74 20  th this element 
07f0: 2a 2f 0a 20 20 76 6f 69 64 20 2a 70 4b 65 79 3b  */.  void *pKey;
0800: 20 69 6e 74 20 6e 4b 65 79 3b 20 20 20 20 2f 2a   int nKey;    /*
0810: 20 4b 65 79 20 61 73 73 6f 63 69 61 74 65 64 20   Key associated 
0820: 77 69 74 68 20 74 68 69 73 20 65 6c 65 6d 65 6e  with this elemen
0830: 74 20 2a 2f 0a 7d 3b 0a 0a 2f 2a 0a 2a 2a 20 41  t */.};../*.** A
0840: 63 63 65 73 73 20 72 6f 75 74 69 6e 65 73 2e 20  ccess routines. 
0850: 20 54 6f 20 64 65 6c 65 74 65 2c 20 69 6e 73 65   To delete, inse
0860: 72 74 20 61 20 4e 55 4c 4c 20 70 6f 69 6e 74 65  rt a NULL pointe
0870: 72 2e 0a 2a 2f 0a 76 6f 69 64 20 73 71 6c 69 74  r..*/.void sqlit
0880: 65 33 48 61 73 68 49 6e 69 74 28 48 61 73 68 2a  e3HashInit(Hash*
0890: 2c 20 69 6e 74 20 63 6f 70 79 4b 65 79 29 3b 0a  , int copyKey);.
08a0: 76 6f 69 64 20 2a 73 71 6c 69 74 65 33 48 61 73  void *sqlite3Has
08b0: 68 49 6e 73 65 72 74 28 48 61 73 68 2a 2c 20 63  hInsert(Hash*, c
08c0: 6f 6e 73 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c  onst void *pKey,
08d0: 20 69 6e 74 20 6e 4b 65 79 2c 20 76 6f 69 64 20   int nKey, void 
08e0: 2a 70 44 61 74 61 29 3b 0a 76 6f 69 64 20 2a 73  *pData);.void *s
08f0: 71 6c 69 74 65 33 48 61 73 68 46 69 6e 64 28 63  qlite3HashFind(c
0900: 6f 6e 73 74 20 48 61 73 68 2a 2c 20 63 6f 6e 73  onst Hash*, cons
0910: 74 20 76 6f 69 64 20 2a 70 4b 65 79 2c 20 69 6e  t void *pKey, in
0920: 74 20 6e 4b 65 79 29 3b 0a 48 61 73 68 45 6c 65  t nKey);.HashEle
0930: 6d 20 2a 73 71 6c 69 74 65 33 48 61 73 68 46 69  m *sqlite3HashFi
0940: 6e 64 45 6c 65 6d 28 63 6f 6e 73 74 20 48 61 73  ndElem(const Has
0950: 68 2a 2c 20 63 6f 6e 73 74 20 76 6f 69 64 20 2a  h*, const void *
0960: 70 4b 65 79 2c 20 69 6e 74 20 6e 4b 65 79 29 3b  pKey, int nKey);
0970: 0a 76 6f 69 64 20 73 71 6c 69 74 65 33 48 61 73  .void sqlite3Has
0980: 68 43 6c 65 61 72 28 48 61 73 68 2a 29 3b 0a 0a  hClear(Hash*);..
0990: 2f 2a 0a 2a 2a 20 4d 61 63 72 6f 73 20 66 6f 72  /*.** Macros for
09a0: 20 6c 6f 6f 70 69 6e 67 20 6f 76 65 72 20 61 6c   looping over al
09b0: 6c 20 65 6c 65 6d 65 6e 74 73 20 6f 66 20 61 20  l elements of a 
09c0: 68 61 73 68 20 74 61 62 6c 65 2e 20 20 54 68 65  hash table.  The
09d0: 20 69 64 69 6f 6d 20 69 73 0a 2a 2a 20 6c 69 6b   idiom is.** lik
09e0: 65 20 74 68 69 73 3a 0a 2a 2a 0a 2a 2a 20 20 20  e this:.**.**   
09f0: 48 61 73 68 20 68 3b 0a 2a 2a 20 20 20 48 61 73  Hash h;.**   Has
0a00: 68 45 6c 65 6d 20 2a 70 3b 0a 2a 2a 20 20 20 2e  hElem *p;.**   .
0a10: 2e 2e 0a 2a 2a 20 20 20 66 6f 72 28 70 3d 73 71  ...**   for(p=sq
0a20: 6c 69 74 65 48 61 73 68 46 69 72 73 74 28 26 68  liteHashFirst(&h
0a30: 29 3b 20 70 3b 20 70 3d 73 71 6c 69 74 65 48 61  ); p; p=sqliteHa
0a40: 73 68 4e 65 78 74 28 70 29 29 7b 0a 2a 2a 20 20  shNext(p)){.**  
0a50: 20 20 20 53 6f 6d 65 53 74 72 75 63 74 75 72 65     SomeStructure
0a60: 20 2a 70 44 61 74 61 20 3d 20 73 71 6c 69 74 65   *pData = sqlite
0a70: 48 61 73 68 44 61 74 61 28 70 29 3b 0a 2a 2a 20  HashData(p);.** 
0a80: 20 20 20 20 2f 2f 20 64 6f 20 73 6f 6d 65 74 68      // do someth
0a90: 69 6e 67 20 77 69 74 68 20 70 44 61 74 61 0a 2a  ing with pData.*
0aa0: 2a 20 20 20 7d 0a 2a 2f 0a 23 64 65 66 69 6e 65  *   }.*/.#define
0ab0: 20 73 71 6c 69 74 65 48 61 73 68 46 69 72 73 74   sqliteHashFirst
0ac0: 28 48 29 20 20 28 28 48 29 2d 3e 66 69 72 73 74  (H)  ((H)->first
0ad0: 29 0a 23 64 65 66 69 6e 65 20 73 71 6c 69 74 65  ).#define sqlite
0ae0: 48 61 73 68 4e 65 78 74 28 45 29 20 20 20 28 28  HashNext(E)   ((
0af0: 45 29 2d 3e 6e 65 78 74 29 0a 23 64 65 66 69 6e  E)->next).#defin
0b00: 65 20 73 71 6c 69 74 65 48 61 73 68 44 61 74 61  e sqliteHashData
0b10: 28 45 29 20 20 20 28 28 45 29 2d 3e 64 61 74 61  (E)   ((E)->data
0b20: 29 0a 23 64 65 66 69 6e 65 20 73 71 6c 69 74 65  ).#define sqlite
0b30: 48 61 73 68 4b 65 79 28 45 29 20 20 20 20 28 28  HashKey(E)    ((
0b40: 45 29 2d 3e 70 4b 65 79 29 0a 23 64 65 66 69 6e  E)->pKey).#defin
0b50: 65 20 73 71 6c 69 74 65 48 61 73 68 4b 65 79 73  e sqliteHashKeys
0b60: 69 7a 65 28 45 29 20 28 28 45 29 2d 3e 6e 4b 65  ize(E) ((E)->nKe
0b70: 79 29 0a 0a 2f 2a 0a 2a 2a 20 4e 75 6d 62 65 72  y)../*.** Number
0b80: 20 6f 66 20 65 6e 74 72 69 65 73 20 69 6e 20 61   of entries in a
0b90: 20 68 61 73 68 20 74 61 62 6c 65 0a 2a 2f 0a 23   hash table.*/.#
0ba0: 64 65 66 69 6e 65 20 73 71 6c 69 74 65 48 61 73  define sqliteHas
0bb0: 68 43 6f 75 6e 74 28 48 29 20 20 28 28 48 29 2d  hCount(H)  ((H)-
0bc0: 3e 63 6f 75 6e 74 29 0a 0a 23 65 6e 64 69 66 20  >count)..#endif 
0bd0: 2f 2a 20 5f 53 51 4c 49 54 45 5f 48 41 53 48 5f  /* _SQLITE_HASH_
0be0: 48 5f 20 2a 2f 0a                                H_ */.