New version of the ahocorasick library (#1200)

The new version is about 25% faster with -O2 and 45% faster with -O3.
No recursion is used (smaller stack size required).
Uses less memory (by valgrind info)
 bigram:
  - original 1796 allocs,   247864 bytes allocated
  - new      1232 allocs,   158880 bytes allocated
 host_match:
  - original 18038 allocs, 3004576 bytes allocated
  - new       6861 allocs,  396624 bytes allocated

The function ac_automata_search() is thread safe.
Optional case-insensitive comparison.
Matching at the beginning and at the end of the string is supported.
One code file and one header file.

1 files changed, 0 insertions, 66 deletions

diff --git a/src/lib/third_party/include/node.h b/src/lib/third_party/include/node.h
deleted file mode 100644
index c172112aa..000000000
--- a/src/lib/third_party/include/node.h
+++ /dev/null
@@ -1,66 +0,0 @@
-/*
- * node.h: automata node header file
- * This file is part of multifast.
- *
- Copyright 2010-2012 Kamiar Kanani <kamiar.kanani@gmail.com>
-
- multifast is free software: you can redistribute it and/or modify
- it under the terms of the GNU Lesser General Public License as published by
- the Free Software Foundation, either version 3 of the License, or
- (at your option) any later version.
-
- multifast 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 Lesser General Public License for more details.
-
- You should have received a copy of the GNU Lesser General Public License
- along with multifast.  If not, see <http://www.gnu.org/licenses/>.
-*/
-
-#ifndef _NODE_H_
-#define _NODE_H_
-
-#include "actypes.h"
-
-/* Forward Declaration */
-struct edge;
-
-/* automata node */
-typedef struct ac_node
-{
-  int id; /* Node ID : for debugging purpose */
-  short int final; /* 0: no ; 1: yes, it is a final node */
-  struct ac_node * failure_node; /* The failure node of this node */
-  unsigned short depth; /* depth: distance between this node and the root */
-
-  /* Matched patterns */
-  AC_PATTERN_t * matched_patterns; /* Array of matched patterns */
-  unsigned short matched_patterns_num; /* Number of matched patterns at this node */
-  unsigned short matched_patterns_max; /* Max capacity of allocated memory for matched_patterns */
-
-  /* Outgoing Edges */
-  struct edge * outgoing; /* Array of outgoing edges */
-  unsigned short outgoing_degree; /* Number of outgoing edges */
-  unsigned short outgoing_max; /* Max capacity of allocated memory for outgoing */
-} AC_NODE_t;
-
-/* The Edge of the Node */
-struct edge
-{
-  AC_ALPHABET_t alpha; /* Edge alpha */
-  struct ac_node * next; /* Target of the edge */
-};
-
-
-AC_NODE_t * node_create            (void);
-AC_NODE_t * node_create_next       (AC_NODE_t * thiz, AC_ALPHABET_t alpha);
-void        node_register_matchstr (AC_NODE_t * thiz, AC_PATTERN_t * str, u_int8_t is_existing);
-void        node_register_outgoing (AC_NODE_t * thiz, AC_NODE_t * next, AC_ALPHABET_t alpha);
-AC_NODE_t * node_find_next         (AC_NODE_t * thiz, AC_ALPHABET_t alpha);
-AC_NODE_t * node_findbs_next       (AC_NODE_t * thiz, AC_ALPHABET_t alpha);
-void        node_release           (AC_NODE_t * thiz, u_int8_t free_pattern);
-void        node_assign_id         (AC_NODE_t * thiz);
-void        node_sort_edges        (AC_NODE_t * thiz);
-
-#endif