1/*-
2 * Copyright 1997-1999, 2001 John-Mark Gurney.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 */
26
27#pragma once
28
29#include "btree.h"
30
31// BTREE TYPE FLAGS
32#define BTFLAG_U160 0x00
33#define BTFLAG_ULONG_ULONG 0x01
34#define BTFLAG_U160_ULONG 0x02
35
36struct btree { // 62 Bytes -> 64B
37 struct btreenode *root;
38 bt_cmp_t cmp;
39
40 unsigned long msize;
41 unsigned long nsize; // sizeof underlying nbtr
42 unsigned long dsize;
43
44 unsigned int numkeys; /* --- 8 bytes | */
45 unsigned int numnodes; /* ------------| */
46
47 unsigned short keyofst; /* --- 8 bytes | */ //TODO can be computed
48 unsigned short nodeofst; /* | */ //TODO can be computed
49 unsigned short nbyte; /* | */
50 unsigned short kbyte; /* ------------| */
51
52 unsigned char t;
53 unsigned char nbits;
54 bts_t s; // 9 bytes
55
56 unsigned int dirty_left; // 4 bytes (num evicted before 1st key)
57 unsigned char dirty; // NOTE: bool: if ANY btn in btr is dirty
58} __attribute__ ((packed));
59
60// Aerospike Index local list ... this is to optimize for space for the high selectivity index.
61typedef struct {
62 uint8_t capacity;
63 uint8_t used;
64 uint8_t data[];
65} __attribute__ ((__packed__)) ai_arr;
66
67/*
68 * Note: The "ai_arr" structure is limited to 8 bits for capacity / used.
69 */
70#define AI_ARR_MAX_SIZE 255
71
72// Do not change order it is same as struct B-tree inside Aerospike Index ~~
73// pretty hacky stuff. Inside Aerospike Index code is_btree is checked
74typedef struct {
75 union {
76 ai_arr *arr;
77 bt *nbtr;
78 } u;
79 bool is_btree;
80} __attribute__ ((__packed__)) ai_nbtr;
81
82//NOTE: For Aerospike, not currently using EVICT, save one byte in bt_n
83// This changes a 2049 allocation to 2048 -> which is IMPORTANT
84typedef struct btreenode { // 9 bytes -> 16 bytes
85 unsigned int scion; /* 4 billion max scion */
86 unsigned short n; /* 65 thousand max entries (per bt_n)*/
87 unsigned char leaf;
88 // DIRTY: -1->CLEAN,
89 // 0->TreeDirty but BTN_clean, 1->ucharDR, 2->ushortDR, 3->uintDR
90 char dirty;
91} __attribute__ ((packed)) bt_n;
92
93// BTREE access of KEYs & NODEs via position in bt_n
94void *KEYS(bt *btr, bt_n *x, int i);
95#define NODES(btr, x) ((bt_n **)((char *)x + btr->nodeofst))
96
97#define GET_BTN_SIZE(leaf) \
98 size_t nsize = leaf ? btr->kbyte : btr->nbyte;
99#define GET_BTN_MSIZE(dirty) \
100 size_t msize = (dirty == -1) ? nsize : nsize + sizeof(void *);
101#define GET_BTN_SIZES(leaf, dirty) \
102 GET_BTN_SIZE(leaf) GET_BTN_MSIZE(dirty)
103#define GET_DS(x, nsize) (*((void **)((char *)x + nsize)))
104
105bt_n *findminnode(bt *btr, bt_n *x);
106