aboutsummaryrefslogtreecommitdiff
path: root/src/lib/third_party
diff options
context:
space:
mode:
authorLuca Deri <deri@Lucas-MacBookPro.local>2015-04-19 07:25:59 +0200
committerLuca Deri <deri@Lucas-MacBookPro.local>2015-04-19 07:25:59 +0200
commit2e5ceac844c32fb52f4f3042be5b872f8b0b4ff0 (patch)
tree01af171f4af2b86efa64d0166dc540ee5c027c95 /src/lib/third_party
parent7fa4694dadf869d1de2baa99383308a163902f8f (diff)
Initial import from SVN
Diffstat (limited to 'src/lib/third_party')
9 files changed, 2435 insertions, 0 deletions
diff --git a/src/lib/third_party/include/actypes.h b/src/lib/third_party/include/actypes.h
new file mode 100644
index 000000000..1900ae9a0
--- /dev/null
+++ b/src/lib/third_party/include/actypes.h
@@ -0,0 +1,135 @@
+/*
+ * actypes.h: Includes basic data types of ahocorasick library
+ * 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 _AC_TYPES_H_
+#define _AC_TYPES_H_
+
+/* AC_ALPHABET_t:
+ * defines the alphabet type.
+ * Actually defining AC_ALPHABET_t as a char will work, but sometimes we deal
+ * with streams of other (bigger) types e.g. integers, specific enum, objects.
+ * Although they consists of string of bytes (chars), but using their specific
+ * types for AC_ALPHABET_t will lead to a better performance. so instead of
+ * dealing with strings of chars, we assume dealing with strings of
+ * AC_ALPHABET_t and leave it optional for other developers to define their
+ * own alphabets.
+ **/
+typedef char AC_ALPHABET_t;
+
+/* AC_REP_t:
+ * Provides a more readable representative for a pattern.
+ * because patterns themselves are not always suitable for displaying
+ * (e.g. for hex patterns), we offer this type to improve intelligibility
+ * of output. furthermore, sometimes it is useful, for example while
+ * retrieving patterns from a database, to maintain their identifiers in the
+ * automata for further reference. we provisioned two possible types as a
+ * union for this purpose. you can add your desired type in it.
+ **/
+typedef union {
+ char * stringy; /* null-terminated string */
+ unsigned long number;
+} AC_REP_t;
+
+/* AC_PATTERN_t:
+ * This is the pattern type that must be fed into AC automata.
+ * the 'astring' field is not null-terminated, due to it can contain zero
+ * value bytes. the 'length' field determines the number of AC_ALPHABET_t it
+ * carries. the 'representative' field is described in AC_REP_t. despite
+ * 'astring', 'representative' can have duplicate values for different given
+ * AC_PATTERN_t. it is an optional field and you can just fill it with 0.
+ * CAUTION:
+ * Not always the 'astring' points to the correct position in memory.
+ * it is the responsibility of your program to maintain a permanent allocation
+ * for astring field of the added pattern to automata.
+ **/
+typedef struct
+{
+ AC_ALPHABET_t * astring; /* String of alphabets */
+ unsigned int length; /* Length of pattern */
+ AC_REP_t rep; /* Representative string (optional) */
+} AC_PATTERN_t;
+
+/* AC_TEXT_t:
+ * The input text type that is fed to ac_automata_search() to be searched.
+ * it is similar to AC_PATTERN_t. actually we could use AC_PATTERN_t as input
+ * text, but for the purpose of being more readable, we defined this new type.
+ **/
+typedef struct
+{
+ AC_ALPHABET_t * astring; /* String of alphabets */
+ unsigned int length; /* Length of string */
+} AC_TEXT_t;
+
+/* AC_MATCH_t:
+ * Provides the structure for reporting a match event.
+ * a match event occurs when the automata reaches a final node. any final
+ * node can match one or more pattern at a position in a text. the
+ * 'patterns' field holds these matched patterns. obviously these
+ * matched patterns have same end-position in the text. there is a relationship
+ * between matched patterns: the shorter one is a factor (tail) of the longer
+ * one. the 'position' maintains the end position of matched patterns. the
+ * start position of patterns could be found by knowing their 'length' in
+ * AC_PATTERN_t. e.g. suppose "recent" and "cent" are matched at
+ * position 40 in the text, then the start position of them are 34 and 36
+ * respectively. finally the field 'match_num' maintains the number of
+ * matched patterns.
+ **/
+typedef struct
+{
+ AC_PATTERN_t * patterns; /* Array of matched pattern */
+ long position; /* The end position of matching pattern(s) in the text */
+ unsigned int match_num; /* Number of matched patterns */
+} AC_MATCH_t;
+
+/* AC_ERROR_t:
+ * Error that may occur while adding a pattern to the automata.
+ * it is returned by ac_automata_add().
+ **/
+typedef enum
+ {
+ ACERR_SUCCESS = 0, /* No error occurred */
+ ACERR_DUPLICATE_PATTERN, /* Duplicate patterns */
+ ACERR_LONG_PATTERN, /* Pattern length is longer than AC_PATTRN_MAX_LENGTH */
+ ACERR_ZERO_PATTERN, /* Empty pattern (zero length) */
+ ACERR_AUTOMATA_CLOSED, /* Automata is closed. after calling
+ ac_automata_finalize() you can not add new patterns to the automata. */
+ } AC_ERROR_t;
+
+/* MATCH_CALBACK_t:
+ * This is the call-back function type that must be given to automata at
+ * initialization to report match occurrence to the caller.
+ * at a match event, the automata will reach you using this function and sends
+ * you a pointer to AC_MATCH_t. using that pointer you can handle
+ * matches. you can send parameters to the call-back function when you call
+ * ac_automata_search(). at call-back, the automata will sent you those
+ * parameters as the second parameter (void *) of MATCH_CALBACK_t. inside
+ * the call-back function you can cast it to whatever you want.
+ * If you return 0 from MATCH_CALBACK_t function to the automata, it will
+ * continue searching, otherwise it will return from ac_automata_search()
+ * to your calling function.
+ **/
+typedef int (*MATCH_CALBACK_f)(AC_MATCH_t *, void *);
+
+/* AC_PATTRN_MAX_LENGTH:
+ * Maximum acceptable pattern length in AC_PATTERN_t.length
+ **/
+#define AC_PATTRN_MAX_LENGTH 1024
+
+#endif
diff --git a/src/lib/third_party/include/ahocorasick.h b/src/lib/third_party/include/ahocorasick.h
new file mode 100644
index 000000000..ea92e4a1b
--- /dev/null
+++ b/src/lib/third_party/include/ahocorasick.h
@@ -0,0 +1,69 @@
+/*
+ * ahocorasick.h: the main ahocorasick 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 _AUTOMATA_H_
+#define _AUTOMATA_H_
+
+#include "node.h"
+
+typedef struct
+{
+ /* The root of the Aho-Corasick trie */
+ AC_NODE_t * root;
+
+ /* maintain all nodes pointers. it will be used to access or release
+ * all nodes. */
+ AC_NODE_t ** all_nodes;
+
+ unsigned int all_nodes_num; /* Number of all nodes in the automata */
+ unsigned int all_nodes_max; /* Current max allocated memory for *all_nodes */
+
+ AC_MATCH_t match; /* Any match is reported with this */
+ MATCH_CALBACK_f match_callback; /* Match call-back function */
+
+ /* this flag indicates that if automata is finalized by
+ * ac_automata_finalize() or not. 1 means finalized and 0
+ * means not finalized (is open). after finalizing automata you can not
+ * add pattern to automata anymore. */
+ unsigned short automata_open;
+
+ /* It is possible to feed a large input to the automata chunk by chunk to
+ * be searched using ac_automata_search(). in fact by default automata
+ * thinks that all chunks are related unless you do ac_automata_reset().
+ * followings are variables that keep track of searching state. */
+ AC_NODE_t * current_node; /* Pointer to current node while searching */
+ unsigned long base_position; /* Represents the position of current chunk
+ related to whole input text */
+
+ /* Statistic Variables */
+ unsigned long total_patterns; /* Total patterns in the automata */
+
+} AC_AUTOMATA_t;
+
+
+AC_AUTOMATA_t * ac_automata_init (MATCH_CALBACK_f mc);
+AC_ERROR_t ac_automata_add (AC_AUTOMATA_t * thiz, AC_PATTERN_t * str);
+void ac_automata_finalize (AC_AUTOMATA_t * thiz);
+int ac_automata_search (AC_AUTOMATA_t * thiz, AC_TEXT_t * str, void * param);
+void ac_automata_reset (AC_AUTOMATA_t * thiz);
+void ac_automata_release (AC_AUTOMATA_t * thiz);
+void ac_automata_display (AC_AUTOMATA_t * thiz, char repcast);
+
+#endif
diff --git a/src/lib/third_party/include/node.h b/src/lib/third_party/include/node.h
new file mode 100644
index 000000000..13cf2ff11
--- /dev/null
+++ b/src/lib/third_party/include/node.h
@@ -0,0 +1,66 @@
+/*
+ * 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);
+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);
+void node_assign_id (AC_NODE_t * thiz);
+void node_sort_edges (AC_NODE_t * thiz);
+
+#endif
diff --git a/src/lib/third_party/include/patricia.h b/src/lib/third_party/include/patricia.h
new file mode 100644
index 000000000..be8476e85
--- /dev/null
+++ b/src/lib/third_party/include/patricia.h
@@ -0,0 +1,302 @@
+/*
+ * $Id: patricia.h,v 1.6 2005/12/07 20:53:01 dplonka Exp $
+ * Dave Plonka <plonka@doit.wisc.edu>
+ *
+ * This product includes software developed by the University of Michigan,
+ * Merit Network, Inc., and their contributors.
+ *
+ * This file had been called "radix.h" in the MRT sources.
+ *
+ * I renamed it to "patricia.h" since it's not an implementation of a general
+ * radix trie. Also, pulled in various requirements from "mrt.h" and added
+ * some other things it could be used as a standalone API.
+
+ https://github.com/deepfield/MRT/blob/master/COPYRIGHT
+
+ Copyright (c) 1999-2013
+
+ The Regents of the University of Michigan ("The Regents") and Merit
+ Network, Inc.
+
+ Redistributions of source code must retain the above copyright notice,
+ this list of conditions and the following disclaimer.
+
+ Redistributions in binary form must reproduce the above copyright
+ notice, this list of conditions and the following disclaimer in the
+ documentation and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef _PATRICIA_H
+#define _PATRICIA_H
+
+#define HAVE_IPV6
+
+/* typedef unsigned int u_int; */
+/* { from defs.h */
+#define prefix_touchar(prefix) ((u_char *)&(prefix)->add.sin)
+
+#ifdef __KERNEL__
+#define MAXLINE 512
+#else
+#define MAXLINE 1024
+#endif
+
+#define BIT_TEST(f, b) ((f) & (b))
+/* } */
+
+#define addroute make_and_lookup
+
+#ifndef __KERNEL__
+#include <sys/types.h> /* for u_* definitions (on FreeBSD 5) */
+#include <errno.h> /* for EAFNOSUPPORT */
+
+#ifndef EAFNOSUPPORT
+# defined EAFNOSUPPORT WSAEAFNOSUPPORT
+#else
+#ifndef WIN32
+# include <netinet/in.h> /* for struct in_addr */
+#endif
+#endif
+
+#ifndef WIN32
+#include <sys/socket.h> /* for AF_INET */
+#else
+#include <winsock2.h>
+#include <ws2tcpip.h> /* IPv6 */
+#endif
+
+#endif /* __KERNEL__ */
+
+/* { from mrt.h */
+
+typedef struct the_prefix4_t {
+ unsigned short family; /* AF_INET | AF_INET6 */
+ unsigned short bitlen; /* same as mask? */
+ int ref_count; /* reference count */
+ struct in_addr sin;
+} prefix4_t;
+
+typedef struct the_prefix_t {
+ unsigned short family; /* AF_INET | AF_INET6 */
+ unsigned short bitlen; /* same as mask? */
+ int ref_count; /* reference count */
+ union {
+ struct in_addr sin;
+#ifdef HAVE_IPV6
+ struct in6_addr sin6;
+#endif /* IPV6 */
+ } add;
+} prefix_t;
+
+/* } */
+
+/* pointer to usr data (ex. route flap info) */
+union patricia_node_value_t {
+ void *user_data;
+ u_int32_t user_value;
+};
+
+typedef struct _patricia_node_t {
+ u_int bit; /* flag if this node used */
+ prefix_t *prefix; /* who we are in patricia tree */
+ struct _patricia_node_t *l, *r; /* left and right children */
+ struct _patricia_node_t *parent;/* may be used */
+ void *data; /* pointer to data */
+ union patricia_node_value_t value;
+} patricia_node_t;
+
+typedef struct _patricia_tree_t {
+ patricia_node_t *head;
+ u_int maxbits; /* for IP, 32 bit addresses */
+ int num_active_node; /* for debug purpose */
+} patricia_tree_t;
+
+typedef void (*void_fn_t)(void *data);
+typedef void (*void_fn2_t)(prefix_t *prefix, void *data);
+
+/* renamed to ndpi_Patricia to avoid name conflicts */
+patricia_node_t *ndpi_patricia_search_exact (patricia_tree_t *patricia, prefix_t *prefix);
+patricia_node_t *ndpi_patricia_search_best (patricia_tree_t *patricia, prefix_t *prefix);
+patricia_node_t * ndpi_patricia_search_best2 (patricia_tree_t *patricia, prefix_t *prefix,
+ int inclusive);
+patricia_node_t *ndpi_patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix);
+void ndpi_patricia_remove (patricia_tree_t *patricia, patricia_node_t *node);
+patricia_tree_t *ndpi_New_Patricia (int maxbits);
+void ndpi_Clear_Patricia (patricia_tree_t *patricia, void_fn_t func);
+void ndpi_Destroy_Patricia (patricia_tree_t *patricia, void_fn_t func);
+void ndpi_patricia_process (patricia_tree_t *patricia, void_fn2_t func);
+
+#define PATRICIA_MAXBITS (sizeof(struct in6_addr) * 8)
+#define PATRICIA_NBIT(x) (0x80 >> ((x) & 0x7f))
+#define PATRICIA_NBYTE(x) ((x) >> 3)
+
+#define PATRICIA_DATA_GET(node, type) (type *)((node)->data)
+#define PATRICIA_DATA_SET(node, value) ((node)->data = (void *)(value))
+
+#define PATRICIA_WALK(Xhead, Xnode) \
+ do { \
+ patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
+ patricia_node_t **Xsp = Xstack; \
+ patricia_node_t *Xrn = (Xhead); \
+ while ((Xnode = Xrn)) { \
+ if (Xnode->prefix)
+
+#define PATRICIA_WALK_ALL(Xhead, Xnode) \
+ do { \
+ patricia_node_t *Xstack[PATRICIA_MAXBITS+1]; \
+ patricia_node_t **Xsp = Xstack; \
+ patricia_node_t *Xrn = (Xhead); \
+ while ((Xnode = Xrn)) { \
+ if (1)
+
+#define PATRICIA_WALK_BREAK { \
+ if (Xsp != Xstack) { \
+ Xrn = *(--Xsp); \
+ } else { \
+ Xrn = (patricia_node_t *) 0; \
+ } \
+ continue; }
+
+#define PATRICIA_WALK_END \
+ if (Xrn->l) { \
+ if (Xrn->r) { \
+ *Xsp++ = Xrn->r; \
+ } \
+ Xrn = Xrn->l; \
+ } else if (Xrn->r) { \
+ Xrn = Xrn->r; \
+ } else if (Xsp != Xstack) { \
+ Xrn = *(--Xsp); \
+ } else { \
+ Xrn = (patricia_node_t *) 0; \
+ } \
+ } \
+ } while (0)
+
+#endif /* _PATRICIA_H */
+
+/*************************
+
+
+ [newtool.gif]
+
+MRT Credits
+
+ The Multi-Threaded Routing Toolkit
+ _________________________________________________________________
+
+ MRT was developed by [1]Merit Network, Inc., under National Science
+ Foundation grant NCR-9318902, "Experimentation with Routing Technology
+ to be Used for Inter-Domain Routing in the Internet."
+
+ Current MRT Staff
+
+ * [2]Craig Labovitz <labovit@merit.edu>
+ * [3]Makaki Hirabaru <masaki@merit.edu>
+ * [4]Farnam Jahanian <farnam@eecs.umich.edu>
+ * Susan Hares <skh@merit.edu>
+ * Susan R. Harris <srh@merit.edu>
+ * Nathan Binkert <binkertn@eecs.umich.edu>
+ * Gerald Winters <gerald@merit.edu>
+
+ Project Alumni
+
+ * [5]Marc Unangst <mju@merit.edu>
+ * John Scudder <jgs@ieng.com>
+
+ The BGP4+ extension was originally written by Francis Dupont
+ <Francis.Dupont@inria.fr>.
+
+ The public domain Struct C-library of linked list, hash table and
+ memory allocation routines was developed by Jonathan Dekock
+ <dekock@cadence.com>.
+
+ Susan Rebecca Harris <srh@merit.edu> provided help with the
+ documentation.
+ David Ward <dward@netstar.com> provided bug fixes and helpful
+ suggestions.
+ Some sections of code and architecture ideas were taken from the GateD
+ routing daemon.
+
+ The first port to Linux with IPv6 was done by Pedro Roque
+ <roque@di.fc.ul.pt>. Some interface routines to the Linux kernel were
+ originally written by him.
+
+ Alexey Kuznetsov made enhancements to 1.4.3a and fixed the Linux
+ kernel intarface. Linux's netlink interface was written, referring to
+ his code "iproute2".
+
+ We would also like to thank our other colleagues in Japan, Portugal,
+ the Netherlands, the UK, and the US for their many contributions to
+ the MRT development effort.
+ _________________________________________________________________
+
+ Cisco is a registered trademark of Cisco Systems Inc.
+ _________________________________________________________________
+
+ Merit Network 4251 Plymouth Road Suite C Ann Arbor, MI 48105-2785
+ 734-764-9430
+ info@merit.edu
+ _________________________________________________________________
+
+ � 1999 Merit Network, Inc.
+ [6]www@merit.edu
+
+References
+
+ 1. http://www.merit.edu/
+ 2. http://www.merit.edu/~labovit
+ 3. http://www.merit.edu/~masaki
+ 4. http://www.eecs.umich.edu/~farnam
+ 5. http://www.contrib.andrew.cmu.edu/~mju/
+ 6. mailto:www@merit.edu
+
+------------
+
+Copyright (c) 1997, 1998, 1999
+
+
+The Regents of the University of Michigan ("The Regents") and Merit Network,
+Inc. All rights reserved.
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+1. Redistributions of source code must retain the above
+ copyright notice, this list of conditions and the
+ following disclaimer.
+2. Redistributions in binary form must reproduce the above
+ copyright notice, this list of conditions and the
+ following disclaimer in the documentation and/or other
+ materials provided with the distribution.
+3. All advertising materials mentioning features or use of
+ this software must display the following acknowledgement:
+This product includes software developed by the University of Michigan, Merit
+Network, Inc., and their contributors.
+4. Neither the name of the University, Merit Network, nor the
+ names of their contributors may be used to endorse or
+ promote products derived from this software without
+ specific prior written permission.
+THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS "AS IS" AND ANY
+EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE FOR ANY
+DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
+ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+
+************************ */
diff --git a/src/lib/third_party/include/sort.h b/src/lib/third_party/include/sort.h
new file mode 100644
index 000000000..ee7df8a10
--- /dev/null
+++ b/src/lib/third_party/include/sort.h
@@ -0,0 +1,6 @@
+/* This is a function ported from the Linux kernel lib/sort.c */
+
+void sort(void *base, size_t num, size_t len,
+ int (*cmp_func)(const void *, const void *),
+ void (*swap_func)(void *, void *, int size));
+
diff --git a/src/lib/third_party/src/ahocorasick.c b/src/lib/third_party/src/ahocorasick.c
new file mode 100644
index 000000000..54a97e776
--- /dev/null
+++ b/src/lib/third_party/src/ahocorasick.c
@@ -0,0 +1,391 @@
+/*
+ * ahocorasick.c: implementation of ahocorasick library's functions
+ * 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 __KERNEL__
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+#endif
+
+#include "ndpi_api.h"
+#include "ahocorasick.h"
+
+/* Allocation step for automata.all_nodes */
+#define REALLOC_CHUNK_ALLNODES 200
+
+/* Private function prototype */
+static void ac_automata_register_nodeptr
+(AC_AUTOMATA_t * thiz, AC_NODE_t * node);
+static void ac_automata_union_matchstrs
+(AC_NODE_t * node);
+static void ac_automata_set_failure
+(AC_AUTOMATA_t * thiz, AC_NODE_t * node, AC_ALPHABET_t * alphas);
+static void ac_automata_traverse_setfailure
+(AC_AUTOMATA_t * thiz, AC_NODE_t * node, AC_ALPHABET_t * alphas);
+
+
+/******************************************************************************
+ * FUNCTION: ac_automata_init
+ * Initialize automata; allocate memories and set initial values
+ * PARAMS:
+ * MATCH_CALBACK mc: call-back function
+ * the call-back function will be used to reach the caller on match occurrence
+ ******************************************************************************/
+AC_AUTOMATA_t * ac_automata_init (MATCH_CALBACK_f mc)
+{
+ AC_AUTOMATA_t * thiz = (AC_AUTOMATA_t *)ndpi_malloc(sizeof(AC_AUTOMATA_t));
+ memset (thiz, 0, sizeof(AC_AUTOMATA_t));
+ thiz->root = node_create ();
+ thiz->all_nodes_max = REALLOC_CHUNK_ALLNODES;
+ thiz->all_nodes = (AC_NODE_t **) ndpi_malloc (thiz->all_nodes_max*sizeof(AC_NODE_t *));
+ thiz->match_callback = mc;
+ ac_automata_register_nodeptr (thiz, thiz->root);
+ ac_automata_reset (thiz);
+ thiz->total_patterns = 0;
+ thiz->automata_open = 1;
+ return thiz;
+}
+
+/******************************************************************************
+ * FUNCTION: ac_automata_add
+ * Adds pattern to the automata.
+ * PARAMS:
+ * AC_AUTOMATA_t * thiz: the pointer to the automata
+ * AC_PATTERN_t * patt: the pointer to added pattern
+ * RETUERN VALUE: AC_ERROR_t
+ * the return value indicates the success or failure of adding action
+ ******************************************************************************/
+AC_ERROR_t ac_automata_add (AC_AUTOMATA_t * thiz, AC_PATTERN_t * patt)
+{
+ unsigned int i;
+ AC_NODE_t * n = thiz->root;
+ AC_NODE_t * next;
+ AC_ALPHABET_t alpha;
+
+ if(!thiz->automata_open)
+ return ACERR_AUTOMATA_CLOSED;
+
+ if (!patt->length)
+ return ACERR_ZERO_PATTERN;
+
+ if (patt->length > AC_PATTRN_MAX_LENGTH)
+ return ACERR_LONG_PATTERN;
+
+ for (i=0; i<patt->length; i++)
+ {
+ alpha = patt->astring[i];
+ if ((next = node_find_next(n, alpha)))
+ {
+ n = next;
+ continue;
+ }
+ else
+ {
+ next = node_create_next(n, alpha);
+ next->depth = n->depth + 1;
+ n = next;
+ ac_automata_register_nodeptr(thiz, n);
+ }
+ }
+
+ if(n->final)
+ return ACERR_DUPLICATE_PATTERN;
+
+ n->final = 1;
+ node_register_matchstr(n, patt);
+ thiz->total_patterns++;
+
+ return ACERR_SUCCESS;
+}
+
+/******************************************************************************
+ * FUNCTION: ac_automata_finalize
+ * Locate the failure node for all nodes and collect all matched pattern for
+ * every node. it also sorts outgoing edges of node, so binary search could be
+ * performed on them. after calling this function the automate literally will
+ * be finalized and you can not add new patterns to the automate.
+ * PARAMS:
+ * AC_AUTOMATA_t * thiz: the pointer to the automata
+ ******************************************************************************/
+void ac_automata_finalize (AC_AUTOMATA_t * thiz)
+{
+ unsigned int i;
+ AC_ALPHABET_t *alphas;
+ AC_NODE_t * node;
+
+ if((alphas = ndpi_malloc(AC_PATTRN_MAX_LENGTH)) != NULL) {
+ ac_automata_traverse_setfailure (thiz, thiz->root, alphas);
+
+ for (i=0; i < thiz->all_nodes_num; i++)
+ {
+ node = thiz->all_nodes[i];
+ ac_automata_union_matchstrs (node);
+ node_sort_edges (node);
+ }
+ thiz->automata_open = 0; /* do not accept patterns any more */
+ ndpi_free(alphas);
+ }
+}
+
+/******************************************************************************
+ * FUNCTION: ac_automata_search
+ * Search in the input text using the given automata. on match event it will
+ * call the call-back function. and the call-back function in turn after doing
+ * its job, will return an integer value to ac_automata_search(). 0 value means
+ * continue search, and non-0 value means stop search and return to the caller.
+ * PARAMS:
+ * AC_AUTOMATA_t * thiz: the pointer to the automata
+ * AC_TEXT_t * txt: the input text that must be searched
+ * void * param: this parameter will be send to call-back function. it is
+ * useful for sending parameter to call-back function from caller function.
+ * RETURN VALUE:
+ * -1: failed call; automata is not finalized
+ * 0: success; continue searching; call-back sent me a 0 value
+ * 1: success; stop searching; call-back sent me a non-0 value
+ ******************************************************************************/
+int ac_automata_search (AC_AUTOMATA_t * thiz, AC_TEXT_t * txt, void * param)
+{
+ unsigned long position;
+ AC_NODE_t *curr;
+ AC_NODE_t *next;
+
+ if(thiz->automata_open)
+ /* you must call ac_automata_locate_failure() first */
+ return -1;
+
+ position = 0;
+ curr = thiz->current_node;
+
+ /* This is the main search loop.
+ * it must be keep as lightweight as possible. */
+ while (position < txt->length)
+ {
+ if(!(next = node_findbs_next(curr, txt->astring[position])))
+ {
+ if(curr->failure_node /* we are not in the root node */)
+ curr = curr->failure_node;
+ else
+ position++;
+ }
+ else
+ {
+ curr = next;
+ position++;
+ }
+
+ if(curr->final && next)
+ /* We check 'next' to find out if we came here after a alphabet
+ * transition or due to a fail. in second case we should not report
+ * matching because it was reported in previous node */
+ {
+ thiz->match.position = position + thiz->base_position;
+ thiz->match.match_num = curr->matched_patterns_num;
+ thiz->match.patterns = curr->matched_patterns;
+ /* we found a match! do call-back */
+ if (thiz->match_callback(&thiz->match, param))
+ return 1;
+ }
+ }
+
+ /* save status variables */
+ thiz->current_node = curr;
+ thiz->base_position += position;
+ return 0;
+}
+
+/******************************************************************************
+ * FUNCTION: ac_automata_reset
+ * reset the automata and make it ready for doing new search on a new text.
+ * when you finished with the input text, you must reset automata state for
+ * new input, otherwise it will not work.
+ * PARAMS:
+ * AC_AUTOMATA_t * thiz: the pointer to the automata
+ ******************************************************************************/
+void ac_automata_reset (AC_AUTOMATA_t * thiz)
+{
+ thiz->current_node = thiz->root;
+ thiz->base_position = 0;
+}
+
+/******************************************************************************
+ * FUNCTION: ac_automata_release
+ * Release all allocated memories to the automata
+ * PARAMS:
+ * AC_AUTOMATA_t * thiz: the pointer to the automata
+ ******************************************************************************/
+void ac_automata_release (AC_AUTOMATA_t * thiz)
+{
+ unsigned int i;
+ AC_NODE_t * n;
+
+ for (i=0; i < thiz->all_nodes_num; i++)
+ {
+ n = thiz->all_nodes[i];
+ node_release(n);
+ }
+ ndpi_free(thiz->all_nodes);
+ ndpi_free(thiz);
+}
+
+#ifndef __KERNEL__
+/******************************************************************************
+ * FUNCTION: ac_automata_display
+ * Prints the automata to output in human readable form. it is useful for
+ * debugging purpose.
+ * PARAMS:
+ * AC_AUTOMATA_t * thiz: the pointer to the automata
+ * char repcast: 'n': print AC_REP_t as number, 's': print AC_REP_t as string
+ ******************************************************************************/
+void ac_automata_display (AC_AUTOMATA_t * thiz, char repcast)
+{
+ unsigned int i, j;
+ AC_NODE_t * n;
+ struct edge * e;
+ AC_PATTERN_t sid;
+
+ printf("---------------------------------\n");
+
+ for (i=0; i<thiz->all_nodes_num; i++)
+ {
+ n = thiz->all_nodes[i];
+ printf("NODE(%3d)/----fail----> NODE(%3d)\n",
+ n->id, (n->failure_node)?n->failure_node->id:1);
+ for (j=0; j<n->outgoing_degree; j++)
+ {
+ e = &n->outgoing[j];
+ printf(" |----(");
+ if(isgraph(e->alpha))
+ printf("%c)---", e->alpha);
+ else
+ printf("0x%x)", e->alpha);
+ printf("--> NODE(%3d)\n", e->next->id);
+ }
+ if (n->matched_patterns_num) {
+ printf("Accepted patterns: {");
+ for (j=0; j<n->matched_patterns_num; j++)
+ {
+ sid = n->matched_patterns[j];
+ if(j) printf(", ");
+ switch (repcast)
+ {
+ case 'n':
+ printf("%ld", sid.rep.number);
+ break;
+ case 's':
+ printf("%s", sid.rep.stringy);
+ break;
+ }
+ }
+ printf("}\n");
+ }
+ printf("---------------------------------\n");
+ }
+}
+#endif /* __KERNEL__ */
+
+/******************************************************************************
+ * FUNCTION: ac_automata_register_nodeptr
+ * Adds the node pointer to all_nodes.
+ ******************************************************************************/
+static void ac_automata_register_nodeptr (AC_AUTOMATA_t * thiz, AC_NODE_t * node)
+{
+ if(thiz->all_nodes_num >= thiz->all_nodes_max)
+ {
+ thiz->all_nodes = ndpi_realloc(thiz->all_nodes,
+ thiz->all_nodes_max*sizeof(AC_NODE_t *),
+ (REALLOC_CHUNK_ALLNODES+thiz->all_nodes_max)*sizeof(AC_NODE_t *)
+ );
+ thiz->all_nodes_max += REALLOC_CHUNK_ALLNODES;
+ }
+ thiz->all_nodes[thiz->all_nodes_num++] = node;
+}
+
+/******************************************************************************
+ * FUNCTION: ac_automata_union_matchstrs
+ * Collect accepted patterns of the node. the accepted patterns consist of the
+ * node's own accepted pattern plus accepted patterns of its failure node.
+ ******************************************************************************/
+static void ac_automata_union_matchstrs (AC_NODE_t * node)
+{
+ unsigned int i;
+ AC_NODE_t * m = node;
+
+ while ((m = m->failure_node))
+ {
+ for (i=0; i < m->matched_patterns_num; i++)
+ node_register_matchstr(node, &(m->matched_patterns[i]));
+
+ if (m->final)
+ node->final = 1;
+ }
+ // TODO : sort matched_patterns? is that necessary? I don't think so.
+}
+
+/******************************************************************************
+ * FUNCTION: ac_automata_set_failure
+ * find failure node for the given node.
+ ******************************************************************************/
+static void ac_automata_set_failure
+(AC_AUTOMATA_t * thiz, AC_NODE_t * node, AC_ALPHABET_t * alphas)
+{
+ unsigned int i, j;
+ AC_NODE_t * m;
+
+ for (i=1; i < node->depth; i++)
+ {
+ m = thiz->root;
+ for (j=i; j < node->depth && m; j++)
+ m = node_find_next (m, alphas[j]);
+ if (m)
+ {
+ node->failure_node = m;
+ break;
+ }
+ }
+ if (!node->failure_node)
+ node->failure_node = thiz->root;
+}
+
+/******************************************************************************
+ * FUNCTION: ac_automata_traverse_setfailure
+ * Traverse all automata nodes using DFS (Depth First Search), meanwhile it set
+ * the failure node for every node it passes through. this function must be
+ * called after adding last pattern to automata. i.e. after calling this you
+ * can not add further pattern to automata.
+ ******************************************************************************/
+static void ac_automata_traverse_setfailure
+(AC_AUTOMATA_t * thiz, AC_NODE_t * node, AC_ALPHABET_t * alphas)
+{
+ unsigned int i;
+ AC_NODE_t * next;
+
+ for (i=0; i < node->outgoing_degree; i++)
+ {
+ alphas[node->depth] = node->outgoing[i].alpha;
+ next = node->outgoing[i].next;
+
+ /* At every node look for its failure node */
+ ac_automata_set_failure (thiz, next, alphas);
+
+ /* Recursively call itself to traverse all nodes */
+ ac_automata_traverse_setfailure (thiz, next, alphas);
+ }
+}
diff --git a/src/lib/third_party/src/node.c b/src/lib/third_party/src/node.c
new file mode 100644
index 000000000..404fb24d4
--- /dev/null
+++ b/src/lib/third_party/src/node.c
@@ -0,0 +1,260 @@
+/*
+ * node.c: implementation of automata node
+ * 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 __KERNEL__
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#endif
+
+#include "ndpi_api.h"
+
+#include "../include/node.h"
+#include "sort.h"
+
+/* reallocation step for AC_NODE_t.matched_patterns */
+#define REALLOC_CHUNK_MATCHSTR 8
+
+/* reallocation step for AC_NODE_t.outgoing array */
+#define REALLOC_CHUNK_OUTGOING 8
+/* TODO: For different depth of node, number of outgoing edges differs
+ considerably, It is efficient to use different chunk size for
+ different depths */
+
+/* Private function prototype */
+void node_init (AC_NODE_t * thiz);
+int node_edge_compare (const void * l, const void * r);
+int node_has_matchstr (AC_NODE_t * thiz, AC_PATTERN_t * newstr);
+
+
+/******************************************************************************
+ * FUNCTION: node_create
+ * Create the node
+ ******************************************************************************/
+AC_NODE_t * node_create(void)
+{
+ AC_NODE_t * thiz = (AC_NODE_t *) ndpi_malloc (sizeof(AC_NODE_t));
+ node_init(thiz);
+ node_assign_id(thiz);
+ return thiz;
+}
+
+/******************************************************************************
+ * FUNCTION: node_init
+ * Initialize node
+ ******************************************************************************/
+void node_init(AC_NODE_t * thiz)
+{
+ memset(thiz, 0, sizeof(AC_NODE_t));
+
+ thiz->outgoing_max = REALLOC_CHUNK_OUTGOING;
+ thiz->outgoing = (struct edge *) ndpi_malloc
+ (thiz->outgoing_max*sizeof(struct edge));
+
+ thiz->matched_patterns_max = REALLOC_CHUNK_MATCHSTR;
+ thiz->matched_patterns = (AC_PATTERN_t *) ndpi_malloc
+ (thiz->matched_patterns_max*sizeof(AC_PATTERN_t));
+}
+
+/******************************************************************************
+ * FUNCTION: node_release
+ * Release node
+ ******************************************************************************/
+void node_release(AC_NODE_t * thiz)
+{
+ ndpi_free(thiz->matched_patterns);
+ ndpi_free(thiz->outgoing);
+ ndpi_free(thiz);
+}
+
+/******************************************************************************
+ * FUNCTION: node_find_next
+ * Find out the next node for a given Alpha to move. this function is used in
+ * the pre-processing stage in which edge array is not sorted. so it uses
+ * linear search.
+ ******************************************************************************/
+AC_NODE_t * node_find_next(AC_NODE_t * thiz, AC_ALPHABET_t alpha)
+{
+ int i;
+
+ for (i=0; i < thiz->outgoing_degree; i++)
+ {
+ if(thiz->outgoing[i].alpha == alpha)
+ return (thiz->outgoing[i].next);
+ }
+ return NULL;
+}
+
+/******************************************************************************
+ * FUNCTION: node_findbs_next
+ * Find out the next node for a given Alpha. this function is used after the
+ * pre-processing stage in which we sort edges. so it uses Binary Search.
+ ******************************************************************************/
+AC_NODE_t * node_findbs_next (AC_NODE_t * thiz, AC_ALPHABET_t alpha)
+{
+ int min, max, mid;
+ AC_ALPHABET_t amid;
+
+ min = 0;
+ max = thiz->outgoing_degree - 1;
+
+ while (min <= max)
+ {
+ mid = (min+max) >> 1;
+ amid = thiz->outgoing[mid].alpha;
+ if (alpha > amid)
+ min = mid + 1;
+ else if (alpha < amid)
+ max = mid - 1;
+ else
+ return (thiz->outgoing[mid].next);
+ }
+ return NULL;
+}
+
+/******************************************************************************
+ * FUNCTION: node_has_matchstr
+ * Determine if a final node contains a pattern in its accepted pattern list
+ * or not. return values: 1 = it has, 0 = it hasn't
+ ******************************************************************************/
+int node_has_matchstr (AC_NODE_t * thiz, AC_PATTERN_t * newstr)
+{
+ int i, j;
+ AC_PATTERN_t * str;
+
+ for (i=0; i < thiz->matched_patterns_num; i++)
+ {
+ str = &thiz->matched_patterns[i];
+
+ if (str->length != newstr->length)
+ continue;
+
+ for (j=0; j<(int)str->length; j++)
+ if(str->astring[j] != newstr->astring[j])
+ continue;
+
+ if (j == str->length)
+ return 1;
+ }
+ return 0;
+}
+
+/******************************************************************************
+ * FUNCTION: node_create_next
+ * Create the next node for the given alpha.
+ ******************************************************************************/
+AC_NODE_t * node_create_next (AC_NODE_t * thiz, AC_ALPHABET_t alpha)
+{
+ AC_NODE_t * next;
+ next = node_find_next (thiz, alpha);
+ if (next)
+ /* The edge already exists */
+ return NULL;
+ /* Otherwise register new edge */
+ next = node_create ();
+ node_register_outgoing(thiz, next, alpha);
+
+ return next;
+}
+
+/******************************************************************************
+ * FUNCTION: node_register_matchstr
+ * Adds the pattern to the list of accepted pattern.
+ ******************************************************************************/
+void node_register_matchstr (AC_NODE_t * thiz, AC_PATTERN_t * str)
+{
+ /* Check if the new pattern already exists in the node list */
+ if (node_has_matchstr(thiz, str))
+ return;
+
+ /* Manage memory */
+ if (thiz->matched_patterns_num >= thiz->matched_patterns_max)
+ {
+ thiz->matched_patterns = (AC_PATTERN_t *) ndpi_realloc
+ (thiz->matched_patterns, thiz->matched_patterns_max*sizeof(AC_PATTERN_t),
+ (REALLOC_CHUNK_MATCHSTR+thiz->matched_patterns_max)*sizeof(AC_PATTERN_t));
+
+ thiz->matched_patterns_max += REALLOC_CHUNK_MATCHSTR;
+ }
+
+ thiz->matched_patterns[thiz->matched_patterns_num].astring = str->astring;
+ thiz->matched_patterns[thiz->matched_patterns_num].length = str->length;
+ thiz->matched_patterns[thiz->matched_patterns_num].rep = str->rep;
+ thiz->matched_patterns_num++;
+}
+
+/******************************************************************************
+ * FUNCTION: node_register_outgoing
+ * Establish an edge between two nodes
+ ******************************************************************************/
+void node_register_outgoing
+(AC_NODE_t * thiz, AC_NODE_t * next, AC_ALPHABET_t alpha)
+{
+ if(thiz->outgoing_degree >= thiz->outgoing_max)
+ {
+ thiz->outgoing = (struct edge *) ndpi_realloc
+ (thiz->outgoing, thiz->outgoing_max*sizeof(struct edge),
+ (REALLOC_CHUNK_OUTGOING+thiz->outgoing_max)*sizeof(struct edge));
+ thiz->outgoing_max += REALLOC_CHUNK_OUTGOING;
+ }
+
+ thiz->outgoing[thiz->outgoing_degree].alpha = alpha;
+ thiz->outgoing[thiz->outgoing_degree++].next = next;
+}
+
+/******************************************************************************
+ * FUNCTION: node_assign_id
+ * assign a unique ID to the node (used for debugging purpose).
+ ******************************************************************************/
+void node_assign_id (AC_NODE_t * thiz)
+{
+ static int unique_id = 1;
+ thiz->id = unique_id ++;
+}
+
+/******************************************************************************
+ * FUNCTION: node_edge_compare
+ * Comparison function for qsort. see man qsort.
+ ******************************************************************************/
+int node_edge_compare (const void * l, const void * r)
+{
+ /* According to man page:
+ * The comparison function must return an integer less than, equal to, or
+ * greater than zero if the first argument is considered to be
+ * respectively less than, equal to, or greater than the second. if two
+ * members compare as equal, their order in the sorted array is undefined.
+ *
+ * NOTE: Because edge alphabets are unique in every node we ignore
+ * equivalence case.
+ **/
+ if ( ((struct edge *)l)->alpha >= ((struct edge *)r)->alpha )
+ return 1;
+ else
+ return -1;
+}
+
+/******************************************************************************
+ * FUNCTION: node_sort_edges
+ * sorts edges alphabets.
+ ******************************************************************************/
+void node_sort_edges (AC_NODE_t * thiz)
+{
+ sort ((void *)thiz->outgoing, thiz->outgoing_degree, sizeof(struct edge), node_edge_compare, NULL);
+}
diff --git a/src/lib/third_party/src/patricia.c b/src/lib/third_party/src/patricia.c
new file mode 100644
index 000000000..b7b4c2010
--- /dev/null
+++ b/src/lib/third_party/src/patricia.c
@@ -0,0 +1,1076 @@
+/*
+ * $Id: patricia.c,v 1.7 2005/12/07 20:46:41 dplonka Exp $
+ * Dave Plonka <plonka@doit.wisc.edu>
+ *
+ * This product includes software developed by the University of Michigan,
+ * Merit Network, Inc., and their contributors.
+ *
+ * This file had been called "radix.c" in the MRT sources.
+ *
+ * I renamed it to "patricia.c" since it's not an implementation of a general
+ * radix trie. Also I pulled in various requirements from "prefix.c" and
+ * "demo.c" so that it could be used as a standalone API.
+
+
+ https://github.com/deepfield/MRT/blob/master/COPYRIGHT
+
+ Copyright (c) 1999-2013
+
+ The Regents of the University of Michigan ("The Regents") and Merit
+ Network, Inc.
+
+ Redistributions of source code must retain the above copyright notice,
+ this list of conditions and the following disclaimer.
+
+ Redistributions in binary form must reproduce the above copyright
+ notice, this list of conditions and the following disclaimer in the
+ documentation and/or other materials provided with the distribution.
+
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef __KERNEL__
+#include <assert.h> /* assert */
+#include <ctype.h> /* isdigit */
+#include <errno.h> /* errno */
+#include <math.h> /* sin */
+#include <stddef.h> /* NULL */
+#include <stdio.h> /* sprintf, fprintf, stderr */
+#include <stdlib.h> /* free, atol, calloc */
+#include <string.h> /* memcpy, strchr, strlen */
+#include <sys/types.h> /* BSD: for inet_addr */
+#ifndef WIN32
+#include <sys/socket.h> /* BSD, Linux: for inet_addr */
+#include <netinet/in.h> /* BSD, Linux: for inet_addr */
+#include <arpa/inet.h> /* BSD, Linux, Solaris: for inet_addr */
+#endif
+#else
+#define assert(a) ;
+#endif /* __KERNEL__ */
+
+#include "patricia.h"
+
+#ifdef __KERNEL__
+
+long atol(const char *nptr) {
+ long l;
+ char *endp;
+
+ l = simple_strtol(nptr, &endp, 10);
+ return(l);
+}
+#endif
+
+// #define PATRICIA_DEBUG
+
+void ndpi_DeleteEntry(void *a) {
+ ndpi_free(a);
+}
+
+/* { from prefix.c */
+
+/* ndpi_prefix_tochar
+ * convert prefix information to bytes
+ */
+u_char *
+ndpi_prefix_tochar (prefix_t * prefix)
+{
+ if(prefix == NULL)
+ return (NULL);
+
+ return ((u_char *) & prefix->add.sin);
+}
+
+int ndpi_comp_with_mask (void *addr, void *dest, u_int mask) {
+ if( /* mask/8 == 0 || */ memcmp (addr, dest, mask / 8) == 0) {
+ int n = mask / 8;
+ int m = ((-1) << (8 - (mask % 8)));
+
+ if(mask % 8 == 0 || (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m))
+ return (1);
+ }
+ return (0);
+}
+
+#if 0 /* this implementation does not support IPv6, using system inet_pton */
+#ifndef WIN32
+/* inet_pton substitute implementation
+ * Uses inet_addr to convert an IP address in dotted decimal notation into
+ * unsigned long and copies the result to dst.
+ * Only supports AF_INET. Follows standard error return conventions of
+ * inet_pton.
+ */
+int
+inet_pton (int af, const char *src, void *dst)
+{
+ u_long result;
+
+ if(af == AF_INET) {
+ result = inet_addr(src);
+ if(result == -1)
+ return 0;
+ else {
+ memcpy (dst, &result, sizeof(struct in_addr));
+ return 1;
+ }
+ }
+#ifdef NT
+#if defined(HAVE_IPV6) && (!defined(__KERNEL__))
+ else if(af == AF_INET6) {
+ struct in6_addr Address;
+ return (inet6_addr(src, &Address));
+ }
+#endif /* HAVE_IPV6 */
+#endif /* NT */
+#ifndef NT
+ else {
+ printf("NOT SUPP\n");
+ errno = EAFNOSUPPORT;
+ return -1;
+ }
+#endif /* NT */
+}
+#endif
+#endif
+
+/* this allows imcomplete prefix */
+int
+ndpi_my_inet_pton (int af, const char *src, void *dst)
+{
+ if(af == AF_INET) {
+ int i;
+ u_char xp[sizeof(struct in_addr)] = {0, 0, 0, 0};
+
+ for (i = 0; ; i++) {
+ int c, val;
+
+ c = *src++;
+ if(!isdigit (c))
+ return (-1);
+ val = 0;
+ do {
+ val = val * 10 + c - '0';
+ if(val > 255)
+ return (0);
+ c = *src++;
+ } while (c && isdigit (c));
+ xp[i] = val;
+ if(c == '\0')
+ break;
+ if(c != '.')
+ return (0);
+ if(i >= 3)
+ return (0);
+ }
+ memcpy (dst, xp, sizeof(struct in_addr));
+ return (1);
+#if defined(HAVE_IPV6) && (!defined(__KERNEL__))
+ } else if(af == AF_INET6) {
+ return (inet_pton (af, src, dst));
+#endif /* HAVE_IPV6 */
+ } else {
+#ifndef NT
+#ifndef __KERNEL__
+ errno = EAFNOSUPPORT;
+#endif
+#endif /* NT */
+ return -1;
+ }
+}
+
+#define PATRICIA_MAX_THREADS 16
+
+/*
+ * convert prefix information to ascii string with length
+ * thread safe and (almost) re-entrant implementation
+ */
+char *
+ndpi_ndpi_prefix_toa2x (prefix_t *prefix, char *buff, int with_len)
+{
+ if(prefix == NULL)
+ return ((char*)"(Null)");
+ assert (prefix->ref_count >= 0);
+ if(buff == NULL) {
+
+ struct buffer {
+ char buffs[PATRICIA_MAX_THREADS][48+5];
+ u_int i;
+ } *buffp;
+
+# if 0
+ THREAD_SPECIFIC_DATA (struct buffer, buffp, 1);
+# else
+ { /* for scope only */
+ static struct buffer local_buff;
+ buffp = &local_buff;
+ }
+# endif
+ if(buffp == NULL) {
+ /* XXX should we report an error? */
+ return (NULL);
+ }
+
+ buff = buffp->buffs[buffp->i++%PATRICIA_MAX_THREADS];
+ }
+ if(prefix->family == AF_INET) {
+ u_char *a;
+ assert (prefix->bitlen <= sizeof(struct in_addr) * 8);
+ a = prefix_touchar (prefix);
+ if(with_len) {
+ sprintf (buff, "%d.%d.%d.%d/%d", a[0], a[1], a[2], a[3],
+ prefix->bitlen);
+ }
+ else {
+ sprintf (buff, "%d.%d.%d.%d", a[0], a[1], a[2], a[3]);
+ }
+ return (buff);
+ }
+#if defined(HAVE_IPV6) && (!defined(__KERNEL__))
+ else if(prefix->family == AF_INET6) {
+ char *r;
+ r = (char *) inet_ntop (AF_INET6, &prefix->add.sin6, buff, 48 /* a guess value */ );
+ if(r && with_len) {
+ assert (prefix->bitlen <= sizeof(struct in6_addr) * 8);
+ sprintf (buff + strlen (buff), "/%d", prefix->bitlen);
+ }
+ return (buff);
+ }
+#endif /* HAVE_IPV6 */
+ else
+ return (NULL);
+}
+
+/* ndpi_prefix_toa2
+ * convert prefix information to ascii string
+ */
+char *
+ndpi_prefix_toa2 (prefix_t *prefix, char *buff)
+{
+ return (ndpi_ndpi_prefix_toa2x (prefix, buff, 0));
+}
+
+/* ndpi_prefix_toa
+ */
+char *
+ndpi_prefix_toa (prefix_t * prefix)
+{
+ return (ndpi_prefix_toa2 (prefix, (char *) NULL));
+}
+
+prefix_t *
+ndpi_New_Prefix2 (int family, void *dest, int bitlen, prefix_t *prefix)
+{
+ int dynamic_allocated = 0;
+ int default_bitlen = sizeof(struct in_addr) * 8;
+
+#if defined(HAVE_IPV6) && (!defined(__KERNEL__))
+ if(family == AF_INET6) {
+ default_bitlen = sizeof(struct in6_addr) * 8;
+ if(prefix == NULL) {
+ prefix = (prefix_t*)ndpi_calloc(1, sizeof (prefix_t));
+ dynamic_allocated++;
+ }
+ memcpy (&prefix->add.sin6, dest, sizeof(struct in6_addr));
+ }
+ else
+#endif /* HAVE_IPV6 */
+ if(family == AF_INET) {
+ if(prefix == NULL) {
+#ifndef NT
+ prefix = (prefix_t*)ndpi_calloc(1, sizeof (prefix4_t));
+#else
+ //for some reason, compiler is getting
+ //prefix4_t size incorrect on NT
+ prefix = ndpi_calloc(1, sizeof (prefix_t));
+#endif /* NT */
+
+ dynamic_allocated++;
+ }
+ memcpy (&prefix->add.sin, dest, sizeof(struct in_addr));
+ }
+ else {
+ return (NULL);
+ }
+
+ prefix->bitlen = (bitlen >= 0)? bitlen: default_bitlen;
+ prefix->family = family;
+ prefix->ref_count = 0;
+ if(dynamic_allocated) {
+ prefix->ref_count++;
+ }
+ /* fprintf(stderr, "[C %s, %d]\n", ndpi_prefix_toa (prefix), prefix->ref_count); */
+ return (prefix);
+}
+
+prefix_t *
+ndpi_New_Prefix (int family, void *dest, int bitlen)
+{
+ return (ndpi_New_Prefix2 (family, dest, bitlen, NULL));
+}
+
+/* ndpi_ascii2prefix
+ */
+prefix_t *
+ndpi_ascii2prefix (int family, char *string)
+{
+ long bitlen;
+ long maxbitlen = 0;
+ char *cp;
+ struct in_addr sin;
+#if defined(HAVE_IPV6) && (!defined(__KERNEL__))
+ struct in6_addr sin6;
+#endif /* HAVE_IPV6 */
+ char save[MAXLINE];
+
+ if(string == NULL)
+ return (NULL);
+
+ /* easy way to handle both families */
+ if(family == 0) {
+ family = AF_INET;
+#if defined(HAVE_IPV6) && (!defined(__KERNEL__))
+ if(strchr (string, ':')) family = AF_INET6;
+#endif /* HAVE_IPV6 */
+ }
+
+ if(family == AF_INET) {
+ maxbitlen = sizeof(struct in_addr) * 8;
+ }
+#if defined(HAVE_IPV6) && (!defined(__KERNEL__))
+ else if(family == AF_INET6) {
+ maxbitlen = sizeof(struct in6_addr) * 8;
+ }
+#endif /* HAVE_IPV6 */
+
+ if((cp = strchr (string, '/')) != NULL) {
+ bitlen = atol (cp + 1);
+ /* *cp = '\0'; */
+ /* copy the string to save. Avoid destroying the string */
+ assert (cp - string < MAXLINE);
+ memcpy (save, string, cp - string);
+ save[cp - string] = '\0';
+ string = save;
+ if((bitlen < 0) || (bitlen > maxbitlen))
+ bitlen = maxbitlen;
+ } else {
+ bitlen = maxbitlen;
+ }
+
+ if(family == AF_INET) {
+ if(ndpi_my_inet_pton (AF_INET, string, &sin) <= 0)
+ return (NULL);
+ return (ndpi_New_Prefix (AF_INET, &sin, bitlen));
+ }
+
+#if defined(HAVE_IPV6) && (!defined(__KERNEL__))
+ else if(family == AF_INET6) {
+ // Get rid of this with next IPv6 upgrade
+#if defined(NT) && !defined(HAVE_INET_NTOP)
+ inet6_addr(string, &sin6);
+ return (ndpi_New_Prefix (AF_INET6, &sin6, bitlen));
+#else
+ if(inet_pton (AF_INET6, string, &sin6) <= 0)
+ return (NULL);
+#endif /* NT */
+ return (ndpi_New_Prefix (AF_INET6, &sin6, bitlen));
+ }
+#endif /* HAVE_IPV6 */
+ else
+ return (NULL);
+}
+
+prefix_t *
+ndpi_Ref_Prefix (prefix_t * prefix)
+{
+ if(prefix == NULL)
+ return (NULL);
+ if(prefix->ref_count == 0) {
+ /* make a copy in case of a static prefix */
+ return (ndpi_New_Prefix2 (prefix->family, &prefix->add, prefix->bitlen, NULL));
+ }
+ prefix->ref_count++;
+ /* fprintf(stderr, "[A %s, %d]\n", ndpi_prefix_toa (prefix), prefix->ref_count); */
+ return (prefix);
+}
+
+void
+ndpi_Deref_Prefix (prefix_t * prefix)
+{
+ if(prefix == NULL)
+ return;
+ /* for secure programming, raise an assert. no static prefix can call this */
+ assert (prefix->ref_count > 0);
+
+ prefix->ref_count--;
+ assert (prefix->ref_count >= 0);
+ if(prefix->ref_count <= 0) {
+ ndpi_DeleteEntry (prefix);
+ return;
+ }
+}
+
+/* } */
+
+/* #define PATRICIA_DEBUG 1 */
+
+static int num_active_patricia = 0;
+
+/* these routines support continuous mask only */
+
+patricia_tree_t *
+ndpi_New_Patricia (int maxbits)
+{
+ patricia_tree_t *patricia = (patricia_tree_t*)ndpi_calloc(1, sizeof *patricia);
+
+ patricia->maxbits = maxbits;
+ patricia->head = NULL;
+ patricia->num_active_node = 0;
+ assert((u_int)maxbits <= PATRICIA_MAXBITS); /* XXX */
+ num_active_patricia++;
+ return (patricia);
+}
+
+
+/*
+ * if func is supplied, it will be called as func(node->data)
+ * before deleting the node
+ */
+
+void
+ndpi_Clear_Patricia (patricia_tree_t *patricia, void_fn_t func)
+{
+ assert (patricia);
+ if(patricia->head) {
+
+ patricia_node_t *Xstack[PATRICIA_MAXBITS+1];
+ patricia_node_t **Xsp = Xstack;
+ patricia_node_t *Xrn = patricia->head;
+
+ while (Xrn) {
+ patricia_node_t *l = Xrn->l;
+ patricia_node_t *r = Xrn->r;
+
+ if(Xrn->prefix) {
+ ndpi_Deref_Prefix (Xrn->prefix);
+ if(Xrn->data && func)
+ func (Xrn->data);
+ }
+ else {
+ assert (Xrn->data == NULL);
+ }
+ ndpi_DeleteEntry (Xrn);
+ patricia->num_active_node--;
+
+ if(l) {
+ if(r) {
+ *Xsp++ = r;
+ }
+ Xrn = l;
+ } else if(r) {
+ Xrn = r;
+ } else if(Xsp != Xstack) {
+ Xrn = *(--Xsp);
+ } else {
+ Xrn = NULL;
+ }
+ }
+ }
+ assert (patricia->num_active_node == 0);
+ /* ndpi_DeleteEntry (patricia); */
+}
+
+
+void
+ndpi_Destroy_Patricia (patricia_tree_t *patricia, void_fn_t func)
+{
+ ndpi_Clear_Patricia (patricia, func);
+ ndpi_DeleteEntry (patricia);
+ num_active_patricia--;
+}
+
+
+/*
+ * if func is supplied, it will be called as func(node->prefix, node->data)
+ */
+
+void
+ndpi_patricia_process (patricia_tree_t *patricia, void_fn2_t func)
+{
+ patricia_node_t *node;
+ assert (func);
+
+ PATRICIA_WALK (patricia->head, node) {
+ func (node->prefix, node->data);
+ } PATRICIA_WALK_END;
+}
+
+size_t
+ndpi_patricia_walk_inorder(patricia_node_t *node, void_fn2_t func)
+{
+ size_t n = 0;
+ assert(func);
+
+ if(node->l) {
+ n += ndpi_patricia_walk_inorder(node->l, func);
+ }
+
+ if(node->prefix) {
+ func(node->prefix, node->data);
+ n++;
+ }
+
+ if(node->r) {
+ n += ndpi_patricia_walk_inorder(node->r, func);
+ }
+
+ return n;
+}
+
+
+patricia_node_t *
+ndpi_patricia_search_exact (patricia_tree_t *patricia, prefix_t *prefix)
+{
+ patricia_node_t *node;
+ u_char *addr;
+ u_int bitlen;
+
+ assert (patricia);
+ assert (prefix);
+ assert (prefix->bitlen <= patricia->maxbits);
+
+ if(patricia->head == NULL)
+ return (NULL);
+
+ node = patricia->head;
+ addr = prefix_touchar (prefix);
+ bitlen = prefix->bitlen;
+
+ while (node->bit < bitlen) {
+
+ if(BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
+#ifdef PATRICIA_DEBUG
+ if(node->prefix)
+ fprintf (stderr, "patricia_search_exact: take right %s/%d\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+ else
+ fprintf (stderr, "patricia_search_exact: take right at %u\n",
+ node->bit);
+#endif /* PATRICIA_DEBUG */
+ node = node->r;
+ }
+ else {
+#ifdef PATRICIA_DEBUG
+ if(node->prefix)
+ fprintf (stderr, "patricia_search_exact: take left %s/%d\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+ else
+ fprintf (stderr, "patricia_search_exact: take left at %u\n",
+ node->bit);
+#endif /* PATRICIA_DEBUG */
+ node = node->l;
+ }
+
+ if(node == NULL)
+ return (NULL);
+ }
+
+#ifdef PATRICIA_DEBUG
+ if(node->prefix)
+ fprintf (stderr, "patricia_search_exact: stop at %s/%d\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+ else
+ fprintf (stderr, "patricia_search_exact: stop at %u\n", node->bit);
+#endif /* PATRICIA_DEBUG */
+ if(node->bit > bitlen || node->prefix == NULL)
+ return (NULL);
+ assert (node->bit == bitlen);
+ assert (node->bit == node->prefix->bitlen);
+ if(ndpi_comp_with_mask (ndpi_prefix_tochar (node->prefix), ndpi_prefix_tochar (prefix),
+ bitlen)) {
+#ifdef PATRICIA_DEBUG
+ fprintf (stderr, "patricia_search_exact: found %s/%d\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+ return (node);
+ }
+ return (NULL);
+}
+
+
+/* if inclusive != 0, "best" may be the given prefix itself */
+patricia_node_t *
+ndpi_patricia_search_best2 (patricia_tree_t *patricia, prefix_t *prefix, int inclusive)
+{
+ patricia_node_t *node;
+ patricia_node_t *stack[PATRICIA_MAXBITS + 1];
+ u_char *addr;
+ u_int bitlen;
+ int cnt = 0;
+
+ assert (patricia);
+ assert (prefix);
+ assert (prefix->bitlen <= patricia->maxbits);
+
+ if(patricia->head == NULL)
+ return (NULL);
+
+ node = patricia->head;
+ addr = prefix_touchar (prefix);
+ bitlen = prefix->bitlen;
+
+ while (node->bit < bitlen) {
+
+ if(node->prefix) {
+#ifdef PATRICIA_DEBUG
+ fprintf (stderr, "patricia_search_best: push %s/%d\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+ stack[cnt++] = node;
+ }
+
+ if(BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
+#ifdef PATRICIA_DEBUG
+ if(node->prefix)
+ fprintf (stderr, "patricia_search_best: take right %s/%d\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+ else
+ fprintf (stderr, "patricia_search_best: take right at %u\n",
+ node->bit);
+#endif /* PATRICIA_DEBUG */
+ node = node->r;
+ }
+ else {
+#ifdef PATRICIA_DEBUG
+ if(node->prefix)
+ fprintf (stderr, "patricia_search_best: take left %s/%d\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+ else
+ fprintf (stderr, "patricia_search_best: take left at %u\n",
+ node->bit);
+#endif /* PATRICIA_DEBUG */
+ node = node->l;
+ }
+
+ if(node == NULL)
+ break;
+ }
+
+ if(inclusive && node && node->prefix)
+ stack[cnt++] = node;
+
+#ifdef PATRICIA_DEBUG
+ if(node == NULL)
+ fprintf (stderr, "patricia_search_best: stop at null\n");
+ else if(node->prefix)
+ fprintf (stderr, "patricia_search_best: stop at %s/%d\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+ else
+ fprintf (stderr, "patricia_search_best: stop at %u\n", node->bit);
+#endif /* PATRICIA_DEBUG */
+
+ if(cnt <= 0)
+ return (NULL);
+
+ while (--cnt >= 0) {
+ node = stack[cnt];
+#ifdef PATRICIA_DEBUG
+ fprintf (stderr, "patricia_search_best: pop %s/%d\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+ if(ndpi_comp_with_mask (ndpi_prefix_tochar (node->prefix),
+ ndpi_prefix_tochar (prefix),
+ node->prefix->bitlen) && node->prefix->bitlen <= bitlen) {
+#ifdef PATRICIA_DEBUG
+ fprintf (stderr, "patricia_search_best: found %s/%d\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+ return (node);
+ }
+ }
+ return (NULL);
+}
+
+
+patricia_node_t *
+ndpi_patricia_search_best (patricia_tree_t *patricia, prefix_t *prefix)
+{
+ return (ndpi_patricia_search_best2 (patricia, prefix, 1));
+}
+
+
+patricia_node_t *
+ndpi_patricia_lookup (patricia_tree_t *patricia, prefix_t *prefix)
+{
+ patricia_node_t *node, *new_node, *parent, *glue;
+ u_char *addr, *test_addr;
+ u_int bitlen, check_bit, differ_bit;
+ int i, j;
+
+ assert (patricia);
+ assert (prefix);
+ assert (prefix->bitlen <= patricia->maxbits);
+
+ if(patricia->head == NULL) {
+ node = (patricia_node_t*)ndpi_calloc(1, sizeof *node);
+ node->bit = prefix->bitlen;
+ node->prefix = ndpi_Ref_Prefix (prefix);
+ node->parent = NULL;
+ node->l = node->r = NULL;
+ node->data = NULL;
+ patricia->head = node;
+#ifdef PATRICIA_DEBUG
+ fprintf (stderr, "patricia_lookup: new_node #0 %s/%d (head)\n",
+ ndpi_prefix_toa (prefix), prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+ patricia->num_active_node++;
+ return (node);
+ }
+
+ addr = prefix_touchar (prefix);
+ bitlen = prefix->bitlen;
+ node = patricia->head;
+
+ while (node->bit < bitlen || node->prefix == NULL) {
+
+ if(node->bit < patricia->maxbits &&
+ BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
+ if(node->r == NULL)
+ break;
+#ifdef PATRICIA_DEBUG
+ if(node->prefix)
+ fprintf (stderr, "patricia_lookup: take right %s/%d\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+ else
+ fprintf (stderr, "patricia_lookup: take right at %u\n", node->bit);
+#endif /* PATRICIA_DEBUG */
+ node = node->r;
+ }
+ else {
+ if(node->l == NULL)
+ break;
+#ifdef PATRICIA_DEBUG
+ if(node->prefix)
+ fprintf (stderr, "patricia_lookup: take left %s/%d\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+ else
+ fprintf (stderr, "patricia_lookup: take left at %u\n", node->bit);
+#endif /* PATRICIA_DEBUG */
+ node = node->l;
+ }
+
+ assert (node);
+ }
+
+ assert (node->prefix);
+#ifdef PATRICIA_DEBUG
+ fprintf (stderr, "patricia_lookup: stop at %s/%d\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+
+ test_addr = prefix_touchar (node->prefix);
+ /* find the first bit different */
+ check_bit = (node->bit < bitlen)? node->bit: bitlen;
+ differ_bit = 0;
+ for (i = 0; (u_int)i*8 < check_bit; i++) {
+ int r;
+
+ if((r = (addr[i] ^ test_addr[i])) == 0) {
+ differ_bit = (i + 1) * 8;
+ continue;
+ }
+ /* I know the better way, but for now */
+ for (j = 0; j < 8; j++) {
+ if(BIT_TEST (r, (0x80 >> j)))
+ break;
+ }
+ /* must be found */
+ assert (j < 8);
+ differ_bit = i * 8 + j;
+ break;
+ }
+ if(differ_bit > check_bit)
+ differ_bit = check_bit;
+#ifdef PATRICIA_DEBUG
+ fprintf (stderr, "patricia_lookup: differ_bit %d\n", differ_bit);
+#endif /* PATRICIA_DEBUG */
+
+ parent = node->parent;
+ while (parent && parent->bit >= differ_bit) {
+ node = parent;
+ parent = node->parent;
+#ifdef PATRICIA_DEBUG
+ if(node->prefix)
+ fprintf (stderr, "patricia_lookup: up to %s/%d\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+ else
+ fprintf (stderr, "patricia_lookup: up to %u\n", node->bit);
+#endif /* PATRICIA_DEBUG */
+ }
+
+ if(differ_bit == bitlen && node->bit == bitlen) {
+ if(node->prefix) {
+#ifdef PATRICIA_DEBUG
+ fprintf (stderr, "patricia_lookup: found %s/%d\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+ return (node);
+ }
+ node->prefix = ndpi_Ref_Prefix (prefix);
+#ifdef PATRICIA_DEBUG
+ fprintf (stderr, "patricia_lookup: new node #1 %s/%d (glue mod)\n",
+ ndpi_prefix_toa (prefix), prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+ assert (node->data == NULL);
+ return (node);
+ }
+
+ new_node = (patricia_node_t*)ndpi_calloc(1, sizeof *new_node);
+ new_node->bit = prefix->bitlen;
+ new_node->prefix = ndpi_Ref_Prefix (prefix);
+ new_node->parent = NULL;
+ new_node->l = new_node->r = NULL;
+ new_node->data = NULL;
+ patricia->num_active_node++;
+
+ if(node->bit == differ_bit) {
+ new_node->parent = node;
+ if(node->bit < patricia->maxbits &&
+ BIT_TEST (addr[node->bit >> 3], 0x80 >> (node->bit & 0x07))) {
+ assert (node->r == NULL);
+ node->r = new_node;
+ }
+ else {
+ assert (node->l == NULL);
+ node->l = new_node;
+ }
+#ifdef PATRICIA_DEBUG
+ fprintf (stderr, "patricia_lookup: new_node #2 %s/%d (child)\n",
+ ndpi_prefix_toa (prefix), prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+ return (new_node);
+ }
+
+ if(bitlen == differ_bit) {
+ if(bitlen < patricia->maxbits &&
+ BIT_TEST (test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) {
+ new_node->r = node;
+ }
+ else {
+ new_node->l = node;
+ }
+ new_node->parent = node->parent;
+ if(node->parent == NULL) {
+ assert (patricia->head == node);
+ patricia->head = new_node;
+ }
+ else if(node->parent->r == node) {
+ node->parent->r = new_node;
+ }
+ else {
+ node->parent->l = new_node;
+ }
+ node->parent = new_node;
+#ifdef PATRICIA_DEBUG
+ fprintf (stderr, "patricia_lookup: new_node #3 %s/%d (parent)\n",
+ ndpi_prefix_toa (prefix), prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+ }
+ else {
+ glue = (patricia_node_t*)ndpi_calloc(1, sizeof *glue);
+ glue->bit = differ_bit;
+ glue->prefix = NULL;
+ glue->parent = node->parent;
+ glue->data = NULL;
+ patricia->num_active_node++;
+ if(differ_bit < patricia->maxbits &&
+ BIT_TEST (addr[differ_bit >> 3], 0x80 >> (differ_bit & 0x07))) {
+ glue->r = new_node;
+ glue->l = node;
+ }
+ else {
+ glue->r = node;
+ glue->l = new_node;
+ }
+ new_node->parent = glue;
+
+ if(node->parent == NULL) {
+ assert (patricia->head == node);
+ patricia->head = glue;
+ }
+ else if(node->parent->r == node) {
+ node->parent->r = glue;
+ }
+ else {
+ node->parent->l = glue;
+ }
+ node->parent = glue;
+#ifdef PATRICIA_DEBUG
+ fprintf (stderr, "patricia_lookup: new_node #4 %s/%d (glue+node)\n",
+ ndpi_prefix_toa (prefix), prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+ }
+ return (new_node);
+}
+
+
+void
+ndpi_patricia_remove (patricia_tree_t *patricia, patricia_node_t *node)
+{
+ patricia_node_t *parent, *child;
+
+ assert (patricia);
+ assert (node);
+
+ if(node->r && node->l) {
+#ifdef PATRICIA_DEBUG
+ fprintf (stderr, "patricia_remove: #0 %s/%d (r & l)\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+
+ /* this might be a placeholder node -- have to check and make sure
+ * there is a prefix aossciated with it ! */
+ if(node->prefix != NULL)
+ ndpi_Deref_Prefix (node->prefix);
+ node->prefix = NULL;
+ /* Also I needed to clear data pointer -- masaki */
+ node->data = NULL;
+ return;
+ }
+
+ if(node->r == NULL && node->l == NULL) {
+#ifdef PATRICIA_DEBUG
+ fprintf (stderr, "patricia_remove: #1 %s/%d (!r & !l)\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+ parent = node->parent;
+ ndpi_Deref_Prefix (node->prefix);
+ ndpi_DeleteEntry (node);
+ patricia->num_active_node--;
+
+ if(parent == NULL) {
+ assert (patricia->head == node);
+ patricia->head = NULL;
+ return;
+ }
+
+ if(parent->r == node) {
+ parent->r = NULL;
+ child = parent->l;
+ }
+ else {
+ assert (parent->l == node);
+ parent->l = NULL;
+ child = parent->r;
+ }
+
+ if(parent->prefix)
+ return;
+
+ /* we need to remove parent too */
+
+ if(parent->parent == NULL) {
+ assert (patricia->head == parent);
+ patricia->head = child;
+ }
+ else if(parent->parent->r == parent) {
+ parent->parent->r = child;
+ }
+ else {
+ assert (parent->parent->l == parent);
+ parent->parent->l = child;
+ }
+ child->parent = parent->parent;
+ ndpi_DeleteEntry (parent);
+ patricia->num_active_node--;
+ return;
+ }
+
+#ifdef PATRICIA_DEBUG
+ fprintf (stderr, "patricia_remove: #2 %s/%d (r ^ l)\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+#endif /* PATRICIA_DEBUG */
+ if(node->r) {
+ child = node->r;
+ }
+ else {
+ assert (node->l);
+ child = node->l;
+ }
+ parent = node->parent;
+ child->parent = parent;
+
+ ndpi_Deref_Prefix (node->prefix);
+ ndpi_DeleteEntry (node);
+ patricia->num_active_node--;
+
+ if(parent == NULL) {
+ assert (patricia->head == node);
+ patricia->head = child;
+ return;
+ }
+
+ if(parent->r == node) {
+ parent->r = child;
+ }
+ else {
+ assert (parent->l == node);
+ parent->l = child;
+ }
+}
+
+/* { from demo.c */
+#if 0
+
+patricia_node_t *
+ndpi_make_and_lookup (patricia_tree_t *tree, char *string)
+{
+ prefix_t *prefix;
+ patricia_node_t *node;
+
+ prefix = ndpi_ascii2prefix (AF_INET, string);
+ printf ("make_and_lookup: %s/%d\n", ndpi_prefix_toa (prefix), prefix->bitlen);
+ node = ndpi_patricia_lookup (tree, prefix);
+ ndpi_Deref_Prefix (prefix);
+ return (node);
+}
+
+patricia_node_t *
+ndpi_try_search_exact (patricia_tree_t *tree, char *string)
+{
+ prefix_t *prefix;
+ patricia_node_t *node;
+
+ prefix = ndpi_ascii2prefix (AF_INET, string);
+ printf ("try_search_exact: %s/%d\n", ndpi_prefix_toa (prefix), prefix->bitlen);
+ if((node = patricia_search_exact (tree, prefix)) == NULL) {
+ printf ("try_search_exact: not found\n");
+ }
+ else {
+ printf ("try_search_exact: %s/%d found\n",
+ ndpi_prefix_toa (node->prefix), node->prefix->bitlen);
+ }
+ ndpi_Deref_Prefix (prefix);
+ return (node);
+}
+
+void
+ndpi_lookup_then_remove (patricia_tree_t *tree, char *string)
+{
+ patricia_node_t *node;
+
+ if((node = try_search_exact (tree, string)))
+ patricia_remove (tree, node);
+}
+#endif
+
+/* } */
diff --git a/src/lib/third_party/src/sort.c b/src/lib/third_party/src/sort.c
new file mode 100644
index 000000000..d6545e85a
--- /dev/null
+++ b/src/lib/third_party/src/sort.c
@@ -0,0 +1,130 @@
+/*
+ * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
+ *
+ * Jan 23 2005 Matt Mackall <mpm@selenic.com>
+ */
+
+#ifdef __KERNEL__
+#include <linux/types.h>
+#else
+#ifdef WIN32
+#include <stdint.h>
+typedef uint32_t u_int32_t;
+#endif
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <sys/types.h>
+#endif
+
+/* This is a function ported from the Linux kernel lib/sort.c */
+
+static void u_int32_t_swap(void *a, void *b, int size)
+{
+ u_int32_t t = *(u_int32_t *)a;
+ *(u_int32_t *)a = *(u_int32_t *)b;
+ *(u_int32_t *)b = t;
+}
+
+static void generic_swap(void *_a, void *_b, int size)
+{
+ char t;
+ char *a = (char*)_a;
+ char *b = (char*)_b;
+
+ do {
+ t = *a;
+ *a++ = *b;
+ *b++ = t;
+ } while (--size > 0);
+}
+
+/**
+ * sort - sort an array of elements
+ * @base: pointer to data to sort
+ * @num: number of elements
+ * @size: size of each element
+ * @cmp_func: pointer to comparison function
+ * @swap_func: pointer to swap function or NULL
+ *
+ * This function does a heapsort on the given array. You may provide a
+ * swap_func function optimized to your element type.
+ *
+ * Sorting time is O(n log n) both on average and worst-case. While
+ * qsort is about 20% faster on average, it suffers from exploitable
+ * O(n*n) worst-case behavior and extra memory requirements that make
+ * it less suitable for kernel use.
+ */
+
+void sort(void *_base, size_t num, size_t size,
+ int (*cmp_func)(const void *, const void *),
+ void (*swap_func)(void *, void *, int size))
+{
+ /* pre-scale counters for performance */
+ int i = (num/2 - 1) * size, n = num * size, c, r;
+ char *base = (char*)_base;
+
+ if (!swap_func)
+ swap_func = (size == 4 ? u_int32_t_swap : generic_swap);
+
+ /* heapify */
+ for ( ; i >= 0; i -= size) {
+ for (r = i; r * 2 + size < n; r = c) {
+ c = r * 2 + size;
+ if (c < n - size &&
+ cmp_func(base + c, base + c + size) < 0)
+ c += size;
+ if (cmp_func(base + r, base + c) >= 0)
+ break;
+ swap_func(base + r, base + c, size);
+ }
+ }
+
+ /* sort */
+ for (i = n - size; i > 0; i -= size) {
+ swap_func(base, base + i, size);
+ for (r = 0; r * 2 + size < i; r = c) {
+ c = r * 2 + size;
+ if (c < i - size &&
+ cmp_func(base + c, base + c + size) < 0)
+ c += size;
+ if (cmp_func(base + r, base + c) >= 0)
+ break;
+ swap_func(base + r, base + c, size);
+ }
+ }
+}
+
+
+#if 0
+/* a simple boot-time regression test */
+
+int cmpint(const void *a, const void *b)
+{
+ return *(int *)a - *(int *)b;
+}
+
+int main(int argc, char *argv[]) {
+ int *a, i, r = 1;
+
+ a = ndpi_malloc(1000 * sizeof(int));
+
+ printf("testing sort()\n");
+
+ for (i = 0; i < 1000; i++) {
+ r = (r * 725861) % 6599;
+ a[i] = r;
+ }
+
+ sort(a, 1000, sizeof(int), cmpint, NULL);
+
+ for (i = 0; i < 999; i++)
+ if (a[i] > a[i+1]) {
+ printf("sort() failed!\n");
+ break;
+ }
+
+ return 0;
+}
+
+#endif
Powered by cgit, Themed by Ted Yin.