← Back to branch summary

~ubuntu-branches/ubuntu/feisty/clamav/feisty

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/include/llvm/ADT/Trie.h

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2007-02-20 10:33:44 UTC
  • mto: This revision was merged to the branch mainline in revision 16.
  • Revision ID: james.westby@ubuntu.com-20070220103344-zgcu2psnx9d98fpa
Tags: upstream-0.90
Import upstream version 0.90

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/include/llvm/ADT/Trie.h
1
 
//===- llvm/ADT/Trie.h ---- Generic trie structure --------------*- C++ -*-===//
2
 
//
3
 
//                     The LLVM Compiler Infrastructure
4
 
//
5
 
// This file is distributed under the University of Illinois Open Source
6
 
// License. See LICENSE.TXT for details.
7
 
//
8
 
//===----------------------------------------------------------------------===//
9
 
//
10
 
// This class defines a generic trie structure. The trie structure
11
 
// is immutable after creation, but the payload contained within it is not.
12
 
//
13
 
//===----------------------------------------------------------------------===//
14
 
 
15
 
#ifndef LLVM_ADT_TRIE_H
16
 
#define LLVM_ADT_TRIE_H
17
 
 
18
 
#include "llvm/ADT/GraphTraits.h"
19
 
#include "llvm/Support/DOTGraphTraits.h"
20
 
 
21
 
#include <cassert>
22
 
#include <vector>
23
 
 
24
 
namespace llvm {
25
 
 
26
 
// FIXME:
27
 
// - Labels are usually small, maybe it's better to use SmallString
28
 
// - Should we use char* during construction?
29
 
// - Should we templatize Empty with traits-like interface?
30
 
 
31
 
template<class Payload>
32
 
class Trie {
33
 
  friend class GraphTraits<Trie<Payload> >;
34
 
  friend class DOTGraphTraits<Trie<Payload> >;
35
 
public:
36
 
  class Node {
37
 
    friend class Trie;
38
 
 
39
 
  public:
40
 
    typedef std::vector<Node*> NodeVectorType;
41
 
    typedef typename NodeVectorType::iterator iterator;
42
 
    typedef typename NodeVectorType::const_iterator const_iterator;
43
 
 
44
 
  private:
45
 
    enum QueryResult {
46
 
      Same           = -3,
47
 
      StringIsPrefix = -2,
48
 
      LabelIsPrefix  = -1,
49
 
      DontMatch      = 0,
50
 
      HaveCommonPart
51
 
    };
52
 
 
53
 
    struct NodeCmp {
54
 
      bool operator() (Node* N1, Node* N2) {
55
 
        return (N1->Label[0] < N2->Label[0]);
56
 
      }
57
 
      bool operator() (Node* N, char Id) {
58
 
        return (N->Label[0] < Id);
59
 
      }
60
 
    };
61
 
 
62
 
    std::string Label;
63
 
    Payload Data;
64
 
    NodeVectorType Children;
65
 
 
66
 
    // Do not implement
67
 
    Node(const Node&);
68
 
    Node& operator=(const Node&);
69
 
 
70
 
    inline void addEdge(Node* N) {
71
 
      if (Children.empty())
72
 
        Children.push_back(N);
73
 
      else {
74
 
        iterator I = std::lower_bound(Children.begin(), Children.end(),
75
 
                                      N, NodeCmp());
76
 
        // FIXME: no dups are allowed
77
 
        Children.insert(I, N);
78
 
      }
79
 
    }
80
 
 
81
 
    inline void setEdge(Node* N) {
82
 
      char Id = N->Label[0];
83
 
      iterator I = std::lower_bound(Children.begin(), Children.end(),
84
 
                                     Id, NodeCmp());
85
 
      assert(I != Children.end() && "Node does not exists!");
86
 
      *I = N;
87
 
    }
88
 
 
89
 
    QueryResult query(const std::string& s) const {
90
 
      unsigned i, l;
91
 
      unsigned l1 = s.length();
92
 
      unsigned l2 = Label.length();
93
 
 
94
 
      // Find the length of common part
95
 
      l = std::min(l1, l2);
96
 
      i = 0;
97
 
      while ((i < l) && (s[i] == Label[i]))
98
 
        ++i;
99
 
 
100
 
      if (i == l) { // One is prefix of another, find who is who
101
 
        if (l1 == l2)
102
 
          return Same;
103
 
        else if (i == l1)
104
 
          return StringIsPrefix;
105
 
        else
106
 
          return LabelIsPrefix;
107
 
      } else // s and Label have common (possible empty) part, return its length
108
 
        return (QueryResult)i;
109
 
    }
110
 
 
111
 
