TABLE OF CONTENTS

trish2/patricia [ Modules ]

[ Top ] [ Modules ]

NAME

patricia

SYNOPSIS

 #include <patricia.h>

DESCRIPTION

EXAMPLE

SEE ALSO

bunch, patricia_node, patricia_t, patricia_new, patricia_free, patricia_save, patricia_load, patricia_add_context_t, PATRICIA_ADD_OPTION_START, PATRICIA_ADD_OPTION_END, PATRICIA_ADD_EVENT_NEW_NODE, PATRICIA_ADD_EVENT_TAIL, PATRICIA_ADD_EVENT_NEXT_NODE, PATRICIA_ADD_EVENT_SPLIT_TAIL, patricia_add_context_init, patricia_add, patricia_compact_tails

trish2/patricia_t [ Structures ]

[ Top ] [ Structures ]

NAME

patricia_t

SYNOPSIS

 #include <patricia.h>
 typedef struct {
   bunch_t *nodes;
   pnode_t *root;
   bunch_t *tails;
   bunch_t *data;
 } patricia_t;

DESCRIPTION

A PATRICIA tree consists of a set of PATRICIA tree nodes. For convenience reasons nodes, tail strings and node data are all claimed from their respective bunches.

ATTRIBUTES

SEE ALSO

patricia, patricia_new, patricia_node, pnode_t, bunch, bunch_new

trish2/patricia_new [ Functions ]

[ Top ] [ Functions ]

NAME

patricia_new

SYNOPSIS

 #include <patricia.h>
 patricia_t *patricia_new(unsigned int node_block, unsigned int string_block, bunch_t *data);

FUNCTION

patricia_new allocates a new patricia_t structure and initializes the nodes and tail strings bunch with block sizes of node_block and string_block respectively. data is the bunch of nodes data created by your own with bunch_new. If data is NULL the nodes will not contain any data at all.

INPUTS

RETURN VALUE

A freshly allocated PATRICIA tree.

SEE ALSO

patricia, patricia_t, patricia_free, bunch_new

trish2/patricia_free [ Functions ]

[ Top ] [ Functions ]

NAME

patricia_free

SYNOPSIS

 #include <patricia.h>
 void patricia_free(patricia_t *pat);

FUNCTION

patricia_free destroys the PATRICIA tree pat. pat should have been created by patricia_new. patricia_free will call bunch_free on both the nodes and tail strings bunch. However it will not free the data bunch.

INPUTS

SEE ALSO

patricia, patricia_t, patricia_new, bunch_free

trish2/patricia_save [ Functions ]

[ Top ] [ Functions ]

NAME

patricia_save

SYNOPSIS

 #include <patricia.h>
 void patricia_save(patricia_t *pat, int options, FILE *f);

FUNCTION

patricia_save writes pat into the file f by using fwrite and bunch_save. options is directly passed to bunch_save, so use BUNCH_PRUNED to prune bunch blocks. The data bunch will also be written.

INPUTS

SEE ALSO

patricia, patricia_t, patricia_new, patricia_load, bunch_save

trish2/patricia_load [ Functions ]

[ Top ] [ Functions ]

NAME

patricia_load

SYNOPSIS

 #include <patricia.h>
 patricia_t *patricia_load(FILE *f);

FUNCTION

patricia_load reads a patricia_t structure from the file handler f. The PATRICIA tree must have been written into the file with patricia_save. Also the cursor in f must be at the same offset than when the tree was written. All node pointers will be automatically corrected with BUNCH_CORRECT_PTR. If the data contains claimed pointers, then you should correct them by yourself.

INPUTS

RETURN VALUE

The PATRICIA tree.

SEE ALSO

patricia, patricia_t, patricia_save, bunch_load

trish2/patricia_add_context_t [ Structures ]

[ Top ] [ Structures ]

NAME

patricia_add_context_t

SYNOPSIS

 #include <patricia.h>
 typedef struct {
   patricia_t *pat;
   int options;
   const wchar_t *word;
   int word_pos;
   pnode_t *current;
   int tail_pos;
   int event;
   pnode_t *parent;
   void *arg;
 } patricia_add_context_t;

DESCRIPTION

patricia_add_context_t is a structure containing the necessary informations to add an entry to a PATRICIA tree. It also contains the current position in the tree during a call to patricia_add.

ATTRIBUTES

SEE ALSO

patricia, particia_t, pnode_t, PATRICIA_ADD_OPTION_START, PATRICIA_ADD_OPTION_END, PATRICIA_ADD_EVENT_NEW_NODE, PATRICIA_ADD_EVENT_TAIL, PATRICIA_ADD_EVENT_NEXT_NODE, PATRICIA_ADD_EVENT_SPLIT_TAIL, patricia_add_context_init, patricia_add

