rangetree.h 8.96 KB
Newer Older
Yoni Fogel's avatar
Yoni Fogel committed
1 2 3 4 5 6
/* -*- 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."

/**
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
7 8 9 10 11 12 13 14 15 16 17
   \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
*/
Yoni Fogel's avatar
Yoni Fogel committed
18

Yoni Fogel's avatar
Yoni Fogel committed
19
//Defines BOOL data type.
Yoni Fogel's avatar
Yoni Fogel committed
20 21
#include <brttypes.h>

Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
22 23 24 25
/** \brief Range with value
    Represents a range of data with an associated value.
    Parameters are never modified on failure with the exception of
    buf and buflen.
Yoni Fogel's avatar
Yoni Fogel committed
26
 */
Yoni Fogel's avatar
Yoni Fogel committed
27
typedef struct {
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
28 29 30
	void*   left;  /**< Left end-point */
  	void*   right; /**< Right end-point */
	void*   data;  /**< Data associated with the range */
Yoni Fogel's avatar
Yoni Fogel committed
31 32
} toku_range;

Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
33 34 35
/** \brief Internal range representation 
    Internal representation of a range tree. Some fields depend on the
    implementation of range trees, and some others are shared. */
Yoni Fogel's avatar
Yoni Fogel committed
36
struct __toku_range_tree_internal {
Yoni Fogel's avatar
Yoni Fogel committed
37
    //Shared fields:
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
38
    /** A comparison function, as in bsearch(3), to compare the end-points of 
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
39
        a range. It is assumed to be commutative. */
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
40 41 42
    int         (*end_cmp)(void*,void*);  
    /** A comparison function, as in bsearch(3), to compare the data associated
        with a range */
Yoni Fogel's avatar
Yoni Fogel committed
43
    int         (*data_cmp)(void*,void*);
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
44
    /** Whether this tree allows ranges to overlap */
Yoni Fogel's avatar
Yoni Fogel committed
45
    BOOL        allow_overlaps;
Yoni Fogel's avatar
Yoni Fogel committed
46
    /** The number of ranges in the range tree */
Yoni Fogel's avatar
Yoni Fogel committed
47
    unsigned    numelements;
Yoni Fogel's avatar
Yoni Fogel committed
48 49 50 51 52 53
    /** The user malloc function */
    void*       (*malloc) (size_t);
    /** The user free function */
    void        (*free)   (void*);
    /** The user realloc function */
    void*       (*realloc)(void*, size_t);
Yoni Fogel's avatar
Yoni Fogel committed
54 55 56 57 58 59 60 61 62 63 64 65 66
#if defined(TOKU_LINEAR_RANGE_TREE)
    #if defined(TOKU_LOG_RANGE_TREE)
        #error Choose just one range tree type.
    #endif
    //Linear version only fields:
    toku_range* ranges;
    unsigned    ranges_len;
#elif defined(TOKU_LOG_RANGE_TREE)
    #error Not defined yet.
    //Log version only fields:
#else
    #error Using an undefined RANGE TREE TYPE.
#endif
Yoni Fogel's avatar
Yoni Fogel committed
67 68
};

Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
69 70
/** Export the internal representation to a sensible name */
/*  These lines will remain. */
Yoni Fogel's avatar
Yoni Fogel committed
71
typedef struct __toku_range_tree_internal toku_range_tree;
Yoni Fogel's avatar
Yoni Fogel committed
72

Yoni Fogel's avatar
Yoni Fogel committed
73 74 75 76 77 78 79 80 81 82 83
/**
    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);

Yoni Fogel's avatar
Yoni Fogel committed
84
/**
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
85 86 87 88 89
    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). 
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
90
                          It must be commutative.
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
91 92 93 94
    \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. 
Yoni Fogel's avatar
Yoni Fogel committed
95 96
    \param user_malloc    A user provided malloc(3) function.
    \param user_free      A user provided free(3) function.
Yoni Fogel's avatar
Yoni Fogel committed
97
    \param user_realloc   A user provided realloc(3) function.
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
98 99 100 101

    \return
    - 0:              Success.
    - EINVAL:         If any pointer argument is NULL.
Yoni Fogel's avatar
Yoni Fogel committed
102
    - Other exit codes may be forwarded from underlying system calls. */
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
103
int toku_rt_create(toku_range_tree** ptree, int (*end_cmp)(void*,void*), 
Yoni Fogel's avatar
Yoni Fogel committed
104 105 106 107
                   int (*data_cmp)(void*,void*), BOOL allow_overlaps,
                   void* (*user_malloc) (size_t),
                   void  (*user_free)   (void*),
                   void* (*user_realloc)(void*, size_t)); 
Yoni Fogel's avatar
Yoni Fogel committed
108 109

/**
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
110 111 112 113
    Destroys and frees a range tree.
    \return
    - 0:              Success.
    - EINVAL:         If tree is NULL.
Yoni Fogel's avatar
Yoni Fogel committed
114
 */
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
115
int toku_rt_close(toku_range_tree* tree  /**< The range tree to free */);
Yoni Fogel's avatar
Yoni Fogel committed
116 117

/**
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140
   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 lenfth 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.
                   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.
Yoni Fogel's avatar
Yoni Fogel committed
141 142
   - Other exit codes may be forwarded from underlying system calls but only
     if buf is not large enough.
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
143 144 145 146

    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).
Yoni Fogel's avatar
Yoni Fogel committed
147
 */
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
148
int toku_rt_find(toku_range_tree* tree,toku_range* query, unsigned k,
Yoni Fogel's avatar
Yoni Fogel committed
149
                 toku_range** buf, unsigned* buflen, unsigned* numfound);
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
150
 
Yoni Fogel's avatar
Yoni Fogel committed
151 152

/**
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
153 154 155 156 157 158 159 160 161 162 163 164 165
    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 the exact range (left, right, and data) 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.
Yoni Fogel's avatar
Yoni Fogel committed
166 167 168 169
 */
int toku_rt_insert(toku_range_tree* tree, toku_range* range);

/**
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
170 171 172 173 174 175 176 177 178 179
    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.
Yoni Fogel's avatar
Yoni Fogel committed
180 181 182 183
 */
int toku_rt_delete(toku_range_tree* tree, toku_range* range);

/**
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200
    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.
Yoni Fogel's avatar
Yoni Fogel committed
201 202
 */
int toku_rt_predecessor(toku_range_tree* tree, void* point, toku_range* pred,
Yoni Fogel's avatar
Yoni Fogel committed
203
                        BOOL* wasfound);
Yoni Fogel's avatar
Yoni Fogel committed
204 205

/**
Vincenzo Liberatore's avatar
Vincenzo Liberatore committed
206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222
    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.
Yoni Fogel's avatar
Yoni Fogel committed
223 224 225
 */
int toku_rt_successor(toku_range_tree* tree, void* point, toku_range* succ,
                      BOOL* wasfound);