nemea-common  1.6.3
Data Structures
prefix_tree.h File Reference
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <getopt.h>
#include <time.h>
#include <inttypes.h>
#include <sys/types.h>
#include <sys/stat.h>

Go to the source code of this file.

Data Structures

struct  prefix_tree_inner_node_t
 Structure - Prefix tree - inner node structure Structure used to keep information about inner node of prefix tree. More...
 
struct  node_domain_extension_t
 Structure - domain extension Structure keeps pointers in linked list to other domain nodes. More...
 
struct  prefix_tree_domain_t
 Structure - Prefix tree - domain name structure Structure used to keep information about domain names. It is domain name structure, which contain information about domain name. More...
 
struct  tree_domain_extension_t
 Structure - Domain names extension Structure used to keep lists of most searched domains, subdomains and least searched subdomains information about prexix tree. More...
 
struct  prefix_tree_t
 Structure - Prefix tree main structure Structure used to keep information about prefix tree. It is main structure, witch contains all information about prexix tree. More...
 

Default values

Defines macros used by prefix tree

#define COUNT_OF_LETTERS_IN_DOMAIN   256 /*< Max count of letter in domain. */
 
#define MAX_SIZE_OF_DOMAIN   256 /*< Max length of domain */
 
#define MAX_SIZE_OF_DEGREE   5 /*< Max size of stored information */
 
#define ADD_TO_LIST_FROM_COUNT_OF_SEARCH   20 /*< Default number of histogram size. */
 
#define ADD_TO_LIST_FROM_COUNT_OF_DIFFERENT_SUBDOMAINS   10 /*< Default number of histogram size. */
 
#define MAX_COUNT_TO_BE_IN_JUST_ONE_SEARCHER   10 /*< Default number of histogram size. */
 
#define PREFIX   1
 
#define SUFFIX   0
 
enum  domain_extension { DOMAIN_EXTENSION_YES , DOMAIN_EXTENSION_NO }
 
enum  relaxation_after_delete { RELAXATION_AFTER_DELETE_YES , RELAXATION_AFTER_DELETE_NO }
 
typedef struct prefix_tree_domain_t prefix_tree_domain_t
 
typedef struct prefix_tree_inner_node_t prefix_tree_inner_node_t
 
typedef struct node_domain_extension_t node_domain_extension_t
 Structure - domain extension Structure keeps pointers in linked list to other domain nodes. More...
 
typedef struct tree_domain_extension_t tree_domain_extension_t
 Structure - Domain names extension Structure used to keep lists of most searched domains, subdomains and least searched subdomains information about prexix tree. More...
 
typedef struct prefix_tree_t prefix_tree_t
 Structure - Prefix tree main structure Structure used to keep information about prefix tree. It is main structure, witch contains all information about prexix tree. More...
 
int prefix_tree_map_character_to_number (unsigned char letter)
 Map character to index Function maps character to index in descendants. More...
 
prefix_tree_tprefix_tree_initialize (unsigned char prefix_suffix, unsigned int size_of_value, int domain_separator, int domain_extension, relaxation_after_delete relaxation)
 Init function for prefix tree Function that incialize prefix tree. More...
 
void prefix_tree_decrease_counters_deleted_inner_node (prefix_tree_inner_node_t *node, int deleted_strings, int deleted_domains)
 Decrease counters in prefix tree, if deleting a node. Function that goes from the node to the root and decreases counters. More...
 
prefix_tree_inner_node_tjoin_nodes (prefix_tree_inner_node_t *node)
 Function joins two nodes into one. If parent has just one child, this function join them into one node. More...
 
void prefix_tree_delete_inner_node (prefix_tree_t *tree, prefix_tree_inner_node_t *node)
 Function which removes inner node and his descendats. Function will erase specified node and all his decendats. Counters will be changed. More...
 
int prefix_tree_destroy_recursive (prefix_tree_t *tree, prefix_tree_inner_node_t *node)
 Destroy all items in prefix tree Function destroy recursively destroies all nodes. More...
 
void prefix_tree_destroy (prefix_tree_t *tree)
 Destroy function for prefix tree Function destroy prefix tree and all item inside. More...
 
