omt.c 28.9 KB
Newer Older
1 2
/* -*- mode: C; c-basic-offset: 4; indent-tabs-mode: nil -*- */
// vim: expandtab:ts=8:sw=4:softtabstop=4:
Bradley C. Kuszmaul's avatar
Bradley C. Kuszmaul committed
3
#ident "$Id$"
4
#ident "Copyright (c) 2007-2010 Tokutek Inc.  All rights reserved."
5
#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."
6

7
#include <toku_portability.h>
Yoni Fogel's avatar
Yoni Fogel committed
8 9
#include <ctype.h>
#include <errno.h>
10 11 12 13 14
#if defined(HAVE_MALLOC_H)
# include <malloc.h>
#elif defined(HAVE_SYS_MALLOC_H)
# include <sys/malloc.h>
#endif
Yoni Fogel's avatar
Yoni Fogel committed
15 16 17 18 19 20 21
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "toku_assert.h"
#include "memory.h"
#include "omt.h"
22
#include "fttypes.h"
23

24 25 26 27 28 29 30 31 32
typedef u_int32_t node_idx;
static const node_idx NODE_NULL = UINT32_MAX;

typedef struct omt_node *OMT_NODE;
struct omt_node {
    u_int32_t weight; /* Size of subtree rooted at this node (including this one). */
    node_idx  left;   /* Index of left  subtree. */
    node_idx  right;  /* Index of right subtree. */
    OMTVALUE  value;  /* The value stored in the node. */
33
} __attribute__((__packed__));
34

Yoni Fogel's avatar
Yoni Fogel committed
35 36 37 38 39 40 41 42

struct omt_array {
    u_int32_t  start_idx;
    u_int32_t  num_values;
    OMTVALUE  *values;
};

struct omt_tree {
43 44 45 46
    node_idx   root;

    OMT_NODE   nodes;
    node_idx   free_idx;
Yoni Fogel's avatar
Yoni Fogel committed
47
};
48

Yoni Fogel's avatar
Yoni Fogel committed
49 50
struct omt {
    BOOL       is_array;
Yoni Fogel's avatar
Yoni Fogel committed
51
    u_int32_t  capacity;
Yoni Fogel's avatar
Yoni Fogel committed
52 53 54 55
    union {
        struct omt_array a;
        struct omt_tree t;
    } i;
56
};
57

58 59
static inline int
omt_create_no_array(OMT *omtp) {
Zardosht Kasheff's avatar
Zardosht Kasheff committed
60
    OMT XMALLOC(result);
61
    if (result==NULL) return ENOMEM;
Yoni Fogel's avatar
Yoni Fogel committed
62 63 64
    result->is_array       = TRUE;
    result->i.a.num_values = 0;
    result->i.a.start_idx  = 0;
65 66 67 68 69 70 71 72 73 74
    *omtp = result;
    return 0;
}

static int omt_create_internal(OMT *omtp, u_int32_t num_starting_nodes) {
    OMT result;
    int r = omt_create_no_array(&result);
    if (r) return r;
    if (num_starting_nodes < 2) num_starting_nodes = 2;
    result->capacity       = 2*num_starting_nodes;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
75
    XMALLOC_N(result->capacity, result->i.a.values);
76 77 78 79
    *omtp = result;
    return 0;
}

80 81 82 83 84 85 86 87 88 89 90 91 92
int
toku_omt_create_steal_sorted_array(OMT *omtp, OMTVALUE **valuesp, u_int32_t numvalues, u_int32_t capacity) {
    if (numvalues>capacity || !*valuesp) return EINVAL;
    int r = omt_create_no_array(omtp);
    if (r) return r;
    OMT result = *omtp;
    result->capacity       = capacity;
    result->i.a.num_values = numvalues;
    result->i.a.values     = *valuesp;
    *valuesp = NULL; //Remove caller's reference.
    return 0;
}

Yoni Fogel's avatar
Yoni Fogel committed
93 94
static inline u_int32_t nweight(OMT omt, node_idx idx) {
    if (idx==NODE_NULL) return 0;
Yoni Fogel's avatar
Yoni Fogel committed
95
    else return (omt->i.t.nodes+idx)->weight;
Yoni Fogel's avatar
Yoni Fogel committed
96 97
}

Yoni Fogel's avatar
Yoni Fogel committed
98 99
static inline u_int32_t omt_size(OMT omt) {
    return omt->is_array ? omt->i.a.num_values : nweight(omt, omt->i.t.root);
Yoni Fogel's avatar
Yoni Fogel committed
100 101 102
}

static inline node_idx omt_node_malloc(OMT omt) {
Yoni Fogel's avatar
Yoni Fogel committed
103
    assert(omt->i.t.free_idx < omt->capacity);
Yoni Fogel's avatar
Yoni Fogel committed
104
    return omt->i.t.free_idx++;
Yoni Fogel's avatar
Yoni Fogel committed
105 106 107
}

static inline void omt_node_free(OMT omt, node_idx idx) {
Yoni Fogel's avatar
Yoni Fogel committed
108
    assert(idx < omt->capacity);
Yoni Fogel's avatar
Yoni Fogel committed
109 110 111 112
}

static inline void fill_array_with_subtree_values(OMT omt, OMTVALUE *array, node_idx tree_idx) {
    if (tree_idx==NODE_NULL) return;
Yoni Fogel's avatar
Yoni Fogel committed
113
    OMT_NODE tree = omt->i.t.nodes+tree_idx;
Yoni Fogel's avatar
Yoni Fogel committed
114 115
    fill_array_with_subtree_values(omt, array, tree->left);
    array[nweight(omt, tree->left)] = tree->value;
116
    fill_array_with_subtree_values(omt, array+nweight(omt, tree->left)+1, tree->right);
Yoni Fogel's avatar
Yoni Fogel committed
117 118 119 120 121 122 123 124 125 126
}