trish2/PATRICIA_ADD_OPTION_START, trish2/PATRICIA_ADD_OPTION_END [ Definitions ]

[ Top ] [ Definitions ]

NAME

PATRICIA_ADD_OPTION_START, PATRICIA_ADD_OPTION_END

SYNOPSIS

 #include <patricia.h>
 #define PATRICIA_ADD_OPTION_START
 #define PATRICIA_ADD_OPTION_END

DESCRIPTION

If the options member of a patricia_add_context_t has PATRICIA_ADD_OPTION_START option bit on, then patricia_add will insert a node with leading character set to PNODE_START before adding the entry. If the options member of a patricia_add_context_t has PATRICIA_ADD_OPTION_END option bit on, then patricia_add will insert a node with leading character set to PNODE_END after adding the entry.

SEE ALSO

patricia, patricia_add_context_t, patricia_add_context_init

trish2/PATRICIA_ADD_EVENT_NEW_NODE, trish2/PATRICIA_ADD_EVENT_TAIL,
trish2/PATRICIA_ADD_EVENT_NEXT_NODE, trish2/PATRICIA_ADD_EVENT_SPLIT_TAIL [ Definitions ]

[ Top ] [ Definitions ]

NAME

PATRICIA_ADD_EVENT_*

SYNOPSIS

 #include <patricia.h>
 #define PATRICIA_ADD_EVENT_NEW_NODE
 #define PATRICIA_ADD_EVENT_TAIL
 #define PATRICIA_ADD_EVENT_NEXT_NODE
 #define PATRICIA_ADD_EVENT_SPLIT_TAIL

DESCRIPTION

During a call to patricia_add, the event member of a patricia_add_context_t is set to the last operation performed on the PATRICIA tree. PATRICIA_ADD_EVENT_NEW_NODE means the current member points to a node that patricia_add had to create to insert the entry. PATRICIA_ADD_EVENT_TAIL means that patricia_add successfully proceeded to the comparison of the entry substring and the tail string of the current node. PATRICIA_ADD_EVENT_NEXT_NODE means patricia_add looked for and found a child node because it reached the end of the tails string of the previous one. PATRICIA_ADD_EVENT_SPLIT_TAIL means patricia_add found a mismatch between the entry and the tail string of the current node thus forcing its splitting into two nodes.

SEE ALSO

patricia, patricia_add_context_t, patricia_add_context_init, patricia_add

trish2/patricia_add_context_init [ Functions ]

[ Top ] [ Functions ]

NAME

patricia_add_context_init

SYNOPSIS

 #include <patricia.h>
 void patricia_add_context_init(patricia_add_context_t *ctx, patricia_t *pat, const wchar_t *word, int options, void *arg);

FUNCTION

patricia_add_context_init prepares a ctx to add entry word into pat.

INPUTS

SEE ALSO

patricia, patricia_add_context_t, PATRICIA_ADD_OPTION_START, PATRICIA_ADD_OPTION_END, patricia_add

trish2/patricia_add [ Functions ]

[ Top ] [ Functions ]

NAME

patricia_add

SYNOPSIS

 #include <patricia.h>
 void patricia_add(patricia_add_context_t *ctx, void (*hook)(const patricia_add_context_t *));

FUNCTION

patricia_add performs the insertion of an entry into a PATRICIA tree. All the information necessary to patricia_add is contained in ctx, you should allocate it and initialize it with patricia_add_context_init. hook is a function that accepts a pointer to a patricia_add_context_t and returns void. If hook is not NULL patricia_add will call it for each character of the entry by setting the last event type. The hook function can examine its argument in order see what is happening, but in any case it should not modify it.

INPUTS

SEE ALSO

patricia, patricia_add_context_t, PATRICIA_ADD_OPTION_START, PATRICIA_ADD_OPTION_END, PATRICIA_ADD_EVENT_NEW_NODE, PATRICIA_ADD_EVENT_TAIL, PATRICIA_ADD_EVENT_NEXT_NODE, PATRICIA_ADD_EVENT_SPLIT_TAIL, patricia_add_context_init

trish2/patricia_compact_tails [ Functions ]

[ Top ] [ Functions ]

NAME

patricia_compact_tails

SYNOPSIS

 #include <patricia.h>
 void patricia_compact_tails(patricia_t *pat);

FUNCTION

Each time patricia_add splits a tail string, it creates strings with successive null characters. patricia_compact_tails removes this lost space by shifting the tail strings in the tail string bunch and updating the nodes pointer to their tail string. This function is time-costly and the space gain is debatable.

INPUTS

SEE ALSO

patricia, patricia_t, bunch