← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/trie.c

  • Committer: brian
  • Date: 2008-07-27 01:05:35 UTC
  • mfrom: (212.5.24 remove-include-dir)
  • Revision ID: brian@localhost.localdomain-20080727010535-y458velrxny2uuhy
Merge from Monty.

Show diffs side-by-side

added added

removed removed

Lines of Context:
mysys/trie.c
1
 
/* Copyright (C) 2005 MySQL AB
2
 
 
3
 
   This program is free software; you can redistribute it and/or modify
4
 
   it under the terms of the GNU General Public License as published by
5
 
   the Free Software Foundation; version 2 of the License.
6
 
 
7
 
   This program is distributed in the hope that it will be useful,
8
 
   but WITHOUT ANY WARRANTY; without even the implied warranty of
9
 
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10
 
   GNU General Public License for more details.
11
 
 
12
 
   You should have received a copy of the GNU General Public License
13
 
   along with this program; if not, write to the Free Software
14
 
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
15
 
 
16
 
/*
17
 
  Implementation of trie and Aho-Corasick automaton.
18
 
  Supports only charsets that can be compared byte-wise.
19
 
  
20
 
  TODO:
21
 
    Add character frequencies. Can increase lookup speed
22
 
    up to 30%.
23
 
    Implement character-wise comparision.
24
 
*/
25
 
 
26
 
 
27
 
#include "mysys_priv.h"
28
 
#include <m_string.h>
29
 
#include <my_trie.h>
30
 
#include <my_base.h>
31
 
 
32
 
 
33
 
/*
34
 
  SYNOPSIS
35
 
    TRIE *trie_init (TRIE *trie, CHARSET_INFO *charset);
36
 
 
37
 
  DESCRIPTION
38
 
    Allocates or initializes a `TRIE' object. If `trie' is a `NULL'
39
 
    pointer, the function allocates, initializes, and returns a new
40
 
    object. Otherwise, the object is initialized and the address of
41
 
    the object is returned.  If `trie_init()' allocates a new object,
42
 
    it will be freed when `trie_free()' is called.
43
 
 
44
 
  RETURN VALUE
45
 
    An initialized `TRIE*' object.  `NULL' if there was insufficient
46
 
    memory to allocate a new object.
47
 
*/
48
 
 
49
 
TRIE *trie_init (TRIE *trie, CHARSET_INFO *charset)
50
 
{
51
 
  MEM_ROOT mem_root;
52
 
  assert(charset);
53
 
  init_alloc_root(&mem_root,
54
 
                  (sizeof(TRIE_NODE) * 128) + ALLOC_ROOT_MIN_BLOCK_SIZE,
55
 
                  sizeof(TRIE_NODE) * 128);
56
 
  if (! trie)
57
 
  {
58
 
    if (! (trie= (TRIE *)alloc_root(&mem_root, sizeof(TRIE))))
59
 
    {
60
 
      free_root(&mem_root, MYF(0));
61
 
      return(NULL);
62
 
    }
63
 
  }
64
 
 
65
 
  memcpy(&trie->mem_root, &mem_root, sizeof(MEM_ROOT));
66
 
  trie->root.leaf= 0;
67
 
  trie->root.c= 0;
68
 
  trie->root.next= NULL;
69
 
  trie->root.links= NULL;
70
 
  trie->root.fail= NULL;
71
 
  trie->charset= charset;
72
 
  trie->nnodes= 0;
73
 
  trie->nwords= 0;
74
 
  return(trie);
75
 
}
76
 
 
77
 
 
78
 
/*
79
 
  SYNOPSIS
80
 
    void trie_free (TRIE *trie);
81
 
    trie - valid pointer to `TRIE'
82
 
 
83
 
  DESCRIPTION
84
 
    Frees the memory allocated for a `trie'.
85
 
 
86
 
  RETURN VALUE
87
 
    None.
88
 
*/
89
 
 
90
 
void trie_free (TRIE *trie)
91
 
{
92
 
  MEM_ROOT mem_root;
93
 
  assert(trie);
94
 
  memcpy(&mem_root, &trie->mem_root, sizeof(MEM_ROOT));
95
 
  free_root(&mem_root, MYF(0));
96
 
  return;
97
 
}
98
 
 
99
 
 
100
 