// Example:  numvalues=4,  halfway=2,  left side is values of size 2
//                                     right side is values+3 of size 1
//           numvalues=3,  halfway=1,  left side is values of size 1
//                                     right side is values+2 of size 1
//           numvalues=2,  halfway=1,  left side is values of size 1
//                                     right side is values+2 of size 0
//           numvalues=1,  halfway=0,  left side is values of size 0
//                                     right side is values of size 0.
Yoni Fogel's avatar
Yoni Fogel committed
127 128
static inline void rebuild_from_sorted_array(OMT omt, node_idx *n_idxp,
                                             OMTVALUE *values, u_int32_t numvalues) {
129
    if (numvalues==0) {
Yoni Fogel's avatar
Yoni Fogel committed
130
        *n_idxp = NODE_NULL;
131 132
    } else {
        u_int32_t halfway = numvalues/2;
Yoni Fogel's avatar
Yoni Fogel committed
133
        node_idx newidx   = omt_node_malloc(omt);
Yoni Fogel's avatar
Yoni Fogel committed
134
        OMT_NODE newnode  = omt->i.t.nodes+newidx;
Yoni Fogel's avatar
Yoni Fogel committed
135
        newnode->weight   = numvalues;
136
        newnode->value    = values[halfway];
137
        *n_idxp = newidx; // update everything before the recursive calls so the second call can be a tail call.
Yoni Fogel's avatar
Yoni Fogel committed
138 139
        rebuild_from_sorted_array(omt, &newnode->left,  values,           halfway);
        rebuild_from_sorted_array(omt, &newnode->right, values+halfway+1, numvalues-(halfway+1));
Yoni Fogel's avatar
Yoni Fogel committed
140 141 142
    }
}

Yoni Fogel's avatar
Yoni Fogel committed
143 144
static inline int maybe_resize_array(OMT omt, u_int32_t n) {
    u_int32_t new_size = n<=2 ? 4 : 2*n;
Yoni Fogel's avatar
Yoni Fogel committed
145
    u_int32_t room = omt->capacity - omt->i.a.start_idx;
Yoni Fogel's avatar
Yoni Fogel committed
146

Yoni Fogel's avatar
Yoni Fogel committed
147
    if (room<n || omt->capacity/2>=new_size) {
Zardosht Kasheff's avatar
Zardosht Kasheff committed
148
        OMTVALUE *XMALLOC_N(new_size, tmp_values);
149
        if (tmp_values==NULL) return get_error_errno();
Yoni Fogel's avatar
Yoni Fogel committed
150 151 152
        memcpy(tmp_values, omt->i.a.values+omt->i.a.start_idx,
               omt->i.a.num_values*sizeof(*tmp_values));
        omt->i.a.start_idx = 0;
Yoni Fogel's avatar
Yoni Fogel committed
153
        omt->capacity  = new_size;
Yoni Fogel's avatar
Yoni Fogel committed
154 155 156
        toku_free(omt->i.a.values);
        omt->i.a.values    = tmp_values;
    }
Yoni Fogel's avatar
Yoni Fogel committed
157 158 159
    return 0;
}

Yoni Fogel's avatar
Yoni Fogel committed
160 161 162 163
static int omt_convert_to_tree(OMT omt) {
    if (!omt->is_array) return 0;
    u_int32_t num_nodes = omt_size(omt);
    u_int32_t new_size  = num_nodes*2;
Yoni Fogel's avatar
Yoni Fogel committed
164
    new_size = new_size < 4 ? 4 : new_size;
Yoni Fogel's avatar
Yoni Fogel committed
165

Zardosht Kasheff's avatar
Zardosht Kasheff committed
166
    OMT_NODE XMALLOC_N(new_size, new_nodes);
167
    if (new_nodes==NULL) return get_error_errno();
Yoni Fogel's avatar
Yoni Fogel committed
168 169 170 171
    OMTVALUE *values     = omt->i.a.values;
    OMTVALUE *tmp_values = values + omt->i.a.start_idx;
    omt->is_array          = FALSE;
    omt->i.t.nodes         = new_nodes;
Yoni Fogel's avatar
Yoni Fogel committed
172
    omt->capacity          = new_size;
173
    omt->i.t.free_idx      = 0;
Yoni Fogel's avatar
Yoni Fogel committed
174 175 176 177 178 179 180 181 182
    omt->i.t.root          = NODE_NULL;
    rebuild_from_sorted_array(omt, &omt->i.t.root, tmp_values, num_nodes);
    toku_free(values);
    return 0;
}

static int omt_convert_to_array(OMT omt) {
    if (omt->is_array) return 0;
    u_int32_t num_values = omt_size(omt);
Yoni Fogel's avatar
Yoni Fogel committed
183 184 185
    u_int32_t new_size  = 2*num_values;
    new_size = new_size < 4 ? 4 : new_size;

Zardosht Kasheff's avatar
Zardosht Kasheff committed
186
    OMTVALUE *XMALLOC_N(new_size, tmp_values);
187
    if (tmp_values==NULL) return get_error_errno();
Yoni Fogel's avatar
Yoni Fogel committed
188 189
    fill_array_with_subtree_values(omt, tmp_values, omt->i.t.root);
    toku_free(omt->i.t.nodes);
Yoni Fogel's avatar
Yoni Fogel committed
190 191
    omt->is_array       = TRUE;
    omt->capacity       = new_size;
Yoni Fogel's avatar
Yoni Fogel committed
192 193 194 195 196 197
    omt->i.a.num_values = num_values;
    omt->i.a.values     = tmp_values;
    omt->i.a.start_idx  = 0;
    return 0;
}