  public:
112
 
    inline explicit Node(const Payload& data, const std::string& label = ""):
113
 
        Label(label), Data(data) { }
114
 
 
115
 
    inline const Payload& data() const { return Data; }
116
 
    inline void setData(const Payload& data) { Data = data; }
117
 
 
118
 
    inline const std::string& label() const { return Label; }
119
 
 
120
 
#if 0
121
 
    inline void dump() {
122
 
      llvm::cerr << "Node: " << this << "\n"
123
 
                << "Label: " << Label << "\n"
124
 
                << "Children:\n";
125
 
 
126
 
      for (iterator I = Children.begin(), E = Children.end(); I != E; ++I)
127
 
        llvm::cerr << (*I)->Label << "\n";
128
 
    }
129
 
#endif
130
 
 
131
 
    inline Node* getEdge(char Id) {
132
 
      Node* fNode = NULL;
133
 
      iterator I = std::lower_bound(Children.begin(), Children.end(),
134
 
                                          Id, NodeCmp());
135
 
      if (I != Children.end() && (*I)->Label[0] == Id)
136
 
        fNode = *I;
137
 
 
138
 
      return fNode;
139
 
    }
140
 
 
141
 
    inline iterator       begin()       { return Children.begin(); }
142
 
    inline const_iterator begin() const { return Children.begin(); }
143
 
    inline iterator       end  ()       { return Children.end();   }
144
 
    inline const_iterator end  () const { return Children.end();   }
145
 
 
146
 
    inline size_t         size () const { return Children.size();  }
147
 
    inline bool           empty() const { return Children.empty(); }
148
 
    inline const Node*   &front() const { return Children.front(); }
149
 
    inline       Node*   &front()       { return Children.front(); }
150
 
    inline const Node*   &back()  const { return Children.back();  }
151
 
    inline       Node*   &back()        { return Children.back();  }
152
 
 
153
 
  };
154
 
 
155
 
private:
156
 
  std::vector<Node*> Nodes;
157
 
  Payload Empty;
158
 
 
159
 
  inline Node* addNode(const Payload& data, const std::string label = "") {
160
 
    Node* N = new Node(data, label);
161
 
    Nodes.push_back(N);
162
 
    return N;
163
 
  }
164
 
 
165
 
  inline Node* splitEdge(Node* N, char Id, size_t index) {
166
 
    Node* eNode = N->getEdge(Id);
167
 
    assert(eNode && "Node doesn't exist");
168
 
 
169
 
    const std::string &l = eNode->Label;
170
 
    assert(index > 0 && index < l.length() && "Trying to split too far!");
171
 
    std::string l1 = l.substr(0, index);
172
 
    std::string l2 = l.substr(index);
173
 
 
174
 
    Node* nNode = addNode(Empty, l1);
175
 
    N->setEdge(nNode);
176
 
 
177
 
    eNode->Label = l2;
178
 
    nNode->addEdge(eNode);
179
 
 
180
 
    return nNode;
181
 
  }
182
 
 
183
 
  // Do not implement
184
 
  Trie(const Trie&);
185
 
  Trie& operator=(const Trie&);
186
 
 
187
 
public:
188
 
  inline explicit Trie(const Payload& empty):Empty(empty) {
189
 
    addNode(Empty);
190
 
  }
191
 
  inline ~Trie() {
192
 
    for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
193
 
      delete Nodes[i];
194
 
  }
195
 
 
196
 
  inline Node* getRoot() const { return Nodes[0]; }
197
 
 
198
 
  bool addString(const std::string& s, const Payload& data);
199
 