void prefix_tree_recursive_plus_domain (prefix_tree_domain_t *domain_parent, prefix_tree_t *tree)
 Recursive change info about parent doimains Function actualize information in parent domains. More...
 
prefix_tree_domain_tprefix_tree_new_domain (prefix_tree_inner_node_t *node, prefix_tree_domain_t *domain_parent, prefix_tree_t *tree)
 Create domain node structure Function Create domian and connects it to the tree. More...
 
prefix_tree_inner_node_tprefix_tree_new_node (prefix_tree_inner_node_t *parent, int map_number)
 Create inner node structure Function Create inned node and connects it to the tree. More...
 
prefix_tree_inner_node_tprefix_tree_add_children_array (prefix_tree_inner_node_t *parent)
 Alloc memory for descendats in inner node Function allocs memory for descendats in inner node. More...
 
prefix_tree_inner_node_tprefix_tree_new_node_parent_is_domain (prefix_tree_domain_t *domain)
 Create descendant of domain Function creates descendant of domain, (domain has other subdomains). More...
 
int prefix_tree_count_to_domain_separator (const char *string, int length, int domain_separator, char prefix)
 Count length of string to dot Function counts length of string to dot. More...
 
prefix_tree_domain_tprefix_tree_add_new_item (prefix_tree_inner_node_t *node, prefix_tree_domain_t *domain, const char *string, int length, prefix_tree_t *tree)
 Add new item to prefix tree Function add new item to prefix tree (place where to add new domain has to be given). More...
 
prefix_tree_inner_node_tprefix_tree_split_node_into_two (prefix_tree_inner_node_t *node, int index)
 Split node into two nodes Function splits node into two nodes, on the given position. This function is needed when inserting new node, which has coomon part of string with some node. More...
 
char * prefix_tree_read_string (prefix_tree_t *tree, prefix_tree_domain_t *domain, char *string)
 Read domain from tree Function return string with the domain name. More...
 
char * prefix_tree_read_inner_node (prefix_tree_t *tree, prefix_tree_inner_node_t *node, char *string)
 Read string from inner node Function return string stored in given inner node. More...
 
prefix_tree_domain_tprefix_tree_add_domain_recursive_prefix (prefix_tree_inner_node_t *node, prefix_tree_domain_t *domain_parent, const char *string, int length, prefix_tree_t *tree)
 Add domain recursive (prefix tree) Function adds domain to the prefix tree. This function is called from prefix_tree_add_domain and needs more parametters. More...
 
prefix_tree_domain_tprefix_tree_add_domain_recursive_suffix (prefix_tree_inner_node_t *node, prefix_tree_domain_t *domain_parent, const char *string, int length, prefix_tree_t *tree)
 Add domain recursive (suffix tree) Function adds domain to the prefix tree. This function is called from prefix_tree_add_domain and needs more parametters. More...
 
prefix_tree_domain_tprefix_tree_insert (prefix_tree_t *tree, const char *string, int length)
 Add domain to prefix tree Function adds domain to the prefix tree. More...
 
prefix_tree_domain_tprefix_tree_search (prefix_tree_t *tree, const char *string, int length)
 Seacrh domain in prefix tree Function adds domain to the prefix tree. More...
 
prefix_tree_domain_tprefix_tree_add_string_exception (prefix_tree_t *tree, const char *string, int length)
 Add domain to prefix tree and set it to the exception state Function adds domain to the prefix tree and set it to the exception state. More...
 
int prefix_tree_is_string_in_exception (prefix_tree_t *tree, const char *string, int length)
 Test domain if is in exception state Function tests domain if is in exception state. More...
 
double prefix_tree_most_used_domain_percent_of_subdomains (prefix_tree_t *tree, int depth)
 Statistic function percent od subdomains in certain depth Function returns percent of subdomains in most searched domain in given depth. More...
 
prefix_tree_inner_node_tprefix_tree_most_substring (prefix_tree_inner_node_t *node)
 Returns inner node with most of different strings Function returns pointer to inner node, which has the most of different strings. More...
 

Macro Definition Documentation

◆ ADD_TO_LIST_FROM_COUNT_OF_DIFFERENT_SUBDOMAINS

#define ADD_TO_LIST_FROM_COUNT_OF_DIFFERENT_SUBDOMAINS   10 /*< Default number of histogram size. */

