/ Check-in [ac645c8f]
Login

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

Overview
Comment:Cleanup the hash functions in FTS3. (CVS 4440)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: ac645c8f30aac0d98fc481260084c9bd3975a845
User & Date: drh 2007-09-20 12:53:28
Context
2007-09-20
14:39
Replace "i64" with "sqlite3_int64" in the w32 VFS. (CVS 4441) check-in: 138d3fcc user: drh tags: trunk
12:53
Cleanup the hash functions in FTS3. (CVS 4440) check-in: ac645c8f user: drh tags: trunk
11:34
get rid of remaining GCC 4.3 -Wall compiler warnings by initializing two variables and one structure properly (although the code path was already rather safe) (CVS 4439) check-in: d748694f user: rse tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/fts3/fts3_hash.c.

    27     27   
    28     28   #include <assert.h>
    29     29   #include <stdlib.h>
    30     30   #include <string.h>
    31     31   
    32     32   #include "fts3_hash.h"
    33     33   
    34         -static void *malloc_and_zero(int n){
    35         -  void *p = malloc(n);
           34  +/*
           35  +** Malloc and Free functions
           36  +*/
           37  +static void *fts3HashMalloc(int n){
           38  +  void *p = sqlite3_malloc(n);
    36     39     if( p ){
    37     40       memset(p, 0, n);
    38     41     }
    39     42     return p;
           43  +}
           44  +static void fts3HashFree(void *p){
           45  +  sqlite3_free(p);
    40     46   }
    41     47   
    42     48   /* Turn bulk memory into a hash table object by initializing the
    43     49   ** fields of the Hash structure.
    44     50   **
    45     51   ** "pNew" is a pointer to the hash table that is to be initialized.
    46     52   ** keyClass is one of the constants 
................................................................................
    54     60     assert( keyClass>=FTS3_HASH_STRING && keyClass<=FTS3_HASH_BINARY );
    55     61     pNew->keyClass = keyClass;
    56     62     pNew->copyKey = copyKey;
    57     63     pNew->first = 0;
    58     64     pNew->count = 0;
    59     65     pNew->htsize = 0;
    60     66     pNew->ht = 0;
    61         -  pNew->xMalloc = malloc_and_zero;
    62         -  pNew->xFree = free;
    63     67   }
    64     68   
    65     69   /* Remove all entries from a hash table.  Reclaim all memory.
    66     70   ** Call this routine to delete a hash table or to reset a hash table
    67     71   ** to the empty state.
    68     72   */
    69     73   void sqlite3Fts3HashClear(fts3Hash *pH){
    70     74     fts3HashElem *elem;         /* For looping over all elements of the table */
    71     75   
    72     76     assert( pH!=0 );
    73     77     elem = pH->first;
    74     78     pH->first = 0;
    75         -  if( pH->ht ) pH->xFree(pH->ht);
           79  +  fts3HashFree(pH->ht);
    76     80     pH->ht = 0;
    77     81     pH->htsize = 0;
    78     82     while( elem ){
    79     83       fts3HashElem *next_elem = elem->next;
    80     84       if( pH->copyKey && elem->pKey ){
    81         -      pH->xFree(elem->pKey);
           85  +      fts3HashFree(elem->pKey);
    82     86       }
    83         -    pH->xFree(elem);
           87  +    fts3HashFree(elem);
    84     88       elem = next_elem;
    85     89     }
    86     90     pH->count = 0;
    87     91   }
    88     92   
    89     93   /*
    90     94   ** Hash and comparison functions when the mode is FTS3_HASH_STRING
    91     95   */
    92         -static int strHash(const void *pKey, int nKey){
           96  +static int fts3StrHash(const void *pKey, int nKey){
    93     97     const char *z = (const char *)pKey;
    94     98     int h = 0;
    95     99     if( nKey<=0 ) nKey = (int) strlen(z);
    96    100     while( nKey > 0  ){
    97    101       h = (h<<3) ^ h ^ *z++;
    98    102       nKey--;
    99    103     }
   100    104     return h & 0x7fffffff;
   101    105   }
   102         -static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){
          106  +static int fts3StrCompare(const void *pKey1, int n1, const void *pKey2, int n2){
   103    107     if( n1!=n2 ) return 1;
   104    108     return strncmp((const char*)pKey1,(const char*)pKey2,n1);
   105    109   }
   106    110   
   107    111   /*
   108    112   ** Hash and comparison functions when the mode is FTS3_HASH_BINARY
   109    113   */
   110         -static int binHash(const void *pKey, int nKey){
          114  +static int fts3BinHash(const void *pKey, int nKey){
   111    115     int h = 0;
   112    116     const char *z = (const char *)pKey;
   113    117     while( nKey-- > 0 ){
   114    118       h = (h<<3) ^ h ^ *(z++);
   115    119     }
   116    120     return h & 0x7fffffff;
   117    121   }
   118         -static int binCompare(const void *pKey1, int n1, const void *pKey2, int n2){
          122  +static int fts3BinCompare(const void *pKey1, int n1, const void *pKey2, int n2){
   119    123     if( n1!=n2 ) return 1;
   120    124     return memcmp(pKey1,pKey2,n1);
   121    125   }
   122    126   
   123    127   /*
   124    128   ** Return a pointer to the appropriate hash function given the key class.
   125    129   **
................................................................................
   130    134   ** single parameter "keyClass".  The return value of hashFunction()
   131    135   ** is a pointer to another function.  Specifically, the return value
   132    136   ** of hashFunction() is a pointer to a function that takes two parameters
   133    137   ** with types "const void*" and "int" and returns an "int".
   134    138   */
   135    139   static int (*hashFunction(int keyClass))(const void*,int){
   136    140     if( keyClass==FTS3_HASH_STRING ){
   137         -    return &strHash;
          141  +    return &fts3StrHash;
   138    142     }else{
   139    143       assert( keyClass==FTS3_HASH_BINARY );
   140         -    return &binHash;
          144  +    return &fts3BinHash;
   141    145     }
   142    146   }
   143    147   
   144    148   /*
   145    149   ** Return a pointer to the appropriate hash function given the key class.
   146    150   **
   147    151   ** For help in interpreted the obscure C code in the function definition,
   148    152   ** see the header comment on the previous function.
   149    153   */
   150    154   static int (*compareFunction(int keyClass))(const void*,int,const void*,int){
   151    155     if( keyClass==FTS3_HASH_STRING ){
   152         -    return &strCompare;
          156  +    return &fts3StrCompare;
   153    157     }else{
   154    158       assert( keyClass==FTS3_HASH_BINARY );
   155         -    return &binCompare;
          159  +    return &fts3BinCompare;
   156    160     }
   157    161   }
   158    162   
   159    163   /* Link an element into the hash table
   160    164   */
   161         -static void insertElement(
          165  +static void fts3HashInsertElement(
   162    166     fts3Hash *pH,            /* The complete hash table */
   163    167     struct _fts3ht *pEntry,  /* The entry into which pNew is inserted */
   164    168     fts3HashElem *pNew       /* The element to be inserted */
   165    169   ){
   166    170     fts3HashElem *pHead;     /* First element already in pEntry */
   167    171     pHead = pEntry->chain;
   168    172     if( pHead ){
................................................................................
   182    186   }
   183    187   
   184    188   
   185    189   /* Resize the hash table so that it cantains "new_size" buckets.
   186    190   ** "new_size" must be a power of 2.  The hash table might fail 
   187    191   ** to resize if sqliteMalloc() fails.
   188    192   */
   189         -static void rehash(fts3Hash *pH, int new_size){
          193  +static void fts3Rehash(fts3Hash *pH, int new_size){
   190    194     struct _fts3ht *new_ht;          /* The new hash table */
   191    195     fts3HashElem *elem, *next_elem;  /* For looping over existing elements */
   192    196     int (*xHash)(const void*,int);   /* The hash function */
   193    197   
   194    198     assert( (new_size & (new_size-1))==0 );
   195         -  new_ht = (struct _fts3ht *)pH->xMalloc( new_size*sizeof(struct _fts3ht) );
          199  +  new_ht = (struct _fts3ht *)fts3HashMalloc( new_size*sizeof(struct _fts3ht) );
   196    200     if( new_ht==0 ) return;
   197         -  if( pH->ht ) pH->xFree(pH->ht);
          201  +  fts3HashFree(pH->ht);
   198    202     pH->ht = new_ht;
   199    203     pH->htsize = new_size;
   200    204     xHash = hashFunction(pH->keyClass);
   201    205     for(elem=pH->first, pH->first=0; elem; elem = next_elem){
   202    206       int h = (*xHash)(elem->pKey, elem->nKey) & (new_size-1);
   203    207       next_elem = elem->next;
   204         -    insertElement(pH, &new_ht[h], elem);
          208  +    fts3HashInsertElement(pH, &new_ht[h], elem);
   205    209     }
   206    210   }
   207    211   
   208    212   /* This function (for internal use only) locates an element in an
   209    213   ** hash table that matches the given key.  The hash for this key has
   210    214   ** already been computed and is passed as the 4th parameter.
   211    215   */
   212         -static fts3HashElem *findElementGivenHash(
          216  +static fts3HashElem *fts3FindElementByHash(
   213    217     const fts3Hash *pH, /* The pH to be searched */
   214    218     const void *pKey,   /* The key we are searching for */
   215    219     int nKey,
   216    220     int h               /* The hash for this key. */
   217    221   ){
   218    222     fts3HashElem *elem;            /* Used to loop thru the element list */
   219    223     int count;                     /* Number of elements left to test */
................................................................................
   233    237     }
   234    238     return 0;
   235    239   }
   236    240   
   237    241   /* Remove a single entry from the hash table given a pointer to that
   238    242   ** element and a hash on the element's key.
   239    243   */
   240         -static void removeElementGivenHash(
          244  +static void fts3RemoveElementByHash(
   241    245     fts3Hash *pH,         /* The pH containing "elem" */
   242    246     fts3HashElem* elem,   /* The element to be removed from the pH */
   243    247     int h                 /* Hash value for the element */
   244    248   ){
   245    249     struct _fts3ht *pEntry;
   246    250     if( elem->prev ){
   247    251       elem->prev->next = elem->next; 
................................................................................
   256    260       pEntry->chain = elem->next;
   257    261     }
   258    262     pEntry->count--;
   259    263     if( pEntry->count<=0 ){
   260    264       pEntry->chain = 0;
   261    265     }
   262    266     if( pH->copyKey && elem->pKey ){
   263         -    pH->xFree(elem->pKey);
          267  +    fts3HashFree(elem->pKey);
   264    268     }
   265         -  pH->xFree( elem );
          269  +  fts3HashFree( elem );
   266    270     pH->count--;
   267    271     if( pH->count<=0 ){
   268    272       assert( pH->first==0 );
   269    273       assert( pH->count==0 );
   270    274       fts3HashClear(pH);
   271    275     }
   272    276   }
................................................................................
   281    285     int (*xHash)(const void*,int);  /* The hash function */
   282    286   
   283    287     if( pH==0 || pH->ht==0 ) return 0;
   284    288     xHash = hashFunction(pH->keyClass);
   285    289     assert( xHash!=0 );
   286    290     h = (*xHash)(pKey,nKey);
   287    291     assert( (pH->htsize & (pH->htsize-1))==0 );
   288         -  elem = findElementGivenHash(pH,pKey,nKey, h & (pH->htsize-1));
          292  +  elem = fts3FindElementByHash(pH,pKey,nKey, h & (pH->htsize-1));
   289    293     return elem ? elem->data : 0;
   290    294   }
   291    295   
   292    296   /* Insert an element into the hash table pH.  The key is pKey,nKey
   293    297   ** and the data is "data".
   294    298   **
   295    299   ** If no element exists with a matching key, then a new
................................................................................
   318    322   
   319    323     assert( pH!=0 );
   320    324     xHash = hashFunction(pH->keyClass);
   321    325     assert( xHash!=0 );
   322    326     hraw = (*xHash)(pKey, nKey);
   323    327     assert( (pH->htsize & (pH->htsize-1))==0 );
   324    328     h = hraw & (pH->htsize-1);
   325         -  elem = findElementGivenHash(pH,pKey,nKey,h);
          329  +  elem = fts3FindElementByHash(pH,pKey,nKey,h);
   326    330     if( elem ){
   327    331       void *old_data = elem->data;
   328    332       if( data==0 ){
   329         -      removeElementGivenHash(pH,elem,h);
          333  +      fts3RemoveElementByHash(pH,elem,h);
   330    334       }else{
   331    335         elem->data = data;
   332    336       }
   333    337       return old_data;
   334    338     }
   335    339     if( data==0 ) return 0;
   336         -  new_elem = (fts3HashElem*)pH->xMalloc( sizeof(fts3HashElem) );
          340  +  new_elem = (fts3HashElem*)fts3HashMalloc( sizeof(fts3HashElem) );
   337    341     if( new_elem==0 ) return data;
   338    342     if( pH->copyKey && pKey!=0 ){
   339         -    new_elem->pKey = pH->xMalloc( nKey );
          343  +    new_elem->pKey = fts3HashMalloc( nKey );
   340    344       if( new_elem->pKey==0 ){
   341         -      pH->xFree(new_elem);
          345  +      fts3HashFree(new_elem);
   342    346         return data;
   343    347       }
   344    348       memcpy((void*)new_elem->pKey, pKey, nKey);
   345    349     }else{
   346    350       new_elem->pKey = (void*)pKey;
   347    351     }
   348    352     new_elem->nKey = nKey;
   349    353     pH->count++;
   350    354     if( pH->htsize==0 ){
   351         -    rehash(pH,8);
          355  +    fts3Rehash(pH,8);
   352    356       if( pH->htsize==0 ){
   353    357         pH->count = 0;
   354         -      pH->xFree(new_elem);
          358  +      fts3HashFree(new_elem);
   355    359         return data;
   356    360       }
   357    361     }
   358    362     if( pH->count > pH->htsize ){
   359         -    rehash(pH,pH->htsize*2);
          363  +    fts3Rehash(pH,pH->htsize*2);
   360    364     }
   361    365     assert( pH->htsize>0 );
   362    366     assert( (pH->htsize & (pH->htsize-1))==0 );
   363    367     h = hraw & (pH->htsize-1);
   364         -  insertElement(pH, &pH->ht[h], new_elem);
          368  +  fts3HashInsertElement(pH, &pH->ht[h], new_elem);
   365    369     new_elem->data = data;
   366    370     return 0;
   367    371   }
   368    372   
   369    373   #endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) */

Changes to ext/fts3/fts3_hash.h.

    30     30   ** this structure opaque.
    31     31   */
    32     32   struct fts3Hash {
    33     33     char keyClass;          /* HASH_INT, _POINTER, _STRING, _BINARY */
    34     34     char copyKey;           /* True if copy of key made on insert */
    35     35     int count;              /* Number of entries in this table */
    36     36     fts3HashElem *first;    /* The first element of the array */
    37         -  void *(*xMalloc)(int);  /* malloc() function to use */
    38         -  void (*xFree)(void *);  /* free() function to use */
    39     37     int htsize;             /* Number of buckets in the hash table */
    40     38     struct _fts3ht {        /* the hash table */
    41     39       int count;               /* Number of entries with this hash */
    42     40       fts3HashElem *chain;     /* Pointer to first entry with this hash */
    43     41     } *ht;
    44     42   };
    45     43