1/*
2 * bt_iteretor.h
3 *
4 * Copyright (C) 2013-2014 Aerospike, Inc.
5 *
6 * Portions may be licensed to Aerospike, Inc. under one or more contributor
7 * license agreements.
8 *
9 * This program is free software: you can redistribute it and/or modify it under
10 * the terms of the GNU Affero General Public License as published by the Free
11 * Software Foundation, either version 3 of the License, or (at your option) any
12 * later version.
13 *
14 * This program is distributed in the hope that it will be useful, but WITHOUT
15 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
16 * FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
17 * details.
18 *
19 * You should have received a copy of the GNU Affero General Public License
20 * along with this program. If not, see http://www.gnu.org/licenses/
21 */
22
23/*
24 * This file implements Aerospike Index B-tree iterators.
25 */
26
27#pragma once
28
29#include "ai_types.h"
30#include "bt.h"
31
32typedef struct btEntry {
33 void *key;
34 void *val;
35 void *stream; // some iterators need the raw stream (INDEX CURSORS)
36 bt_n *x; // some iterators need the position in the bt_n
37 int i; // some iterators need the position in the bt_n
38 bool missed;
39 uint32 dr; // RANGE DELETEs simulate Keys using DR
40} btEntry;
41
42typedef struct bTreeLinkedListNode { // 3ptr(24) 2int(8) -> 32 bytes
43 struct bTreeLinkedListNode *parent;
44 struct btreenode *self;
45 struct bTreeLinkedListNode *child;
46 int ik;
47 int in; //TODO in not needed, ik & logic is enough
48} bt_ll_n;
49
50typedef void iter_single(struct btIterator *iter);
51
52/* using 16 as 8^16 can hold 2.8e14 elements (8 is min members in a btn)*/
53#define MAX_BTREE_DEPTH 16
54typedef struct btIterator { // 60B + 16*bt_ll_n(512) -> dont malloc
55 bt *btr;
56 bt_ll_n *bln;
57 int depth;
58 iter_single *iNode; // function to iterate on node's
59 iter_single *iLeaf; // function to iterate on leaf's
60 bool finished;
61 long high; // HIGH for INT & LONG
62 uint160 highy; // HIGH for U160
63 uchar num_nodes; // \/-slot in nodes[]
64 bt_ll_n nodes[MAX_BTREE_DEPTH];
65} btIterator;
66
67typedef struct btSIter { // btIterator 500+ bytes -> STACK (globals) ALLOCATE
68 btIterator x;
69 bool missed; // CURRENT iteration is miss
70 bool nim; // NEXT iteration is miss
71 bool empty;
72 bool scan;
73 col_type_t ktype;
74 btEntry be;
75 ai_obj key; // static AI_OBJ for be.key
76 char dofree;
77} btSIter;
78
79#define II_FAIL -1
80#define II_OK 0
81#define II_LEAF_EXIT 1
82#define II_ONLY_RIGHT 2
83#define II_MISS 3
84#define II_L_MISS 4
85
86bt_ll_n *get_new_iter_child(btIterator *iter);
87void to_child(btIterator *iter, bt_n* self);
88int init_iterator(bt *btr, bt_data_t simkey, struct btIterator *iter);
89
90btSIter *btGetRangeIter (bt *btr, ai_obj *alow, ai_obj *ahigh, bool asc);
91btSIter *btGetFullRangeIter(bt *btr, bool asc, cswc_t *w);
92btSIter *btGetFullXthIter (bt *btr, ulong x, bool asc, cswc_t *w, long lim);
93btSIter *btSetFullRangeIter(btSIter *iter, bt *btr, bool asc, cswc_t *w);
94btSIter *btSetRangeIter (btSIter *iter, bt *btr, ai_obj *alow, ai_obj *ahigh, bool asc);
95btEntry *btRangeNext (btSIter *iter, bool asc);
96void btReleaseRangeIterator(btSIter *iter);
97bool assignMinKey(bt *btr, ai_obj *key);
98bool assignMaxKey(bt *btr, ai_obj *key);
99