Yoni Fogel's avatar
Yoni Fogel committed
198
static inline int maybe_resize_or_convert(OMT omt, u_int32_t n) {
Yoni Fogel's avatar
Yoni Fogel committed
199 200
    if (omt->is_array) return maybe_resize_array(omt, n);

Yoni Fogel's avatar
Yoni Fogel committed
201
    u_int32_t new_size = n<=2 ? 4 : 2*n;
Yoni Fogel's avatar
Yoni Fogel committed
202 203 204 205 206

    /* Rebuild/realloc the nodes array iff any of the following:
     *  The array is smaller than the number of elements we want.
     *  We are increasing the number of elements and there is no free space.
     *  The array is too large. */
Yoni Fogel's avatar
Yoni Fogel committed
207 208 209
    //Rebuilding means we first turn it to an array.
    //Lets pause at the array form.
    u_int32_t num_nodes = nweight(omt, omt->i.t.root);
Yoni Fogel's avatar
Yoni Fogel committed
210 211 212
    if ((omt->capacity/2 >= new_size) ||
        (omt->i.t.free_idx>=omt->capacity && num_nodes<n) ||
        (omt->capacity<n)) {
Yoni Fogel's avatar
Yoni Fogel committed
213
        return omt_convert_to_array(omt);
Yoni Fogel's avatar
Yoni Fogel committed
214
    }
Yoni Fogel's avatar
Yoni Fogel committed
215
    return 0;
Yoni Fogel's avatar
Yoni Fogel committed
216 217 218 219
}

static inline void fill_array_with_subtree_idxs(OMT omt, node_idx *array, node_idx tree_idx) {
    if (tree_idx==NODE_NULL) return;
Yoni Fogel's avatar
Yoni Fogel committed
220
    OMT_NODE tree = omt->i.t.nodes+tree_idx;
Yoni Fogel's avatar
Yoni Fogel committed
221 222
    fill_array_with_subtree_idxs(omt, array, tree->left);
    array[nweight(omt, tree->left)] = tree_idx;
223
    fill_array_with_subtree_idxs(omt, array+nweight(omt, tree->left)+1, tree->right);
Yoni Fogel's avatar
Yoni Fogel committed
224 225 226 227 228 229 230 231 232 233
}

/* Reuses existing OMT_NODE structures (used for rebalancing). */
static inline void rebuild_subtree_from_idxs(OMT omt, node_idx *n_idxp, node_idx *idxs,
                                             u_int32_t numvalues) {
    if (numvalues==0) {
        *n_idxp=NODE_NULL;
    } else {
        u_int32_t halfway = numvalues/2;
        node_idx newidx   = idxs[halfway];
Yoni Fogel's avatar
Yoni Fogel committed
234
        OMT_NODE newnode  = omt->i.t.nodes+newidx;
Yoni Fogel's avatar
Yoni Fogel committed
235
        newnode->weight   = numvalues;
236
        // value is already in there.
Yoni Fogel's avatar
Yoni Fogel committed
237 238 239
        rebuild_subtree_from_idxs(omt, &newnode->left,  idxs,           halfway);
        rebuild_subtree_from_idxs(omt, &newnode->right, idxs+halfway+1, numvalues-(halfway+1));
        *n_idxp = newidx;
240 241 242
    }
}

Yoni Fogel's avatar
Yoni Fogel committed
243
static inline void rebalance(OMT omt, node_idx *n_idxp) {
Yoni Fogel's avatar
Yoni Fogel committed
244
    node_idx idx = *n_idxp;
Yoni Fogel's avatar
Yoni Fogel committed
245 246 247 248 249 250 251 252
    if (idx==omt->i.t.root) {
        //Try to convert to an array.
        //If this fails, (malloc) nothing will have changed.
        //In the failure case we continue on to the standard rebalance
        //algorithm.
        int r = omt_convert_to_array(omt);
        if (r==0) return;
    }
Yoni Fogel's avatar
Yoni Fogel committed
253
    OMT_NODE n   = omt->i.t.nodes+idx;
Yoni Fogel's avatar
Yoni Fogel committed
254 255 256 257 258 259 260 261 262 263 264 265
    node_idx *tmp_array;
    size_t mem_needed = n->weight*sizeof(*tmp_array);
    size_t mem_free   = (omt->capacity-omt->i.t.free_idx)*sizeof(*omt->i.t.nodes);
    BOOL malloced;
    if (mem_needed<=mem_free) {
        //There is sufficient free space at the end of the nodes array
        //to hold enough node indexes to rebalance.
        malloced  = FALSE;
        tmp_array = (node_idx*)(omt->i.t.nodes+omt->i.t.free_idx);
    }
    else {
        malloced  = TRUE;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
266
        XMALLOC_N(n->weight, tmp_array);
Yoni Fogel's avatar
Yoni Fogel committed
267 268 269 270 271
        if (tmp_array==NULL) return;    //Don't rebalance.  Still a working tree.
    }
    fill_array_with_subtree_idxs(omt, tmp_array, idx);
    rebuild_subtree_from_idxs(omt, n_idxp, tmp_array, n->weight);
    if (malloced) toku_free(tmp_array);
Yoni Fogel's avatar
Yoni Fogel committed
272 273 274 275
}

static inline BOOL will_need_rebalance(OMT omt, node_idx n_idx, int leftmod, int rightmod) {
    if (n_idx==NODE_NULL) return FALSE;
Yoni Fogel's avatar
Yoni Fogel committed
276
    OMT_NODE n = omt->i.t.nodes+n_idx;
277 278
    // one of the 1's is for the root.
    // the other is to take ceil(n/2)
Yoni Fogel's avatar
Yoni Fogel committed
279 280
    u_int32_t weight_left  = nweight(omt, n->left)  + leftmod;
    u_int32_t weight_right = nweight(omt, n->right) + rightmod;
281 282 283
    return (BOOL)((1+weight_left < (1+1+weight_right)/2)
		  ||
		  (1+weight_right < (1+1+weight_left)/2));
284
}
Yoni Fogel's avatar
Yoni Fogel committed
285 286

