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 <stdio.h>
19 : : #include <stdlib.h>
20 : : #include <string.h>
21 : : #include <stdint.h>
22 : :
23 : : #include "btree.h"
24 : : #include "btree_fast_str_kv.h"
25 : :
26 : : #include "memleak.h"
27 : :
28 : : typedef uint16_t key_len_t;
29 : :
30 : : /*
31 : : === node->data structure overview ===
32 : :
33 : : [offset of key 1]: sizeof(key_len_t) bytes
34 : : [offset of key 2]: ...
35 : : ...
36 : : [offset of key n]: ...
37 : : [offset of key n+1]: points to the byte offset right after the end of n-th entry
38 : : [key 1][value 1]
39 : : [key 2][value 2]
40 : : ...
41 : : [key n][value n]
42 : :
43 : : Note that the maximum node size is limited to 2^(8*sizeof(key_len_t)) bytes
44 : : */
45 : :
46 : 349852 : static void _get_fast_str_kv(struct bnode *node, idx_t idx, void *key, void *value)
47 : : {
48 : : int ksize, vsize;
49 : : void *key_ptr, *ptr;
50 : : key_len_t *_offset_arr;
51 : : key_len_t keylen, _keylen;
52 : : key_len_t offset;
53 : :
54 : 349852 : _get_kvsize(node->kvsize, ksize, vsize);
55 : 349852 : ksize = sizeof(void *);
56 : :
57 : 349852 : ptr = node->data;
58 : :
59 : : // get offset array
60 : 349852 : _offset_arr = (key_len_t*)ptr;
61 : :
62 : : // get keylen & offset
63 : 349852 : offset = _endian_decode(_offset_arr[idx]);
64 : 349852 : keylen = _endian_decode(_offset_arr[idx+1]) - offset - vsize;
65 : :
66 : : // if KEY already points to previous key, then free it
67 : 349852 : memcpy(&key_ptr, key, ksize);
68 [ + + ]: 349852 : if (key_ptr) {
69 : 238251 : free(key_ptr);
70 : : }
71 : :
72 : : // allocate space for key
73 : 349852 : key_ptr = (void*)malloc(sizeof(key_len_t) + keylen);
74 : :
75 : : // copy key
76 : 349852 : _keylen = _endian_encode(keylen);
77 : 349852 : memcpy(key_ptr, &_keylen, sizeof(key_len_t));
78 : 349852 : memcpy((uint8_t*)key_ptr + sizeof(key_len_t),
79 : 699704 : (uint8_t*)ptr + offset, keylen);
80 : : // copy key pointer
81 : 349852 : memcpy(key, &key_ptr, ksize);
82 : : // copy value
83 [ + + ]: 349852 : if (value) {
84 : 50947 : memcpy(value, (uint8_t*)ptr + offset + keylen, vsize);
85 : : }
86 : 349852 : }
87 : :
88 : 9327 : static void _set_fast_str_kv(struct bnode *node, idx_t idx, void *key, void *value)
89 : : {
90 : : int ksize, vsize, i;
91 : : void *key_ptr, *ptr;
92 : : key_len_t *_offset_arr, offset;
93 : : key_len_t keylen_ins, keylen_idx;
94 : : key_len_t _keylen_ins;
95 : : key_len_t offset_idx, offset_next, next_len;
96 : :
97 : 9327 : _get_kvsize(node->kvsize, ksize, vsize);
98 : 9327 : ksize = sizeof(void *);
99 : :
100 : 9327 : ptr = node->data;
101 : :
102 : : // get offset array
103 : 9327 : _offset_arr = (key_len_t*)ptr;
104 : :
105 : : // copy key info from KEY
106 : 9327 : memcpy(&key_ptr, key, ksize);
107 : 9327 : memcpy(&_keylen_ins, key_ptr, sizeof(key_len_t));
108 : 9327 : keylen_ins = _endian_decode(_keylen_ins);
109 : :
110 : : // get (previous) keylen & offset
111 [ + + ]: 9327 : if (idx < node->nentry) {
112 : : // overwriting the existing entry
113 : 1610 : offset_idx = _endian_decode(_offset_arr[idx]);
114 : 1610 : offset_next = _endian_decode(_offset_arr[idx+1]);
115 : 1610 : keylen_idx = offset_next - offset_idx - vsize;
116 : :
117 [ - + ]: 1610 : if (keylen_ins != keylen_idx) {
118 : : // if key length is not same
119 [ # # ]: 0 : if (idx+1 < node->nentry) {
120 : : // 'idx' is not the last entry
121 : : // shift idx+1 ~ nentry-1 KVs to right
122 : 0 : next_len = _endian_decode(_offset_arr[node->nentry]) - offset_next;
123 : :
124 : : // move
125 : 0 : memmove((uint8_t*)ptr + offset_next + (keylen_ins - keylen_idx),
126 : 0 : (uint8_t*)ptr + offset_next, next_len);
127 : : }
128 : :
129 : : // update offset array
130 [ # # ]: 0 : for (i=idx+1; i<=node->nentry; ++i){
131 : 0 : offset = _endian_decode(_offset_arr[i]);
132 : 0 : offset = offset + keylen_ins - keylen_idx;
133 : 0 : _offset_arr[i] = _endian_encode(offset);
134 : : }
135 : : }
136 : : } else {
137 : : // append at the end (new entry)
138 [ + + ]: 7717 : if (node->nentry > 0) {
139 : : // shift KV pairs to right by sizeof(key_len_t) bytes
140 : : // for making a room in offset array
141 : 7677 : offset = _endian_decode(_offset_arr[0]);
142 : 7677 : next_len = _endian_decode(_offset_arr[node->nentry]) - offset;
143 : 7677 : memmove((uint8_t*)ptr + offset + sizeof(key_len_t),
144 : 15354 : (uint8_t*)ptr + offset, next_len);
145 : :
146 : : // update offset array
147 [ + + ]: 875382 : for (i=0;i<=node->nentry;++i){
148 : 867705 : offset = _endian_decode(_offset_arr[i]);
149 : 867705 : offset = offset + sizeof(key_len_t);
150 : 867705 : _offset_arr[i] = _endian_encode(offset);
151 : : }
152 : 7677 : offset_idx = _endian_decode(_offset_arr[idx]);
153 : : } else {
154 : : // this means that idx == 0, and
155 : : // there are two (idx, idx+1) entries in offset array
156 : 40 : offset_idx = sizeof(key_len_t) * 2;
157 : 40 : _offset_arr[0] = _endian_encode(offset_idx);
158 : : }
159 : 7717 : offset = _endian_decode(_offset_arr[idx]);
160 : 7717 : offset = offset + keylen_ins + vsize;
161 : 7717 : _offset_arr[idx+1] = _endian_encode(offset);
162 : : }
163 : : // copy key into the node
164 : 9327 : memcpy((uint8_t*)ptr + offset_idx, (uint8_t*)key_ptr + sizeof(key_len_t), keylen_ins);
165 : : // copy value
166 : 9327 : memcpy((uint8_t*)ptr + offset_idx + keylen_ins, value, vsize);
167 : 9327 : }
168 : :
169 : 45 : static void _ins_fast_str_kv(struct bnode *node, idx_t idx, void *key, void *value)
170 : : {
171 : : int ksize, vsize, i;
172 : : void *key_ptr, *ptr;
173 : : key_len_t *_offset_arr;
174 : : key_len_t keylen_ins;
175 : : key_len_t _keylen_ins;
176 : : key_len_t offset, offset_begin, offset_idx, offset_next, next_len;
177 : :
178 : 45 : _get_kvsize(node->kvsize, ksize, vsize);
179 : 45 : ksize = sizeof(void *);
180 : :
181 : 45 : ptr = node->data;
182 : :
183 : : // get offset array
184 : 45 : _offset_arr = (key_len_t*)ptr;
185 : :
186 : : // get (previous) keylen & offset
187 : 45 : offset_begin = _endian_decode(_offset_arr[0]);
188 : 45 : offset_idx = _endian_decode(_offset_arr[idx]);
189 : 45 : offset_next = _endian_decode(_offset_arr[idx+1]);
190 : :
191 [ + + ][ + - ]: 45 : if (key && value) {
192 : : // insert
193 : :
194 : : // copy key info from KEY to KEY_PTR
195 : 44 : memcpy(&key_ptr, key, ksize);
196 : 44 : memcpy(&_keylen_ins, key_ptr, sizeof(key_len_t));
197 : 44 : keylen_ins = _endian_decode(_keylen_ins);
198 : :
199 : : // move idx ~ nentry-1 KVs to right by (keylen + vsize + sizeof(key_len_t))
200 : 44 : next_len = _endian_decode(_offset_arr[node->nentry]) - offset_idx;
201 : 44 : memmove((uint8_t*)ptr + offset_idx + keylen_ins + vsize + sizeof(key_len_t),
202 : 88 : (uint8_t*)ptr + offset_idx, next_len);
203 : :
204 : : // move 0 ~ idx to right by sizeof(key_len_t)
205 : 44 : next_len = _endian_decode(_offset_arr[idx]) - offset_begin;
206 : 44 : memmove((uint8_t*)ptr + offset_begin + sizeof(key_len_t),
207 : 88 : (uint8_t*)ptr + offset_begin, next_len);
208 : 44 : offset_idx += sizeof(key_len_t);
209 : :
210 : : // also move offset array
211 : 88 : memmove(_offset_arr + (idx+1), _offset_arr + idx,
212 : 132 : sizeof(key_len_t) * (node->nentry - idx + 1));
213 : :
214 : : // copy key into the node
215 : 44 : memcpy((uint8_t*)ptr + offset_idx, (uint8_t*)key_ptr + sizeof(key_len_t), keylen_ins);
216 : : // copy value
217 : 44 : memcpy((uint8_t*)ptr + offset_idx + keylen_ins, value, vsize);
218 : :
219 : : // update offset array
220 [ + + ]: 251 : for (i=0;i<=node->nentry+1;++i){
221 : 207 : offset = _endian_decode(_offset_arr[i]);
222 [ + + ]: 207 : if (i <= idx) {
223 : 47 : offset = offset + sizeof(key_len_t);
224 : : } else {
225 : 160 : offset = offset + sizeof(key_len_t) + keylen_ins + vsize;
226 : : }
227 : 207 : _offset_arr[i] = _endian_encode(offset);
228 : : }
229 : : }else{
230 : : // we have to move idx+1 ~ nentry KVs to appropriate position
231 : : key_len_t len_left, len_right;
232 : :
233 : : // get the length of the key to be removed
234 : 1 : keylen_ins = offset_next - offset_idx - vsize;
235 : 1 : len_left = _endian_decode(_offset_arr[idx]) - offset_begin;
236 : 1 : len_right = _endian_decode(_offset_arr[node->nentry]) - offset_next;
237 : :
238 : : // shift offset array first
239 : 3 : memmove(_offset_arr + idx, _offset_arr + (idx+1),
240 : 4 : sizeof(key_len_t) * (node->nentry - (idx+1) + 1));
241 : :
242 : : // move 0 ~ idx to left by sizeof(key_len_t)
243 : 1 : memmove((uint8_t*)ptr + offset_begin - sizeof(key_len_t),
244 : 2 : (uint8_t*)ptr + offset_begin, len_left);
245 : :
246 : : // move idx+1 ~ nentry-1
247 : 1 : memmove((uint8_t*)ptr + offset_idx - sizeof(key_len_t),
248 : 2 : (uint8_t*)ptr + offset_next, len_right);
249 : :
250 : : // update offset array
251 [ + + ]: 3 : for (i=0;i<node->nentry;++i){
252 : 2 : offset = _endian_decode(_offset_arr[i]);
253 [ - + ]: 2 : if (i < idx) {
254 : 0 : offset = offset - sizeof(key_len_t);
255 : : } else {
256 : 2 : offset = offset - (sizeof(key_len_t) + keylen_ins + vsize);
257 : : }
258 : 2 : _offset_arr[i] = _endian_encode(offset);
259 : : }
260 : : }
261 : 45 : }
262 : :
263 : 112 : static void _copy_fast_str_kv(struct bnode *node_dst,
264 : : struct bnode *node_src,
265 : : idx_t dst_idx,
266 : : idx_t src_idx,
267 : : idx_t len)
268 : : {
269 : : int i;
270 : : int ksize, vsize;
271 : : void *ptr_src, *ptr_dst, *ptr_swap;
272 : : key_len_t *_src_offset_arr, *_dst_offset_arr;
273 : : key_len_t offset, src_offset, src_len, dst_offset;
274 : :
275 : : // not support when dst_idx != 0
276 [ - + ]: 112 : assert(dst_idx == 0);
277 : :
278 : 112 : _get_kvsize(node_src->kvsize, ksize, vsize);
279 : :
280 : 112 : ptr_src = node_src->data;
281 : 112 : ptr_dst = node_dst->data;
282 : :
283 : : // get offset array
284 : 112 : _src_offset_arr = (key_len_t*)ptr_src;
285 : 112 : _dst_offset_arr = (key_len_t*)ptr_dst;
286 : :
287 : : // calculate offset of src_idx
288 : 112 : src_offset = _endian_decode(_src_offset_arr[src_idx]);
289 : :
290 : : // calculate offset of dst_idx
291 : 112 : dst_offset = 0 + sizeof(key_len_t)*(len+1);
292 : :
293 : : // calculate data length to be copied
294 : 112 : src_len = _endian_decode(_src_offset_arr[src_idx+len]) - src_offset;
295 : :
296 [ + + ]: 112 : if (node_dst == node_src) {
297 : : // to avoid corruption due to memcpy from/to same region
298 : 56 : ptr_swap = ptr_dst;
299 : 56 : ptr_dst = (void *)malloc(dst_offset + src_len);
300 : 56 : _dst_offset_arr = (key_len_t*)ptr_dst;
301 : : }
302 : :
303 : : // copy
304 : 112 : memcpy((uint8_t*)ptr_dst + dst_offset,
305 : 224 : (uint8_t*)ptr_src + src_offset, src_len);
306 : :
307 : : // update offset array
308 [ + + ]: 10169 : for (i=0;i<=len;++i){
309 : 10057 : offset = _endian_decode(_src_offset_arr[src_idx + i]);
310 : 10057 : offset = offset + dst_offset - src_offset;
311 : 10057 : _dst_offset_arr[dst_idx + i] = _endian_encode(offset);
312 : : }
313 : :
314 [ + + ]: 112 : if (node_dst == node_src) {
315 : : // copy to the original node and free
316 : 56 : memcpy(ptr_swap, ptr_dst, dst_offset + src_len);
317 : 56 : free(ptr_dst);
318 : : }
319 : 112 : }
320 : :
321 : 0 : static size_t _get_fast_str_kv_size(struct btree *tree, void *key, void *value)
322 : : {
323 : : void *key_ptr;
324 : : key_len_t keylen, _keylen;
325 : :
326 [ # # ]: 0 : if (key) {
327 : 0 : memcpy(&key_ptr, key, sizeof(void *));
328 : 0 : memcpy(&_keylen, key_ptr, sizeof(key_len_t));
329 : 0 : keylen = _endian_decode(_keylen);
330 : : }
331 : :
332 [ # # ][ # # ]: 0 : return ((key)?(sizeof(key_len_t) + keylen):0) + ((value)?tree->vsize:0);
333 : : }
334 : :
335 : 9460 : static size_t _get_fast_str_data_size(
336 : : struct bnode *node, void *new_minkey, void *key_arr, void *value_arr, size_t len)
337 : : {
338 : : int ksize, vsize, i;
339 : : void *ptr, *key_ptr;
340 : : size_t size;
341 : : key_len_t *_offset_arr;
342 : : key_len_t keylen, _keylen;
343 : :
344 : 9460 : _get_kvsize(node->kvsize, ksize, vsize);
345 : 9460 : ksize = sizeof(void *);
346 : :
347 : 9460 : ptr = node->data;
348 : :
349 [ + + ]: 9460 : if (node->nentry == 0) return 0;
350 : :
351 : : // get offset array
352 : 9428 : _offset_arr = (key_len_t*)ptr;
353 : :
354 : : // get size from the last offset
355 : 9428 : size = _endian_decode(_offset_arr[node->nentry]);
356 : :
357 : : // if new_minkey exists
358 [ - + ]: 9428 : if (new_minkey) {
359 : : // subtract the length of the smallest key-value pair
360 : 0 : size -= _endian_decode(_offset_arr[1]) - _endian_decode(_offset_arr[0]);
361 : : // get the length of 'new_minkey'
362 : 0 : memcpy(&key_ptr, new_minkey, ksize);
363 : 0 : memcpy(&_keylen, key_ptr, sizeof(key_len_t));
364 : 0 : keylen = _endian_decode(_keylen);
365 : 0 : size += keylen + vsize;
366 : : }
367 : :
368 [ + + ][ + - ]: 9428 : if (key_arr && value_arr && len > 0) {
[ + - ]
369 : : // there are KV pairs to be inserted
370 [ + + ]: 18840 : for (i=0;i<len;++i){
371 : 9420 : memcpy(&key_ptr, (uint8_t*)key_arr + ksize*i, ksize);
372 : 9420 : memcpy(&_keylen, key_ptr, sizeof(key_len_t));
373 : 9420 : keylen = _endian_decode(_keylen);
374 : 9420 : size += sizeof(key_len_t) + keylen + vsize;
375 : : }
376 : : }
377 : :
378 : 9460 : return size;
379 : : }
380 : :
381 : 125192 : INLINE void _init_fast_str_kv_var(struct btree *tree, void *key, void *value)
382 : : {
383 [ + - ]: 125192 : if (key) memset(key, 0, sizeof(void *));
384 [ + + ]: 125192 : if (value) memset(value, 0, tree->vsize);
385 : 125192 : }
386 : :
387 : 125192 : static void _free_fast_str_kv_var(struct btree *tree, void *key, void *value)
388 : : {
389 : : void *key_ptr;
390 : :
391 : 125192 : memcpy(&key_ptr, key, sizeof(void *));
392 [ + + ]: 125192 : if (key_ptr) {
393 : 116442 : free(key_ptr);
394 : 116442 : key_ptr = NULL;
395 : 116442 : memcpy(key, &key_ptr, sizeof(void *));
396 : : }
397 : 125192 : }
398 : :
399 : 13794 : static void _set_fast_str_key(struct btree *tree, void *dst, void *src)
400 : : {
401 : : void *key_ptr_old, *key_ptr_new;
402 : : key_len_t keylen_new, _keylen_new, inflen, keylen_alloc;
403 : 13794 : size_t size_key = sizeof(key_len_t);
404 : :
405 : 13794 : memset(&inflen, 0xff, sizeof(inflen));
406 : :
407 : 13794 : memcpy(&key_ptr_new, src, sizeof(void *));
408 : 13794 : memcpy(&_keylen_new, key_ptr_new, size_key);
409 : 13794 : keylen_new = _endian_decode(_keylen_new);
410 : :
411 : : // free previous key (if exist)
412 : 13794 : memcpy(&key_ptr_old, dst, sizeof(void *));
413 [ + + ]: 13794 : if (key_ptr_old) {
414 : 4461 : free(key_ptr_old);
415 : : }
416 : :
417 [ + + ]: 13794 : keylen_alloc = (keylen_new == inflen)?(0):(keylen_new);
418 : 13794 : key_ptr_old = (void*)malloc(size_key + keylen_alloc);
419 : : // copy keylen
420 : 13794 : memcpy(key_ptr_old, key_ptr_new, size_key);
421 [ + + ]: 13794 : if (keylen_alloc) {
422 : 13792 : memcpy((uint8_t*)key_ptr_old + size_key,
423 : 13792 : (uint8_t*)key_ptr_new + size_key, keylen_new);
424 : : }
425 : 13794 : memcpy(dst, &key_ptr_old, sizeof(void *));
426 : 13794 : }
427 : :
428 : 25186 : INLINE void _set_fast_str_value(struct btree *tree, void *dst, void *src)
429 : : {
430 : 25186 : memcpy(dst, src, tree->vsize);
431 : 25186 : }
432 : :
433 : 168 : INLINE void _get_fast_str_nth_idx(struct bnode *node, idx_t num, idx_t den, idx_t *idx)
434 : : {
435 : 168 : size_t rem = node->nentry - (int)(node->nentry / den) * den;
436 : 168 : *idx = (int)(node->nentry / den) * num + ((num < rem)?(num):(rem));
437 : 168 : }
438 : :
439 : 56 : INLINE void _get_fast_str_nth_splitter(struct bnode *prev_node, struct bnode *node, void *key)
440 : : {
441 : : // always return the smallest key of 'node'
442 : 56 : _get_fast_str_kv(node, 0, key, NULL);
443 : 56 : }
444 : :
445 : 32878 : void btree_fast_str_kv_set_key(void *key, void *str, size_t len)
446 : : {
447 : : void *key_ptr;
448 : 32878 : key_len_t keylen = len;
449 : : key_len_t _keylen;
450 : :
451 : 32878 : key_ptr = (void *)malloc(sizeof(key_len_t) + keylen);
452 : 32878 : _keylen = _endian_encode(keylen);
453 : 32878 : memcpy(key_ptr, &_keylen, sizeof(key_len_t));
454 : 32878 : memcpy((uint8_t*)key_ptr + sizeof(key_len_t), str, keylen);
455 : 32878 : memcpy(key, &key_ptr, sizeof(void *));
456 : 32878 : }
457 : :
458 : : // create an infinite key that is larger than any other keys
459 : 2 : void btree_fast_str_kv_set_inf_key(void *key)
460 : : {
461 : : void *key_ptr;
462 : : key_len_t keylen;
463 : : key_len_t _keylen;
464 : :
465 : : // just containing length (0xff..) info
466 : 2 : key_ptr = (void *)malloc(sizeof(key_len_t));
467 : 2 : memset(&keylen, 0xff, sizeof(key_len_t));
468 : 2 : _keylen = _endian_encode(keylen);
469 : 2 : memcpy(key_ptr, &_keylen, sizeof(key_len_t));
470 : 2 : memcpy(key, &key_ptr, sizeof(void *));
471 : 2 : }
472 : :
473 : : // return true if KEY is infinite key
474 : 632902 : int btree_fast_str_kv_is_inf_key(void *key)
475 : : {
476 : : void *key_ptr;
477 : : key_len_t keylen, inflen;
478 : : key_len_t _keylen;
479 : :
480 : 632902 : memset(&inflen, 0xff, sizeof(key_len_t));
481 : 632902 : memcpy(&key_ptr, key, sizeof(void *));
482 [ + + ]: 632902 : if (key_ptr) {
483 : 632866 : memcpy(&_keylen, key_ptr, sizeof(key_len_t));
484 : 632866 : keylen = _endian_decode(_keylen);
485 [ + + ]: 632866 : if (keylen == inflen) {
486 : 6 : return 1;
487 : : }
488 : : }
489 : 632902 : return 0;
490 : : }
491 : :
492 : 632909 : void btree_fast_str_kv_get_key(void *key, void *strbuf, size_t *len)
493 : : {
494 : : void *key_ptr;
495 : : key_len_t keylen, inflen;
496 : : key_len_t _keylen;
497 : :
498 : 632909 : memset(&inflen, 0xff, sizeof(key_len_t));
499 : :
500 : 632909 : memcpy(&key_ptr, key, sizeof(void *));
501 [ + + ]: 632909 : if (key_ptr) {
502 : 632873 : memcpy(&_keylen, key_ptr, sizeof(key_len_t));
503 : 632873 : keylen = _endian_decode(_keylen);
504 [ + - ]: 632873 : if (keylen != inflen) {
505 : 632873 : memcpy(strbuf, (uint8_t*)key_ptr + sizeof(key_len_t), keylen);
506 : : }
507 : 632873 : *len = keylen;
508 : : } else {
509 : 36 : *len = 0;
510 : : }
511 : 632909 : }
512 : :
513 : 37402 : void btree_fast_str_kv_free_key(void *key)
514 : : {
515 : : void *key_ptr;
516 : 37402 : memcpy(&key_ptr, key, sizeof(void *));
517 [ + + ]: 37402 : if (key_ptr) free(key_ptr);
518 : 37402 : key_ptr = NULL;
519 : 37402 : memcpy(key, &key_ptr, sizeof(void *));
520 : 37402 : }
521 : :
522 : 22789 : INLINE bid_t _fast_str_value_to_bid_64(void *value)
523 : : {
524 : 22789 : return *((bid_t *)value);
525 : : }
526 : :
527 : 25 : INLINE void* _fast_str_bid_to_value_64(bid_t *bid)
528 : : {
529 : 25 : return (void *)bid;
530 : : }
531 : :
532 : 286 : int _cmp_fast_str64(void *key1, void *key2, void* aux)
533 : : {
534 : : (void) aux;
535 : : void *key_ptr1, *key_ptr2;
536 : : key_len_t keylen1, keylen2, inflen;
537 : : key_len_t _keylen1, _keylen2;
538 : :
539 : 286 : memcpy(&key_ptr1, key1, sizeof(void *));
540 : 286 : memcpy(&key_ptr2, key2, sizeof(void *));
541 : :
542 [ + + ][ - + ]: 286 : if (key_ptr1 == NULL && key_ptr2 == NULL) {
543 : 0 : return 0;
544 [ + + ]: 286 : } else if (key_ptr1 == NULL) {
545 : 38 : return -1;
546 [ - + ]: 248 : } else if (key_ptr2 == NULL) {
547 : 0 : return 1;
548 : : }
549 : :
550 : 248 : memcpy(&_keylen1, key_ptr1, sizeof(key_len_t));
551 : 248 : memcpy(&_keylen2, key_ptr2, sizeof(key_len_t));
552 : 248 : keylen1 = _endian_decode(_keylen1);
553 : 248 : keylen2 = _endian_decode(_keylen2);
554 : :
555 : 248 : memset(&inflen, 0xff, sizeof(key_len_t));
556 [ - + ]: 248 : if (keylen1 == inflen) {
557 : 0 : return 1;
558 [ - + ]: 248 : } else if (keylen2 == inflen) {
559 : 0 : return -1;
560 : : }
561 : :
562 [ + + ]: 248 : if (keylen1 == keylen2) {
563 : : return memcmp((uint8_t*)key_ptr1 + sizeof(key_len_t),
564 : 126 : (uint8_t*)key_ptr2 + sizeof(key_len_t), keylen1);
565 : : }else{
566 [ + + ]: 122 : key_len_t len = MIN(keylen1, keylen2);
567 : : int cmp = memcmp((uint8_t*)key_ptr1 + sizeof(key_len_t),
568 : 122 : (uint8_t*)key_ptr2 + sizeof(key_len_t), len);
569 [ + + ]: 122 : if (cmp != 0) return cmp;
570 : : else {
571 : 286 : return (int)((int)keylen1 - (int)keylen2);
572 : : }
573 : : }
574 : : }
575 : :
576 : 1141 : struct btree_kv_ops * btree_fast_str_kv_get_kb64_vb64(struct btree_kv_ops *kv_ops)
577 : : {
578 : : struct btree_kv_ops *btree_kv_ops;
579 [ + - ]: 1141 : if (kv_ops) {
580 : 1141 : btree_kv_ops = kv_ops;
581 : : }else{
582 : 0 : btree_kv_ops = (struct btree_kv_ops *)malloc(sizeof(struct btree_kv_ops));
583 : : }
584 : :
585 : 1141 : btree_kv_ops->get_kv = _get_fast_str_kv;
586 : 1141 : btree_kv_ops->set_kv = _set_fast_str_kv;
587 : 1141 : btree_kv_ops->ins_kv = _ins_fast_str_kv;
588 : 1141 : btree_kv_ops->copy_kv = _copy_fast_str_kv;
589 : 1141 : btree_kv_ops->set_key = _set_fast_str_key;
590 : 1141 : btree_kv_ops->set_value = _set_fast_str_value;
591 : 1141 : btree_kv_ops->get_data_size = _get_fast_str_data_size;
592 : 1141 : btree_kv_ops->get_kv_size = _get_fast_str_kv_size;
593 : 1141 : btree_kv_ops->init_kv_var = _init_fast_str_kv_var;
594 : 1141 : btree_kv_ops->free_kv_var = _free_fast_str_kv_var;
595 : :
596 : 1141 : btree_kv_ops->get_nth_idx = _get_fast_str_nth_idx;
597 : 1141 : btree_kv_ops->get_nth_splitter = _get_fast_str_nth_splitter;
598 : :
599 : 1141 : btree_kv_ops->cmp = _cmp_fast_str64;
600 : :
601 : 1141 : btree_kv_ops->bid2value = _fast_str_bid_to_value_64;
602 : 1141 : btree_kv_ops->value2bid = _fast_str_value_to_bid_64;
603 : :
604 : 1141 : return btree_kv_ops;
605 : : }
|
