webengine/webkitutils/SqliteSymbian/hash.c
author andy simpson <andrews@symbian.org>
Mon, 14 Dec 2009 16:23:31 +0000
branchRCL_1
changeset 20 5c0a4bf7051b
parent 0 dd21522fd290
permissions -rw-r--r--
Added tag PDK_2.0.2 for changeset e9f2e9160591
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
0
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
     1
/*
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
     2
** 2001 September 22
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
     3
**
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
     4
** The author disclaims copyright to this source code.  In place of
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
     5
** a legal notice, here is a blessing:
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
     6
**
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
     7
**    May you do good and not evil.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
     8
**    May you find forgiveness for yourself and forgive others.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
     9
**    May you share freely, never taking more than you give.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    10
**
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    11
*************************************************************************
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    12
** This is the implementation of generic hash-tables
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    13
** used in SQLite.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    14
**
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    15
** $Id: hash.c,v 1.18 2006/02/14 10:48:39 danielk1977 Exp $
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    16
*/
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    17
#include "sqliteInt.h"
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    18
#include <assert.h>
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    19
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    20
/* Turn bulk memory into a hash table object by initializing the
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    21
** fields of the Hash structure.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    22
**
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    23
** "pNew" is a pointer to the hash table that is to be initialized.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    24
** keyClass is one of the constants SQLITE_HASH_INT, SQLITE_HASH_POINTER,
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    25
** SQLITE_HASH_BINARY, or SQLITE_HASH_STRING.  The value of keyClass 
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    26
** determines what kind of key the hash table will use.  "copyKey" is
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    27
** true if the hash table should make its own private copy of keys and
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    28
** false if it should just use the supplied pointer.  CopyKey only makes
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    29
** sense for SQLITE_HASH_STRING and SQLITE_HASH_BINARY and is ignored
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    30
** for other key classes.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    31
*/
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    32
void sqlite3HashInit(Hash *pNew, int keyClass, int copyKey){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    33
  assert( pNew!=0 );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    34
  assert( keyClass>=SQLITE_HASH_STRING && keyClass<=SQLITE_HASH_BINARY );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    35
  pNew->keyClass = keyClass;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    36
#if 0
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    37
  if( keyClass==SQLITE_HASH_POINTER || keyClass==SQLITE_HASH_INT ) copyKey = 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    38
#endif
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    39
  pNew->copyKey = copyKey;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    40
  pNew->first = 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    41
  pNew->count = 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    42
  pNew->htsize = 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    43
  pNew->ht = 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    44
  pNew->xMalloc = sqlite3MallocX;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    45
  pNew->xFree = sqlite3FreeX;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    46
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    47
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    48
/* Remove all entries from a hash table.  Reclaim all memory.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    49
** Call this routine to delete a hash table or to reset a hash table
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    50
** to the empty state.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    51
*/
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    52
void sqlite3HashClear(Hash *pH){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    53
  HashElem *elem;         /* For looping over all elements of the table */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    54
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    55
  assert( pH!=0 );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    56
  elem = pH->first;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    57
  pH->first = 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    58
  if( pH->ht ) pH->xFree(pH->ht);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    59
  pH->ht = 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    60
  pH->htsize = 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    61
  while( elem ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    62
    HashElem *next_elem = elem->next;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    63
    if( pH->copyKey && elem->pKey ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    64
      pH->xFree(elem->pKey);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    65
    }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    66
    pH->xFree(elem);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    67
    elem = next_elem;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    68
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    69
  pH->count = 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    70
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    71
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    72
#if 0 /* NOT USED */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    73
/*
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    74
** Hash and comparison functions when the mode is SQLITE_HASH_INT
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    75
*/
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    76
static int intHash(const void *pKey, int nKey){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    77
  return nKey ^ (nKey<<8) ^ (nKey>>8);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    78
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    79
static int intCompare(const void *pKey1, int n1, const void *pKey2, int n2){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    80
  return n2 - n1;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    81
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    82
#endif
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    83
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    84
#if 0 /* NOT USED */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    85
/*
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    86
** Hash and comparison functions when the mode is SQLITE_HASH_POINTER
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    87
*/
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    88
static int ptrHash(const void *pKey, int nKey){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    89
  uptr x = Addr(pKey);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    90
  return x ^ (x<<8) ^ (x>>8);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    91
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    92
static int ptrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    93
  if( pKey1==pKey2 ) return 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    94
  if( pKey1<pKey2 ) return -1;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    95
  return 1;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    96
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    97
#endif
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    98
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
    99
/*
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   100
** Hash and comparison functions when the mode is SQLITE_HASH_STRING
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   101
*/
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   102
static int strHash(const void *pKey, int nKey){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   103
  const char *z = (const char *)pKey;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   104
  int h = 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   105
  if( nKey<=0 ) nKey = strlen(z);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   106
  while( nKey > 0  ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   107
    h = (h<<3) ^ h ^ sqlite3UpperToLower[(unsigned char)*z++];
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   108
    nKey--;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   109
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   110
  return h & 0x7fffffff;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   111
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   112
static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   113
  if( n1!=n2 ) return 1;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   114
  return sqlite3StrNICmp((const char*)pKey1,(const char*)pKey2,n1);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   115
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   116
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   117
/*
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   118
** Hash and comparison functions when the mode is SQLITE_HASH_BINARY
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   119
*/
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   120
static int binHash(const void *pKey, int nKey){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   121
  int h = 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   122
  const char *z = (const char *)pKey;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   123
  while( nKey-- > 0 ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   124
    h = (h<<3) ^ h ^ *(z++);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   125
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   126
  return h & 0x7fffffff;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   127
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   128
static int binCompare(const void *pKey1, int n1, const void *pKey2, int n2){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   129
  if( n1!=n2 ) return 1;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   130
  return memcmp(pKey1,pKey2,n1);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   131
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   132
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   133
/*
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   134
** Return a pointer to the appropriate hash function given the key class.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   135
**
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   136
** The C syntax in this function definition may be unfamilar to some 
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   137
** programmers, so we provide the following additional explanation:
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   138
**
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   139
** The name of the function is "hashFunction".  The function takes a
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   140
** single parameter "keyClass".  The return value of hashFunction()
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   141
** is a pointer to another function.  Specifically, the return value
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   142
** of hashFunction() is a pointer to a function that takes two parameters
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   143
** with types "const void*" and "int" and returns an "int".
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   144
*/
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   145
static int (*hashFunction(int keyClass))(const void*,int){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   146
#if 0  /* HASH_INT and HASH_POINTER are never used */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   147
  switch( keyClass ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   148
    case SQLITE_HASH_INT:     return &intHash;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   149
    case SQLITE_HASH_POINTER: return &ptrHash;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   150
    case SQLITE_HASH_STRING:  return &strHash;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   151
    case SQLITE_HASH_BINARY:  return &binHash;;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   152
    default: break;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   153
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   154
  return 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   155
#else
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   156
  if( keyClass==SQLITE_HASH_STRING ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   157
    return &strHash;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   158
  }else{
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   159
    assert( keyClass==SQLITE_HASH_BINARY );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   160
    return &binHash;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   161
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   162
#endif
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   163
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   164
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   165
/*
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   166
** Return a pointer to the appropriate hash function given the key class.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   167
**
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   168
** For help in interpreted the obscure C code in the function definition,
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   169
** see the header comment on the previous function.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   170
*/
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   171
static int (*compareFunction(int keyClass))(const void*,int,const void*,int){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   172
#if 0 /* HASH_INT and HASH_POINTER are never used */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   173
  switch( keyClass ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   174
    case SQLITE_HASH_INT:     return &intCompare;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   175
    case SQLITE_HASH_POINTER: return &ptrCompare;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   176
    case SQLITE_HASH_STRING:  return &strCompare;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   177
    case SQLITE_HASH_BINARY:  return &binCompare;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   178
    default: break;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   179
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   180
  return 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   181
#else
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   182
  if( keyClass==SQLITE_HASH_STRING ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   183
    return &strCompare;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   184
  }else{
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   185
    assert( keyClass==SQLITE_HASH_BINARY );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   186
    return &binCompare;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   187
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   188
#endif
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   189
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   190
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   191
/* Link an element into the hash table
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   192
*/
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   193
static void insertElement(
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   194
  Hash *pH,              /* The complete hash table */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   195
  struct _ht *pEntry,    /* The entry into which pNew is inserted */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   196
  HashElem *pNew         /* The element to be inserted */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   197
){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   198
  HashElem *pHead;       /* First element already in pEntry */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   199
  pHead = pEntry->chain;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   200
  if( pHead ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   201
    pNew->next = pHead;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   202
    pNew->prev = pHead->prev;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   203
    if( pHead->prev ){ pHead->prev->next = pNew; }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   204
    else             { pH->first = pNew; }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   205
    pHead->prev = pNew;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   206
  }else{
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   207
    pNew->next = pH->first;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   208
    if( pH->first ){ pH->first->prev = pNew; }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   209
    pNew->prev = 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   210
    pH->first = pNew;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   211
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   212
  pEntry->count++;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   213
  pEntry->chain = pNew;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   214
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   215
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   216
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   217
/* Resize the hash table so that it cantains "new_size" buckets.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   218
** "new_size" must be a power of 2.  The hash table might fail 
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   219
** to resize if sqliteMalloc() fails.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   220
*/
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   221
static void rehash(Hash *pH, int new_size){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   222
  struct _ht *new_ht;            /* The new hash table */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   223
  HashElem *elem, *next_elem;    /* For looping over existing elements */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   224
  int (*xHash)(const void*,int); /* The hash function */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   225
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   226
  assert( (new_size & (new_size-1))==0 );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   227
  new_ht = (struct _ht *)pH->xMalloc( new_size*sizeof(struct _ht) );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   228
  if( new_ht==0 ) return;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   229
  if( pH->ht ) pH->xFree(pH->ht);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   230
  pH->ht = new_ht;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   231
  pH->htsize = new_size;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   232
  xHash = hashFunction(pH->keyClass);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   233
  for(elem=pH->first, pH->first=0; elem; elem = next_elem){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   234
    int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   235
    next_elem = elem->next;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   236
    insertElement(pH, &new_ht[h], elem);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   237
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   238
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   239
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   240
/* This function (for internal use only) locates an element in an
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   241
** hash table that matches the given key.  The hash for this key has
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   242
** already been computed and is passed as the 4th parameter.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   243
*/
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   244
static HashElem *findElementGivenHash(
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   245
  const Hash *pH,     /* The pH to be searched */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   246
  const void *pKey,   /* The key we are searching for */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   247
  int nKey,
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   248
  int h               /* The hash for this key. */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   249
){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   250
  HashElem *elem;                /* Used to loop thru the element list */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   251
  int count;                     /* Number of elements left to test */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   252
  int (*xCompare)(const void*,int,const void*,int);  /* comparison function */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   253
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   254
  if( pH->ht ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   255
    struct _ht *pEntry = &pH->ht[h];
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   256
    elem = pEntry->chain;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   257
    count = pEntry->count;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   258
    xCompare = compareFunction(pH->keyClass);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   259
    while( count-- && elem ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   260
      if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){ 
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   261
        return elem;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   262
      }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   263
      elem = elem->next;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   264
    }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   265
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   266
  return 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   267
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   268
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   269
/* Remove a single entry from the hash table given a pointer to that
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   270
** element and a hash on the element's key.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   271
*/
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   272
static void removeElementGivenHash(
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   273
  Hash *pH,         /* The pH containing "elem" */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   274
  HashElem* elem,   /* The element to be removed from the pH */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   275
  int h             /* Hash value for the element */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   276
){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   277
  struct _ht *pEntry;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   278
  if( elem->prev ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   279
    elem->prev->next = elem->next; 
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   280
  }else{
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   281
    pH->first = elem->next;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   282
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   283
  if( elem->next ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   284
    elem->next->prev = elem->prev;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   285
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   286
  pEntry = &pH->ht[h];
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   287
  if( pEntry->chain==elem ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   288
    pEntry->chain = elem->next;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   289
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   290
  pEntry->count--;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   291
  if( pEntry->count<=0 ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   292
    pEntry->chain = 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   293
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   294
  if( pH->copyKey && elem->pKey ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   295
    pH->xFree(elem->pKey);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   296
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   297
  pH->xFree( elem );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   298
  pH->count--;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   299
  if( pH->count<=0 ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   300
    assert( pH->first==0 );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   301
    assert( pH->count==0 );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   302
    sqlite3HashClear(pH);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   303
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   304
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   305
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   306
/* Attempt to locate an element of the hash table pH with a key
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   307
** that matches pKey,nKey.  Return the data for this element if it is
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   308
** found, or NULL if there is no match.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   309
*/
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   310
void *sqlite3HashFind(const Hash *pH, const void *pKey, int nKey){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   311
  int h;             /* A hash on key */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   312
  HashElem *elem;    /* The element that matches key */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   313
  int (*xHash)(const void*,int);  /* The hash function */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   314
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   315
  if( pH==0 || pH->ht==0 ) return 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   316
  xHash = hashFunction(pH->keyClass);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   317
  assert( xHash!=0 );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   318
  h = (*xHash)(pKey,nKey);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   319
  assert( (pH->htsize & (pH->htsize-1))==0 );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   320
  elem = findElementGivenHash(pH,pKey,nKey, h & (pH->htsize-1));
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   321
  return elem ? elem->data : 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   322
}
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   323
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   324
/* Insert an element into the hash table pH.  The key is pKey,nKey
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   325
** and the data is "data".
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   326
**
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   327
** If no element exists with a matching key, then a new
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   328
** element is created.  A copy of the key is made if the copyKey
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   329
** flag is set.  NULL is returned.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   330
**
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   331
** If another element already exists with the same key, then the
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   332
** new data replaces the old data and the old data is returned.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   333
** The key is not copied in this instance.  If a malloc fails, then
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   334
** the new data is returned and the hash table is unchanged.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   335
**
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   336
** If the "data" parameter to this function is NULL, then the
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   337
** element corresponding to "key" is removed from the hash table.
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   338
*/
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   339
void *sqlite3HashInsert(Hash *pH, const void *pKey, int nKey, void *data){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   340
  int hraw;             /* Raw hash value of the key */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   341
  int h;                /* the hash of the key modulo hash table size */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   342
  HashElem *elem;       /* Used to loop thru the element list */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   343
  HashElem *new_elem;   /* New element added to the pH */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   344
  int (*xHash)(const void*,int);  /* The hash function */
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   345
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   346
  assert( pH!=0 );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   347
  xHash = hashFunction(pH->keyClass);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   348
  assert( xHash!=0 );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   349
  hraw = (*xHash)(pKey, nKey);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   350
  assert( (pH->htsize & (pH->htsize-1))==0 );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   351
  h = hraw & (pH->htsize-1);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   352
  elem = findElementGivenHash(pH,pKey,nKey,h);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   353
  if( elem ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   354
    void *old_data = elem->data;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   355
    if( data==0 ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   356
      removeElementGivenHash(pH,elem,h);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   357
    }else{
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   358
      elem->data = data;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   359
    }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   360
    return old_data;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   361
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   362
  if( data==0 ) return 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   363
  new_elem = (HashElem*)pH->xMalloc( sizeof(HashElem) );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   364
  if( new_elem==0 ) return data;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   365
  if( pH->copyKey && pKey!=0 ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   366
    new_elem->pKey = pH->xMalloc( nKey );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   367
    if( new_elem->pKey==0 ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   368
      pH->xFree(new_elem);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   369
      return data;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   370
    }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   371
    memcpy((void*)new_elem->pKey, pKey, nKey);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   372
  }else{
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   373
    new_elem->pKey = (void*)pKey;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   374
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   375
  new_elem->nKey = nKey;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   376
  pH->count++;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   377
  if( pH->htsize==0 ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   378
    rehash(pH,8);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   379
    if( pH->htsize==0 ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   380
      pH->count = 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   381
      pH->xFree(new_elem);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   382
      return data;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   383
    }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   384
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   385
  if( pH->count > pH->htsize ){
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   386
    rehash(pH,pH->htsize*2);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   387
  }
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   388
  assert( pH->htsize>0 );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   389
  assert( (pH->htsize & (pH->htsize-1))==0 );
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   390
  h = hraw & (pH->htsize-1);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   391
  insertElement(pH, &pH->ht[h], new_elem);
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   392
  new_elem->data = data;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   393
  return 0;
dd21522fd290 Revision: 200911
Kiiskinen Klaus (Nokia-D-MSW/Tampere) <klaus.kiiskinen@nokia.com>
parents:
diff changeset
   394
}