Definition at line 69 of file prefix_tree.h.

◆ ADD_TO_LIST_FROM_COUNT_OF_SEARCH

#define ADD_TO_LIST_FROM_COUNT_OF_SEARCH   20 /*< Default number of histogram size. */

Definition at line 68 of file prefix_tree.h.

◆ COUNT_OF_LETTERS_IN_DOMAIN

#define COUNT_OF_LETTERS_IN_DOMAIN   256 /*< Max count of letter in domain. */

Definition at line 65 of file prefix_tree.h.

◆ MAX_COUNT_TO_BE_IN_JUST_ONE_SEARCHER

#define MAX_COUNT_TO_BE_IN_JUST_ONE_SEARCHER   10 /*< Default number of histogram size. */

Definition at line 70 of file prefix_tree.h.

◆ MAX_SIZE_OF_DEGREE

#define MAX_SIZE_OF_DEGREE   5 /*< Max size of stored information */

Definition at line 67 of file prefix_tree.h.

◆ MAX_SIZE_OF_DOMAIN

#define MAX_SIZE_OF_DOMAIN   256 /*< Max length of domain */

Definition at line 66 of file prefix_tree.h.

◆ PREFIX

#define PREFIX   1

Definition at line 71 of file prefix_tree.h.

◆ SUFFIX

#define SUFFIX   0

Definition at line 72 of file prefix_tree.h.

Typedef Documentation

◆ node_domain_extension_t

Structure - domain extension Structure keeps pointers in linked list to other domain nodes.

◆ prefix_tree_domain_t

Definition at line 1 of file prefix_tree.h.

◆ prefix_tree_inner_node_t

Definition at line 1 of file prefix_tree.h.

◆ prefix_tree_t

typedef struct prefix_tree_t prefix_tree_t

Structure - Prefix tree main structure Structure used to keep information about prefix tree. It is main structure, witch contains all information about prexix tree.

◆ tree_domain_extension_t

Structure - Domain names extension Structure used to keep lists of most searched domains, subdomains and least searched subdomains information about prexix tree.

Enumeration Type Documentation

◆ domain_extension

Inicialization parametters for allowing domain extension information.

Enumerator
DOMAIN_EXTENSION_YES 
DOMAIN_EXTENSION_NO 

Definition at line 78 of file prefix_tree.h.

◆ relaxation_after_delete

Inicialization parametters for relaxation tree after deleting node.

Enumerator
RELAXATION_AFTER_DELETE_YES 
RELAXATION_AFTER_DELETE_NO 

Definition at line 86 of file prefix_tree.h.

Function Documentation

◆ join_nodes()

Function joins two nodes into one. If parent has just one child, this function join them into one node.

Parameters
[in]nodeparent node, which would be joined with son.
Returns
joined inner node

◆ prefix_tree_add_children_array()

prefix_tree_inner_node_t* prefix_tree_add_children_array ( prefix_tree_inner_node_t parent)

Alloc memory for descendats in inner node Function allocs memory for descendats in inner node.

Parameters
[in]parentparent node
Returns
pointer to inner node structure, which was given in parametter

◆ prefix_tree_add_domain_recursive_prefix()

prefix_tree_domain_t* prefix_tree_add_domain_recursive_prefix ( prefix_tree_inner_node_t node,
prefix_tree_domain_t domain_parent,
const char *  string,
int  length,
prefix_tree_t tree 
)

Add domain recursive (prefix tree) Function adds domain to the prefix tree. This function is called from prefix_tree_add_domain and needs more parametters.

Parameters
[in]nodeinner node where to insert of find domain
[in]domain_parentneares domain parent
[in]stringstring to add to prefix tree
[in]lengthlength of string
[in]treepointer to the prefix tree
Returns
added or found domain

◆ prefix_tree_add_domain_recursive_suffix()

prefix_tree_domain_t* prefix_tree_add_domain_recursive_suffix ( prefix_tree_inner_node_t node,
prefix_tree_domain_t domain_parent,
const char *  string,
int  length,
prefix_tree_t tree 
)

Add domain recursive (suffix tree) Function adds domain to the prefix tree. This function is called from prefix_tree_add_domain and needs more parametters.