/*
101
 
  SYNOPSIS
102
 
    bool trie_insert (TRIE *trie, const uchar *key, uint keylen);
103
 
    trie - valid pointer to `TRIE'
104
 
    key - valid pointer to key to insert
105
 
    keylen - non-0 key length
106
 
 
107
 
  DESCRIPTION
108
 
    Inserts new key into trie.
109
 
 
110
 
  RETURN VALUE
111
 
    Upon successful completion, `trie_insert' returns `false'. Otherwise
112
 
    `true' is returned.
113
 
 
114
 
  NOTES
115
 
    If this function fails you must assume `trie' is broken.
116
 
    However it can be freed with trie_free().
117
 
*/
118
 
 
119
 
bool trie_insert (TRIE *trie, const uchar *key, uint keylen)
120
 
{
121
 
  TRIE_NODE *node;
122
 
  TRIE_NODE *next;
123
 
  uchar p;
124
 
  uint k;
125
 
  assert(trie && key && keylen);
126
 
  node= &trie->root;
127
 
  trie->root.fail= NULL;
128
 
  for (k= 0; k < keylen; k++)
129
 
  {
130
 
    p= key[k];
131
 
    for (next= node->links; next; next= next->next)
132
 
      if (next->c == p)
133
 
        break;
134
 
 
135
 
    if (! next)
136
 
    {
137
 
      TRIE_NODE *tmp= (TRIE_NODE *)alloc_root(&trie->mem_root,
138
 
                                              sizeof(TRIE_NODE));
139
 
      if (! tmp)
140
 
        return(true);
141
 
      tmp->leaf= 0;
142
 
      tmp->c= p;
143
 
      tmp->links= tmp->fail= tmp->next= NULL;
144
 
      trie->nnodes++;
145
 
      if (! node->links)
146
 
      {
147
 
        node->links= tmp;
148
 
      }
149
 
      else
150
 
      {
151
 
        for (next= node->links; next->next; next= next->next) /* no-op */;
152
 
        next->next= tmp;
153
 
      }
154
 
      node= tmp;
155
 
    }
156
 
    else
157
 
    {
158
 
      node= next;
159
 
    }
160
 
  }
161
 
  node->leaf= keylen;
162
 
  trie->nwords++;
163
 
  return(false);
164
 
}
165
 
 
166
 
 
167
 
/*
168
 
  SYNOPSIS
169
 
    bool trie_prepare (TRIE *trie);
170
 
    trie - valid pointer to `TRIE'
171
 
 
172
 
  DESCRIPTION
173
 
    Constructs Aho-Corasick automaton.
174
 
 
175
 
  RETURN VALUE
176
 
    Upon successful completion, `trie_prepare' returns `false'. Otherwise
177
 
    `true' is returned.
178
 
*/
179
 
 
180
 
bool ac_trie_prepare (TRIE *trie)
181
 
{
182
 
  TRIE_NODE **tmp_nodes;
183
 
  TRIE_NODE *node;
184
 
  uint32_t fnode= 0;
185
 
  uint32_t lnode= 0;
186
 
  assert(trie);
187
 
 
188
 
  tmp_nodes= (TRIE_NODE **)my_malloc(trie->nnodes * sizeof(TRIE_NODE *), MYF(0));
189
 
  if (! tmp_nodes)
190
 
    return(true);
191
 
 
192
 
  trie->root.fail= &trie->root;
193
 
  for (node= trie->root.links; node; node= node->next)
194
 
  {
195
 
    node->fail= &trie->root;
196
 
    tmp_nodes[lnode++]= node;
197
 
  }
198
 
 
199
 
  while (fnode < lnode)
200
 
  {
201
 
    TRIE_NODE *current= (TRIE_NODE *)tmp_nodes[fnode++];
202
 
    for (node= current->links; node; node= node->next)
203
 
    {
204
 
      TRIE_NODE *fail= current->fail;
205
 
      tmp_nodes[lnode++]= node;
206
 
      while (! (node->fail= trie_goto(&trie->root, fail, node->c)))
207
 
        fail= fail->fail;
208
 
    }
209
 
  }
210
 
  my_free((uchar*)tmp_nodes, MYF(0));
211
 
  return(false);
212
 
}
213
 
 
214
 
 
215
 
/*
216
 
  SYNOPSIS
217
 
    void ac_trie_init (TRIE *trie, AC_TRIE_STATE *state);
218
 
    trie - valid pointer to `TRIE'
219
 
    state - value pointer to `AC_TRIE_STATE'
220
 
 
221
 
  DESCRIPTION
222
 
    Initializes `AC_TRIE_STATE' object.
223
 
*/
224
 
 
225
 
void ac_trie_init (TRIE *trie, AC_TRIE_STATE *state)
226
 
{
227
 
  assert(trie && state);
228
 
  state->trie= trie;
229
 
  state->node= &trie->root;
230
 
  return;
231
 
}