libdoodle(3) [debian man page]
LIBDOODLE(3) Library Functions Manual LIBDOODLE(3) NAME
libdoodle - multi-suffix tree based file search library 0.7.0 SYNOPSIS
#include <doodle.h> typedef void (*DOODLE_Logger)(void * context, unsigned int level, const char * message, ...); typedef struct { char * filename; unsigned int mod_time; } DOODLE_FileInfo; typedef void (*DOODLE_TreeCallback)(const DOODLE_FileInfo * fileinfo, void * arg); unsigned int DOODLE_getFileCount(const struct DOODLE_SuffixTree * tree); const DOODLE_File * DOODLE_getFileAt(const struct DOODLE_SuffixTree * tree, unsigned int index); struct DOODLE_SuffixTree * DOODLE_tree_create(DOODLE_Logger log, void * context, const char * database); void DOODLE_tree_set_memory_limit(struct DOODLE_SuffixTree *tree, size_t limit); void DOODLE_tree_destroy(struct DOODLE_SuffixTree * tree); int DOODLE_tree_expand(struct DOODLE_SuffixTree * tree, const unsigned char * searchString, const char * fileName); int DOODLE_tree_truncate(struct DOODLE_SuffixTree * tree, const char * fileName); int DOODLE_tree_dump(FILE * stream, struct DOODLE_SuffixTree * tree); int DOODLE_tree_search_approx(struct DOODLE_SuffixTree * tree, const unsigned int approx, const int ignore_case, const unsigned char * ss, DOODLE_ResultCallback * callback, void * arg); int DOODLE_tree_search(struct DOODLE_SuffixTree * tree, const unsigned char * substring, DOODLE_ResultCallback * callback, void * arg); DESCRIPTION
libdoodle is a library that provides a multi-suffix tree to lookup files. The basic use is to create a suffix tree, add some keywords (associated with a file), search the tree and finally free the tree. libdoodle features code to quickly serialize the tree into a compact format. In order to use libdoodle, client code first creates a tree (passing a callback function that will log all error messages associated with this tree and the name of the database) using DOODLE_tree_create. The tree can then be searched using DOODLE_tree_search or DOO- DLE_tree_search_approx (which requires additional processing with DOODLE_tree_iterate to walk over the individual results). The tree can be expanded with new search strings (DOODLE_tree_expand) and existing matches can be removed with DOODLE_tree_truncate. It is only possi- ble to remove all keywords for a given file. With DOODLE_getFileAt and DOODLE_getFileCount it is possible to inspect the files that are currently in the tree (and to check if their respective modification timestamps, useful for keeping track of when an entry maybe outdated). Finally the tree must be released using DOODLE_tree_destroy. This writes the changes to the disk and frees all associated resources. Example code for using the complete libdoodle API can be found in doodle.c. If jni.h was found when libdoodle was compiled, libdoodle will contain methods that allow Java code to directly use libdoodle. See org.gnunet.doodle.Doodle for Java code providing an interface to lib- doodle and for a sample main method that demonstrates searching the doodle database from Java. SEE ALSO
doodle(1), extract(1), libextractor(3) LEGAL NOTICE
libdoodle and doodle are released under the GPL. BUGS
There is at least one known bug, but nobody was able to reproduce it yet. But in general things work fine. :-) REPORTING BUGS
Report bugs to mantis <https://gnunet.org/bugs/> or by sending electronic mail to <christian@grothoff.org> AUTHORS
doodle was originally written by Christian Grothoff <christian@grothoff.org>. AVAILABILITY
You can obtain the original author's latest version from http://grothoff.org/christian/doodle/. libdoodle Jan 1 2010 LIBDOODLE(3)
Check Out this Related Man Page
RBTREE(3) BSD Library Functions Manual RBTREE(3) NAME
rbtree -- red-black tree LIBRARY
Standard C Library (libc, -lc) SYNOPSIS
#include <sys/rbtree.h> void rb_tree_init(rb_tree_t *rbt, const rb_tree_ops_t *ops); void * rb_tree_insert_node(rb_tree_t *rbt, void *rb); void rb_tree_remove_node(rb_tree_t *rbt, void *rb); void * rb_tree_find_node(rb_tree_t *rbt, const void *key); void * rb_tree_find_node_geq(rb_tree_t *rbt, const void *key); void * rb_tree_find_node_leq(rb_tree_t *rbt, const void *key); void * rb_tree_iterate(rb_tree_t *rbt, void *rb, const unsigned int direction); DESCRIPTION
rbtree provides red-black trees. A red-black tree is a binary search tree with the node color as an extra attribute. It fulfills a set of conditions: 1. Every search path from the root to a leaf consists of the same number of black nodes. 2. Each red node (except for the root) has a black parent. 3. Each leaf node is black. Every operation on a red-black tree is bounded as O(lg n). The maximum height of a red-black tree is 2lg (n+1). TYPES
rb_tree_t A red-black tree. typedef signed int (*const rbto_compare_nodes_fn)(void *context, const void *node1, const void *node2); The node-comparison operator. Defines an ordering on nodes. Returns a negative value if the first node node1 precedes the second node node2. Returns a positive value if the first node node1 follows the second node node2. Returns 0 if the first node node1 and the second node node2 are identical according to the ordering. typedef signed int (*const rbto_compare_key_fn)(void *context, const void *node, const void *key); The node-key comparison operator. Defines the order of nodes and keys. Returns a negative value if the node node precedes the key key. Returns a positive value if the node node follows the key key. Returns 0 if the node node is identical to the key key accord- ing to the ordering. rb_tree_ops_t Defines the operator for comparing two nodes in the same tree, the operator for comparing a node in the tree with a key, the offset of member rb_node_t within a node, and the opaque context passed to the operators. Members of rb_tree_ops_t are rbto_compare_nodes_fn rbto_compare_nodes; rbto_compare_key_fn rbto_compare_key; size_t rbto_node_offset; void *rbto_context; rb_node_t A node in a red-black tree has this structure as a member. FUNCTIONS
rb_tree_init(rbt, ops) Initialize the red-black tree rbt. Let the comparison operators given by ops define the order of nodes in the tree for the purposes of insertion, search, and iteration. rb_tree_init() always succeeds. rb_tree_insert_node(rbt, rb) Insert the node rb into the tree rbt. Return inserted node on success, already existing node on failure. rb_tree_remove_node(rbt, rb) Remove the node rb from the tree rbt. rb_tree_find_node(rbt, key) Search the tree rbt for a node exactly matching key. If no such node is in the tree, return NULL. Otherwise, return the matching node. rb_tree_find_node_geq(rbt, key) Search the tree rbt for a node that exactly matches key and return it. If no such node is present, return the first node following key or, if no such node is in the tree, return NULL. rb_tree_find_node_leq(rbt, key) Search the tree rbt for a node that exactly matches key and return it. If no such node is present, return the first node preceding key or, if no such node is in the tree, return NULL. rb_tree_iterate(rbt, rb, direction) If direction is RB_DIR_LEFT, return the node in the tree rbt immediately preceding the node rb or, if rb is NULL, return the last node in rbt or, if the tree is empty, return NULL. If direction is RB_DIR_RIGHT, return the node in the tree rbt immediately following the node rb or, if rb is NULL, return the first node in rbt or, if the tree is empty, return NULL. CODE REFERENCES
The rbtree interface is implemented in common/lib/libc/gen/rb.c. SEE ALSO
queue(3), tree(3) HISTORY
The rbtree interface first appeared in NetBSD 6.0. AUTHORS
Matt Thomas <matt@NetBSD.org> wrote rbtree. Niels Provos <provos@citi.umich.edu> wrote the tree(3) manual page. Portions of this page derive from that page. BSD
August 19, 2012 BSD