diff options
Diffstat (limited to 'externals/mysql/mysys/trie.c')
| -rw-r--r-- | externals/mysql/mysys/trie.c | 236 |
1 files changed, 0 insertions, 236 deletions
diff --git a/externals/mysql/mysys/trie.c b/externals/mysql/mysys/trie.c deleted file mode 100644 index 5738b9b866b..00000000000 --- a/externals/mysql/mysys/trie.c +++ /dev/null @@ -1,236 +0,0 @@ -/* Copyright (C) 2005 MySQL AB - - This program is free software; you can redistribute it and/or modify - it under the terms of the GNU General Public License as published by - the Free Software Foundation; version 2 of the License. - - This program is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this program; if not, write to the Free Software - Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ - -/* - Implementation of trie and Aho-Corasick automaton. - Supports only charsets that can be compared byte-wise. - - TODO: - Add character frequencies. Can increase lookup speed - up to 30%. - Implement character-wise comparision. -*/ - - -#include "mysys_priv.h" -#include <m_string.h> -#include <my_trie.h> -#include <my_base.h> - - -/* - SYNOPSIS - TRIE *trie_init (TRIE *trie, CHARSET_INFO *charset); - - DESCRIPTION - Allocates or initializes a `TRIE' object. If `trie' is a `NULL' - pointer, the function allocates, initializes, and returns a new - object. Otherwise, the object is initialized and the address of - the object is returned. If `trie_init()' allocates a new object, - it will be freed when `trie_free()' is called. - - RETURN VALUE - An initialized `TRIE*' object. `NULL' if there was insufficient - memory to allocate a new object. -*/ - -TRIE *trie_init (TRIE *trie, CHARSET_INFO *charset) -{ - MEM_ROOT mem_root; - DBUG_ENTER("trie_init"); - DBUG_ASSERT(charset); - init_alloc_root(&mem_root, - (sizeof(TRIE_NODE) * 128) + ALLOC_ROOT_MIN_BLOCK_SIZE, - sizeof(TRIE_NODE) * 128); - if (! trie) - { - if (! (trie= (TRIE *)alloc_root(&mem_root, sizeof(TRIE)))) - { - free_root(&mem_root, MYF(0)); - DBUG_RETURN(NULL); - } - } - - memcpy(&trie->mem_root, &mem_root, sizeof(MEM_ROOT)); - trie->root.leaf= 0; - trie->root.c= 0; - trie->root.next= NULL; - trie->root.links= NULL; - trie->root.fail= NULL; - trie->charset= charset; - trie->nnodes= 0; - trie->nwords= 0; - DBUG_RETURN(trie); -} - - -/* - SYNOPSIS - void trie_free (TRIE *trie); - trie - valid pointer to `TRIE' - - DESCRIPTION - Frees the memory allocated for a `trie'. - - RETURN VALUE - None. -*/ - -void trie_free (TRIE *trie) -{ - MEM_ROOT mem_root; - DBUG_ENTER("trie_free"); - DBUG_ASSERT(trie); - memcpy(&mem_root, &trie->mem_root, sizeof(MEM_ROOT)); - free_root(&mem_root, MYF(0)); - DBUG_VOID_RETURN; -} - - -/* - SYNOPSIS - my_bool trie_insert (TRIE *trie, const uchar *key, uint keylen); - trie - valid pointer to `TRIE' - key - valid pointer to key to insert - keylen - non-0 key length - - DESCRIPTION - Inserts new key into trie. - - RETURN VALUE - Upon successful completion, `trie_insert' returns `FALSE'. Otherwise - `TRUE' is returned. - - NOTES - If this function fails you must assume `trie' is broken. - However it can be freed with trie_free(). -*/ - -my_bool trie_insert (TRIE *trie, const uchar *key, uint keylen) -{ - TRIE_NODE *node; - TRIE_NODE *next; - uchar p; - uint k; - DBUG_ENTER("trie_insert"); - DBUG_ASSERT(trie && key && keylen); - node= &trie->root; - trie->root.fail= NULL; - for (k= 0; k < keylen; k++) - { - p= key[k]; - for (next= node->links; next; next= next->next) - if (next->c == p) - break; - - if (! next) - { - TRIE_NODE *tmp= (TRIE_NODE *)alloc_root(&trie->mem_root, - sizeof(TRIE_NODE)); - if (! tmp) - DBUG_RETURN(TRUE); - tmp->leaf= 0; - tmp->c= p; - tmp->links= tmp->fail= tmp->next= NULL; - trie->nnodes++; - if (! node->links) - { - node->links= tmp; - } - else - { - for (next= node->links; next->next; next= next->next) /* no-op */; - next->next= tmp; - } - node= tmp; - } - else - { - node= next; - } - } - node->leaf= keylen; - trie->nwords++; - DBUG_RETURN(FALSE); -} - - -/* - SYNOPSIS - my_bool trie_prepare (TRIE *trie); - trie - valid pointer to `TRIE' - - DESCRIPTION - Constructs Aho-Corasick automaton. - - RETURN VALUE - Upon successful completion, `trie_prepare' returns `FALSE'. Otherwise - `TRUE' is returned. -*/ - -my_bool ac_trie_prepare (TRIE *trie) -{ - TRIE_NODE **tmp_nodes; - TRIE_NODE *node; - uint32 fnode= 0; - uint32 lnode= 0; - DBUG_ENTER("trie_prepare"); - DBUG_ASSERT(trie); - - tmp_nodes= (TRIE_NODE **)my_malloc(trie->nnodes * sizeof(TRIE_NODE *), MYF(0)); - if (! tmp_nodes) - DBUG_RETURN(TRUE); - - trie->root.fail= &trie->root; - for (node= trie->root.links; node; node= node->next) - { - node->fail= &trie->root; - tmp_nodes[lnode++]= node; - } - - while (fnode < lnode) - { - TRIE_NODE *current= (TRIE_NODE *)tmp_nodes[fnode++]; - for (node= current->links; node; node= node->next) - { - TRIE_NODE *fail= current->fail; - tmp_nodes[lnode++]= node; - while (! (node->fail= trie_goto(&trie->root, fail, node->c))) - fail= fail->fail; - } - } - my_free((uchar*)tmp_nodes, MYF(0)); - DBUG_RETURN(FALSE); -} - - -/* - SYNOPSIS - void ac_trie_init (TRIE *trie, AC_TRIE_STATE *state); - trie - valid pointer to `TRIE' - state - value pointer to `AC_TRIE_STATE' - - DESCRIPTION - Initializes `AC_TRIE_STATE' object. -*/ - -void ac_trie_init (TRIE *trie, AC_TRIE_STATE *state) -{ - DBUG_ENTER("ac_trie_init"); - DBUG_ASSERT(trie && state); - state->trie= trie; - state->node= &trie->root; - DBUG_VOID_RETURN; -} |