SQLite

Check-in [cc29ddd6be]
Login

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

Overview
Comment:Use Knuth multiplicative hashing for the symbol table.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: cc29ddd6be60bdbf107f285c9eb57d5896ebca2d
User & Date: drh 2016-09-28 20:42:31.903
Context
2016-09-29
15:53
Clarification and typo-fixes in comments. No changes to code. (check-in: e2cd79aa31 user: drh tags: trunk)
2016-09-28
20:42
Use Knuth multiplicative hashing for the symbol table. (check-in: cc29ddd6be user: drh tags: trunk)
16:05
Two more typo fixes in comments. (check-in: 40c0fb0af6 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/hash.c.
52
53
54
55
56
57
58



59

60
61
62
63
64
65
66
/*
** The hashing function.
*/
static unsigned int strHash(const char *z){
  unsigned int h = 0;
  unsigned char c;
  while( (c = (unsigned char)*z++)!=0 ){     /*OPTIMIZATION-IF-TRUE*/



    h = (h<<3) ^ h ^ sqlite3UpperToLower[c];

  }
  return h;
}


/* Link pNew element into the hash table pH.  If pEntry!=0 then also
** insert pNew into the pEntry hash bucket.







>
>
>
|
>







52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/*
** The hashing function.
*/
static unsigned int strHash(const char *z){
  unsigned int h = 0;
  unsigned char c;
  while( (c = (unsigned char)*z++)!=0 ){     /*OPTIMIZATION-IF-TRUE*/
    /* Knuth multiplicative hashing.  (Sorting & Searching, p. 510).
    ** 0x9e3779b1 is 2654435761 which is the closest prime number to
    ** (2**32)*golden_ratio, where golden_ratio = (sqrt(5) - 1)/2. */
    h += sqlite3UpperToLower[c];
    h *= 0x9e3779b1;
  }
  return h;
}


/* Link pNew element into the hash table pH.  If pEntry!=0 then also
** insert pNew into the pEntry hash bucket.