Back to index

lightning-sunbird  0.9+nobinonly
Functions | Variables
hash.c File Reference
#include "sqliteInt.h"
#include <assert.h>

Go to the source code of this file.

Functions

void sqlite3HashInit (Hash *pNew, int keyClass, int copyKey)
void sqlite3HashClear (Hash *pH)
static int strHash (const void *pKey, int nKey)
static int strCompare (const void *pKey1, int n1, const void *pKey2, int n2)
static int binHash (const void *pKey, int nKey)
static int binCompare (const void *pKey1, int n1, const void *pKey2, int n2)
static void insertElement (Hash *pH, struct _ht *pEntry, HashElem *pNew)
static void rehash (Hash *pH, int new_size)
static HashElemfindElementGivenHash (const Hash *pH, const void *pKey, int nKey, int h)
static void removeElementGivenHash (Hash *pH, HashElem *elem, int h)
voidsqlite3HashFind (const Hash *pH, const void *pKey, int nKey)
voidsqlite3HashInsert (Hash *pH, const void *pKey, int nKey, void *data)

Variables

static int(*)(const void *, inthashFunction (int keyClass)
static int(*)(const void
*, int, const void *, int
compareFunction (int keyClass)

Function Documentation

static int binCompare ( const void pKey1,
int  n1,
const void pKey2,
int  n2 
) [static]

Definition at line 128 of file hash.c.

                                                                           {
  if( n1!=n2 ) return 1;
  return memcmp(pKey1,pKey2,n1);
}

Here is the call graph for this function:

static int binHash ( const void pKey,
int  nKey 
) [static]

Definition at line 120 of file hash.c.

                                              {
  int h = 0;
  const char *z = (const char *)pKey;
  while( nKey-- > 0 ){
    h = (h<<3) ^ h ^ *(z++);
  }
  return h & 0x7fffffff;
}
static HashElem* findElementGivenHash ( const Hash pH,
const void pKey,
int  nKey,
int  h 
) [static]

Definition at line 244 of file hash.c.

 {
  HashElem *elem;                /* Used to loop thru the element list */
  int count;                     /* Number of elements left to test */
  int (*xCompare)(const void*,int,const void*,int);  /* comparison function */

  if( pH->ht ){
    struct _ht *pEntry = &pH->ht[h];
    elem = pEntry->chain;
    count = pEntry->count;
    xCompare = compareFunction(pH->keyClass);
    while( count-- && elem ){
      if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){ 
        return elem;
      }
      elem = elem->next;
    }
  }
  return 0;
}

Here is the caller graph for this function:

static void insertElement ( Hash pH,
struct _ht *  pEntry,
HashElem pNew 
) [static]

Definition at line 193 of file hash.c.

 {
  HashElem *pHead;       /* First element already in pEntry */
  pHead = pEntry->chain;
  if( pHead ){
    pNew->next = pHead;
    pNew->prev = pHead->prev;
    if( pHead->prev ){ pHead->prev->next = pNew; }
    else             { pH->first = pNew; }
    pHead->prev = pNew;
  }else{
    pNew->next = pH->first;
    if( pH->first ){ pH->first->prev = pNew; }
    pNew->prev = 0;
    pH->first = pNew;
  }
  pEntry->count++;
  pEntry->chain = pNew;
}

Here is the caller graph for this function:

static void rehash ( Hash pH,
int  new_size 
) [static]

Definition at line 221 of file hash.c.

                                          {
  struct _ht *new_ht;            /* The new hash table */
  HashElem *elem, *next_elem;    /* For looping over existing elements */
  int (*xHash)(const void*,int); /* The hash function */

  assert( (new_size & (new_size-1))==0 );
  new_ht = (struct _ht *)pH->xMalloc( new_size*sizeof(struct _ht) );
  if( new_ht==0 ) return;
  if( pH->ht ) pH->xFree(pH->ht);
  pH->ht = new_ht;
  pH->htsize = new_size;
  xHash = hashFunction(pH->keyClass);
  for(elem=pH->first, pH->first=0; elem; elem = next_elem){
    int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
    next_elem = elem->next;
    insertElement(pH, &new_ht[h], elem);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void removeElementGivenHash ( Hash pH,
HashElem elem,
int  h 
) [static]

Definition at line 272 of file hash.c.

 {
  struct _ht *pEntry;
  if( elem->prev ){
    elem->prev->next = elem->next; 
  }else{
    pH->first = elem->next;
  }
  if( elem->next ){
    elem->next->prev = elem->prev;
  }
  pEntry = &pH->ht[h];
  if( pEntry->chain==elem ){
    pEntry->chain = elem->next;
  }
  pEntry->count--;
  if( pEntry->count<=0 ){
    pEntry->chain = 0;
  }
  if( pH->copyKey && elem->pKey ){
    pH->xFree(elem->pKey);
  }
  pH->xFree( elem );
  pH->count--;
  if( pH->count<=0 ){
    assert( pH->first==0 );
    assert( pH->count==0 );
    sqlite3HashClear(pH);
  }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 52 of file hash.c.

                               {
  HashElem *elem;         /* For looping over all elements of the table */

  assert( pH!=0 );
  elem = pH->first;
  pH->first = 0;
  if( pH->ht ) pH->xFree(pH->ht);
  pH->ht = 0;
  pH->htsize = 0;
  while( elem ){
    HashElem *next_elem = elem->next;
    if( pH->copyKey && elem->pKey ){
      pH->xFree(elem->pKey);
    }
    pH->xFree(elem);
    elem = next_elem;
  }
  pH->count = 0;
}

Here is the caller graph for this function:

void* sqlite3HashFind ( const Hash pH,
const void pKey,
int  nKey 
)

Definition at line 310 of file hash.c.

                                                                 {
  int h;             /* A hash on key */
  HashElem *elem;    /* The element that matches key */
  int (*xHash)(const void*,int);  /* The hash function */

  if( pH==0 || pH->ht==0 ) return 0;
  xHash = hashFunction(pH->keyClass);
  assert( xHash!=0 );
  h = (*xHash)(pKey,nKey);
  assert( (pH->htsize & (pH->htsize-1))==0 );
  elem = findElementGivenHash(pH,pKey,nKey, h & (pH->htsize-1));
  return elem ? elem->data : 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void sqlite3HashInit ( Hash pNew,
int  keyClass,
int  copyKey 
)

Definition at line 32 of file hash.c.

                                                           {
  assert( pNew!=0 );
  assert( keyClass>=SQLITE_HASH_STRING && keyClass<=SQLITE_HASH_BINARY );
  pNew->keyClass = keyClass;
#if 0
  if( keyClass==SQLITE_HASH_POINTER || keyClass==SQLITE_HASH_INT ) copyKey = 0;
#endif
  pNew->copyKey = copyKey;
  pNew->first = 0;
  pNew->count = 0;
  pNew->htsize = 0;
  pNew->ht = 0;
  pNew->xMalloc = sqlite3MallocX;
  pNew->xFree = sqlite3FreeX;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void* sqlite3HashInsert ( Hash pH,
const void pKey,
int  nKey,
void data 
)

Definition at line 339 of file hash.c.

                                                                         {
  int hraw;             /* Raw hash value of the key */
  int h;                /* the hash of the key modulo hash table size */
  HashElem *elem;       /* Used to loop thru the element list */
  HashElem *new_elem;   /* New element added to the pH */
  int (*xHash)(const void*,int);  /* The hash function */

  assert( pH!=0 );
  xHash = hashFunction(pH->keyClass);
  assert( xHash!=0 );
  hraw = (*xHash)(pKey, nKey);
  assert( (pH->htsize & (pH->htsize-1))==0 );
  h = hraw & (pH->htsize-1);
  elem = findElementGivenHash(pH,pKey,nKey,h);
  if( elem ){
    void *old_data = elem->data;
    if( data==0 ){
      removeElementGivenHash(pH,elem,h);
    }else{
      elem->data = data;
    }
    return old_data;
  }
  if( data==0 ) return 0;
  new_elem = (HashElem*)pH->xMalloc( sizeof(HashElem) );
  if( new_elem==0 ) return data;
  if( pH->copyKey && pKey!=0 ){
    new_elem->pKey = pH->xMalloc( nKey );
    if( new_elem->pKey==0 ){
      pH->xFree(new_elem);
      return data;
    }
    memcpy((void*)new_elem->pKey, pKey, nKey);
  }else{
    new_elem->pKey = (void*)pKey;
  }
  new_elem->nKey = nKey;
  pH->count++;
  if( pH->htsize==0 ){
    rehash(pH,8);
    if( pH->htsize==0 ){
      pH->count = 0;
      pH->xFree(new_elem);
      return data;
    }
  }
  if( pH->count > pH->htsize ){
    rehash(pH,pH->htsize*2);
  }
  assert( pH->htsize>0 );
  assert( (pH->htsize & (pH->htsize-1))==0 );
  h = hraw & (pH->htsize-1);
  insertElement(pH, &pH->ht[h], new_elem);
  new_elem->data = data;
  return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

static int strCompare ( const void pKey1,
int  n1,
const void pKey2,
int  n2 
) [static]

Definition at line 112 of file hash.c.

                                                                           {
  if( n1!=n2 ) return 1;
  return sqlite3StrNICmp((const char*)pKey1,(const char*)pKey2,n1);
}

Here is the call graph for this function:

static int strHash ( const void pKey,
int  nKey 
) [static]

Definition at line 102 of file hash.c.

                                              {
  const char *z = (const char *)pKey;
  int h = 0;
  if( nKey<=0 ) nKey = strlen(z);
  while( nKey > 0  ){
    h = (h<<3) ^ h ^ sqlite3UpperToLower[(unsigned char)*z++];
    nKey--;
  }
  return h & 0x7fffffff;
}

Variable Documentation

int(*)(const void*, int, const void*, int) compareFunction(int keyClass) [static]

Definition at line 171 of file hash.c.

                                                                            {
#if 0 /* HASH_INT and HASH_POINTER are never used */
  switch( keyClass ){
    case SQLITE_HASH_INT:     return &intCompare;
    case SQLITE_HASH_POINTER: return &ptrCompare;
    case SQLITE_HASH_STRING:  return &strCompare;
    case SQLITE_HASH_BINARY:  return &binCompare;
    default: break;
  }
  return 0;
#else
  if( keyClass==SQLITE_HASH_STRING ){
    return &strCompare;
  }else{
    assert( keyClass==SQLITE_HASH_BINARY );
    return &binCompare;
  }
#endif
}
int(*)(const void*, int) hashFunction(int keyClass) [static]

Definition at line 145 of file hash.c.

                                                         {
#if 0  /* HASH_INT and HASH_POINTER are never used */
  switch( keyClass ){
    case SQLITE_HASH_INT:     return &intHash;
    case SQLITE_HASH_POINTER: return &ptrHash;
    case SQLITE_HASH_STRING:  return &strHash;
    case SQLITE_HASH_BINARY:  return &binHash;;
    default: break;
  }
  return 0;
#else
  if( keyClass==SQLITE_HASH_STRING ){
    return &strHash;
  }else{
    assert( keyClass==SQLITE_HASH_BINARY );
    return &binHash;
  }
#endif
}