xref: /6.0.3/forestdb/src/hbtrie.h (revision 56236603)
1/* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2/*
3 *     Copyright 2010 Couchbase, Inc
4 *
5 *   Licensed under the Apache License, Version 2.0 (the "License");
6 *   you may not use this file except in compliance with the License.
7 *   You may obtain a copy of the License at
8 *
9 *       http://www.apache.org/licenses/LICENSE-2.0
10 *
11 *   Unless required by applicable law or agreed to in writing, software
12 *   distributed under the License is distributed on an "AS IS" BASIS,
13 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 *   See the License for the specific language governing permissions and
15 *   limitations under the License.
16 */
17
18#ifndef _JSAHN_HBTRIE_H
19#define _JSAHN_HBTRIE_H
20
21#include "common.h"
22#include "btree.h"
23#include "list.h"
24
25#ifdef __cplusplus
26extern "C" {
27#endif
28
29#define HBTRIE_MAX_KEYLEN (FDB_MAX_KEYLEN_INTERNAL+16)
30#define HBTRIE_HEADROOM (256)
31
32typedef size_t hbtrie_func_readkey(void *handle, uint64_t offset, void *buf);
33typedef int hbtrie_cmp_func(void *key1, void *key2, void* aux);
34// a function pointer to a routine that returns a function pointer
35typedef hbtrie_cmp_func *hbtrie_cmp_map(void *chunk, void *aux);
36
37typedef enum {
38    /**
39     * HB+trie operation success.
40     */
41    HBTRIE_RESULT_SUCCESS,
42    /**
43     * Meta data in index node is corrupted.
44     */
45    HBTRIE_RESULT_INDEX_CORRUPTED,
46    /**
47     * Meta data format is too old.
48     */
49    HBTRIE_RESULT_INDEX_VERSION_NOT_SUPPORTED,
50    /**
51     * HB+trie operation fails.
52     */
53    HBTRIE_RESULT_FAIL,
54    /**
55     * HB+trie recoverable corruption.
56     */
57    HBTRIE_CORRUPTED_RECOVERING_ERR
58
59} hbtrie_result;
60
61#define HBTRIE_FLAG_COMPACT (0x01)
62struct btree_blk_ops;
63struct btree_kv_ops;
64struct hbtrie {
65    uint8_t chunksize;
66    uint8_t valuelen;
67    uint8_t flag;
68    uint8_t leaf_height_limit;
69    uint32_t btree_nodesize;
70    bid_t root_bid;
71    void *btreeblk_handle;
72    void *doc_handle;
73    void *aux;
74
75    struct btree_blk_ops *btree_blk_ops;
76    struct btree_kv_ops *btree_kv_ops;
77    struct btree_kv_ops *btree_leaf_kv_ops;
78    hbtrie_func_readkey *readkey;
79    hbtrie_cmp_map *map;
80    btree_cmp_args cmp_args;
81    void *last_map_chunk;
82};
83
84struct hbtrie_iterator {
85    struct hbtrie trie;
86    struct list btreeit_list;
87    void *curkey;
88    size_t keylen;
89    uint8_t flags;
90#define HBTRIE_ITERATOR_REV    0x01
91#define HBTRIE_ITERATOR_FAILED 0x02
92#define HBTRIE_ITERATOR_MOVED  0x04
93};
94
95#define HBTRIE_ITR_IS_REV(iterator) \
96    ((iterator)->flags & HBTRIE_ITERATOR_REV)
97#define HBTRIE_ITR_IS_FWD(iterator) \
98    (!((iterator)->flags & HBTRIE_ITERATOR_REV))
99#define HBTRIE_ITR_SET_REV(iterator) \
100    ((iterator)->flags |= HBTRIE_ITERATOR_REV)
101#define HBTRIE_ITR_SET_FWD(iterator) \
102    ((iterator)->flags &= ~HBTRIE_ITERATOR_REV)
103#define HBTRIE_ITR_IS_FAILED(iterator) \
104    ((iterator)->flags & HBTRIE_ITERATOR_FAILED)
105#define HBTRIE_ITR_SET_FAILED(iterator) \
106    ((iterator)->flags |= HBTRIE_ITERATOR_FAILED)
107#define HBTRIE_ITR_CLR_FAILED(iterator) \
108    ((iterator)->flags &= ~HBTRIE_ITERATOR_FAILED)
109#define HBTRIE_ITR_IS_MOVED(iterator) \
110    ((iterator)->flags & HBTRIE_ITERATOR_MOVED)
111#define HBTRIE_ITR_SET_MOVED(iterator) \
112    ((iterator)->flags |= HBTRIE_ITERATOR_MOVED)
113
114int _hbtrie_reform_key(struct hbtrie *trie, void *rawkey, int rawkeylen, void *outkey);
115void hbtrie_get_chunk(struct hbtrie *trie,
116                      void *key,
117                      int keylen,
118                      int chunkno,
119                      void *out);
120
121void hbtrie_init(struct hbtrie *trie,
122                 int chunksize,
123                 int valuelen,
124                 int btree_nodesize,
125                 bid_t root_bid,
126                 void *btreeblk_handle,
127                 struct btree_blk_ops *btree_blk_ops,
128                 void *doc_handle,
129                 hbtrie_func_readkey *readkey);
130void hbtrie_free(struct hbtrie *trie);
131
132void hbtrie_set_flag(struct hbtrie *trie, uint8_t flag);
133void hbtrie_set_leaf_height_limit(struct hbtrie *trie, uint8_t limit);
134void hbtrie_set_leaf_cmp(struct hbtrie *trie, btree_cmp_func *cmp);
135void hbtrie_set_map_function(struct hbtrie *trie,
136                             hbtrie_cmp_map *map_func);
137
138hbtrie_result hbtrie_iterator_init(struct hbtrie *trie,
139                                   struct hbtrie_iterator *it,
140                                   void *initial_key,
141                                   size_t keylen);
142hbtrie_result hbtrie_iterator_free(struct hbtrie_iterator *it);
143hbtrie_result hbtrie_last(struct hbtrie_iterator *it);
144hbtrie_result hbtrie_prev(struct hbtrie_iterator *it,
145                          void *key_buf,
146                          size_t *keylen,
147                          void *value_buf);
148hbtrie_result hbtrie_next(struct hbtrie_iterator *it,
149                          void *key_buf,
150                          size_t *keylen,
151                          void *value_buf);
152hbtrie_result hbtrie_next_partial(struct hbtrie_iterator *it,
153                                  void *key_buf,
154                                  size_t *keylen,
155                                  void *value_buf);
156hbtrie_result hbtrie_next_value_only(struct hbtrie_iterator *it,
157                                 void *value_buf);
158
159hbtrie_result hbtrie_find(struct hbtrie *trie,
160                          void *rawkey,
161                          int rawkeylen,
162                          void *valuebuf);
163hbtrie_result hbtrie_find_offset(struct hbtrie *trie,
164                                 void *rawkey,
165                                 int rawkeylen,
166                                 void *valuebuf);
167hbtrie_result hbtrie_find_partial(struct hbtrie *trie, void *rawkey,
168                                  int rawkeylen, void *valuebuf);
169
170hbtrie_result hbtrie_remove(struct hbtrie *trie, void *rawkey, int rawkeylen);
171hbtrie_result hbtrie_remove_partial(struct hbtrie *trie,
172                                    void *rawkey,
173                                    int rawkeylen);
174hbtrie_result hbtrie_insert(struct hbtrie *trie,
175                            void *rawkey,
176                            int rawkeylen,
177                            void *value,
178                            void *oldvalue_out);
179hbtrie_result hbtrie_insert_partial(struct hbtrie *trie,
180                                    void *rawkey, int rawkeylen,
181                                    void *value, void *oldvalue_out);
182
183#ifdef __cplusplus
184}
185#endif
186
187#endif
188