static inline void insert_internal(OMT omt, node_idx *n_idxp, OMTVALUE value, u_int32_t index, node_idx **rebalance_idx) {
Yoni Fogel's avatar
Yoni Fogel committed
287
    if (*n_idxp==NODE_NULL) {
288
        assert(index==0);
Yoni Fogel's avatar
Yoni Fogel committed
289
        node_idx newidx  = omt_node_malloc(omt);
Yoni Fogel's avatar
Yoni Fogel committed
290
        OMT_NODE newnode = omt->i.t.nodes+newidx;
Yoni Fogel's avatar
Yoni Fogel committed
291 292 293 294 295
        newnode->weight  = 1;
        newnode->left    = NODE_NULL;
        newnode->right   = NODE_NULL;
        newnode->value   = value;
        *n_idxp = newidx;
296
    } else {
Yoni Fogel's avatar
Yoni Fogel committed
297
        node_idx idx = *n_idxp;
Yoni Fogel's avatar
Yoni Fogel committed
298
        OMT_NODE n   = omt->i.t.nodes+idx;
Yoni Fogel's avatar
Yoni Fogel committed
299
        n->weight++;
Yoni Fogel's avatar
Yoni Fogel committed
300
        if (index <= nweight(omt, n->left)) {
Yoni Fogel's avatar
Yoni Fogel committed
301 302 303 304
            if (*rebalance_idx==NULL && will_need_rebalance(omt, idx, 1, 0)) {
                *rebalance_idx = n_idxp;
            }
            insert_internal(omt, &n->left,  value, index, rebalance_idx);
305
        } else {
Yoni Fogel's avatar
Yoni Fogel committed
306 307 308
            if (*rebalance_idx==NULL && will_need_rebalance(omt, idx, 0, 1)) {
                *rebalance_idx = n_idxp;
            }
Yoni Fogel's avatar
Yoni Fogel committed
309
            u_int32_t sub_index = index-nweight(omt, n->left)-1;
Yoni Fogel's avatar
Yoni Fogel committed
310
            insert_internal(omt, &n->right, value, sub_index, rebalance_idx);
311 312 313 314
        }
    }
}

Yoni Fogel's avatar
Yoni Fogel committed
315 316
static inline void set_at_internal_array(OMT omt, OMTVALUE v, u_int32_t index) {
    omt->i.a.values[omt->i.a.start_idx+index] = v;
317 318
}

Yoni Fogel's avatar
Yoni Fogel committed
319 320
static inline void set_at_internal(OMT omt, node_idx n_idx, OMTVALUE v, u_int32_t index) {
    assert(n_idx!=NODE_NULL);
Yoni Fogel's avatar
Yoni Fogel committed
321
    OMT_NODE n = omt->i.t.nodes+n_idx;
Yoni Fogel's avatar
Yoni Fogel committed
322 323 324
    if (index<nweight(omt, n->left))
	set_at_internal(omt, n->left, v, index);
    else if (index==nweight(omt, n->left)) {
325 326
	n->value = v;
    } else {
Yoni Fogel's avatar
Yoni Fogel committed
327
	set_at_internal(omt, n->right, v, index-nweight(omt, n->left)-1);
328 329 330
    }
}

Yoni Fogel's avatar
Yoni Fogel committed
331
static inline void delete_internal(OMT omt, node_idx *n_idxp, u_int32_t index, OMTVALUE *vp, node_idx **rebalance_idx) {
Yoni Fogel's avatar
Yoni Fogel committed
332
    assert(*n_idxp!=NODE_NULL);
Yoni Fogel's avatar
Yoni Fogel committed
333
    OMT_NODE n = omt->i.t.nodes+*n_idxp;
Yoni Fogel's avatar
Yoni Fogel committed
334
    if (index < nweight(omt, n->left)) {
335
        n->weight--;
Yoni Fogel's avatar
Yoni Fogel committed
336 337 338 339
        if (*rebalance_idx==NULL && will_need_rebalance(omt, *n_idxp, -1, 0)) {
            *rebalance_idx = n_idxp;
        }
        delete_internal(omt, &n->left, index, vp, rebalance_idx);
Yoni Fogel's avatar
Yoni Fogel committed
340 341 342 343 344 345 346 347 348 349 350
    } else if (index == nweight(omt, n->left)) {
        if (n->left==NODE_NULL) {
            u_int32_t idx = *n_idxp;
            *n_idxp = n->right;
            *vp     = n->value;
            omt_node_free(omt, idx);
        } else if (n->right==NODE_NULL) {
            u_int32_t idx = *n_idxp;
            *n_idxp = n->left;
            *vp     = n->value;
            omt_node_free(omt, idx);
351 352 353
        } else {
            OMTVALUE zv;
            // delete the successor of index, get the value, and store it here.
Yoni Fogel's avatar
Yoni Fogel committed
354 355 356 357
            if (*rebalance_idx==NULL && will_need_rebalance(omt, *n_idxp, 0, -1)) {
                *rebalance_idx = n_idxp;
            }
            delete_internal(omt, &n->right, 0, &zv, rebalance_idx);
358 359 360 361 362
            n->value = zv;
            n->weight--;
        }
    } else {
        n->weight--;
Yoni Fogel's avatar
Yoni Fogel committed
363 364 365 366
        if (*rebalance_idx==NULL && will_need_rebalance(omt, *n_idxp, 0, -1)) {
            *rebalance_idx = n_idxp;
        }
        delete_internal(omt, &n->right, index-nweight(omt, n->left)-1, vp, rebalance_idx);
367 368 369
    }
}

Yoni Fogel's avatar
Yoni Fogel committed
370 371
static inline void fetch_internal_array(OMT V, u_int32_t i, OMTVALUE *v) {
    *v = V->i.a.values[V->i.a.start_idx+i];
372 373
}

374
static inline void fetch_internal(OMT V, node_idx idx, u_int32_t i, OMTVALUE *v) {
Yoni Fogel's avatar
Yoni Fogel committed
375
    OMT_NODE n = V->i.t.nodes+idx;
Yoni Fogel's avatar
Yoni Fogel committed
376
    if (i < nweight(V, n->left)) {
377
        fetch_internal(V, n->left,  i, v);
Yoni Fogel's avatar
Yoni Fogel committed
378
    } else if (i == nweight(V, n->left)) {
379 380
        *v = n->value;
    } else {
381
        fetch_internal(V, n->right, i-nweight(V, n->left)-1, v);
382 383 384
    }
}

