Lines Matching defs:hash
451 ** or SHA3-256 hash of the entire source tree. If the source code has
453 ** four hexadecimal digits of the hash may be modified.
491 ** of the hash might be different from [SQLITE_SOURCE_ID].)^
13886 /************** Include hash.h in the middle of sqliteInt.h ******************/
13887 /************** Begin file hash.h ********************************************/
13899 ** This is the header file for the generic hash-table implementation
13909 /* A complete hash table is an instance of the following structure.
13917 ** All elements of the hash table are on a single doubly-linked list.
13928 ** the hash table.
13931 unsigned int htsize; /* Number of buckets in the hash table */
13934 struct _ht { /* the hash table */
13935 unsigned int count; /* Number of entries with this hash */
13936 HashElem *chain; /* Pointer to first entry with this hash */
13940 /* Each element in the hash table is an instance of the following
13961 ** Macros for looping over all elements of a hash table. The idiom is
13979 ** Number of entries in a hash table
13985 /************** End of hash.h ************************************************/
14655 ** The LEGACY names are stored in the internal symbol hash table
15485 #define BTREE_UNORDERED 8 /* Use of a hash implementation is OK */
16840 ** read into internal hash tables.
16936 ** A hash table for built-in function definitions. (Application-defined
16937 ** functions use a regular table table from hash.h.)
16941 ** macro to compute a hash on the function name.
17302 ** structure is held in the db->aHash hash table.
17318 FuncDef *pHash; /* Next with a different name but the same hash */
17538 ** hash table.
17580 u8 hName; /* Column name hash for faster lookup */
17898 ** is held in Schema.fkeyHash with a hash key of Z.
19299 ** 1. In the "trigHash" hash table (part of the sqlite3* that represents the
25334 ** fatal. For example, if a malloc fails while resizing a hash table, this
25336 ** hash table will continue to function normally. So a malloc failure
25337 ** during a hash table resize is a benign fault.
26334 ** Number of freelist hash slots
26424 ** for smaller chunks, or a hash on the block size for larger
26458 u32 size, hash;
26468 hash = size % N_HASH;
26469 memsys3UnlinkFromList(i, &mem3.aiHash[hash]);
26489 ** small chunk list, or into the large chunk hash table.
26492 u32 size, hash;
26502 hash = size % N_HASH;
26503 memsys3LinkIntoList(i, &mem3.aiHash[hash]);
26591 ** or same size hash. In other words, *pRoot is an entry in either
26600 ** linked into the hash tables. That is not the normal state of
26660 ** chunk table or in the large chunk hash table. This is
26670 int hash = nBlock % N_HASH;
26671 for(i=mem3.aiHash[hash]; i>0; i=mem3.aPool[i].u.list.next){
26673 memsys3UnlinkFromList(i, &mem3.aiHash[hash]);
26931 fprintf(out, "hash(%2d):", i);
33956 ** Compute an 8-bit hash on a string that is insensitive to case differences
35317 /************** Begin file hash.c ********************************************/
35329 ** This is the implementation of generic hash-tables
35335 /* Turn bulk memory into a hash table object by initializing the
35338 ** "pNew" is a pointer to the hash table that is to be initialized.
35348 /* Remove all entries from a hash table. Reclaim all memory.
35349 ** Call this routine to delete a hash table or to reset a hash table
35386 /* Link pNew element into the hash table pH. If pEntry!=0 then also
35387 ** insert pNew into the pEntry hash bucket.
35390 Hash *pH, /* The complete hash table */
35417 /* Resize the hash table so that it cantains "new_size" buckets.
35419 ** The hash table might fail to resize if sqlite3_malloc() fails or
35424 struct _ht *new_ht; /* The new hash table */
35434 /* The inability to allocates space for a larger hash table is
35439 ** use the actual amount of space allocated for the hash table (which
35460 ** hash table that matches the given key. If no element is found,
35462 ** If pH is not NULL, then the hash for this key is written to *pH.
35467 unsigned int *pHash /* Write the hash value here */
35471 unsigned int h; /* The computed hash */
35496 /* Remove a single entry from the hash table given a pointer to that
35497 ** element and a hash on the element's key.
35530 /* Attempt to locate an element of the hash table pH with a key
35540 /* Insert an element into the hash table pH. The key is pKey
35549 ** the new data is returned and the hash table is unchanged.
35552 ** element corresponding to "key" is removed from the hash table.
35555 unsigned int h; /* the hash of the key modulo hash table size */
35588 /************** End of hash.c ************************************************/
52254 /* Number of u32 values in hash table. */
52256 /* Maximum number of entries in hash table before
52261 ** (an arbitrary prime)in the hash function provided
52279 ** a hash table that will hold up to BITVEC_MXHASH distinct values.
52384 /* if there wasn't a hash collision, and this doesn't */
52385 /* completely fill the hash, then just add it without */
52395 /* in hash, if not, try to find a spot for it */
52401 /* we didn't find it in the hash. h points to the first */
52403 /* make our hash too "full". */
52433 ** that BitvecClear can use to rebuilt its hash table.
53656 PgHdr1 *pNext; /* Next in hash table chain */
54066 ** This function is used to resize the hash table used by the cache passed
54131 ** Remove the page supplied as an argument from the hash table
54191 ** cache, then there is no point in scanning the entire hash table.
54192 ** Only scan those hash slots that might contain pages that need to
54199 ** It is necessary to scan the entire hash table */
54544 /* Step 1: Search the hash table for an existing entry. */
54548 /* Step 2: If the page was found in the hash table, then return it.
54549 ** If the page was not in the hash table and createFlag is 0, abort.
54550 ** Otherwise (page not in hash and createFlag!=0) continue with
56743 ** on the cache using a hash function. This is used for testing
56748 ** Return a 32-bit hash of the page data for pPage.
56751 u32 hash = 0;
56754 hash = (hash*1039) + pData[i];
56756 return hash;
56768 ** that the page is either dirty or still matches the calculated page-hash.
56941 ** - 4 bytes: Random number used for page hash.
57003 /* The random check-hash initializer */
57901 PAGERTRACE(("PLAYBACK %d page %d hash(%08x) %s\n",
58580 PAGERTRACE(("FETCH %d page %d hash(%08x)\n",
60000 PAGERTRACE(("STORE %d page %d hash(%08x)\n",
61533 PAGERTRACE(("JOURNAL %d page %d needSync=%d hash(%08x)\n",
62760 ** from its hash chain. Also, if the PGHDR_NEED_SYNC flag was set for
63531 ** database page number associated with each wal frame, and a hash-table
63546 ** Even without using the hash table, the last frame for page P
63553 ** The hash table consists of HASHTABLE_NSLOT 16-bit unsigned integers.
63555 ** hash table for each page number in the mapping section, so the hash
63557 ** prior to finding a match is 1. Each entry of the hash table is an
63562 ** K will be (mxFrame%HASHTABLE_NPAGE).) Unused slots of the hash table
63565 ** To look for page P in the hash table, first compute a hash iKey on
63570 ** Then start scanning entries of the hash table, starting with iKey
63571 ** (wrapping around to the beginning when the end of the hash table is
63572 ** reached) until an unused hash slot is found. Let the first unused slot
63574 ** wrap-around.) Because the hash table is never more than half full,
63578 ** no hash slot such that aHash[i]==p) then page P is not in the
63583 ** A hash search begins with the last index block and moves toward the
63598 ** Both readers can use the same hash table and mapping section to get
63599 ** the correct result. There may be entries in the hash table with
63601 ** slots in the hash table and so the first reader will get an answer as
63602 ** if no values greater than K0 had ever been inserted into the hash table
63609 ** from the hash table at this point.
63918 ** Each page of the wal-index mapping contains a hash-table made up of
63951 ** Define the parameters of the hash tables in the wal-index file. There
63952 ** is a hash-table following every HASHTABLE_NPAGE page numbers in the
63963 ** The block of page numbers associated with the first hash-table in a
63965 ** hash-table on each aligned 32KB page of the wal-index.
64328 ** Compute a hash on a page number. The resulting hash value must land
64330 ** the hash to the next value in the event of a collision.
64343 ** of a page hash table in the wal-index. This becomes the return value
64348 volatile ht_slot *aHash; /* Start of the wal-index hash table */
64354 ** Return pointers to the hash table and page number array stored on
64358 ** Set output variable pLoc->aHash to point to the start of the hash table
64360 ** number of the first frame indexed by this hash table. If a
64361 ** slot in the hash table is set to N, it refers to frame number
64365 ** first frame indexed by the hash table, frame (pLoc->iZero).
64392 ** Return the number of the wal-index page that contains the hash-table
64421 ** Remove entries from the hash table that point to WAL slots greater
64427 ** At most only the hash table containing pWal->hdr.mxFrame needs to be
64428 ** updated. Any later hash tables will be automatically cleared when
64429 ** pWal->hdr.mxFrame advances to the point where those hash tables are
64445 /* Obtain pointers to the hash-table and page-number array containing
64447 ** that the page said hash-table and array reside on is already mapped.(1)
64454 /* Zero all hash-table entries that correspond to frame numbers greater
64474 ** via the hash table even after the cleanup.
64496 WalHashLoc sLoc; /* Wal-index hash table location */
64501 ** page number array and hash table entry.
64505 int idx; /* Value to write to hash-table slot */
64506 int nCollide; /* Number of hash collisions */
64511 /* If this is the first entry to be added to this hash-table, zero the
64512 ** entire hash table and aPgno[] array before proceeding.
64524 ** the hash-table before writing any new entries.
64531 /* Write the aPgno[] array entry and the hash-table slot. */
64540 /* Verify that the number of entries in the hash table exactly equals
64545 int nEntry = 0; /* Number of entries in the hash table */
64551 ** via the hash table. This turns out to be a really, really expensive
64616 u32 *aPrivate = 0; /* Heap copy of *-shm hash being populated */
66511 int iHash; /* Used to loop through N hash tables */
66528 /* Search the hash table or tables for an entry matching page number
66530 ** hash table (each hash table indexes up to HASHTABLE_NPAGE frames).
66533 ** that adds entries to the wal-index (and possibly to this hash
66534 ** table). This means the value just read from the hash
66544 ** if we had exclusive access to the hash-table:
66547 ** This condition filters out normal hash-table collisions.
66550 ** This condition filters out entries that were added to the hash
66557 int nCollide; /* Number of hash collisions remaining */
66584 ** result obtained using the hash indexes above. */
90999 ** Compute a bloom filter hash using pOp->p4.i registers from aMem[] beginning
91000 ** with pOp->p3. Return the hash.
97238 ** of that table into the internal index hash table. This will cause
98854 ** Compute a hash on the P4 registers starting with r[P3] and
98855 ** add that hash to the bloom filter contained in r[P1].
98871 printf("hash: %llu modulo %d -> %u\n", h, pIn1->n, (int)(h%pIn1->n));
98882 ** Compute a hash on the key contained in the P4 registers starting
98883 ** with r[P3]. Check to see if that hash is found in the
98907 printf("hash: %llu modulo %d -> %u\n", h, pIn1->n, (int)(h%pIn1->n));
114884 u32 iHash; /* Tiebreaker hash */
115108 ** considering only any trailing columns and the sample hash value, this
115936 ** be loaded into internal hash tables where is can be used.
116685 ** hash tables.
118034 ** the index hash table and free all memory structures associated
118260 ** the table data structure from the hash table. But it does destroy
118338 ** Unlink the given table from the hash tables and the delete the
120073 ** is added to the internal hash tables, assuming no errors have
123168 ** This file contains functions used to access the internal hash tables
123250 ** Locate and return an entry from the db.aCollSeq hash table. If the entry
123254 ** Each pointer stored in the sqlite3.aCollSeq hash table contains an
123286 ** to the hash table).
123504 ** Insert a new FuncDef into a FuncDefHash hash table.
123608 ** new entry to the hash table and return it.
123639 ** of the schema hash tables).
126939 ** to the global function hash table. This occurs at start-time (as
128559 ** hash table.
128570 /* Remove the FK from the fkeyHash hash table. */
135495 ** for a table, that can potentially disrupt the hash table, so restart
147064 ** Remove a trigger from the hash tables of the sqlite* pointer.
166815 ** yy_action. Used to detect hash collisions.
171836 ** might be implemented more directly using a hand-written hash table.
171894 /* aKWHash[i] is the hash value for the i-th keyword */
171907 /* aKWNext[] forms the hash collision chain. If aKWHash[i]==0
171908 ** then the i-th keyword has no more hash collisions. Otherwise,
171909 ** the next keyword with the same hash is aKWHash[i]-1. */
173521 ** the hash might be different from SQLITE_SOURCE_ID.
175289 ** to the hash table.
179218 ** This is the header file for the generic hash-table implementation
179220 ** hash table implementation for the full-text indexing module.
179230 /* A complete hash table is an instance of the following structure.
179243 int htsize; /* Number of buckets in the hash table */
179244 struct _fts3ht { /* the hash table */
179245 int count; /* Number of entries with this hash */
179246 Fts3HashElem *chain; /* Pointer to first entry with this hash */
179250 /* Each element in the hash table is an instance of the following
179263 ** There are 2 different modes of operation for a hash table:
179296 ** Macros for looping over all elements of a hash table. The idiom is
179314 ** Number of entries in a hash table
179344 ** Fts3Table.pendingTerms hash table. Normally, the hash table is
179348 ** segment is created and the hash table cleared immediately.
179545 ** The following array of hash tables is used to buffer pending index
179556 ** pending data structures, including hash table overhead, but not including
179557 ** malloc overhead. When nPendingData exceeds nMaxPendingData, all hash
179954 Fts3Hash hash; /* Hash table */
180822 Fts3Hash *pHash = &((Fts3HashWrapper*)pAux)->hash;
181199 void *pAux, /* Pointer to tokenizer hash table */
181209 void *pAux, /* Pointer to tokenizer hash table */
183157 ** hash-table to the database.
183249 ** the pending-terms hash-table have already been flushed into the database
183265 ** hash-table. Any changes made to the database are reverted by SQLite.
183654 ** allocated for the tokenizer hash table.
183660 sqlite3Fts3HashClear(&pHash->hash);
183719 /* Allocate and initialize the hash-table used to store tokenizers. */
183724 sqlite3Fts3HashInit(&pHash->hash, FTS3_HASH_STRING, 1);
183728 /* Load the built-in tokenizers into the hash table */
183730 if( sqlite3Fts3HashInsert(&pHash->hash, "simple", 7, (void *)pSimple)
183731 || sqlite3Fts3HashInsert(&pHash->hash, "porter", 7, (void *)pPorter)
183734 || sqlite3Fts3HashInsert(&pHash->hash, "unicode61", 10, (void *)pUnicode)
183737 || (pIcu && sqlite3Fts3HashInsert(&pHash->hash, "icu", 4, (void *)pIcu))
183746 rc = sqlite3Fts3ExprInitTestInterface(db, &pHash->hash);
183750 /* Create the virtual table wrapper around the hash-table and overload
183755 && SQLITE_OK==(rc=sqlite3Fts3InitHashTable(db,&pHash->hash,"fts3_tokenizer"))
183780 /* An error has occurred. Delete the hash table and return the error code. */
183783 sqlite3Fts3HashClear(&pHash->hash);
187627 ** This is the implementation of generic hash-tables used in SQLite.
187628 ** We've modified it slightly to serve as a standalone hash table
187664 /* Turn bulk memory into a hash table object by initializing the
187667 ** "pNew" is a pointer to the hash table that is to be initialized.
187670 ** determines what kind of key the hash table will use. "copyKey" is
187671 ** true if the hash table should make its own private copy of keys and
187685 /* Remove all entries from a hash table. Reclaim all memory.
187686 ** Call this routine to delete a hash table or to reset a hash table
187744 ** Return a pointer to the appropriate hash function given the key class.
187765 ** Return a pointer to the appropriate hash function given the key class.
187779 /* Link an element into the hash table
187782 Fts3Hash *pH, /* The complete hash table */
187805 /* Resize the hash table so that it cantains "new_size" buckets.
187806 ** "new_size" must be a power of 2. The hash table might fail
187812 struct _fts3ht *new_ht; /* The new hash table */
187814 int (*xHash)(const void*,int); /* The hash function */
187832 ** hash table that matches the given key. The hash for this key has
187839 int h /* The hash for this key. */
187860 /* Remove a single entry from the hash table given a pointer to that
187861 ** element and a hash on the element's key.
187902 int h; /* A hash on key */
187903 int (*xHash)(const void*,int); /* The hash function */
187914 ** Attempt to locate an element of the hash table pH with a key
187925 /* Insert an element into the hash table pH. The key is pKey,nKey
187935 ** the new data is returned and the hash table is unchanged.
187938 ** element corresponding to "key" is removed from the hash table.
187941 Fts3Hash *pH, /* The hash table to insert into */
187946 int hraw; /* Raw hash value of the key */
187947 int h; /* the hash of the key modulo hash table size */
187950 int (*xHash)(const void*,int); /* The hash function */
188712 ** hash table. This function may be called as follows:
188721 ** containing a pointer to be stored as the hash data corresponding
188727 ** is a blob containing the pointer stored as the hash data corresponding
188728 ** to string <key-name> (after the hash-table is updated, if applicable).
188832 Fts3Hash *pHash, /* Tokenizer hash table */
189128 ** the hash table pointed to by argument pHash. The hash table must
190635 ** Add an entry to one of the pending-terms hash tables.
190641 Fts3Hash *pHash, /* Pending terms hash table to add entry to */
190670 ** pending-terms hash-table. The docid used is that currently stored in
190700 ** zText==0. In this case, add zero token entries to the hash table and
190783 ** Discard the contents of the pending-terms hash tables.
190802 ** pendingTerms hash table.
190913 ** Remove all data from the FTS3 table. Clear the hash table containing
190919 /* Discard the contents of the pending-terms hash table. */
191552 ** the contents of the pending-terms hash table to the database.
191578 ** the pending terms hash table contains the terms "sqlite", "mysql" and
191600 Fts3HashElem **aElem = 0; /* Array of term hash entries to scan */
191641 ** the index. All that is required is a straight hash-lookup.
195508 ** data in the pendingTerms hash table. */
195680 ** Flush any data in the pending-terms hash table to disk. If successful,
201072 /* Size of hash table Rtree.aHash. This hash table is not expected to
201117 ** linked together via the pointer normally used for hash chains -
201311 RtreeNode *pNext; /* Next node in this hash collision chain */
201574 ** Search the node hash table for node iNode. If found, return a pointer
201584 ** Add node pNode to the node hash table.
201595 ** Remove node pNode from the node hash table.
201651 /* Check if the requested node is already in the hash table. If so,
203746 /* Remove the node from the in-memory hash table and link it into
215627 ** The keys of the SessionTable.aChange[] hash table are all rows that have
215631 ** The data associated with each hash-table entry is a structure containing
215642 int nEntry; /* Total number of entries in hash table */
215808 ** this structure stored in a SessionTable.aChange[] hash table.
215816 SessionChange *pNext; /* For hash-table collisions */
215976 ** This macro is used to calculate hash key values for data structures. In
215978 ** as a series of unsigned integers. In order to calculate a hash-key value
215990 #define HASH_APPEND(hash, add) ((hash) << 3) ^ (hash) ^ (unsigned int)(add)
215993 ** Append the hash of the 64-bit integer passed as the second argument to the
215994 ** hash-key value passed as the first. Return the new hash-key value.
216002 ** Append the hash of the blob passed via the second and third arguments to
216003 ** the hash-key value passed as the first. Return the new hash-key value.
216012 ** Append the hash of the data type passed as the second argument to the
216013 ** hash-key value passed as the first. Return the new hash-key value.
216021 ** It calculates a hash based on the primary key values of the old.* or
216033 int bNew, /* True to hash the new.* PK */
216106 ** hash key. Assume the has table has nBucket buckets. The hash keys
216117 int nBucket /* Assume this many buckets in hash table */
216431 ** If required, grow the hash table used to store changes on table pTab
216437 ** that case the hash-table does not grow, but SQLITE_OK is returned anyway.
216438 ** Growing the hash table in this case is a performance optimization only,
216813 ** to the changed-rows hash table associated with table pTab.
216837 /* Grow the hash table if required */
216862 /* Calculate the hash-key for this change. If the primary key of the row
216869 /* Search the hash table for an existing record for this row. */
216928 /* Add the change to the hash-table */
217383 ** of the changed-rows hash tables are also deleted.
217429 ** associated hash-tables. */
218092 int i; /* Used to iterate through hash buckets */
220482 int bRebase, /* True for a rebase hash-table */
220660 ** the first argument to the changegroup hash tables.
220665 int bRebase /* True if hash table is for rebasing */
220734 /* Search for existing entry. If found, remove it from the hash table.
220798 ** hash tables attached to the SessionTable objects in list p->pList.
221106 sqlite3_rebaser *p, /* Rebaser hash table */
222136 int nHashSize; /* Bytes of memory for in-memory hash */
222412 ** Flush any data stored in the in-memory hash tables to the database.
222418 ** Discard any data stored in the in-memory hash tables. Do not write it
222522 ** Create a hash table, free a hash table.
222537 ** Empty (but do not delete) a hash table.
223031 ** fts5yy_action. Used to detect hash collisions.
225353 u32 hash = 13;
225356 /* Calculate a hash value for this term. This is the same hash checksum
225359 ** designed to produce hash table collisions really do work. */
225361 hash = (hash << 3) ^ hash ^ pTerm[i];
225363 hash = (hash << 3) ^ hash ^ iIdx;
225364 hash = hash % ArraySize(p->apHash);
225366 for(pEntry=p->apHash[hash]; pEntry; pEntry=pEntry->pNext){
225383 pEntry->pNext = p->apHash[hash];
225384 p->apHash[hash] = pEntry;
229466 ** This file contains the implementation of an in-memory hash table used
229475 int nEntry; /* Number of entries currently in hash */
229478 Fts5HashEntry **aSlot; /* Array of hash slots */
229482 ** Each entry in the hash table is represented by an object of the
229504 Fts5HashEntry *pHashNext; /* Next hash entry with same hash-key */
229527 ** Allocate a new hash table.
229557 ** Free a hash table object.
229568 ** Empty (but do not delete) a hash table.
229604 ** Resize the hash table by doubling the number of slots.
229678 ** Add an entry to the in-memory hash table. The key is the concatenation
229701 /* Attempt to locate an existing hash entry */
229713 /* If an existing hash entry cannot be found, create a new one. */
229727 /* Allocate new Fts5HashEntry and add it to the hash table. */
229743 /* Add the first rowid field to the hash-entry */
229755 /* Appending to an existing hash-entry. Check that there is enough
229834 ** Arguments pLeft and pRight point to linked-lists of hash-entry objects,
229879 ** Extract all tokens from hash table iHash and link them into a list
229880 ** in sorted order. The hash table is cleared before returning. It is
229929 ** Query the hash table for a doclist associated with term pTerm/nTerm.
230289 ** in-memory hash tables before they are flushed to disk.
232509 ** in-memory hash table. If there is no such term in the hash-table, the
233496 /* Add a segment iterator for the current contents of the hash table. */
233707 ** Discard all data currently cached in the hash-tables.
234572 ** Flush the contents of in-memory hash table iHash to a new level-0
234608 /* Begin scanning through hash table entries. This loop runs once for each
234609 ** term/doclist currently stored within the hash table. */
234730 ** Flush any data stored in the in-memory hash tables to the database.
234733 /* Unless it is empty, flush the hash table to disk */
235345 /* Allocate the hash table if it has not already been allocated */
235350 /* Flush the hash table to disk if required */
235374 ** Discard any data stored in the in-memory hash tables. Do not write it
235966 ** This check may only be performed if the hash table is empty. This
235967 ** is because the hash table only supports a single scan query at
237252 void *pAux, /* Pointer to tokenizer hash table */
237262 void *pAux, /* Pointer to tokenizer hash table */
238592 ** the pending-terms hash-table have already been flushed into the database
238603 ** hash-table. Any changes made to the database are reverted by SQLite.
243697 void *pAux, /* Pointer to tokenizer hash table */
243707 void *pAux, /* Pointer to tokenizer hash table */