1/*
2 * bt.h
3 *
4 * Copyright (C) 2012-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 * Creation of different btree types and
24 * Public Btree Operations w/ stream abstractions under the covers
25 */
26
27#pragma once
28
29#include "ai_obj.h"
30#include "btreepriv.h"
31
32bt *createIBT (col_type_t ktype, int imatch);
33bt *createNBT (col_type_t ktype);
34
35/* different Btree types */
36#define INDEX_BTREE 0
37#define NODE_BTREE 1
38
39// SPAN OUTS
40// This values are choosen to fit the node size into multiples
41// of cacheline (64 byte)
42#define BTREE_LONG_TYPE_DEGREE 31 // node size becomes 504
43#define BTREE_STRING_TYPE_DEGREE 18 // node size becomes 512
44
45#define NBT_DG(btr) \
46 (btr->s.btype == NODE_BTREE && C_IS_DG(btr->s.ktype))
47
48#define NBT(btr) (NBT_DG(btr))
49
50typedef struct ulong_ulong_key {
51 ulong key;
52 ulong val;
53} __attribute__ ((packed)) llk;
54#define LL(btr) (btr->s.bflag & BTFLAG_ULONG_ULONG)
55#define LL_SIZE 16
56typedef struct u160_ulong_key {
57 uint160 key;
58 ulong val;
59} __attribute__ ((packed)) ylk;
60#define YL(btr) (btr->s.bflag & BTFLAG_U160_ULONG)
61#define YL_SIZE 28
62
63typedef struct btk_t {
64 llk LL;
65 ylk YL;
66} btk_t;
67
68#define DECLARE_BT_KEY(akey, ret) \
69 bool med; uint32 ksize; btk_t btk; \
70 char *btkey = createBTKey(akey, &med, &ksize, btr, &btk);/*FREE ME 026*/ \
71 if (!btkey) return ret;
72
73typedef struct crs_t {
74 llk LL_StreamPtr;
75 ylk YL_StreamPtr;
76} crs_t;
77
78#define OTHER_BT(btr) (btr->s.bflag >= BTFLAG_ULONG_ULONG)
79#define NONE_BT(btr) (btr->s.bflag == BTFLAG_U160)
80#define BIG_BT(btr) (btr->s.ksize > 8)
81
82#define IS_GHOST(btr, rrow) (NONE_BT(btr) && rrow && !(*(uchar *)rrow))
83
84void btIndAdd (bt *ibtr, ai_obj *ikey, bt *nbtr);
85bt *btIndFind (bt *ibtr, ai_obj *ikey);
86int btIndDelete(bt *ibtr, ai_obj *ikey);
87
88bool btIndNodeAdd (bt *nbtr, ai_obj *apk);
89bool btIndNodeExist (bt *nbtr, ai_obj *apk);
90int btIndNodeDelete (bt *nbtr, ai_obj *apk, ai_obj *ocol);
91