  const Payload& lookup(const std::string& s) const;
200
 
 
201
 
};
202
 
 
203
 
// Define this out-of-line to dissuade the C++ compiler from inlining it.
204
 
template<class Payload>
205
 
bool Trie<Payload>::addString(const std::string& s, const Payload& data) {
206
 
  Node* cNode = getRoot();
207
 
  Node* tNode = NULL;
208
 
  std::string s1(s);
209
 
 
210
 
  while (tNode == NULL) {
211
 
    char Id = s1[0];
212
 
    if (Node* nNode = cNode->getEdge(Id)) {
213
 
      typename Node::QueryResult r = nNode->query(s1);
214
 
 
215
 
      switch (r) {
216
 
      case Node::Same:
217
 
      case Node::StringIsPrefix:
218
 
        // Currently we don't allow to have two strings in the trie one
219
 
        // being a prefix of another. This should be fixed.
220
 
        assert(0 && "FIXME!");
221
 
        return false;
222
 
      case Node::DontMatch:
223
 
        assert(0 && "Impossible!");
224
 
        return false;
225
 
      case Node::LabelIsPrefix:
226
 
        s1 = s1.substr(nNode->label().length());
227
 
        cNode = nNode;
228
 
        break;
229
 
      default:
230
 
        nNode = splitEdge(cNode, Id, r);
231
 
        tNode = addNode(data, s1.substr(r));
232
 
        nNode->addEdge(tNode);
233
 
      }
234
 
    } else {
235
 
      tNode = addNode(data, s1);
236
 
      cNode->addEdge(tNode);
237
 
    }
238
 
  }
239
 
 
240
 
  return true;
241
 
}
242
 
 
243
 
template<class Payload>
244
 
const Payload& Trie<Payload>::lookup(const std::string& s) const {
245
 
  Node* cNode = getRoot();
246
 
  Node* tNode = NULL;
247
 
  std::string s1(s);
248
 
 
249
 
  while (tNode == NULL) {
250
 
    char Id = s1[0];
251
 
    if (Node* nNode = cNode->getEdge(Id)) {
252
 
      typename Node::QueryResult r = nNode->query(s1);
253
 
 
254
 
      switch (r) {
255
 
      case Node::Same:
256
 
        tNode = nNode;
257
 
        break;
258
 
      case Node::StringIsPrefix:
259
 
        return Empty;
260
 
      case Node::DontMatch:
261
 
        assert(0 && "Impossible!");
262
 
        return Empty;
263
 
      case Node::LabelIsPrefix:
264
 
        s1 = s1.substr(nNode->label().length());
265
 
        cNode = nNode;
266
 
        break;
267
 
      default:
268
 
        return Empty;
269
 
      }
270
 
    } else
271
 
      return Empty;
272
 
  }
273
 
 
274
 
  return tNode->data();
275
 
}
276
 
 
277
 
template<class Payload>
278
 
struct GraphTraits<Trie<Payload> > {
279
 
  typedef Trie<Payload> TrieType;
280
 
  typedef typename TrieType::Node NodeType;
281
 
  typedef typename NodeType::iterator ChildIteratorType;
282
 
 
283
 
  static inline NodeType *getEntryNode(const TrieType& T) {
284
 
    return T.getRoot();
285
 
  }
286
 
 
287
 
  static inline ChildIteratorType child_begin(NodeType *N) {
288
 
    return N->begin();
289
 
  }
290
 
  static inline ChildIteratorType child_end(NodeType *N) { return N->end(); }
291
 
 
292
 
  typedef typename std::vector<NodeType*>::const_iterator nodes_iterator;
293
 
 
294
 
  static inline nodes_iterator nodes_begin(const TrieType& G) {
295
 
    return G.Nodes.begin();
296
 
  }
297
 
  static inline nodes_iterator nodes_end(const TrieType& G) {
298
 
    return G.Nodes.end();
299
 
  }
300
 
 
301
 
};
302
 
 
303
 
template<class Payload>
304
 
struct DOTGraphTraits<Trie<Payload> > : public DefaultDOTGraphTraits {
305
 
  typedef typename Trie<Payload>::Node NodeType;
306
 
  typedef typename GraphTraits<Trie<Payload> >::ChildIteratorType EdgeIter;
307
 
 
308
 
  static std::string getGraphName(const Trie<Payload>& T) {
309
 
    return "Trie";
310
 
  }
311
 
 
312
 
  static std::string getNodeLabel(NodeType* Node, const Trie<Payload>& T) {
313
 
    if (T.getRoot() == Node)
314
 
      return "<Root>";
315
 
    else
316
 
      return Node->label();
317
 
  }
318
 
 
319
 
  static std::string getEdgeSourceLabel(NodeType* Node, EdgeIter I) {
320
 
    NodeType* N = *I;
321
 
    return N->label().substr(0, 1);
322
 
  }
323
 
 
324
 
  static std::string getNodeAttributes(const NodeType* Node,
325
 
                                       const Trie<Payload>& T) {
326
 
    if (Node->data() != T.Empty)
327
 
      return "color=blue";
328
 
 
329
 
    return "";
330
 
  }
331
 
 
332
 
};
333
 
 
334
 
} // end of llvm namespace
335
 
 
336
 
#endif // LLVM_ADT_TRIE_H