Lines Matching refs:trie
106 // Interface functions for int TRIE
108 static pANTLR3_TRIE_ENTRY intTrieGet (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key);
109 static ANTLR3_BOOLEAN intTrieDel (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key);
110 static ANTLR3_BOOLEAN intTrieAdd (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key, ANTLR3_UINT32 type, ANTLR3_INTKEY intType, void * data, void (ANTLR3_CDECL *freeptr)(void *));
111 static void intTrieFree (pANTLR3_INT_TRIE trie);
1698 * patricia trie are usually a lot lower than the 64 bits we
1735 /** Rather than use the bit index of a trie node to shift
1740 * cache while ever a trie is in heavy use, such as in
1763 /* INT TRIE Implementation of depth 64 bits, being the number of bits
1770 pANTLR3_INT_TRIE trie;
1772 trie = (pANTLR3_INT_TRIE) ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE)); /* Base memory required */
1774 if (trie == NULL)
1783 trie->root = (pANTLR3_INT_TRIE_NODE) ANTLR3_CALLOC(1, sizeof(ANTLR3_INT_TRIE));
1785 if (trie->root == NULL)
1787 ANTLR3_FREE(trie);
1791 trie->add = intTrieAdd;
1792 trie->del = intTrieDel;
1793 trie->free = intTrieFree;
1794 trie->get = intTrieGet;
1798 * keys in the trie. This is the trie 'depth'. The limit for
1801 trie->root->bitNum = depth;
1806 trie->root->leftN = trie->root;
1807 trie->root->rightN = trie->root;
1808 trie->count = 0;
1814 return trie;
1817 /** Search the int Trie and return a pointer to the first bucket indexed
1818 * by the key if it is contained in the trie, otherwise NULL.
1821 intTrieGet (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key)
1826 if (trie->count == 0)
1828 return NULL; /* Nothing in this trie yet */
1830 /* Starting at the root node in the trie, compare the bit index
1833 * then by definition (as the bit index decreases as we descent the trie)
1837 * means the entry was not in the trie, and we return NULL. A backward pointer
1841 thisNode = trie->root; /* Start at the root node */
1870 * we wanted, or if that key is not in the trie it is another key
1873 * to the trie.
1885 return NULL; /* That key is not in the trie (note that we set the pointer to -1 if no payload) */
1891 intTrieDel (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key)
1895 p=trie->root;
1901 /** Add an entry into the INT trie.
1902 * Basically we descend the trie as we do when searching it, which will
1903 * locate the only node in the trie that can be reached by the bit pattern of the
1904 * key. If the key is actually at that node, then if the trie accepts duplicates
1907 * whether the key was already in the trie.
1909 * into the trie with a bit index of the leftmost differing bit and the left or right
1913 intTrieAdd (pANTLR3_INT_TRIE trie, ANTLR3_INTKEY key, ANTLR3_UINT32 type, ANTLR3_INTKEY intVal, void * data, void (ANTLR3_CDECL *freeptr)(void *))
1923 /* Cache the bit depth of this trie, which is always the highest index,
1926 depth = trie->root->bitNum;
1928 thisNode = trie->root; /* Start with the root node */
1929 nextNode = trie->root->leftN; /* And assume we start to the left */
1960 * if this trie accepts duplicate keys.
1962 if (trie->allowDups ==ANTLR3_TRUE)
1999 trie->count++;
2005 * trie.
2085 thisNode = trie->root;
2086 entNode = trie->root->leftN;
2181 trie->count++;
2249 intTrieFree (pANTLR3_INT_TRIE trie)
2253 freeIntNode(trie->root);
2258 ANTLR3_FREE(trie);