Parameters
[in]nodeinner node where to insert of find domain
[in]domain_parentneares domain parent
[in]stringstring to add to prefix tree
[in]lengthlength of string
[in]treepointer to the prefix tree
Returns
added or found domain

◆ prefix_tree_add_new_item()

prefix_tree_domain_t* prefix_tree_add_new_item ( prefix_tree_inner_node_t node,
prefix_tree_domain_t domain,
const char *  string,
int  length,
prefix_tree_t tree 
)

Add new item to prefix tree Function add new item to prefix tree (place where to add new domain has to be given).

Parameters
[in]nodenode where to add new item
[in]domainnearest parent domain
[in]stringstring with new item
[in]lengthlength of string
[in]treepointer to the prefix tree
Returns
pointer to new domain structure

◆ prefix_tree_add_string_exception()

prefix_tree_domain_t* prefix_tree_add_string_exception ( prefix_tree_t tree,
const char *  string,
int  length 
)

Add domain to prefix tree and set it to the exception state Function adds domain to the prefix tree and set it to the exception state.

Parameters
[in]treepointer to the prefix tree
[in]stringstring witch should be added
[in]lengthlength of string
Returns
added or found domain

◆ prefix_tree_count_to_domain_separator()

int prefix_tree_count_to_domain_separator ( const char *  string,
int  length,
int  domain_separator,
char  prefix 
)

Count length of string to dot Function counts length of string to dot.

Parameters
[in]string
[in]lengthof string
[in]separatorof domain
[in]prefixor suffix
Returns
length to dot

◆ prefix_tree_decrease_counters_deleted_inner_node()

void prefix_tree_decrease_counters_deleted_inner_node ( prefix_tree_inner_node_t node,
int  deleted_strings,
int  deleted_domains 
)

Decrease counters in prefix tree, if deleting a node. Function that goes from the node to the root and decreases counters.

Parameters
[in]nodefrom which to start decreasing.
[in]deleted_stringscount of deleted strings.
[in]deleted_domainscount of deleted domain nodes.

◆ prefix_tree_delete_inner_node()

void prefix_tree_delete_inner_node ( prefix_tree_t tree,
prefix_tree_inner_node_t node 
)

Function which removes inner node and his descendats. Function will erase specified node and all his decendats. Counters will be changed.

Parameters
[in]treepointer to tree in which is the deleted node.
[in]nodeparent node, which would be joined with son.

◆ prefix_tree_destroy()

void prefix_tree_destroy ( prefix_tree_t tree)

Destroy function for prefix tree Function destroy prefix tree and all item inside.

Parameters
[in]treepointer to prefix tree

◆ prefix_tree_destroy_recursive()

int prefix_tree_destroy_recursive ( prefix_tree_t tree,
prefix_tree_inner_node_t node 
)

Destroy all items in prefix tree Function destroy recursively destroies all nodes.

Parameters
[in]treepointer to prefix tree
[in]nodepointer to inner node, which will be destroied
Returns
count of deleted domains

◆ prefix_tree_initialize()

prefix_tree_t* prefix_tree_initialize ( unsigned char  prefix_suffix,
unsigned int  size_of_value,
int  domain_separator,
int  domain_extension,
relaxation_after_delete  relaxation 
)

Init function for prefix tree Function that incialize prefix tree.

Parameters
[in]PREFIXfor prefix tree or SUFFIX for suffix tree
[in]sizeof space for value
[in]characterof domain separator, when this value is in string, special domain node for value is created
[in]domain_extensioncan has value of DOMAIN_EXTENSION_YES or DOMAIN_EXTENSION_NO. If is it set on YES it will store addintional structure for searching domains via their usage.
Returns
pointer to prefix tree structure

◆ prefix_tree_insert()

prefix_tree_domain_t* prefix_tree_insert ( prefix_tree_t tree,
const char *  string,
int  length 
)

Add domain to prefix tree Function adds domain to the prefix tree.

Parameters
[in]treepointer to the prefix tree
[in]stringstring witch should be added
[in]lengthlength of string
Returns
added or found domain

◆ prefix_tree_is_string_in_exception()

int prefix_tree_is_string_in_exception ( prefix_tree_t tree,
const char *  string,
int  length 
)

Test domain if is in exception state Function tests domain if is in exception state.

