Back to index

php5  5.3.10
Functions | Variables
hash.c File Reference
#include "sqliteInt.h"
#include <assert.h>

Go to the source code of this file.

Functions

void sqliteHashInit (Hash *new, int keyClass, int copyKey)
void sqliteHashClear (Hash *pH)
static int intHash (const void *pKey, int nKey)
static int intCompare (const void *pKey1, int n1, const void *pKey2, int n2)
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 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)
void * sqliteHashFind (const Hash *pH, const void *pKey, int nKey)
void * sqliteHashInsert (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 115 of file hash.c.

                                                                           {
  if( n1!=n2 ) return n2-n1;
  return memcmp(pKey1,pKey2,n1);
}
static int binHash ( const void *  pKey,
int  nKey 
) [static]

Definition at line 107 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 203 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 ){
    elem = pH->ht[h].chain;
    count = pH->ht[h].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 int intCompare ( const void *  pKey1,
int  n1,
const void *  pKey2,
int  n2 
) [static]

Definition at line 74 of file hash.c.

                                                                           {
  return n2 - n1;
}
static int intHash ( const void *  pKey,
int  nKey 
) [static]

Definition at line 71 of file hash.c.

                                              {
  return nKey ^ (nKey<<8) ^ (nKey>>8);
}
static void rehash ( Hash pH,
int  new_size 
) [static]

Definition at line 165 of file hash.c.

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

  assert( (new_size & (new_size-1))==0 );
  new_ht = (struct _ht *)sqliteMalloc( new_size*sizeof(struct _ht) );
  if( new_ht==0 ) return;
  if( pH->ht ) sqliteFree(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;
    x = new_ht[h].chain;
    if( x ){
      elem->next = x;
      elem->prev = x->prev;
      if( x->prev ) x->prev->next = elem;
      else          pH->first = elem;
      x->prev = elem;
    }else{
      elem->next = pH->first;
      if( pH->first ) pH->first->prev = elem;
      elem->prev = 0;
      pH->first = elem;
    }
    new_ht[h].chain = elem;
    new_ht[h].count++;
  }
}

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 230 of file hash.c.

 {
  if( elem->prev ){
    elem->prev->next = elem->next; 
  }else{
    pH->first = elem->next;
  }
  if( elem->next ){
    elem->next->prev = elem->prev;
  }
  if( pH->ht[h].chain==elem ){
    pH->ht[h].chain = elem->next;
  }
  pH->ht[h].count--;
  if( pH->ht[h].count<=0 ){
    pH->ht[h].chain = 0;
  }
  if( pH->copyKey && elem->pKey ){
    sqliteFree(elem->pKey);
  }
  sqliteFree( elem );
  pH->count--;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void sqliteHashClear ( Hash pH)

Definition at line 48 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 ) sqliteFree(pH->ht);
  pH->ht = 0;
  pH->htsize = 0;
  while( elem ){
    HashElem *next_elem = elem->next;
    if( pH->copyKey && elem->pKey ){
      sqliteFree(elem->pKey);
    }
    sqliteFree(elem);
    elem = next_elem;
  }
  pH->count = 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

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

Definition at line 261 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 sqliteHashInit ( Hash new,
int  keyClass,
int  copyKey 
)

Definition at line 32 of file hash.c.

                                                         {
  assert( new!=0 );
  assert( keyClass>=SQLITE_HASH_INT && keyClass<=SQLITE_HASH_BINARY );
  new->keyClass = keyClass;
  new->copyKey = copyKey &&
                (keyClass==SQLITE_HASH_STRING || keyClass==SQLITE_HASH_BINARY);
  new->first = 0;
  new->count = 0;
  new->htsize = 0;
  new->ht = 0;
}

Here is the caller graph for this function:

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

Definition at line 290 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*)sqliteMalloc( sizeof(HashElem) );
  if( new_elem==0 ) return data;
  if( pH->copyKey && pKey!=0 ){
    new_elem->pKey = sqliteMallocRaw( nKey );
    if( new_elem->pKey==0 ){
      sqliteFree(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;
    sqliteFree(new_elem);
    return data;
  }
  if( pH->count > pH->htsize ){
    rehash(pH,pH->htsize*2);
  }
  assert( (pH->htsize & (pH->htsize-1))==0 );
  h = hraw & (pH->htsize-1);
  elem = pH->ht[h].chain;
  if( elem ){
    new_elem->next = elem;
    new_elem->prev = elem->prev;
    if( elem->prev ){ elem->prev->next = new_elem; }
    else            { pH->first = new_elem; }
    elem->prev = new_elem;
  }else{
    new_elem->next = pH->first;
    new_elem->prev = 0;
    if( pH->first ){ pH->first->prev = new_elem; }
    pH->first = new_elem;
  }
  pH->ht[h].count++;
  pH->ht[h].chain = 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 99 of file hash.c.

                                                                           {
  if( n1!=n2 ) return n2-n1;
  return sqliteStrNICmp((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 96 of file hash.c.

                                              {
  return sqliteHashNoCase((const char*)pKey, nKey); 
}

Here is the call graph for this function:


Variable Documentation

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

Definition at line 149 of file hash.c.

                                                                            {
  switch( keyClass ){
    case SQLITE_HASH_INT:     return &intCompare;
    /* case SQLITE_HASH_POINTER: return &ptrCompare; // NOT USED */
    case SQLITE_HASH_STRING:  return &strCompare;
    case SQLITE_HASH_BINARY:  return &binCompare;
    default: break;
  }
  return 0;
}
int(*)(const void*, int) hashFunction(int keyClass) [static]

Definition at line 132 of file hash.c.

                                                         {
  switch( keyClass ){
    case SQLITE_HASH_INT:     return &intHash;
    /* case SQLITE_HASH_POINTER: return &ptrHash; // NOT USED */
    case SQLITE_HASH_STRING:  return &strHash;
    case SQLITE_HASH_BINARY:  return &binHash;;
    default: break;
  }
  return 0;
}