Yoni Fogel's avatar
Yoni Fogel committed
385 386 387 388 389 390 391 392 393
static inline int iterate_internal_array(OMT omt,
                                  u_int32_t left, u_int32_t right,
                                  int (*f)(OMTVALUE, u_int32_t, void*), void*v) {
    int r;
    u_int32_t i;

    for (i = left; i < right; i++) {
        r = f(omt->i.a.values[i+omt->i.a.start_idx], i, v);
        if (r!=0) return r;
394 395
    }
    return 0;
Yoni Fogel's avatar
Yoni Fogel committed
396 397
}

Yoni Fogel's avatar
Yoni Fogel committed
398 399
static inline int iterate_internal(OMT omt, u_int32_t left, u_int32_t right,
                                   node_idx n_idx, u_int32_t idx,
Yoni Fogel's avatar
Yoni Fogel committed
400 401 402
                                   int (*f)(OMTVALUE, u_int32_t, void*), void*v) {
    int r;
    if (n_idx==NODE_NULL) return 0;
Yoni Fogel's avatar
Yoni Fogel committed
403
    OMT_NODE n = omt->i.t.nodes+n_idx;
Yoni Fogel's avatar
Yoni Fogel committed
404 405 406 407 408
    u_int32_t idx_root = idx+nweight(omt,n->left);
    if (left< idx_root && (r=iterate_internal(omt, left, right, n->left, idx, f, v))) return r;
    if (left<=idx_root && idx_root<right && (r=f(n->value, idx_root, v))) return r;
    if (idx_root+1<right) return iterate_internal(omt, left, right, n->right, idx_root+1, f, v);
    return 0;
Yoni Fogel's avatar
Yoni Fogel committed
409 410
}

Yoni Fogel's avatar
Yoni Fogel committed
411 412 413 414 415
static inline int find_internal_zero_array(OMT omt, int (*h)(OMTVALUE, void*extra), void*extra, OMTVALUE *value, u_int32_t *index) {
    u_int32_t min   = omt->i.a.start_idx;
    u_int32_t limit = omt->i.a.start_idx + omt->i.a.num_values;
    u_int32_t best_pos  = NODE_NULL;
    u_int32_t best_zero = NODE_NULL;
416

Yoni Fogel's avatar
Yoni Fogel committed
417 418 419 420 421 422 423
    while (min!=limit) {
        u_int32_t mid = (min + limit) / 2;
        int hv = h(omt->i.a.values[mid], extra);
        if (hv<0) {
            min = mid+1;
        }
        else if (hv>0) {
424
            best_pos  = mid;
Yoni Fogel's avatar
Yoni Fogel committed
425 426 427 428 429 430
            limit     = mid;
        }
        else {
            best_zero = mid;
            limit     = mid;
        }
Yoni Fogel's avatar
Yoni Fogel committed
431
    }
Yoni Fogel's avatar
Yoni Fogel committed
432 433 434 435 436 437 438 439 440
    if (best_zero!=NODE_NULL) {
        //Found a zero
        if (value!=NULL) *value = omt->i.a.values[best_zero];
        *index = best_zero - omt->i.a.start_idx;
        return 0;
    }
    if (best_pos!=NODE_NULL) *index = best_pos - omt->i.a.start_idx;
    else                     *index = omt->i.a.num_values;
    return DB_NOTFOUND;
Yoni Fogel's avatar
Yoni Fogel committed
441 442
}

443 444 445
static inline int find_internal_zero(OMT omt, node_idx n_idx, int (*h)(OMTVALUE, void*extra), void*extra, OMTVALUE *value, u_int32_t *index)
// requires: index!=NULL
{
Yoni Fogel's avatar
Yoni Fogel committed
446
    if (n_idx==NODE_NULL) {
447
	*index = 0;
448 449
	return DB_NOTFOUND;
    }
Yoni Fogel's avatar
Yoni Fogel committed
450
    OMT_NODE n = omt->i.t.nodes+n_idx;
451 452
    int hv = h(n->value, extra);
    if (hv<0) {
453
        int r = find_internal_zero(omt, n->right, h, extra, value, index);
454
        *index += nweight(omt, n->left)+1;
455 456
        return r;
    } else if (hv>0) {
457
        return find_internal_zero(omt, n->left, h, extra, value, index);
458
    } else {
459
        int r = find_internal_zero(omt, n->left, h, extra, value, index);
460
        if (r==DB_NOTFOUND) {
461
            *index = nweight(omt, n->left);
462
            if (value!=NULL) *value = n->value;
463 464 465 466 467 468
            r = 0;
        }
        return r;
    }
}

Yoni Fogel's avatar
Yoni Fogel committed
469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484

static inline int find_internal_plus_array(OMT omt, int (*h)(OMTVALUE, void*extra), void*extra, OMTVALUE *value, u_int32_t *index) {
    u_int32_t min   = omt->i.a.start_idx;
    u_int32_t limit = omt->i.a.start_idx + omt->i.a.num_values;
    u_int32_t best  = NODE_NULL;

    while (min!=limit) {
        u_int32_t mid = (min + limit) / 2;
        int hv = h(omt->i.a.values[mid], extra);
        if (hv>0) {
            best  = mid;
            limit = mid;
        }
        else {
            min = mid+1;
        }
485
    }
Yoni Fogel's avatar
Yoni Fogel committed
486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511
    if (best==NODE_NULL) return DB_NOTFOUND;
    if (value!=NULL) *value = omt->i.a.values[best];
    *index = best - omt->i.a.start_idx;
    return 0;
}

static inline int find_internal_minus_array(OMT omt, int (*h)(OMTVALUE, void*extra), void*extra, OMTVALUE *value, u_int32_t *index) {
    u_int32_t min   = omt->i.a.start_idx;
    u_int32_t limit = omt->i.a.start_idx + omt->i.a.num_values;
    u_int32_t best  = NODE_NULL;

    while (min!=limit) {
        u_int32_t mid = (min + limit) / 2;
        int hv = h(omt->i.a.values[mid], extra);
        if (hv<0) {
            best = mid;
            min  = mid+1;
        }
        else {
            limit = mid;
        }
    }
    if (best==NODE_NULL) return DB_NOTFOUND;
    if (value!=NULL) *value = omt->i.a.values[best];
    *index = best - omt->i.a.start_idx;
    return 0;
512 513 514
}

