engine/sqlite/src/hash.h
author Sebastian Brannstrom <sebastianb@symbian.org>
Fri, 09 Jul 2010 23:58:47 +0100
branch3rded
changeset 175 cd124c4eb6b9
parent 2 29cda98b007e
permissions -rw-r--r--
Started port to 3rd edition
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
2
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
     1
/*
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
     2
** 2001 September 22
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
     3
**
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
     4
** The author disclaims copyright to this source code.  In place of
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
     5
** a legal notice, here is a blessing:
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
     6
**
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
     7
**    May you do good and not evil.
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
     8
**    May you find forgiveness for yourself and forgive others.
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
     9
**    May you share freely, never taking more than you give.
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    10
**
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    11
*************************************************************************
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    12
** This is the header file for the generic hash-table implemenation
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    13
** used in SQLite.
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    14
**
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    15
** $Id: hash.h 1282 2008-11-13 09:31:33Z LarsPson $
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    16
*/
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    17
#ifndef _SQLITE_HASH_H_
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    18
#define _SQLITE_HASH_H_
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    19
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    20
/* Forward declarations of structures. */
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    21
typedef struct Hash Hash;
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    22
typedef struct HashElem HashElem;
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    23
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    24
/* A complete hash table is an instance of the following structure.
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    25
** The internals of this structure are intended to be opaque -- client
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    26
** code should not attempt to access or modify the fields of this structure
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    27
** directly.  Change this structure only by using the routines below.
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    28
** However, many of the "procedures" and "functions" for modifying and
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    29
** accessing this structure are really macros, so we can't really make
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    30
** this structure opaque.
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    31
*/
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    32
struct Hash {
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    33
  char keyClass;          /* SQLITE_HASH_INT, _POINTER, _STRING, _BINARY */
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    34
  char copyKey;           /* True if copy of key made on insert */
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    35
  int count;              /* Number of entries in this table */
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    36
  int htsize;             /* Number of buckets in the hash table */
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    37
  HashElem *first;        /* The first element of the array */
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    38
  struct _ht {            /* the hash table */
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    39
    int count;               /* Number of entries with this hash */
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    40
    HashElem *chain;         /* Pointer to first entry with this hash */
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    41
  } *ht;
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    42
};
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    43
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    44
/* Each element in the hash table is an instance of the following 
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    45
** structure.  All elements are stored on a single doubly-linked list.
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    46
**
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    47
** Again, this structure is intended to be opaque, but it can't really
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    48
** be opaque because it is used by macros.
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    49
*/
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    50
struct HashElem {
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    51
  HashElem *next, *prev;   /* Next and previous elements in the table */
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    52
  void *data;              /* Data associated with this element */
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    53
  void *pKey; int nKey;    /* Key associated with this element */
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    54
};
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    55
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    56
/*
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    57
** There are 4 different modes of operation for a hash table:
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    58
**
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    59
**   SQLITE_HASH_INT         nKey is used as the key and pKey is ignored.
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    60
**
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    61
**   SQLITE_HASH_POINTER     pKey is used as the key and nKey is ignored.
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    62
**
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    63
**   SQLITE_HASH_STRING      pKey points to a string that is nKey bytes long
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    64
**                           (including the null-terminator, if any).  Case
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    65
**                           is ignored in comparisons.
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    66
**
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    67
**   SQLITE_HASH_BINARY      pKey points to binary data nKey bytes long. 
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    68
**                           memcmp() is used to compare keys.
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    69
**
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    70
** A copy of the key is made for SQLITE_HASH_STRING and SQLITE_HASH_BINARY
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    71
** if the copyKey parameter to HashInit is 1.  
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    72
*/
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    73
/* #define SQLITE_HASH_INT       1 // NOT USED */
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    74
/* #define SQLITE_HASH_POINTER   2 // NOT USED */
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    75
#define SQLITE_HASH_STRING    3
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    76
#define SQLITE_HASH_BINARY    4
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    77
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    78
/*
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    79
** Access routines.  To delete, insert a NULL pointer.
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    80
*/
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    81
void sqlite3HashInit(Hash*, int keytype, int copyKey);
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    82
void *sqlite3HashInsert(Hash*, const void *pKey, int nKey, void *pData);
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    83
void *sqlite3HashFind(const Hash*, const void *pKey, int nKey);
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    84
HashElem *sqlite3HashFindElem(const Hash*, const void *pKey, int nKey);
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    85
void sqlite3HashClear(Hash*);
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    86
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    87
/*
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    88
** Macros for looping over all elements of a hash table.  The idiom is
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    89
** like this:
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    90
**
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    91
**   Hash h;
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    92
**   HashElem *p;
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    93
**   ...
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    94
**   for(p=sqliteHashFirst(&h); p; p=sqliteHashNext(p)){
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    95
**     SomeStructure *pData = sqliteHashData(p);
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    96
**     // do something with pData
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    97
**   }
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    98
*/
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
    99
#define sqliteHashFirst(H)  ((H)->first)
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
   100
#define sqliteHashNext(E)   ((E)->next)
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
   101
#define sqliteHashData(E)   ((E)->data)
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
   102
#define sqliteHashKey(E)    ((E)->pKey)
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
   103
#define sqliteHashKeysize(E) ((E)->nKey)
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
   104
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
   105
/*
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
   106
** Number of entries in a hash table
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
   107
*/
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
   108
#define sqliteHashCount(H)  ((H)->count)
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
   109
29cda98b007e Initial import of Podcatcher from the Bergamot project
skip
parents:
diff changeset
   110
#endif /* _SQLITE_HASH_H_ */