/ Check-in [d5b0269e]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Optimizations in the hash table module. (CVS 1896)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:d5b0269e0dd7c310460a7ffc4120ed45db823ce9
User & Date: drh 2004-08-20 14:08:51
Context
2004-08-20
16:02
Add support for named wildcards in SQL statements. (CVS 1897) check-in: d3be0b7c user: drh tags: trunk
14:08
Optimizations in the hash table module. (CVS 1896) check-in: d5b0269e user: drh tags: trunk
2004-08-19
15:12
Enhance lemon so that a @X instead of just X in the code expands to the major token value rather than the minor token value. Use this to make the parser a few hundred bytes smaller. (CVS 1895) check-in: 28215096 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/hash.c.

     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** This is the implementation of generic hash-tables
    13     13   ** used in SQLite.
    14     14   **
    15         -** $Id: hash.c,v 1.14 2004/06/30 22:43:22 drh Exp $
           15  +** $Id: hash.c,v 1.15 2004/08/20 14:08:51 drh Exp $
    16     16   */
    17     17   #include "sqliteInt.h"
    18     18   #include <assert.h>
    19     19   
    20     20   /* Turn bulk memory into a hash table object by initializing the
    21     21   ** fields of the Hash structure.
    22     22   **
................................................................................
    27     27   ** true if the hash table should make its own private copy of keys and
    28     28   ** false if it should just use the supplied pointer.  CopyKey only makes
    29     29   ** sense for SQLITE_HASH_STRING and SQLITE_HASH_BINARY and is ignored
    30     30   ** for other key classes.
    31     31   */
    32     32   void sqlite3HashInit(Hash *pNew, int keyClass, int copyKey){
    33     33     assert( pNew!=0 );
    34         -  assert( keyClass>=SQLITE_HASH_INT && keyClass<=SQLITE_HASH_BINARY );
           34  +  assert( keyClass>=SQLITE_HASH_STRING && keyClass<=SQLITE_HASH_BINARY );
    35     35     pNew->keyClass = keyClass;
    36         -  pNew->copyKey = copyKey &&
    37         -                (keyClass==SQLITE_HASH_STRING || keyClass==SQLITE_HASH_BINARY);
           36  +#if 0
           37  +  if( keyClass==SQLITE_HASH_POINTER || keyClass==SQLITE_HASH_INT ) copyKey = 0;
           38  +#endif
           39  +  pNew->copyKey = copyKey;
    38     40     pNew->first = 0;
    39     41     pNew->count = 0;
    40     42     pNew->htsize = 0;
    41     43     pNew->ht = 0;
    42     44   }
    43     45   
    44     46   /* Remove all entries from a hash table.  Reclaim all memory.
................................................................................
    95     97   /*
    96     98   ** Hash and comparison functions when the mode is SQLITE_HASH_STRING
    97     99   */
    98    100   static int strHash(const void *pKey, int nKey){
    99    101     return sqlite3HashNoCase((const char*)pKey, nKey); 
   100    102   }
   101    103   static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){
   102         -  if( n1!=n2 ) return n2-n1;
          104  +  if( n1!=n2 ) return 1;
   103    105     return sqlite3StrNICmp((const char*)pKey1,(const char*)pKey2,n1);
   104    106   }
   105    107   
   106    108   /*
   107    109   ** Hash and comparison functions when the mode is SQLITE_HASH_BINARY
   108    110   */
   109    111   static int binHash(const void *pKey, int nKey){
................................................................................
   111    113     const char *z = (const char *)pKey;
   112    114     while( nKey-- > 0 ){
   113    115       h = (h<<3) ^ h ^ *(z++);
   114    116     }
   115    117     return h & 0x7fffffff;
   116    118   }
   117    119   static int binCompare(const void *pKey1, int n1, const void *pKey2, int n2){
   118         -  if( n1!=n2 ) return n2-n1;
          120  +  if( n1!=n2 ) return 1;
   119    121     return memcmp(pKey1,pKey2,n1);
   120    122   }
   121    123   
   122    124   /*
   123    125   ** Return a pointer to the appropriate hash function given the key class.
   124    126   **
   125    127   ** The C syntax in this function definition may be unfamilar to some 
................................................................................
   128    130   ** The name of the function is "hashFunction".  The function takes a
   129    131   ** single parameter "keyClass".  The return value of hashFunction()
   130    132   ** is a pointer to another function.  Specifically, the return value
   131    133   ** of hashFunction() is a pointer to a function that takes two parameters
   132    134   ** with types "const void*" and "int" and returns an "int".
   133    135   */
   134    136   static int (*hashFunction(int keyClass))(const void*,int){
          137  +#if 0  /* HASH_INT and HASH_POINTER are never used */
   135    138     switch( keyClass ){
   136         -    /* case SQLITE_HASH_INT:     return &intHash; // NOT USED */
   137         -    /* case SQLITE_HASH_POINTER: return &ptrHash; // NOT USED */
          139  +    case SQLITE_HASH_INT:     return &intHash;
          140  +    case SQLITE_HASH_POINTER: return &ptrHash;
   138    141       case SQLITE_HASH_STRING:  return &strHash;
   139    142       case SQLITE_HASH_BINARY:  return &binHash;;
   140    143       default: break;
   141    144     }
   142    145     return 0;
          146  +#else
          147  +  if( keyClass==SQLITE_HASH_STRING ){
          148  +    return &strHash;
          149  +  }else{
          150  +    assert( keyClass==SQLITE_HASH_BINARY );
          151  +    return &binHash;
          152  +  }
          153  +#endif
   143    154   }
   144    155   
   145    156   /*
   146    157   ** Return a pointer to the appropriate hash function given the key class.
   147    158   **
   148    159   ** For help in interpreted the obscure C code in the function definition,
   149    160   ** see the header comment on the previous function.
   150    161   */
   151    162   static int (*compareFunction(int keyClass))(const void*,int,const void*,int){
          163  +#if 0 /* HASH_INT and HASH_POINTER are never used */
   152    164     switch( keyClass ){
   153         -    /* case SQLITE_HASH_INT:     return &intCompare; // NOT USED */
   154         -    /* case SQLITE_HASH_POINTER: return &ptrCompare; // NOT USED */
          165  +    case SQLITE_HASH_INT:     return &intCompare;
          166  +    case SQLITE_HASH_POINTER: return &ptrCompare;
   155    167       case SQLITE_HASH_STRING:  return &strCompare;
   156    168       case SQLITE_HASH_BINARY:  return &binCompare;
   157    169       default: break;
   158    170     }
   159    171     return 0;
          172  +#else
          173  +  if( keyClass==SQLITE_HASH_STRING ){
          174  +    return &strCompare;
          175  +  }else{
          176  +    assert( keyClass==SQLITE_HASH_BINARY );
          177  +    return &binCompare;
          178  +  }
          179  +#endif
          180  +}
          181  +
          182  +/* Link an element into the hash table
          183  +*/
          184  +static void insertElement(
          185  +  Hash *pH,              /* The complete hash table */
          186  +  struct _ht *pEntry,    /* The entry into which pNew is inserted */
          187  +  HashElem *pNew         /* The element to be inserted */
          188  +){
          189  +  HashElem *pHead;       /* First element already in pEntry */
          190  +  pHead = pEntry->chain;
          191  +  if( pHead ){
          192  +    pNew->next = pHead;
          193  +    pNew->prev = pHead->prev;
          194  +    if( pHead->prev ){ pHead->prev->next = pNew; }
          195  +    else             { pH->first = pNew; }
          196  +    pHead->prev = pNew;
          197  +  }else{
          198  +    pNew->next = pH->first;
          199  +    if( pH->first ){ pH->first->prev = pNew; }
          200  +    pNew->prev = 0;
          201  +    pH->first = pNew;
          202  +  }
          203  +  pEntry->count++;
          204  +  pEntry->chain = pNew;
   160    205   }
   161    206   
   162    207   
   163    208   /* Resize the hash table so that it cantains "new_size" buckets.
   164    209   ** "new_size" must be a power of 2.  The hash table might fail 
   165    210   ** to resize if sqliteMalloc() fails.
   166    211   */
   167    212   static void rehash(Hash *pH, int new_size){
   168    213     struct _ht *new_ht;            /* The new hash table */
   169    214     HashElem *elem, *next_elem;    /* For looping over existing elements */
   170         -  HashElem *x;                   /* Element being copied to new hash table */
   171    215     int (*xHash)(const void*,int); /* The hash function */
   172    216   
   173    217     assert( (new_size & (new_size-1))==0 );
   174    218     new_ht = (struct _ht *)sqliteMalloc( new_size*sizeof(struct _ht) );
   175    219     if( new_ht==0 ) return;
   176    220     if( pH->ht ) sqliteFree(pH->ht);
   177    221     pH->ht = new_ht;
   178    222     pH->htsize = new_size;
   179    223     xHash = hashFunction(pH->keyClass);
   180    224     for(elem=pH->first, pH->first=0; elem; elem = next_elem){
   181    225       int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
   182    226       next_elem = elem->next;
   183         -    x = new_ht[h].chain;
   184         -    if( x ){
   185         -      elem->next = x;
   186         -      elem->prev = x->prev;
   187         -      if( x->prev ) x->prev->next = elem;
   188         -      else          pH->first = elem;
   189         -      x->prev = elem;
   190         -    }else{
   191         -      elem->next = pH->first;
   192         -      if( pH->first ) pH->first->prev = elem;
   193         -      elem->prev = 0;
   194         -      pH->first = elem;
   195         -    }
   196         -    new_ht[h].chain = elem;
   197         -    new_ht[h].count++;
          227  +    insertElement(pH, &new_ht[h], elem);
   198    228     }
   199    229   }
   200    230   
   201    231   /* This function (for internal use only) locates an element in an
   202    232   ** hash table that matches the given key.  The hash for this key has
   203    233   ** already been computed and is passed as the 4th parameter.
   204    234   */