//  If direction <0 then find the largest  i such that h(V_i,extra)<0.
515 516 517
static inline int find_internal_minus(OMT omt, node_idx n_idx, int (*h)(OMTVALUE, void*extra), void*extra, OMTVALUE *value, u_int32_t *index)
// requires: index!=NULL
{
Yoni Fogel's avatar
Yoni Fogel committed
518
    if (n_idx==NODE_NULL) return DB_NOTFOUND;
Yoni Fogel's avatar
Yoni Fogel committed
519
    OMT_NODE n = omt->i.t.nodes+n_idx;
520 521
    int hv = h(n->value, extra);
    if (hv<0) {
522 523
        int r = find_internal_minus(omt, n->right, h, extra, value, index);
        if (r==0) *index += nweight(omt, n->left)+1;
524
        else if (r==DB_NOTFOUND) {
525
            *index = nweight(omt, n->left);
526
            if (value!=NULL) *value = n->value;
527 528 529 530
            r = 0;
        }
        return r;
    } else {
531
        return find_internal_minus(omt, n->left, h, extra, value, index);
532 533 534 535
    }
}

//  If direction >0 then find the smallest i such that h(V_i,extra)>0.
536 537 538
static inline int find_internal_plus(OMT omt, node_idx n_idx, int (*h)(OMTVALUE, void*extra), void*extra, OMTVALUE *value, u_int32_t *index)
// requires: index!=NULL
{
Yoni Fogel's avatar
Yoni Fogel committed
539
    if (n_idx==NODE_NULL) return DB_NOTFOUND;
Yoni Fogel's avatar
Yoni Fogel committed
540
    OMT_NODE n = omt->i.t.nodes+n_idx;
541 542
    int hv = h(n->value, extra);
    if (hv>0) {
543
        int r = find_internal_plus(omt, n->left, h, extra, value, index);
544
        if (r==DB_NOTFOUND) {
545
            *index = nweight(omt, n->left);
546
            if (value!=NULL) *value = n->value;
547 548 549 550
            r = 0;
        }
        return r;
    } else {
551 552
        int r = find_internal_plus(omt, n->right, h, extra, value, index);
        if (r==0) *index += nweight(omt, n->left)+1;
553 554 555 556
        return r;
    }
}

Yoni Fogel's avatar
Yoni Fogel committed
557 558 559 560 561 562 563
//TODO: Put all omt API functions here.
int toku_omt_create (OMT *omtp) {
    return omt_create_internal(omtp, 2);
}

void toku_omt_destroy(OMT *omtp) {
    OMT omt=*omtp;
Yoni Fogel's avatar
Yoni Fogel committed
564 565
    if (omt->is_array) toku_free(omt->i.a.values);
    else               toku_free(omt->i.t.nodes);
Yoni Fogel's avatar
Yoni Fogel committed
566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586
    toku_free(omt);
    *omtp=NULL;
}

u_int32_t toku_omt_size(OMT V) {
    return omt_size(V);
}

int toku_omt_create_from_sorted_array(OMT *omtp, OMTVALUE *values, u_int32_t numvalues) {
    OMT omt = NULL;
    int r;
    if ((r = omt_create_internal(&omt, numvalues))) return r;
    memcpy(omt->i.a.values, values, numvalues*sizeof(*values));
    omt->i.a.num_values = numvalues;
    *omtp=omt;
    return 0;
}

int toku_omt_insert_at(OMT omt, OMTVALUE value, u_int32_t index) {
    int r;
    if (index>omt_size(omt)) return EINVAL;
Yoni Fogel's avatar
Yoni Fogel committed
587
    if ((r=maybe_resize_or_convert(omt, 1+omt_size(omt)))) return r;
Yoni Fogel's avatar
Yoni Fogel committed
588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623
    if (omt->is_array && index!=omt->i.a.num_values &&
        (index!=0 || omt->i.a.start_idx==0)) {
        if ((r=omt_convert_to_tree(omt))) return r;
    }
    if (omt->is_array) {
        if (index==omt->i.a.num_values) {
            omt->i.a.values[omt->i.a.start_idx+(omt->i.a.num_values)] = value;
        }
        else {
            omt->i.a.values[--omt->i.a.start_idx] = value;
        }
        omt->i.a.num_values++;
    }
    else {
        node_idx* rebalance_idx = NULL;
        insert_internal(omt, &omt->i.t.root, value, index, &rebalance_idx);
        if (rebalance_idx) rebalance(omt, rebalance_idx);
    }
    return 0;
}

int toku_omt_set_at (OMT omt, OMTVALUE value, u_int32_t index) {
    if (index>=omt_size(omt)) return EINVAL;
    if (omt->is_array) {
        set_at_internal_array(omt, value, index);
    }
    else {
        set_at_internal(omt, omt->i.t.root, value, index);
    }
    return 0;
}

int toku_omt_delete_at(OMT omt, u_int32_t index) {
    OMTVALUE v;
    int r;
    if (index>=omt_size(omt)) return EINVAL;
624
    if ((r=maybe_resize_or_convert(omt, omt_size(omt)-1))) return r;
Yoni Fogel's avatar
Yoni Fogel committed
625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641
    if (omt->is_array && index!=0 && index!=omt->i.a.num_values-1) {
        if ((r=omt_convert_to_tree(omt))) return r;
    }
    if (omt->is_array) {
        //Testing for 0 does not rule out it being the last entry.
        //Test explicitly for num_values-1
        if (index!=omt->i.a.num_values-1) omt->i.a.start_idx++;
        omt->i.a.num_values--;
    }
    else {
        node_idx* rebalance_idx = NULL;
        delete_internal(omt, &omt->i.t.root, index, &v, &rebalance_idx);
        if (rebalance_idx) rebalance(omt, rebalance_idx);
    }
    return 0;
}

