Initial import from SVN

5 files changed, 578 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));
+