← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to mysys/trie.c

  • Committer: Jim Winstead
  • Date: 2008-07-19 02:56:45 UTC
  • mto: (202.1.8 codestyle)
  • mto: This revision was merged to the branch mainline in revision 207.
  • Revision ID: jimw@mysql.com-20080719025645-w2pwytebgzusjzjb
Various fixes to enable compilation on Mac OS X, and remove the glib dependency.
Temporarily disables tab-completion in the drizzle client until an appropriate
autoconf check can be added/enabled.

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 fnode= 0;
 
185
  uint32 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
}