642
int toku_omt_fetch(OMT V, u_int32_t i, OMTVALUE *v) {
Yoni Fogel's avatar
Yoni Fogel committed
643 644 645 646 647 648 649 650 651 652
    if (i>=omt_size(V)) return EINVAL;
    if (V->is_array) {
        fetch_internal_array(V, i, v);
    }
    else {
        fetch_internal(V, V->i.t.root, i, v);
    }
    return 0;
}

653 654 655 656 657 658 659 660 661 662 663 664 665
static int
free_item (OMTVALUE lev, u_int32_t UU(idx), void *vsi) {
    assert(vsi == NULL);
    toku_free(lev);
    return 0;
}


void toku_omt_free_items(OMT omt) {
    int r = toku_omt_iterate(omt, free_item, NULL);
    lazy_assert_zero(r);
}

Yoni Fogel's avatar
Yoni Fogel committed
666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684
int toku_omt_iterate(OMT omt, int (*f)(OMTVALUE, u_int32_t, void*), void*v) {
    if (omt->is_array) {
        return iterate_internal_array(omt, 0, omt_size(omt), f, v);
    }
    return iterate_internal(omt, 0, nweight(omt, omt->i.t.root), omt->i.t.root, 0, f, v);
}

int toku_omt_iterate_on_range(OMT omt, u_int32_t left, u_int32_t right, int (*f)(OMTVALUE, u_int32_t, void*), void*v) {
    if (right>omt_size(omt)) return EINVAL;
    if (omt->is_array) {
        return iterate_internal_array(omt, left, right, f, v);
    }
    return iterate_internal(omt, left, right, omt->i.t.root, 0, f, v);
}

int toku_omt_insert(OMT omt, OMTVALUE value, int(*h)(OMTVALUE, void*v), void *v, u_int32_t *index) {
    int r;
    u_int32_t idx;

685
    r = toku_omt_find_zero(omt, h, v, NULL, &idx);
Yoni Fogel's avatar
Yoni Fogel committed
686 687 688 689 690 691 692 693 694 695 696 697
    if (r==0) {
        if (index) *index = idx;
        return DB_KEYEXIST;
    }
    if (r!=DB_NOTFOUND) return r;

    if ((r = toku_omt_insert_at(omt, value, idx))) return r;
    if (index) *index = idx;

    return 0;
}

698
int toku_omt_find_zero(OMT V, int (*h)(OMTVALUE, void*extra), void*extra, OMTVALUE *value, u_int32_t *index) {
Yoni Fogel's avatar
Yoni Fogel committed
699 700 701 702 703 704 705 706 707 708 709 710
    u_int32_t tmp_index;
    if (index==NULL) index=&tmp_index;
    int r;
    if (V->is_array) {
        r = find_internal_zero_array(V, h, extra, value, index);
    }
    else {
        r = find_internal_zero(V, V->i.t.root, h, extra, value, index);
    }
    return r;
}

711
int toku_omt_find(OMT V, int (*h)(OMTVALUE, void*extra), void*extra, int direction, OMTVALUE *value, u_int32_t *index) {
712 713
    u_int32_t tmp_index;
    int r;
714
    if (index==NULL) index=&tmp_index;
715 716
    if (direction==0) {
	abort();
717
    } else if (direction<0) {
Yoni Fogel's avatar
Yoni Fogel committed
718 719 720 721 722 723
        if (V->is_array) {
            r = find_internal_minus_array(V, h, extra, value, index);
        }
        else {
            r = find_internal_minus(V, V->i.t.root, h, extra, value, index);
        }
724
    } else {
Yoni Fogel's avatar
Yoni Fogel committed
725 726 727 728 729 730
        if (V->is_array) {
            r = find_internal_plus_array(V, h, extra, value, index);
        }
        else {
            r = find_internal_plus( V, V->i.t.root, h, extra, value, index);
        }
731
    }
732
    return r;
733 734 735
}

int toku_omt_split_at(OMT omt, OMT *newomtp, u_int32_t index) {
Yoni Fogel's avatar
Yoni Fogel committed
736 737 738 739 740 741 742 743 744 745 746 747 748 749 750
    int r;
    OMT newomt;
    if (index>omt_size(omt)) return EINVAL;

    if ((r=omt_convert_to_array(omt))) return r;
    u_int32_t newsize = omt_size(omt)-index;
    if ((r=toku_omt_create_from_sorted_array(&newomt,
                                   omt->i.a.values+omt->i.a.start_idx+index,
                                   newsize))) return r;
    omt->i.a.num_values = index;
    if ((r=maybe_resize_array(omt, index))) {
        //Restore size.
        omt->i.a.num_values += newsize;
        toku_omt_destroy(&newomt);
        return r;
Yoni Fogel's avatar
Yoni Fogel committed
751
    }
Yoni Fogel's avatar
Yoni Fogel committed
752 753
    *newomtp = newomt;
    return 0;
754
}
755

756
int toku_omt_merge(OMT leftomt, OMT rightomt, OMT *newomtp) {
Yoni Fogel's avatar
Yoni Fogel committed
757
    int r;
758
    OMT newomt = 0;
Yoni Fogel's avatar
Yoni Fogel committed
759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778
    u_int32_t newsize = omt_size(leftomt)+omt_size(rightomt);
    if ((r = omt_create_internal(&newomt, newsize))) return r;

    if (leftomt->is_array) {
        memcpy(newomt->i.a.values,
               leftomt->i.a.values+leftomt->i.a.start_idx,
               leftomt->i.a.num_values*sizeof(*newomt->i.a.values));
    }
    else {
        fill_array_with_subtree_values(leftomt,  newomt->i.a.values,                   leftomt->i.t.root);
    }
    if (rightomt->is_array) {
        memcpy(newomt->i.a.values+omt_size(leftomt),
               rightomt->i.a.values+rightomt->i.a.start_idx,
               rightomt->i.a.num_values*sizeof(*newomt->i.a.values));
    }
    else {
        fill_array_with_subtree_values(rightomt, newomt->i.a.values+omt_size(leftomt), rightomt->i.t.root);
    }
    newomt->i.a.num_values = newsize;
779 780 781
    toku_omt_destroy(&leftomt);
    toku_omt_destroy(&rightomt);
    *newomtp = newomt;
Yoni Fogel's avatar
Yoni Fogel committed
782
    return 0;
783 784
}

