/* -*- mode: C; c-basic-offset: 4 -*- */ #ident "Copyright (c) 2007-8 Tokutek Inc. All rights reserved." #ident "The technology is licensed by the Massachusetts Institute of Technology, Rutgers State University of New Jersey, and the Research Foundation of State University of New York at Stony Brook under United States of America Serial No. 11/760379 and to the patents and/or patent applications resulting from it." #if !defined(TOKU_RANGE_TREE_H) #define TOKU_RANGE_TREE_H /** \file rangetree.h \brief Range trees: header and comments Range trees are an ordered data structure to hold intervals. You can learn about range trees at http://en.wikipedia.org/wiki/Interval_tree or by consulting the textbooks, e.g., Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7 */ //Defines BOOL data type. #include <brttypes.h> #include <db.h> struct __toku_point; #if !defined(__TOKU_POINT) #define __TOKU_POINT typedef struct __toku_point toku_point; #endif /** \brief Range with value Represents a range of data with an associated value. */ typedef struct { toku_point* left; /**< Left end-point */ toku_point* right; /**< Right end-point */ } toku_interval; typedef struct { toku_interval ends; TXNID data; /**< Data associated with the range */ } toku_range; /** Export the internal representation to a sensible name */ /* These lines will remain. */ typedef struct __toku_range_tree toku_range_tree; /** \brief Internal range representation Internal representation of a range tree. Some fields depend on the implementation of range trees, and some others are shared. Parameters are never modified on failure with the exception of buf and buflen. */ struct __toku_range_tree; /** Gets whether the range tree allows overlapping ranges. \param tree The range tree. \param allowed Returns whether overlaps are allowed. \return - 0: Success. - EINVAL: If any pointer argument is NULL. */ int toku_rt_get_allow_overlaps(toku_range_tree* tree, BOOL* allowed); /** Creates a range tree. \param ptree Points to the new range tree if create is successful \param end_cmp User provided function to compare end points. Return value conforms to cmp in qsort(3). It is assumed to define a total order. \param data_cmp User provided function to compare data values. Return value conforms to cmp in qsort(3). \param allow_overlaps Whether ranges in this range tree are permitted to overlap. \param user_malloc A user provided malloc(3) function. \param user_free A user provided free(3) function. \param user_realloc A user provided realloc(3) function. \return - 0: Success. - EINVAL: If any pointer argument is NULL. - EINVAL: If allow_overlaps = TRUE and the implementation does not support overlaps. - Other exit codes may be forwarded from underlying system calls. */ int toku_rt_create(toku_range_tree** ptree, int (*end_cmp)(const toku_point*,const toku_point*), int (*data_cmp)(const TXNID,const TXNID), BOOL allow_overlaps, void* (*user_malloc) (size_t), void (*user_free) (void*), void* (*user_realloc)(void*, size_t)); /** Destroys and frees a range tree. \param tree The range tree to close. \return - 0: Success. - EINVAL: If tree is NULL. */ int toku_rt_close(toku_range_tree* tree); /** Deletes all elements of a range tree. \param tree The range tree to clear. */ void toku_rt_clear(toku_range_tree* tree); /** Finds ranges in the range tree that overlap a query range. \param tree The range tree to search in. \param query The range to query. range.data must be NULL. \param k The maximum number of ranges to return. The special value '0' is used to request ALL overlapping ranges. \param buf A pointer to the buffer used to return ranges. The buffer will be increased using realloc(3) if necessary. NOTE: buf must have been dynamically allocated i.e. via malloc(3), calloc(3), etc. The buffer will not be modified unless it is too small. \param buflen A pointer to the current length of the buffer. If the buffer is increased, then buflen will be updated. \param numfound The number of ranges found. This will necessarily be <= k unless k == 0. If k != 0 && numfound == k, there may be additional ranges that overlap the queried range but were skipped to accomodate the request of k. \return - 0: Success. - EINVAL: If any pointer argument is NULL. If range.data != NULL. If buflen == 0. - Other exit codes may be forwarded from underlying system calls if buf is not large enough. Growth direction: It may be useful in the future to add an extra out parameter to specify whether more elements exist in the tree that overlap (in excess of the requested limit of k). */ int toku_rt_find(toku_range_tree* tree,toku_interval* query, u_int32_t k, toku_range** buf, u_int32_t* buflen, u_int32_t* numfound); /** Inserts a range into the range tree. \param tree The range tree to insert into. \param range The range to insert. \return - 0: Success. - EINVAL: If any pointer argument is NULL. - EDOM: If an equivalent range (left, right, and data according to end_cmp and data_cmp) already exists in the tree. If an overlapping range exists in the tree and allow_overlaps == FALSE. - Other exit codes may be forwarded from underlying system calls. */ int toku_rt_insert(toku_range_tree* tree, toku_range* range); /** Deletes a range from the range tree. \param tree The range tree to delete from. \param range The range to delete. \return - 0: Success. - EINVAL: If any pointer argument is NULL. - EDOM: If the exact range (left, right, and data) did not exist in the tree. */ int toku_rt_delete(toku_range_tree* tree, toku_range* range); /** Finds the strict predecessor range of a point i.e. the rightmost range completely to the left of the query point according to end_cmp. This operation is only defined if allow_overlaps == FALSE. \param tree The range tree to search in. \param point The point to query. Must be a valid argument to end_cmp. \param pred A buffer to return the predecessor. \param wasfound Whether a predecessor was found. If no range is strictly to the left of the query point this will be false. \return - 0: Success. - EINVAL: If any pointer argument is NULL. If tree allows overlaps. - Other exit codes may be forwarded from underlying system calls. */ int toku_rt_predecessor(toku_range_tree* tree, toku_point* point, toku_range* pred, BOOL* wasfound); /** Finds the strict successor range of a point i.e. the leftmost range completely to the right of the query point according to end_cmp. This operation is only defined if allow_overlaps == FALSE. \param tree The range tree to search in. \param point The point to query. Must be a valid argument to end_cmp. \param succ A buffer to return the successor range. \param wasfound Whether a predecessor was found. If no range is strictly to the left of the query point this will be false. \return - 0: Success. - EINVAL: If any pointer argument is NULL. If tree allows overlaps. - Other exit codes may be forwarded from underlying system calls. */ int toku_rt_successor(toku_range_tree* tree, toku_point* point, toku_range* succ, BOOL* wasfound); /** Finds the number of elements in the range tree. \param tree The range tree. \param size A buffer to return the the number of elements in the range tree. \return - 0: Success. - EINVAL: If any pointer argument is NULL. */ int toku_rt_get_size(toku_range_tree* tree, u_int32_t* size); int toku_rt_iterate(toku_range_tree* tree, int (*f)(toku_range*,void*), void* extra); #endif /* #if !defined(TOKU_RANGE_TREE_H) */