Parameters
[in]treepointer to the prefix tree
[in]stringstring witch should be added
[in]lengthlength of string
Returns
1 is in exception, 0 not in exception

◆ prefix_tree_map_character_to_number()

int prefix_tree_map_character_to_number ( unsigned char  letter)

Map character to index Function maps character to index in descendants.

Parameters
[in]lettercharacter
Returns
letter mapped index.

◆ prefix_tree_most_substring()

prefix_tree_inner_node_t* prefix_tree_most_substring ( prefix_tree_inner_node_t node)

Returns inner node with most of different strings Function returns pointer to inner node, which has the most of different strings.

Parameters
[in]nodepointer to the node, from which the searching starts.
Returns
NULL if the node does not exist(does not have inner node child) or pointer to inner node.

◆ prefix_tree_most_used_domain_percent_of_subdomains()

double prefix_tree_most_used_domain_percent_of_subdomains ( prefix_tree_t tree,
int  depth 
)

Statistic function percent od subdomains in certain depth Function returns percent of subdomains in most searched domain in given depth.

Parameters
[in]treepointer to the prefix tree
[in]depth
Returns
added or found domain

◆ prefix_tree_new_domain()

prefix_tree_domain_t* prefix_tree_new_domain ( prefix_tree_inner_node_t node,
prefix_tree_domain_t domain_parent,
prefix_tree_t tree 
)

Create domain node structure Function Create domian and connects it to the tree.

Parameters
[in]nodeparent node (contain last letter of domain)
[in]domain_parentpointer to parent domain
[in]treepointer to prefix tree
Returns
pointer to domain structure

◆ prefix_tree_new_node()

prefix_tree_inner_node_t* prefix_tree_new_node ( prefix_tree_inner_node_t parent,
int  map_number 
)

Create inner node structure Function Create inned node and connects it to the tree.

Parameters
[in]parentparent node
[in]map_numbernumber of first character of new node (index on this node in parent)
Returns
pointer to inner node structure

◆ prefix_tree_new_node_parent_is_domain()

prefix_tree_inner_node_t* prefix_tree_new_node_parent_is_domain ( prefix_tree_domain_t domain)

Create descendant of domain Function creates descendant of domain, (domain has other subdomains).

Parameters
[in]domaindomain where to add descendant
Returns
pointer to descendant inner node

◆ prefix_tree_read_inner_node()

char* prefix_tree_read_inner_node ( prefix_tree_t tree,
prefix_tree_inner_node_t node,
char *  string 
)

Read string from inner node Function return string stored in given inner node.

Parameters
[in]pointerto the tree
[in]nodepointer to node
[in]stringpointer on memory where to store string
Returns
pointer to string

◆ prefix_tree_read_string()

char* prefix_tree_read_string ( prefix_tree_t tree,
prefix_tree_domain_t domain,
char *  string 
)

Read domain from tree Function return string with the domain name.

Parameters
[in]pointerto the tree
[in]domainpointer to domain, which should be returned in string
[in]stringpointer on memory where to store string
Returns
pointer to string

◆ prefix_tree_recursive_plus_domain()

void prefix_tree_recursive_plus_domain ( prefix_tree_domain_t domain_parent,
prefix_tree_t tree 
)

Recursive change info about parent doimains Function actualize information in parent domains.

Parameters
[in]domain_parentdomain where to actualize inforamtion
[in]treepointer to prefix tree

◆ prefix_tree_search()

prefix_tree_domain_t* prefix_tree_search ( prefix_tree_t tree,
const char *  string,
int  length 
)

Seacrh domain in prefix tree Function adds domain to the prefix tree.

Parameters
[in]treepointer to the prefix tree
[in]stringstring witch should be added
[in]lengthlength of string
Returns
added or found domain

◆ prefix_tree_split_node_into_two()

prefix_tree_inner_node_t* prefix_tree_split_node_into_two ( prefix_tree_inner_node_t node,
int  index 
)

Split node into two nodes Function splits node into two nodes, on the given position. This function is needed when inserting new node, which has coomon part of string with some node.

Parameters
[in]nodenode which will be splitted
[in]indexposition in string (where to split the node)
Returns
pointer to first node. Seccond splitted node is descendant of first node.