1 /****************************************************************************
2  *
3  * Copyright (C) 2014-2021 Cisco and/or its affiliates. All rights reserved.
4  * Copyright (C) 2006-2013 Sourcefire, Inc.
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License Version 2 as
8  * published by the Free Software Foundation.  You may not use, modify or
9  * distribute this program under any other version of the GNU General
10  * Public License.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
20  *
21  ****************************************************************************/
22 
23 /*
24  * @file    sfdir.h
25  * @author  Adam Keeton <akeeton@sourcefire.com>
26  * @date    Thu July 20 10:16:26 EDT 2006
27  *
28  * The implementation uses an multibit-trie that is similar to Gupta et-al's
29  * DIR-n-m.
30 */
31 
32 #ifndef SFRT_DIR_H_
33 #define SFRT_DIR_H_
34 
35 /*******************************************************************/
36 /* DIR-n-m data structures
37  * Each table in the DIR-n-m method is represented by a
38  * dir_sub_table_t.  They are managed by a dir_table_t. */
39 typedef struct
40 {
41     word *entries;
42     uint8_t *lengths;
43     int num_entries; /* Number of entries in this table */
44     int width;       /* width of this table. */
45                      /* While one determines the other, this way fewer
46                       * calculations are needed at runtime, since both
47                       * are used. */
48     int cur_num;     /* Present number of used nodes */
49 
50     /** number of entries filled including chidren sub_tables. This is used
51      * for freeing sub_tables when all entried are freed by delete operation.
52      */
53     int filledEntries;
54 } dir_sub_table_t;
55 
56 /* Master data structure for the DIR-n-m derivative */
57 typedef struct
58 {
59     int *dimensions;    /* DIR-n-m will consist of any number of arbitrarily
60                          * long tables. This variable keeps track of the
61                          * dimensions */
62     int dim_size;       /* And this variable keeps track of 'dimensions''s
63                          * dimensions! */
64     uint32_t mem_cap;  /* User-defined maximum memory that can be allocated
65                          * for the DIR-n-m derivative */
66 
67     int cur_num;        /* Present number of used nodes */
68 
69     uint32_t allocated;
70 
71     dir_sub_table_t *sub_table;
72 } dir_table_t;
73 
74 /*******************************************************************/
75 /* DIR-n-m functions, these are not intended to be called directly */
76 dir_table_t *  sfrt_dir_new(uint32_t mem_cap, int count,...);
77 void           sfrt_dir_free(void *);
78 tuple_t        sfrt_dir_lookup(uint32_t* adr, int numAdrDwords, void *table);
79 int            sfrt_dir_insert(uint32_t* adr, int numAdrDwords, int len, word data_index,
80                                int behavior, void *table);
81 uint32_t      sfrt_dir_usage(void *table);
82 void          sfrt_dir_print(void *table);
83 word sfrt_dir_remove(uint32_t* adr, int numAdrDwords, int len, int behavior, void *table);
84 
85 #endif /* SFRT_DIR_H_ */
86 
87