Branch data Line data Source code
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 : : #include <stdlib.h>
19 : : #include <string.h>
20 : :
21 : : #include "btree.h"
22 : : #include "btree_kv.h"
23 : : #include "memleak.h"
24 : :
25 : 456693250 : INLINE void _get_kv(struct bnode *node, idx_t idx, void *key, void *value)
26 : : {
27 : : int ksize, vsize;
28 : : void *ptr;
29 : 456693250 : _get_kvsize(node->kvsize, ksize, vsize);
30 : 456693250 : ptr = (uint8_t *)node->data + (idx * (ksize+vsize));
31 : :
32 : 456693250 : memcpy(key, ptr, ksize);
33 [ + + ]: 456693250 : if (value) {
34 : 60929804 : memcpy(value, (uint8_t *)ptr + ksize, vsize);
35 : : }
36 : 456693250 : }
37 : :
38 : 4767290 : INLINE void _set_kv(struct bnode *node, idx_t idx, void *key, void *value)
39 : : {
40 : : int ksize, vsize;
41 : : void *ptr;
42 : 4767290 : _get_kvsize(node->kvsize, ksize, vsize);
43 : 4767290 : ptr = (uint8_t *)node->data + (idx * (ksize+vsize));
44 : :
45 : 4767290 : memcpy(ptr, key, ksize);
46 : 4767290 : memcpy((uint8_t *)ptr + ksize, value, vsize);
47 : 4767290 : }
48 : :
49 : 3860718 : INLINE void _ins_kv(struct bnode *node, idx_t idx, void *key, void *value)
50 : : {
51 : : int ksize, vsize, kvsize;
52 : : void *ptr;
53 : 3860718 : _get_kvsize(node->kvsize, ksize, vsize);
54 : 3860718 : kvsize = ksize + vsize;
55 : 3860718 : ptr = node->data;
56 : :
57 [ + + ][ + - ]: 3860718 : if (key && value) {
58 : : // insert
59 : : memmove(
60 : 3860703 : (uint8_t *)ptr + (idx+1)*kvsize,
61 : : (uint8_t *)ptr + idx*kvsize,
62 : 7721406 : (node->nentry - idx)*kvsize);
63 : 3860703 : memcpy((uint8_t *)ptr + idx*kvsize, key, ksize);
64 : 3860703 : memcpy((uint8_t *)ptr + idx*kvsize + ksize, value, vsize);
65 : : }else{
66 : : // remove
67 : : memmove(
68 : 15 : (uint8_t *)ptr + idx*kvsize,
69 : : (uint8_t *)ptr + (idx+1)*kvsize,
70 : 15 : (node->nentry - (idx+1))*kvsize);
71 : : }
72 : 3860718 : }
73 : :
74 : 108834 : INLINE void _copy_kv(
75 : : struct bnode *node_dst, struct bnode *node_src, idx_t dst_idx, idx_t src_idx, idx_t len)
76 : : {
77 : : int ksize, vsize, kvsize;
78 : : void *ptr_src, *ptr_dst;
79 : :
80 [ + + ]: 108834 : if (node_dst == node_src) {
81 : 108834 : return;
82 : : }
83 : :
84 : 54421 : _get_kvsize(node_src->kvsize, ksize, vsize);
85 : 54421 : kvsize = ksize + vsize;
86 : :
87 : 54421 : ptr_src = node_src->data;
88 : 54421 : ptr_dst = node_dst->data;
89 : :
90 : : memcpy(
91 : 54421 : (uint8_t *)ptr_dst + kvsize * dst_idx,
92 : : (uint8_t *)ptr_src + kvsize * src_idx,
93 : 54421 : kvsize * len);
94 : : }
95 : :
96 : 8596052 : INLINE size_t _get_data_size(
97 : : struct bnode *node, void *new_minkey, void *key_arr, void *value_arr, size_t len)
98 : : {
99 : : int ksize, vsize;
100 : 8596052 : _get_kvsize(node->kvsize, ksize, vsize);
101 [ + + ][ + - ]: 8596052 : return node->nentry * (ksize + vsize) + ((key_arr && value_arr)?((ksize + vsize)*len):0);
102 : : }
103 : :
104 : 8 : INLINE size_t _get_kv_size(struct btree *tree, void *key, void *value)
105 : : {
106 [ + + ][ + + ]: 8 : return (((uint8_t *)key) ? tree->ksize : 0) + (((uint8_t *)value) ? tree->vsize : 0);
107 : : }
108 : :
109 : 132331375 : INLINE void _init_kv_var(struct btree *tree, void *key, void *value)
110 : : {
111 [ + + ]: 132331375 : if (key) memset(key, 0, tree->ksize);
112 [ + + ]: 132331375 : if (value) memset(value, 0, tree->vsize);
113 : 132331375 : }
114 : :
115 : 10668899 : INLINE void _set_key(struct btree *tree, void *dst, void *src)
116 : : {
117 : 10668899 : memcpy(dst, src, tree->ksize);
118 : 10668899 : }
119 : :
120 : 23379571 : INLINE void _set_value(struct btree *tree, void *dst, void *src)
121 : : {
122 : 23379571 : memcpy(dst, src, tree->vsize);
123 : 23379571 : }
124 : :
125 : 163245 : INLINE void _get_nth_idx(struct bnode *node, idx_t num, idx_t den, idx_t *idx)
126 : : {
127 : 163245 : size_t rem = node->nentry - (int)(node->nentry / den) * den;
128 : 163245 : *idx = (node->nentry / den) * num + ((num < rem)?(num):(rem));
129 : 163245 : }
130 : :
131 : 54415 : INLINE void _get_nth_splitter(struct bnode *prev_node, struct bnode *node, void *key)
132 : : {
133 : : int ksize, vsize;
134 : :
135 : 54415 : _get_kvsize(node->kvsize, ksize, vsize);
136 : : // always return the first key of the NODE
137 : 54415 : memcpy(key, node->data, ksize);
138 : 54415 : }
139 : :
140 : 50813147 : INLINE bid_t _value_to_bid_64(void *value)
141 : : {
142 : 50813147 : return *((bid_t *)value);
143 : : }
144 : :
145 : 34444 : INLINE void* _bid_to_value_64(bid_t *bid)
146 : : {
147 : 34444 : return (void *)bid;
148 : : }
149 : :
150 : 5 : INLINE int _cmp_uint32_t(void *key1, void *key2, void *aux)
151 : : {
152 : : (void) aux;
153 : : uint32_t a, b;
154 : 5 : a = deref32(key1);
155 : 5 : b = deref32(key2);
156 : :
157 : : #ifdef __BIT_CMP
158 : 5 : return _CMP_U32(a, b);
159 : : #else
160 : : if (a < b) {
161 : : return -1;
162 : : } else if (a > b) {
163 : : return 1;
164 : : } else {
165 : : return 0;
166 : : }
167 : : #endif
168 : : }
169 : :
170 : 643 : INLINE int _cmp_uint64_t(void *key1, void *key2, void *aux)
171 : : {
172 : : (void) aux;
173 : : uint64_t a,b;
174 : 643 : a = deref64(key1);
175 : 643 : b = deref64(key2);
176 : :
177 : : #ifdef __BIT_CMP
178 : 643 : return _CMP_U64(a, b);
179 : : #else
180 : : if (a < b) {
181 : : return -1;
182 : : } else if (a > b) {
183 : : return 1;
184 : : } else {
185 : : return 0;
186 : : }
187 : : #endif
188 : : }
189 : :
190 : 5 : INLINE int _cmp_binary32(void *key1, void *key2, void *aux)
191 : : {
192 : : (void) aux;
193 : :
194 : : #ifdef __BIT_CMP
195 : : uint32_t a,b;
196 : 5 : a = _endian_encode(deref32(key1));
197 : 5 : b = _endian_encode(deref32(key2));
198 : 5 : return _CMP_U32(a, b);
199 : : #else
200 : : return memcmp(key1, key2, 8);
201 : : #endif
202 : : }
203 : :
204 : 410273863 : INLINE int _cmp_binary64(void *key1, void *key2, void *aux)
205 : : {
206 : : (void) aux;
207 : : #ifdef __BIT_CMP
208 : : uint64_t a,b;
209 : 410273863 : a = _endian_encode(deref64(key1));
210 : 409906816 : b = _endian_encode(deref64(key2));
211 : 410046486 : return _CMP_U64(a, b);
212 : : #else
213 : : return memcmp(key1, key2, 8);
214 : : #endif
215 : : }
216 : :
217 : : // key: uint64_t, value: uint64_t
218 : : static struct btree_kv_ops kv_ops_ku64_vu64 = {
219 : : _get_kv, _set_kv, _ins_kv, _copy_kv, _get_data_size, _get_kv_size, _init_kv_var, NULL,
220 : : _set_key, _set_value, _get_nth_idx, _get_nth_splitter,
221 : : _cmp_uint64_t, _value_to_bid_64, _bid_to_value_64};
222 : :
223 : : static struct btree_kv_ops kv_ops_ku32_vu64 = {
224 : : _get_kv, _set_kv, _ins_kv, _copy_kv, _get_data_size, _get_kv_size, _init_kv_var, NULL,
225 : : _set_key, _set_value, _get_nth_idx, _get_nth_splitter,
226 : : _cmp_uint32_t, _value_to_bid_64, _bid_to_value_64};
227 : :
228 : 7 : struct btree_kv_ops * btree_kv_get_ku64_vu64()
229 : : {
230 : 7 : return &kv_ops_ku64_vu64;
231 : : }
232 : :
233 : 1 : struct btree_kv_ops * btree_kv_get_ku32_vu64()
234 : : {
235 : 1 : return &kv_ops_ku32_vu64;
236 : : }
237 : :
238 : 1151 : struct btree_kv_ops * btree_kv_get_kb64_vb64(struct btree_kv_ops *kv_ops)
239 : : {
240 : : struct btree_kv_ops *btree_kv_ops;
241 [ + + ]: 1151 : if (kv_ops) {
242 : 1147 : btree_kv_ops = kv_ops;
243 : : }else{
244 : 4 : btree_kv_ops = (struct btree_kv_ops *)malloc(sizeof(struct btree_kv_ops));
245 : : }
246 : :
247 : 1151 : btree_kv_ops->get_kv = _get_kv;
248 : 1151 : btree_kv_ops->set_kv = _set_kv;
249 : 1151 : btree_kv_ops->ins_kv = _ins_kv;
250 : 1151 : btree_kv_ops->copy_kv = _copy_kv;
251 : 1151 : btree_kv_ops->set_key = _set_key;
252 : 1151 : btree_kv_ops->set_value = _set_value;
253 : 1151 : btree_kv_ops->get_data_size = _get_data_size;
254 : 1151 : btree_kv_ops->get_kv_size = _get_kv_size;
255 : 1151 : btree_kv_ops->init_kv_var = _init_kv_var;
256 : 1151 : btree_kv_ops->free_kv_var = NULL;
257 : :
258 : 1151 : btree_kv_ops->get_nth_idx = _get_nth_idx;
259 : 1151 : btree_kv_ops->get_nth_splitter = _get_nth_splitter;
260 : :
261 : 1151 : btree_kv_ops->cmp = _cmp_binary64;
262 : :
263 : 1151 : btree_kv_ops->bid2value = _bid_to_value_64;
264 : 1151 : btree_kv_ops->value2bid = _value_to_bid_64;
265 : :
266 : 1151 : return btree_kv_ops;
267 : : }
268 : :
269 : 3 : struct btree_kv_ops * btree_kv_get_kb32_vb64(struct btree_kv_ops *kv_ops)
270 : : {
271 : : struct btree_kv_ops *btree_kv_ops;
272 [ + + ]: 3 : if (kv_ops) {
273 : 1 : btree_kv_ops = kv_ops;
274 : : }else{
275 : 2 : btree_kv_ops = (struct btree_kv_ops *)malloc(sizeof(struct btree_kv_ops));
276 : : }
277 : :
278 : 3 : btree_kv_ops->get_kv = _get_kv;
279 : 3 : btree_kv_ops->set_kv = _set_kv;
280 : 3 : btree_kv_ops->ins_kv = _ins_kv;
281 : 3 : btree_kv_ops->copy_kv = _copy_kv;
282 : 3 : btree_kv_ops->set_key = _set_key;
283 : 3 : btree_kv_ops->set_value = _set_value;
284 : 3 : btree_kv_ops->get_data_size = _get_data_size;
285 : 3 : btree_kv_ops->get_kv_size = _get_kv_size;
286 : 3 : btree_kv_ops->init_kv_var = _init_kv_var;
287 : 3 : btree_kv_ops->free_kv_var = NULL;
288 : :
289 : 3 : btree_kv_ops->get_nth_idx = _get_nth_idx;
290 : 3 : btree_kv_ops->get_nth_splitter = _get_nth_splitter;
291 : :
292 : 3 : btree_kv_ops->cmp = _cmp_binary32;
293 : :
294 : 3 : btree_kv_ops->bid2value = _bid_to_value_64;
295 : 3 : btree_kv_ops->value2bid = _value_to_bid_64;
296 : :
297 : 3 : return btree_kv_ops;
298 : : }
299 : :
300 : :
|