................................................................................
   209    239     int h               /* The hash for this key. */
   210    240   ){
   211    241     HashElem *elem;                /* Used to loop thru the element list */
   212    242     int count;                     /* Number of elements left to test */
   213    243     int (*xCompare)(const void*,int,const void*,int);  /* comparison function */
   214    244   
   215    245     if( pH->ht ){
   216         -    elem = pH->ht[h].chain;
   217         -    count = pH->ht[h].count;
          246  +    struct _ht *pEntry = &pH->ht[h];
          247  +    elem = pEntry->chain;
          248  +    count = pEntry->count;
   218    249       xCompare = compareFunction(pH->keyClass);
   219    250       while( count-- && elem ){
   220    251         if( (*xCompare)(elem->pKey,elem->nKey,pKey,nKey)==0 ){ 
   221    252           return elem;
   222    253         }
   223    254         elem = elem->next;
   224    255       }
................................................................................
   230    261   ** element and a hash on the element's key.
   231    262   */
   232    263   static void removeElementGivenHash(
   233    264     Hash *pH,         /* The pH containing "elem" */
   234    265     HashElem* elem,   /* The element to be removed from the pH */
   235    266     int h             /* Hash value for the element */
   236    267   ){
          268  +  struct _ht *pEntry;
   237    269     if( elem->prev ){
   238    270       elem->prev->next = elem->next; 
   239    271     }else{
   240    272       pH->first = elem->next;
   241    273     }
   242    274     if( elem->next ){
   243    275       elem->next->prev = elem->prev;
   244    276     }
   245         -  if( pH->ht[h].chain==elem ){
   246         -    pH->ht[h].chain = elem->next;
          277  +  pEntry = &pH->ht[h];
          278  +  if( pEntry->chain==elem ){
          279  +    pEntry->chain = elem->next;
   247    280     }
   248         -  pH->ht[h].count--;
   249         -  if( pH->ht[h].count<=0 ){
   250         -    pH->ht[h].chain = 0;
          281  +  pEntry->count--;
          282  +  if( pEntry->count<=0 ){
          283  +    pEntry->chain = 0;
   251    284     }
   252    285     if( pH->copyKey && elem->pKey ){
   253    286       sqliteFree(elem->pKey);
   254    287     }
   255    288     sqliteFree( elem );
   256    289     pH->count--;
   257    290   }
................................................................................
   323    356       }
   324    357       memcpy((void*)new_elem->pKey, pKey, nKey);
   325    358     }else{
   326    359       new_elem->pKey = (void*)pKey;
   327    360     }
   328    361     new_elem->nKey = nKey;
   329    362     pH->count++;
   330         -  if( pH->htsize==0 ) rehash(pH,8);
   331    363     if( pH->htsize==0 ){
   332         -    pH->count = 0;
   333         -    sqliteFree(new_elem);
   334         -    return data;
          364  +    rehash(pH,8);
          365  +    if( pH->htsize==0 ){
          366  +      pH->count = 0;
          367  +      sqliteFree(new_elem);
          368  +      return data;
          369  +    }
   335    370     }
   336    371     if( pH->count > pH->htsize ){
   337    372       rehash(pH,pH->htsize*2);
   338    373     }
          374  +  assert( pH->htsize>0 );
   339    375     assert( (pH->htsize & (pH->htsize-1))==0 );
   340    376     h = hraw & (pH->htsize-1);
   341         -  elem = pH->ht[h].chain;
   342         -  if( elem ){
   343         -    new_elem->next = elem;
   344         -    new_elem->prev = elem->prev;
   345         -    if( elem->prev ){ elem->prev->next = new_elem; }
   346         -    else            { pH->first = new_elem; }
   347         -    elem->prev = new_elem;
   348         -  }else{
   349         -    new_elem->next = pH->first;
   350         -    new_elem->prev = 0;
   351         -    if( pH->first ){ pH->first->prev = new_elem; }
   352         -    pH->first = new_elem;
   353         -  }
   354         -  pH->ht[h].count++;
   355         -  pH->ht[h].chain = new_elem;
          377  +  insertElement(pH, &pH->ht[h], new_elem);
   356    378     new_elem->data = data;
   357    379     return 0;
   358    380   }

Changes to src/hash.h.

     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** This is the header file for the generic hash-table implemenation
    13     13   ** used in SQLite.
    14     14   **
    15         -** $Id: hash.h,v 1.7 2004/05/08 08:23:25 danielk1977 Exp $
           15  +** $Id: hash.h,v 1.8 2004/08/20 14:08:51 drh Exp $
    16     16   */
    17     17   #ifndef _SQLITE_HASH_H_
    18     18   #define _SQLITE_HASH_H_
    19     19   
    20     20   /* Forward declarations of structures. */
    21     21   typedef struct Hash Hash;
    22     22   typedef struct HashElem HashElem;
................................................................................
    66     66   **
    67     67   **   SQLITE_HASH_BINARY      pKey points to binary data nKey bytes long. 
    68     68   **                           memcmp() is used to compare keys.
    69     69   **
    70     70   ** A copy of the key is made for SQLITE_HASH_STRING and SQLITE_HASH_BINARY
    71     71   ** if the copyKey parameter to HashInit is 1.  
    72     72   */
    73         -#define SQLITE_HASH_INT       1
           73  +/* #define SQLITE_HASH_INT       1 // NOT USED */
    74     74   /* #define SQLITE_HASH_POINTER   2 // NOT USED */
    75     75   #define SQLITE_HASH_STRING    3
    76     76   #define SQLITE_HASH_BINARY    4
    77     77   
    78     78   /*
    79     79   ** Access routines.  To delete, insert a NULL pointer.
    80     80   */
................................................................................
   103    103   
   104    104   /*
   105    105   ** Number of entries in a hash table
   106    106   */
   107    107   #define sqliteHashCount(H)  ((H)->count)
   108    108   
   109    109   #endif /* _SQLITE_HASH_H_ */
   110         -
   111         -
   112         -