Skip navigation links

MySQL Newsletter - Subscribe Today!

The world's most popular open source database

MySQL 5.1: mysql/src/5.1-dbg/mysys/trie.c File Reference

mysql/src/5.1-dbg/mysys/trie.c File Reference

#include "mysys_priv.h"
#include <m_string.h>
#include <my_trie.h>
#include <my_base.h>

Include dependency graph for trie.c:

Go to the source code of this file.


Functions

TRIE * trie_init (TRIE *trie, CHARSET_INFO *charset)
void trie_free (TRIE *trie)
my_bool trie_insert (TRIE *trie, const byte *key, uint keylen)
my_bool ac_trie_prepare (TRIE *trie)
void ac_trie_init (TRIE *trie, AC_TRIE_STATE *state)

Function Documentation

void ac_trie_init ( TRIE *  trie,
AC_TRIE_STATE *  state 
)

Definition at line 230 of file trie.c.

References DBUG_ASSERT, DBUG_ENTER, DBUG_VOID_RETURN, st_ac_trie_state::node, st_trie::root, and st_ac_trie_state::trie.

00231 {
00232   DBUG_ENTER("ac_trie_init");
00233   DBUG_ASSERT(trie && state);
00234   state->trie= trie;
00235   state->node= &trie->root;
00236   DBUG_VOID_RETURN;
00237 }

my_bool ac_trie_prepare ( TRIE *  trie  ) 

Definition at line 184 of file trie.c.

References st_trie_node::c, DBUG_ASSERT, DBUG_ENTER, DBUG_RETURN, fail(), st_trie_node::fail, FALSE, st_trie_node::links, my_free, my_malloc(), MYF, st_trie_node::next, st_trie::nnodes, st_trie::root, trie_goto(), and TRUE.

00185 {
00186   TRIE_NODE **tmp_nodes;
00187   TRIE_NODE *node;
00188   uint32 fnode= 0;
00189   uint32 lnode= 0;
00190   DBUG_ENTER("trie_prepare");
00191   DBUG_ASSERT(trie);
00192 
00193   tmp_nodes= (TRIE_NODE **)my_malloc(trie->nnodes * sizeof(TRIE_NODE *), MYF(0));
00194   if (! tmp_nodes)
00195     DBUG_RETURN(TRUE);
00196 
00197   trie->root.fail= &trie->root;
00198   for (node= trie->root.links; node; node= node->next)
00199   {
00200     node->fail= &trie->root;
00201     tmp_nodes[lnode++]= node;
00202   }
00203 
00204   while (fnode < lnode)
00205   {
00206     TRIE_NODE *current= (TRIE_NODE *)tmp_nodes[fnode++];
00207     for (node= current->links; node; node= node->next)
00208     {
00209       TRIE_NODE *fail= current->fail;
00210       tmp_nodes[lnode++]= node;
00211       while (! (node->fail= trie_goto(&trie->root, fail, node->c)))
00212         fail= fail->fail;
00213     }
00214   }
00215   my_free((gptr)tmp_nodes, MYF(0));
00216   DBUG_RETURN(FALSE);
00217 }

Here is the call graph for this function:

void trie_free ( TRIE *  trie  ) 

Definition at line 92 of file trie.c.

References DBUG_ASSERT, DBUG_ENTER, DBUG_VOID_RETURN, free_root(), st_trie::mem_root, memcpy, and MYF.

00093 {
00094   MEM_ROOT mem_root;
00095   DBUG_ENTER("trie_free");
00096   DBUG_ASSERT(trie);
00097   memcpy(&mem_root, &trie->mem_root, sizeof(MEM_ROOT));
00098   free_root(&mem_root, MYF(0));
00099   DBUG_VOID_RETURN;
00100 }

Here is the call graph for this function:

TRIE* trie_init ( TRIE *  trie,
CHARSET_INFO *  charset 
)

Definition at line 50 of file trie.c.

References alloc_root(), ALLOC_ROOT_MIN_BLOCK_SIZE, st_trie_node::c, st_trie::charset, charset, DBUG_ASSERT, DBUG_ENTER, DBUG_RETURN, st_trie_node::fail, free_root(), init_alloc_root(), st_trie_node::leaf, st_trie_node::links, st_trie::mem_root, memcpy, MYF, st_trie_node::next, st_trie::nnodes, NULL, st_trie::nwords, and st_trie::root.

00051 {
00052   MEM_ROOT mem_root;
00053   DBUG_ENTER("trie_init");
00054   DBUG_ASSERT(charset);
00055   init_alloc_root(&mem_root,
00056                   (sizeof(TRIE_NODE) * 128) + ALLOC_ROOT_MIN_BLOCK_SIZE,
00057                   sizeof(TRIE_NODE) * 128);
00058   if (! trie)
00059   {
00060     if (! (trie= (TRIE *)alloc_root(&mem_root, sizeof(TRIE))))
00061     {
00062       free_root(&mem_root, MYF(0));
00063       DBUG_RETURN(NULL);
00064     }
00065   }
00066 
00067   memcpy(&trie->mem_root, &mem_root, sizeof(MEM_ROOT));
00068   trie->root.leaf= 0;
00069   trie->root.c= 0;
00070   trie->root.next= NULL;
00071   trie->root.links= NULL;
00072   trie->root.fail= NULL;
00073   trie->charset= charset;
00074   trie->nnodes= 0;
00075   trie->nwords= 0;
00076   DBUG_RETURN(trie);
00077 }

Here is the call graph for this function:

my_bool trie_insert ( TRIE *  trie,
const byte *  key,
uint  keylen 
)

Definition at line 122 of file trie.c.

References alloc_root(), st_trie_node::c, DBUG_ASSERT, DBUG_ENTER, DBUG_RETURN, st_trie_node::fail, st_trie_node::links, st_trie::mem_root, st_trie_node::next, st_trie::nnodes, NULL, p, st_trie::root, and TRUE.

00123 {
00124   TRIE_NODE *node;
00125   TRIE_NODE *next;
00126   byte p;
00127   uint k;
00128   DBUG_ENTER("trie_insert");
00129   DBUG_ASSERT(trie && key && keylen);
00130   node= &trie->root;
00131   trie->root.fail= NULL;
00132   for (k= 0; k < keylen; k++)
00133   {
00134     p= key[k];
00135     for (next= node->links; next; next= next->next)
00136       if (next->c == p)
00137         break;
00138 
00139     if (! next)
00140     {
00141       TRIE_NODE *tmp= (TRIE_NODE *)alloc_root(&trie->mem_root,
00142                                               sizeof(TRIE_NODE));
00143       if (! tmp)
00144         DBUG_RETURN(TRUE);
00145       tmp->leaf= 0;
00146       tmp->c= p;
00147       tmp->links= tmp->fail= tmp->next= NULL;
00148       trie->nnodes++;
00149       if (! node->links)
00150       {
00151         node->links= tmp;
00152       }
00153       else
00154       {
00155         for (next= node->links; next->next; next= next->next) /* no-op */;
00156         next->next= tmp;
00157       }
00158       node= tmp;
00159     }
00160     else
00161     {
00162       node= next;
00163     }
00164   }
00165   node->leaf= keylen;
00166   trie->nwords++;
00167   DBUG_RETURN(FALSE);
00168 }

Here is the call graph for this function:

Generated on Sat Sep 9 02:12:02 2006 for MySQL 5.1 by  doxygen 1.4.7