Zardosht Kasheff's avatar
Zardosht Kasheff committed
785 786 787 788 789 790
struct copy_data_extra {
    OMTVALUE *a;
    u_int32_t eltsize;
};

static int copy_data_iter(OMTVALUE v, u_int32_t idx, void *ve) {
791
    struct copy_data_extra *e = cast_to_typeof(e) ve;
Zardosht Kasheff's avatar
Zardosht Kasheff committed
792 793 794 795 796 797 798 799 800 801 802 803 804 805 806
    memcpy(e->a[idx], v, e->eltsize);
    return 0;
}

static int omt_copy_data(OMTVALUE *a, OMT omt, u_int32_t eltsize) {
    struct copy_data_extra extra = { .a = a, .eltsize = eltsize };
    if (omt->is_array) {
        return iterate_internal_array(omt, 0, omt_size(omt), copy_data_iter, &extra);
    }
    return iterate_internal(omt, 0, nweight(omt, omt->i.t.root), omt->i.t.root, 0, copy_data_iter, &extra);
}

int toku_omt_clone(OMT *dest, OMT src, u_int32_t eltsize) {
    u_int32_t size = omt_size(src);
    if (size == 0) {
Leif Walsh's avatar
Leif Walsh committed
807
        toku_omt_create(dest);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
808 809
        return 0;
    }
810
    OMTVALUE *XMALLOC_N(size, a);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
811
    for (u_int32_t i = 0; i < size; ++i) {
812
        a[i] = cast_to_typeof(a[i]) toku_xmalloc(eltsize);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
813 814 815 816 817 818 819 820 821 822 823 824 825 826
    }
    int r = omt_copy_data(a, src, eltsize);
    if (r != 0) { goto err; }
    r = toku_omt_create_steal_sorted_array(dest, &a, size, size);
    if (r != 0) { goto err; }
    return 0;
err:
    toku_free(a);
    return r;
}

int toku_omt_clone_pool(OMT *dest, OMT src, u_int32_t eltsize) {
    u_int32_t size = omt_size(src);
    if (size == 0) {
Leif Walsh's avatar
Leif Walsh committed
827
        toku_omt_create(dest);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
828 829
        return 0;
    }
830 831
    OMTVALUE *XMALLOC_N(size, a);
    unsigned char *XMALLOC_N(eltsize * size, data);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
832 833 834 835 836 837 838 839 840 841 842 843 844 845
    for (u_int32_t i = 0; i < size; ++i) {
        a[i] = &data[eltsize * i];
    }
    int r = omt_copy_data(a, src, eltsize);
    if (r != 0) { goto err; }
    r = toku_omt_create_steal_sorted_array(dest, &a, size, size);
    if (r != 0) { goto err; }
    return 0;
err:
    toku_free(data);
    toku_free(a);
    return r;
}

Leif Walsh's avatar
Leif Walsh committed
846 847 848 849 850 851 852 853 854 855 856
void toku_omt_free_items_pool(OMT omt) {
    if (toku_omt_size(omt) == 0) {
        return;
    }
    OMTVALUE v;
    int r = toku_omt_fetch(omt, 0, &v);
    lazy_assert_zero(r);
    invariant(v != NULL);
    toku_free(v);
}

Zardosht Kasheff's avatar
Zardosht Kasheff committed
857 858 859
int toku_omt_clone_noptr(OMT *dest, OMT src) {
    u_int32_t size = omt_size(src);
    if (size == 0) {
Leif Walsh's avatar
Leif Walsh committed
860
        toku_omt_create(dest);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
861 862
        return 0;
    }
863
    OMTVALUE *XMALLOC_N(size, a);
Zardosht Kasheff's avatar
Zardosht Kasheff committed
864 865 866 867 868 869 870 871 872 873 874 875 876
    if (src->is_array) {
        memcpy(a, src->i.a.values + src->i.a.start_idx, size * (sizeof *src->i.a.values));
    } else {
        fill_array_with_subtree_values(src, a, src->i.t.root);
    }
    int r = toku_omt_create_steal_sorted_array(dest, &a, size, size);
    if (r != 0) { goto err; }
    return 0;
err:
    toku_free(a);
    return r;
}

Yoni Fogel's avatar
Yoni Fogel committed
877
void toku_omt_clear(OMT omt) {
Yoni Fogel's avatar
Yoni Fogel committed
878 879 880 881 882 883 884
    if (omt->is_array) {
        omt->i.a.start_idx  = 0;
        omt->i.a.num_values = 0;
    }
    else {
        omt->i.t.free_idx = 0;
        omt->i.t.root     = NODE_NULL;
Yoni Fogel's avatar
Yoni Fogel committed
885 886 887 888
        int r = omt_convert_to_array(omt);
        assert((!omt->is_array) == (r!=0));
        //If we fail to convert (malloc), then nothing has changed.
        //Continue anyway.
Yoni Fogel's avatar
Yoni Fogel committed
889
    }
Yoni Fogel's avatar
Yoni Fogel committed
890 891
}

892
unsigned long toku_omt_memory_size (OMT omt) {
Yoni Fogel's avatar
Yoni Fogel committed
893
    if (omt->is_array) {
Yoni Fogel's avatar
Yoni Fogel committed
894
        return sizeof(*omt)+omt->capacity*sizeof(omt->i.a.values[0]);
895
    }
Yoni Fogel's avatar
Yoni Fogel committed
896
    return sizeof(*omt)+omt->capacity*sizeof(omt->i.t.nodes[0]);
897
}
898