Lines Matching defs:Hash
651 ** hash of the entire source tree.
6810 /************** Include hash.h in the middle of sqliteInt.h ******************/
6811 /************** Begin file hash.h ********************************************/
6823 ** This is the header file for the generic hash-table implemenation
6830 typedef struct Hash Hash;
6833 /* A complete hash table is an instance of the following structure.
6841 ** All elements of the hash table are on a single doubly-linked list.
6842 ** Hash.first points to the head of this list.
6844 ** There are Hash.htsize buckets. Each bucket points to a spot in
6848 ** Hash.htsize and Hash.ht may be zero. In that case lookup is done
6850 ** Hash.ht table is never allocated because if there are few elements
6852 ** the hash table.
6854 struct Hash {
6855 unsigned int htsize; /* Number of buckets in the hash table */
6858 struct _ht { /* the hash table */
6859 int count; /* Number of entries with this hash */
6860 HashElem *chain; /* Pointer to first entry with this hash */
6864 /* Each element in the hash table is an instance of the following
6879 SQLITE_PRIVATE void sqlite3HashInit(Hash*);
6880 SQLITE_PRIVATE void *sqlite3HashInsert(Hash*, const char *pKey, int nKey, void *pData);
6881 SQLITE_PRIVATE void *sqlite3HashFind(const Hash*, const char *pKey, int nKey);
6882 SQLITE_PRIVATE void sqlite3HashClear(Hash*);
6885 ** Macros for looping over all elements of a hash table. The idiom is
6888 ** Hash h;
6903 ** Number of entries in a hash table
6909 /************** End of hash.h ************************************************/
7488 #define BTREE_UNORDERED 16 /* Use of a hash implementation is OK */
8311 u32 pageHash; /* Hash of page content */
8821 Hash tblHash; /* All tables indexed by name */
8822 Hash idxHash; /* All (named) indices indexed by name */
8823 Hash trigHash; /* All triggers indexed by name */
8824 Hash fkeyHash; /* All foreign keys by referenced table name */
8845 ** read into internal hash tables.
8896 ** A hash table for function definitions.
8898 ** Hash each FuncDef structure into one of the FuncDefHash.a[] slots.
8902 FuncDef *a[23]; /* Hash table for functions */
9001 Hash aModule; /* populated by sqlite3_create_module() */
9007 FuncDefHash aFunc; /* Hash table of connection functions */
9008 Hash aCollSeq; /* All collating sequences */
9047 #define SQLITE_InternChanges 0x00000200 /* Uncommitted Hash table changes */
9101 ** hash table. When multiple functions have the same name, the hash table
9114 FuncDef *pHash; /* Next with a different name but the same hash */
9210 ** hash table.
10408 * 1. In the "trigHash" hash table (part of the sqlite3* that represents the
11515 ** Hash table for global functions - functions common to all
12245 Hash hash; /* A set is just a hash table */
12246 HashElem *prev; /* Previously accessed hash elemen */
14059 ** fatal. For example, if a malloc fails while resizing a hash table, this
14061 ** hash table will continue to function normally. So a malloc failure
14062 ** during a hash table resize is a benign fault.
14912 ** Number of freelist hash slots
15002 ** for smaller chunks, or a hash on the block size for larger
15036 u32 size, hash;
15046 hash = size % N_HASH;
15047 memsys3UnlinkFromList(i, &mem3.aiHash[hash]);
15067 ** small chunk list, or into the large chunk hash table.
15070 u32 size, hash;
15080 hash = size % N_HASH;
15081 memsys3LinkIntoList(i, &mem3.aiHash[hash]);
15169 ** or same size hash. In other words, *pRoot is an entry in either
15178 ** linked into the hash tables. That is not the normal state of
15238 ** chunk table or in the large chunk hash table. This is
15248 int hash = nBlock % N_HASH;
15249 for(i=mem3.aiHash[hash]; i>0; i=mem3.aPool[i].u.list.next){
15251 memsys3UnlinkFromList(i, &mem3.aiHash[hash]);
15509 fprintf(out, "hash(%2d):", i);
21024 /************** Begin file hash.c ********************************************/
21036 ** This is the implementation of generic hash-tables
21040 /* Turn bulk memory into a hash table object by initializing the
21041 ** fields of the Hash structure.
21043 ** "pNew" is a pointer to the hash table that is to be initialized.
21045 SQLITE_PRIVATE void sqlite3HashInit(Hash *pNew){
21053 /* Remove all entries from a hash table. Reclaim all memory.
21054 ** Call this routine to delete a hash table or to reset a hash table
21057 SQLITE_PRIVATE void sqlite3HashClear(Hash *pH){
21088 /* Link pNew element into the hash table pH. If pEntry!=0 then also
21089 ** insert pNew into the pEntry hash bucket.
21092 Hash *pH, /* The complete hash table */
21119 /* Resize the hash table so that it cantains "new_size" buckets.
21121 ** The hash table might fail to resize if sqlite3_malloc() fails or
21125 static int rehash(Hash *pH, unsigned int new_size){
21126 struct _ht *new_ht; /* The new hash table */
21136 /* The inability to allocates space for a larger hash table is
21158 ** hash table that matches the given key. The hash for this key has
21162 const Hash *pH, /* The pH to be searched */
21165 unsigned int h /* The hash for this key. */
21187 /* Remove a single entry from the hash table given a pointer to that
21188 ** element and a hash on the element's key.
21191 Hash *pH, /* The pH containing "elem" */
21193 unsigned int h /* Hash value for the element */
21221 /* Attempt to locate an element of the hash
21225 SQLITE_PRIVATE void *sqlite3HashFind(const Hash *pH, const char *pKey, int nKey){
21227 unsigned int h; /* A hash on key */
21241 /* Insert an element into the hash table pH. The key is pKey,nKey
21250 ** the new data is returned and the hash table is unchanged.
21253 ** element corresponding to "key" is removed from the hash table.
21255 SQLITE_PRIVATE void *sqlite3HashInsert(Hash *pH, const char *pKey, int nKey, void *data){
21256 unsigned int h; /* the hash of the key modulo hash table size */
21301 /************** End of hash.c ************************************************/
32477 /* Number of u32 values in hash table. */
32479 /* Maximum number of entries in hash table before
32484 ** (an arbitrary prime)in the hash function provided
32502 ** a hash table that will hold up to BITVEC_MXHASH distinct values.
32523 u32 aHash[BITVEC_NINT]; /* Hash table representation */
32604 /* if there wasn't a hash collision, and this doesn't */
32605 /* completely fill the hash, then just add it without */
32615 /* in hash, if not, try to find a spot for it */
32621 /* we didn't find it in the hash. h points to the first */
32623 /* make our hash too "full". */
32653 ** that BitvecClear can use to rebuilt its hash table.
33463 /* Hash table of all pages. The following variables may only be accessed
33470 PgHdr1 **apHash; /* Hash table for fast lookup by key */
33483 PgHdr1 *pNext; /* Next in hash table chain */
33740 ** This function is used to resize the hash table used by the cache passed
33812 ** Remove the page supplied as an argument from the hash table
34016 /* Search the hash table for an existing entry. */
35948 ** on the cache using a hash function. This is used for testing
35953 ** Return a 32-bit hash of the page data for pPage.
35956 u32 hash = 0;
35959 hash = (hash*1039) + pData[i];
35961 return hash;
35973 ** that the page is either dirty or still matches the calculated page-hash.
36142 ** - 4 bytes: Random number used for page hash.
36204 /* The random check-hash initialiser */
36458 ** Find a page in the hash table given its page number. Return
37028 PAGERTRACE(("PLAYBACK %d page %d hash(%08x) %s\n",
37653 PAGERTRACE(("FETCH %d page %d hash(%08x)\n",
38841 PAGERTRACE(("STORE %d page %d hash(%08x)\n",
40154 PAGERTRACE(("JOURNAL %d page %d needSync=%d hash(%08x)\n",
41136 ** from its hash chain. Also, if the PGHDR_NEED_SYNC flag was set for
41746 ** database page number associated with each wal frame, and a hash-table
41761 ** Even without using the hash table, the last frame for page P
41768 ** The hash table consists of HASHTABLE_NSLOT 16-bit unsigned integers.
41770 ** hash table for each page number in the mapping section, so the hash
41772 ** prior to finding a match is 1. Each entry of the hash table is an
41777 ** K will be (mxFrame%HASHTABLE_NPAGE).) Unused slots of the hash table
41780 ** To look for page P in the hash table, first compute a hash iKey on
41785 ** Then start scanning entries of the hash table, starting with iKey
41786 ** (wrapping around to the beginning when the end of the hash table is
41787 ** reached) until an unused hash slot is found. Let the first unused slot
41789 ** wrap-around.) Because the hash table is never more than half full,
41793 ** no hash slot such that aHash[i]==p) then page P is not in the
41798 ** A hash search begins with the last index block and moves toward the
41813 ** Both readers can use the same hash table and mapping section to get
41814 ** the correct result. There may be entries in the hash table with
41816 ** slots in the hash table and so the first reader will get an answer as
41817 ** if no values greater than K0 had ever been inserted into the hash table
41822 ** When a rollback occurs, the value of K is decreased. Hash table entries
41824 ** from the hash table at this point.
42022 ** Each page of the wal-index mapping contains a hash-table made up of
42055 ** Define the parameters of the hash tables in the wal-index file. There
42056 ** is a hash-table following every HASHTABLE_NPAGE page numbers in the
42067 ** The block of page numbers associated with the first hash-table in a
42069 ** hash-table on each aligned 32KB page of the wal-index.
42375 ** Compute a hash on a page number. The resulting hash value must land
42377 ** the hash to the next value in the event of a collision.
42389 ** Return pointers to the hash table and page number array stored on
42393 ** Set output variable *paHash to point to the start of the hash table
42395 ** number of the first frame indexed by this hash table. If a
42396 ** slot in the hash table is set to N, it refers to frame number
42400 ** first frame indexed by the hash table, frame (*piZero+1).
42405 volatile ht_slot **paHash, /* OUT: Pointer to hash index */
42435 ** Return the number of the wal-index page that contains the hash-table
42463 ** Remove entries from the hash table that point to WAL slots greater
42469 ** At most only the hash table containing pWal->hdr.mxFrame needs to be
42470 ** updated. Any later hash tables will be automatically cleared when
42471 ** pWal->hdr.mxFrame advances to the point where those hash tables are
42475 volatile ht_slot *aHash = 0; /* Pointer to hash table to clear */
42476 volatile u32 *aPgno = 0; /* Page number array for hash table */
42489 /* Obtain pointers to the hash-table and page-number array containing
42491 ** that the page said hash-table and array reside on is already mapped.
42497 /* Zero all hash-table entries that correspond to frame numbers greater
42516 ** via the hash table even after the cleanup.
42520 int iKey; /* Hash key */
42540 volatile ht_slot *aHash = 0; /* Hash table */
42545 ** page number array and hash table entry.
42548 int iKey; /* Hash table key */
42549 int idx; /* Value to write to hash-table slot */
42550 int nCollide; /* Number of hash collisions */
42555 /* If this is the first entry to be added to this hash-table, zero the
42556 ** entire hash table and aPgno[] array before proceding.
42567 ** the hash-table before writing any new entries.
42574 /* Write the aPgno[] array entry and the hash-table slot. */
42583 /* Verify that the number of entries in the hash table exactly equals
42588 int nEntry = 0; /* Number of entries in the hash table */
42594 ** via the hash table. This turns out to be a really, really expensive
43723 int iHash; /* Used to loop through N hash tables */
43739 /* Search the hash table or tables for an entry matching page number
43741 ** hash table (each hash table indexes up to HASHTABLE_NPAGE frames).
43744 ** that adds entries to the wal-index (and possibly to this hash
43745 ** table). This means the value just read from the hash
43755 ** if we had exclusive access to the hash-table:
43758 ** This condition filters out normal hash-table collisions.
43761 ** This condition filters out entries that were added to the hash
43765 volatile ht_slot *aHash; /* Pointer to hash table */
43768 int iKey; /* Hash slot index */
43769 int nCollide; /* Number of hash collisions remaining */
43792 ** result obtained using the hash indexes above. */
65170 ** of that table into the internal index hash table. This will cause
73730 ** be loaded into internal hash tables where is can be used.
74174 ** hash tables.
75216 ** the index hash table and free all memory structures associated
75222 Hash *pHash = &db->aDb[iDb].pSchema->idxHash;
75245 ** Erase all schema information from the in-memory hash tables of
75278 ** schema hash tables and therefore do not have to make any changes
75334 ** the table data structure from the hash table. But it does destroy
75380 ** Unlink the given table from the hash tables and the delete the
76265 ** is added to the internal hash tables, assuming no errors have
76695 Hash *pHash;
78563 ** This file contains functions used to access the internal hash tables
78686 ** Locate and return an entry from the db.aCollSeq hash table. If the entry
78690 ** Each pointer stored in the sqlite3.aCollSeq hash table contains an
78723 ** to the hash table).
78815 FuncDefHash *pHash, /* Hash table to search */
78816 int h, /* Hash of the name */
78830 ** Insert a new FuncDef into a FuncDefHash hash table.
78833 FuncDefHash *pHash, /* The hash table into which to insert */
78885 int h; /* Hash value */
78931 ** new entry to the hash table and return it.
78953 ** of the schema hash tables).
78958 Hash temp1;
78959 Hash temp2;
81137 ** to the global function hash table. This occurs at start-time (as
82389 ** hash table.
82397 /* Remove the FK from the fkeyHash hash table. */
86576 Hash *pTbls;
92781 Hash *pHash = &db->aDb[iDb].pSchema->trigHash;
93051 ** Remove a trigger from the hash tables of the sqlite* pointer.
93054 Hash *pHash = &(db->aDb[iDb].pSchema->trigHash);
100366 ** number is used to fill in empty slots of the hash
100485 ** yy_action. Used to detect hash collisions.
103713 ** might be implemented more directly using a hand-written hash table.
103718 /* Hash score: 175 */
105458 HashElem *i; /* Hash table iterator */
105829 ** to the hash table.
108257 ** This is the header file for the generic hash-table implemenation
108259 ** hash table implementation for the full-text indexing module.
108269 /* A complete hash table is an instance of the following structure.
108282 int htsize; /* Number of buckets in the hash table */
108283 struct _fts3ht { /* the hash table */
108284 int count; /* Number of entries with this hash */
108285 Fts3HashElem *chain; /* Pointer to first entry with this hash */
108289 /* Each element in the hash table is an instance of the following
108302 ** There are 2 different modes of operation for a hash table:
108335 ** Macros for looping over all elements of a hash table. The idiom is
108353 ** Number of entries in a hash table
108371 ** Fts3Table.pendingTerms hash table. Normally, the hash table is
108375 ** segment is created and the hash table cleared immediately.
108476 /* The following hash table is used to buffer pending index updates during
108478 ** pending data, including hash table overhead, but not malloc overhead.
109070 void *pAux, /* Hash table containing tokenizers */
109253 void *pAux, /* Pointer to tokenizer hash table */
109263 void *pAux, /* Pointer to tokenizer hash table */
111418 ** hash-table to the database.
111437 ** the pending-terms hash-table have already been flushed into the database
111448 ** hash-table. Any changes made to the database are reverted by SQLite.
111789 ** allocated for the tokenizer hash table.
111833 /* Allocate and initialise the hash-table used to store tokenizers. */
111841 /* Load the built-in tokenizers into the hash table */
111859 /* Create the virtual table wrapper around the hash-table and overload
111885 /* An error has occurred. Delete the hash table and return the error code. */
112664 ** Function to query the hash-table of tokenizers (see README.tokenizers).
112856 ** This is the implementation of generic hash-tables used in SQLite.
112857 ** We've modified it slightly to serve as a standalone hash table
112888 /* Turn bulk memory into a hash table object by initializing the
112889 ** fields of the Hash structure.
112891 ** "pNew" is a pointer to the hash table that is to be initialized.
112894 ** determines what kind of key the hash table will use. "copyKey" is
112895 ** true if the hash table should make its own private copy of keys and
112909 /* Remove all entries from a hash table. Reclaim all memory.
112910 ** Call this routine to delete a hash table or to reset a hash table
112934 ** Hash and comparison functions when the mode is FTS3_HASH_STRING
112952 ** Hash and comparison functions when the mode is FTS3_HASH_BINARY
112968 ** Return a pointer to the appropriate hash function given the key class.
112989 ** Return a pointer to the appropriate hash function given the key class.
113003 /* Link an element into the hash table
113006 Fts3Hash *pH, /* The complete hash table */
113029 /* Resize the hash table so that it cantains "new_size" buckets.
113030 ** "new_size" must be a power of 2. The hash table might fail
113036 struct _fts3ht *new_ht; /* The new hash table */
113038 int (*xHash)(const void*,int); /* The hash function */
113056 ** hash table that matches the given key. The hash for this key has
113063 int h /* The hash for this key. */
113084 /* Remove a single entry from the hash table given a pointer to that
113085 ** element and a hash on the element's key.
113090 int h /* Hash value for the element */
113126 int h; /* A hash on key */
113127 int (*xHash)(const void*,int); /* The hash function */
113138 ** Attempt to locate an element of the hash table pH with a key
113149 /* Insert an element into the hash table pH. The key is pKey,nKey
113159 ** the new data is returned and the hash table is unchanged.
113162 ** element corresponding to "key" is removed from the hash table.
113165 Fts3Hash *pH, /* The hash table to insert into */
113170 int hraw; /* Raw hash value of the key */
113171 int h; /* the hash of the key modulo hash table size */
113174 int (*xHash)(const void*,int); /* The hash function */
113903 ** hash table. This function may be called as follows:
113912 ** containing a pointer to be stored as the hash data corresponding
113918 ** is a blob containing the pointer stored as the hash data corresponding
113919 ** to string <key-name> (after the hash-table is updated, if applicable).
114016 Fts3Hash *pHash, /* Tokenizer hash table */
114295 ** the hash table pointed to by argument pHash. The hash table must
114630 ** Data structure used while accumulating terms in the pending-terms hash
114631 ** table. The hash table entry maps from term (a string) to a malloc'd
115105 ** pending-terms hash-table. The docid used is that currently stored in
115200 ** Discard the contents of the pending-terms hash table.
115214 ** pendingTerms hash table.
115302 ** Remove all data from the FTS3 table. Clear the hash table containing
115308 /* Discard the contents of the pending-terms hash table. */
115795 ** the contents of the pending-terms hash table to the database.
115823 Fts3HashElem **aElem = 0; /* Array of term hash entries to scan */
116680 ** of the pending-terms hash table to the database.
116992 Fts3SegReader *pReader = 0; /* Used to iterate through the hash table */
117010 ** pending-terms hash table using the Fts3SegReader iterator. The callback
117409 ** data in the pendingTerms hash table.
117454 ** Flush any data in the pending-terms hash table to disk. If successful,
119250 /* Size of hash table Rtree.aHash. This hash table is not expected to
119268 RtreeNode *aHash[HASHSIZE]; /* Hash table of in-memory nodes. */
119272 ** linked together via the pointer normally used for hash chains -
119379 RtreeNode *pNext; /* Next node in this hash chain */
119523 ** Search the node hash table for node iNode. If found, return a pointer
119533 ** Add node pNode to the node hash table.
119544 ** Remove node pNode from the node hash table.
119590 /* Check if the requested node is already in the hash table. If so,
121522 /* Remove the node from the in-memory hash table and link it into
