]>
Commit | Line | Data |
---|---|---|
f67539c2 TL |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | ||
4 | #pragma once | |
5 | ||
20effc67 | 6 | #include <algorithm> |
f67539c2 TL |
7 | #include <iostream> |
8 | ||
20effc67 TL |
9 | #include <boost/iterator/counting_iterator.hpp> |
10 | ||
f67539c2 TL |
11 | #include "include/byteorder.h" |
12 | ||
13 | #include "crimson/common/layout.h" | |
14 | ||
15 | namespace crimson::common { | |
16 | ||
17 | template <typename T, bool is_const> | |
18 | struct maybe_const_t { | |
19 | }; | |
20 | template<typename T> | |
21 | struct maybe_const_t<T, true> { | |
22 | using type = const T*; | |
23 | }; | |
24 | template<typename T> | |
25 | struct maybe_const_t<T, false> { | |
26 | using type = T*; | |
27 | }; | |
28 | ||
29 | ||
30 | /** | |
31 | * FixedKVNodeLayout | |
32 | * | |
33 | * Reusable implementation of a fixed size block mapping | |
34 | * K -> V with internal representations KINT and VINT. | |
35 | * | |
36 | * Uses absl::container_internal::Layout for the actual memory layout. | |
37 | * | |
38 | * The primary interface exposed is centered on the iterator | |
39 | * and related methods. | |
40 | * | |
41 | * Also included are helpers for doing splits and merges as for a btree. | |
42 | */ | |
43 | template < | |
44 | size_t CAPACITY, | |
45 | typename Meta, | |
46 | typename MetaInt, | |
47 | typename K, | |
48 | typename KINT, | |
49 | typename V, | |
50 | typename VINT, | |
51 | bool VALIDATE_INVARIANTS=true> | |
52 | class FixedKVNodeLayout { | |
53 | char *buf = nullptr; | |
54 | ||
55 | using L = absl::container_internal::Layout<ceph_le32, MetaInt, KINT, VINT>; | |
56 | static constexpr L layout{1, 1, CAPACITY, CAPACITY}; | |
57 | ||
58 | public: | |
59 | template <bool is_const> | |
60 | struct iter_t { | |
61 | friend class FixedKVNodeLayout; | |
62 | using parent_t = typename maybe_const_t<FixedKVNodeLayout, is_const>::type; | |
63 | ||
64 | parent_t node; | |
20effc67 | 65 | uint16_t offset = 0; |
f67539c2 | 66 | |
20effc67 | 67 | iter_t() = default; |
f67539c2 TL |
68 | iter_t( |
69 | parent_t parent, | |
70 | uint16_t offset) : node(parent), offset(offset) {} | |
71 | ||
20effc67 TL |
72 | iter_t(const iter_t &) noexcept = default; |
73 | iter_t(iter_t &&) noexcept = default; | |
f67539c2 TL |
74 | iter_t &operator=(const iter_t &) = default; |
75 | iter_t &operator=(iter_t &&) = default; | |
76 | ||
77 | operator iter_t<!is_const>() const { | |
78 | static_assert(!is_const); | |
79 | return iter_t<!is_const>(node, offset); | |
80 | } | |
81 | ||
82 | // Work nicely with for loops without requiring a nested type. | |
20effc67 | 83 | using reference = iter_t&; |
f67539c2 TL |
84 | iter_t &operator*() { return *this; } |
85 | iter_t *operator->() { return this; } | |
86 | ||
87 | iter_t operator++(int) { | |
88 | auto ret = *this; | |
89 | ++offset; | |
90 | return ret; | |
91 | } | |
92 | ||
93 | iter_t &operator++() { | |
94 | ++offset; | |
95 | return *this; | |
96 | } | |
97 | ||
20effc67 TL |
98 | iter_t operator--(int) { |
99 | assert(offset > 0); | |
100 | auto ret = *this; | |
101 | --offset; | |
102 | return ret; | |
103 | } | |
104 | ||
105 | iter_t &operator--() { | |
106 | assert(offset > 0); | |
107 | --offset; | |
108 | return *this; | |
109 | } | |
110 | ||
f67539c2 TL |
111 | uint16_t operator-(const iter_t &rhs) const { |
112 | assert(rhs.node == node); | |
113 | return offset - rhs.offset; | |
114 | } | |
115 | ||
116 | iter_t operator+(uint16_t off) const { | |
117 | return iter_t( | |
118 | node, | |
119 | offset + off); | |
120 | } | |
121 | iter_t operator-(uint16_t off) const { | |
122 | return iter_t( | |
123 | node, | |
124 | offset - off); | |
125 | } | |
126 | ||
127 | bool operator==(const iter_t &rhs) const { | |
128 | assert(node == rhs.node); | |
129 | return rhs.offset == offset; | |
130 | } | |
131 | ||
132 | bool operator!=(const iter_t &rhs) const { | |
133 | return !(*this == rhs); | |
134 | } | |
135 | ||
136 | K get_key() const { | |
137 | return K(node->get_key_ptr()[offset]); | |
138 | } | |
139 | ||
140 | K get_next_key_or_max() const { | |
141 | auto next = *this + 1; | |
142 | if (next == node->end()) | |
143 | return std::numeric_limits<K>::max(); | |
144 | else | |
145 | return next->get_key(); | |
146 | } | |
147 | ||
148 | void set_val(V val) const { | |
149 | static_assert(!is_const); | |
150 | node->get_val_ptr()[offset] = VINT(val); | |
151 | } | |
152 | ||
153 | V get_val() const { | |
154 | return V(node->get_val_ptr()[offset]); | |
155 | }; | |
156 | ||
157 | bool contains(K addr) const { | |
158 | return (get_key() <= addr) && (get_next_key_or_max() > addr); | |
159 | } | |
160 | ||
161 | uint16_t get_offset() const { | |
162 | return offset; | |
163 | } | |
164 | ||
165 | private: | |
166 | void set_key(K _lb) const { | |
167 | static_assert(!is_const); | |
168 | KINT lb; | |
169 | lb = _lb; | |
170 | node->get_key_ptr()[offset] = lb; | |
171 | } | |
172 | ||
173 | typename maybe_const_t<char, is_const>::type get_key_ptr() const { | |
174 | return reinterpret_cast< | |
175 | typename maybe_const_t<char, is_const>::type>( | |
176 | node->get_key_ptr() + offset); | |
177 | } | |
178 | ||
179 | typename maybe_const_t<char, is_const>::type get_val_ptr() const { | |
180 | return reinterpret_cast< | |
181 | typename maybe_const_t<char, is_const>::type>( | |
182 | node->get_val_ptr() + offset); | |
183 | } | |
184 | }; | |
185 | using const_iterator = iter_t<true>; | |
186 | using iterator = iter_t<false>; | |
187 | ||
188 | struct delta_t { | |
189 | enum class op_t : uint8_t { | |
190 | INSERT, | |
191 | REMOVE, | |
192 | UPDATE, | |
193 | } op; | |
194 | KINT key; | |
195 | VINT val; | |
196 | ||
197 | void replay(FixedKVNodeLayout &l) { | |
198 | switch (op) { | |
199 | case op_t::INSERT: { | |
200 | l.insert(l.lower_bound(key), key, val); | |
201 | break; | |
202 | } | |
203 | case op_t::REMOVE: { | |
204 | auto iter = l.find(key); | |
205 | assert(iter != l.end()); | |
206 | l.remove(iter); | |
207 | break; | |
208 | } | |
209 | case op_t::UPDATE: { | |
210 | auto iter = l.find(key); | |
211 | assert(iter != l.end()); | |
212 | l.update(iter, val); | |
213 | break; | |
214 | } | |
215 | default: | |
216 | assert(0 == "Impossible"); | |
217 | } | |
218 | } | |
219 | ||
220 | bool operator==(const delta_t &rhs) const { | |
221 | return op == rhs.op && | |
222 | key == rhs.key && | |
223 | val == rhs.val; | |
224 | } | |
225 | }; | |
226 | ||
227 | public: | |
228 | class delta_buffer_t { | |
229 | std::vector<delta_t> buffer; | |
230 | public: | |
231 | bool empty() const { | |
232 | return buffer.empty(); | |
233 | } | |
234 | void insert( | |
235 | const K &key, | |
236 | const V &val) { | |
237 | KINT k; | |
238 | k = key; | |
239 | buffer.push_back( | |
240 | delta_t{ | |
241 | delta_t::op_t::INSERT, | |
242 | k, | |
243 | VINT(val) | |
244 | }); | |
245 | } | |
246 | void update( | |
247 | const K &key, | |
248 | const V &val) { | |
249 | KINT k; | |
250 | k = key; | |
251 | buffer.push_back( | |
252 | delta_t{ | |
253 | delta_t::op_t::UPDATE, | |
254 | k, | |
255 | VINT(val) | |
256 | }); | |
257 | } | |
258 | void remove(const K &key) { | |
259 | KINT k; | |
260 | k = key; | |
261 | buffer.push_back( | |
262 | delta_t{ | |
263 | delta_t::op_t::REMOVE, | |
264 | k, | |
265 | VINT() | |
266 | }); | |
267 | } | |
268 | void replay(FixedKVNodeLayout &node) { | |
269 | for (auto &i: buffer) { | |
270 | i.replay(node); | |
271 | } | |
272 | } | |
273 | size_t get_bytes() const { | |
274 | return buffer.size() * sizeof(delta_t); | |
275 | } | |
276 | void copy_out(char *out, size_t len) { | |
277 | assert(len == get_bytes()); | |
278 | ::memcpy(out, reinterpret_cast<const void *>(buffer.data()), get_bytes()); | |
279 | buffer.clear(); | |
280 | } | |
281 | void copy_in(const char *out, size_t len) { | |
282 | assert(empty()); | |
283 | assert(len % sizeof(delta_t) == 0); | |
284 | buffer = std::vector( | |
285 | reinterpret_cast<const delta_t*>(out), | |
286 | reinterpret_cast<const delta_t*>(out + len)); | |
287 | } | |
288 | bool operator==(const delta_buffer_t &rhs) const { | |
289 | return buffer == rhs.buffer; | |
290 | } | |
291 | }; | |
292 | ||
293 | void journal_insert( | |
294 | const_iterator _iter, | |
295 | const K &key, | |
296 | const V &val, | |
297 | delta_buffer_t *recorder) { | |
298 | auto iter = iterator(this, _iter.offset); | |
299 | if (recorder) { | |
300 | recorder->insert( | |
301 | key, | |
302 | val); | |
303 | } | |
304 | insert(iter, key, val); | |
305 | } | |
306 | ||
307 | void journal_update( | |
308 | const_iterator _iter, | |
309 | const V &val, | |
310 | delta_buffer_t *recorder) { | |
311 | auto iter = iterator(this, _iter.offset); | |
312 | if (recorder) { | |
313 | recorder->update(iter->get_key(), val); | |
314 | } | |
315 | update(iter, val); | |
316 | } | |
317 | ||
318 | void journal_replace( | |
319 | const_iterator _iter, | |
320 | const K &key, | |
321 | const V &val, | |
322 | delta_buffer_t *recorder) { | |
323 | auto iter = iterator(this, _iter.offset); | |
324 | if (recorder) { | |
325 | recorder->remove(iter->get_key()); | |
326 | recorder->insert(key, val); | |
327 | } | |
328 | replace(iter, key, val); | |
329 | } | |
330 | ||
331 | ||
332 | void journal_remove( | |
333 | const_iterator _iter, | |
334 | delta_buffer_t *recorder) { | |
335 | auto iter = iterator(this, _iter.offset); | |
336 | if (recorder) { | |
337 | recorder->remove(iter->get_key()); | |
338 | } | |
339 | remove(iter); | |
340 | } | |
341 | ||
342 | ||
343 | FixedKVNodeLayout(char *buf) : | |
344 | buf(buf) {} | |
345 | ||
346 | virtual ~FixedKVNodeLayout() = default; | |
347 | ||
348 | const_iterator begin() const { | |
349 | return const_iterator( | |
350 | this, | |
351 | 0); | |
352 | } | |
353 | ||
354 | const_iterator end() const { | |
355 | return const_iterator( | |
356 | this, | |
357 | get_size()); | |
358 | } | |
359 | ||
360 | iterator begin() { | |
361 | return iterator( | |
362 | this, | |
363 | 0); | |
364 | } | |
365 | ||
366 | iterator end() { | |
367 | return iterator( | |
368 | this, | |
369 | get_size()); | |
370 | } | |
371 | ||
372 | const_iterator iter_idx(uint16_t off) const { | |
373 | return const_iterator( | |
374 | this, | |
375 | off); | |
376 | } | |
377 | ||
378 | const_iterator find(K l) const { | |
379 | auto ret = begin(); | |
380 | for (; ret != end(); ++ret) { | |
381 | if (ret->get_key() == l) | |
382 | break; | |
383 | } | |
384 | return ret; | |
385 | } | |
386 | iterator find(K l) { | |
387 | const auto &tref = *this; | |
388 | return iterator(this, tref.find(l).offset); | |
389 | } | |
390 | ||
391 | const_iterator lower_bound(K l) const { | |
20effc67 TL |
392 | auto it = std::lower_bound(boost::make_counting_iterator<uint16_t>(0), |
393 | boost::make_counting_iterator<uint16_t>(get_size()), | |
394 | l, | |
395 | [this](uint16_t i, K key) { | |
396 | const_iterator iter(this, i); | |
397 | return iter->get_key() < key; | |
398 | }); | |
399 | return const_iterator(this, *it); | |
f67539c2 | 400 | } |
20effc67 | 401 | |
f67539c2 TL |
402 | iterator lower_bound(K l) { |
403 | const auto &tref = *this; | |
404 | return iterator(this, tref.lower_bound(l).offset); | |
405 | } | |
406 | ||
407 | const_iterator upper_bound(K l) const { | |
20effc67 TL |
408 | auto it = std::upper_bound(boost::make_counting_iterator<uint16_t>(0), |
409 | boost::make_counting_iterator<uint16_t>(get_size()), | |
410 | l, | |
411 | [this](K key, uint16_t i) { | |
412 | const_iterator iter(this, i); | |
413 | return key < iter->get_key(); | |
414 | }); | |
415 | return const_iterator(this, *it); | |
f67539c2 | 416 | } |
20effc67 | 417 | |
f67539c2 TL |
418 | iterator upper_bound(K l) { |
419 | const auto &tref = *this; | |
420 | return iterator(this, tref.upper_bound(l).offset); | |
421 | } | |
422 | ||
423 | const_iterator get_split_pivot() const { | |
424 | return iter_idx(get_size() / 2); | |
425 | } | |
426 | ||
427 | uint16_t get_size() const { | |
428 | return *layout.template Pointer<0>(buf); | |
429 | } | |
430 | ||
431 | /** | |
432 | * set_size | |
433 | * | |
434 | * Set size representation to match size | |
435 | */ | |
436 | void set_size(uint16_t size) { | |
437 | *layout.template Pointer<0>(buf) = size; | |
438 | } | |
439 | ||
440 | /** | |
441 | * get_meta/set_meta | |
442 | * | |
443 | * Enables stashing a templated type within the layout. | |
444 | * Cannot be modified after initial write as it is not represented | |
445 | * in delta_t | |
446 | */ | |
447 | Meta get_meta() const { | |
448 | MetaInt &metaint = *layout.template Pointer<1>(buf); | |
449 | return Meta(metaint); | |
450 | } | |
451 | void set_meta(const Meta &meta) { | |
452 | *layout.template Pointer<1>(buf) = MetaInt(meta); | |
453 | } | |
454 | ||
455 | constexpr static size_t get_capacity() { | |
456 | return CAPACITY; | |
457 | } | |
458 | ||
459 | bool operator==(const FixedKVNodeLayout &rhs) const { | |
460 | if (get_size() != rhs.get_size()) { | |
461 | return false; | |
462 | } | |
463 | ||
464 | auto iter = begin(); | |
465 | auto iter2 = rhs.begin(); | |
466 | while (iter != end()) { | |
467 | if (iter->get_key() != iter2->get_key() || | |
468 | iter->get_val() != iter2->get_val()) { | |
469 | return false; | |
470 | } | |
471 | iter++; | |
472 | iter2++; | |
473 | } | |
474 | return true; | |
475 | } | |
476 | ||
477 | /** | |
478 | * split_into | |
479 | * | |
480 | * Takes *this and splits its contents into left and right. | |
481 | */ | |
482 | K split_into( | |
483 | FixedKVNodeLayout &left, | |
484 | FixedKVNodeLayout &right) const { | |
485 | auto piviter = get_split_pivot(); | |
486 | ||
487 | left.copy_from_foreign(left.begin(), begin(), piviter); | |
488 | left.set_size(piviter - begin()); | |
489 | ||
490 | right.copy_from_foreign(right.begin(), piviter, end()); | |
491 | right.set_size(end() - piviter); | |
492 | ||
493 | auto [lmeta, rmeta] = get_meta().split_into(piviter->get_key()); | |
494 | left.set_meta(lmeta); | |
495 | right.set_meta(rmeta); | |
496 | ||
497 | return piviter->get_key(); | |
498 | } | |
499 | ||
500 | /** | |
501 | * merge_from | |
502 | * | |
503 | * Takes two nodes and copies their contents into *this. | |
504 | * | |
505 | * precondition: left.size() + right.size() < CAPACITY | |
506 | */ | |
507 | void merge_from( | |
508 | const FixedKVNodeLayout &left, | |
509 | const FixedKVNodeLayout &right) | |
510 | { | |
511 | copy_from_foreign( | |
512 | end(), | |
513 | left.begin(), | |
514 | left.end()); | |
515 | set_size(left.get_size()); | |
516 | copy_from_foreign( | |
517 | end(), | |
518 | right.begin(), | |
519 | right.end()); | |
520 | set_size(left.get_size() + right.get_size()); | |
521 | set_meta(Meta::merge_from(left.get_meta(), right.get_meta())); | |
522 | } | |
523 | ||
524 | /** | |
525 | * balance_into_new_nodes | |
526 | * | |
527 | * Takes the contents of left and right and copies them into | |
528 | * replacement_left and replacement_right such that in the | |
529 | * event that the number of elements is odd the extra goes to | |
530 | * the left side iff prefer_left. | |
531 | */ | |
532 | static K balance_into_new_nodes( | |
533 | const FixedKVNodeLayout &left, | |
534 | const FixedKVNodeLayout &right, | |
535 | bool prefer_left, | |
536 | FixedKVNodeLayout &replacement_left, | |
537 | FixedKVNodeLayout &replacement_right) | |
538 | { | |
539 | auto total = left.get_size() + right.get_size(); | |
540 | auto pivot_idx = (left.get_size() + right.get_size()) / 2; | |
541 | if (total % 2 && prefer_left) { | |
542 | pivot_idx++; | |
543 | } | |
544 | auto replacement_pivot = pivot_idx >= left.get_size() ? | |
545 | right.iter_idx(pivot_idx - left.get_size())->get_key() : | |
546 | left.iter_idx(pivot_idx)->get_key(); | |
547 | ||
548 | if (pivot_idx < left.get_size()) { | |
549 | replacement_left.copy_from_foreign( | |
550 | replacement_left.end(), | |
551 | left.begin(), | |
552 | left.iter_idx(pivot_idx)); | |
553 | replacement_left.set_size(pivot_idx); | |
554 | ||
555 | replacement_right.copy_from_foreign( | |
556 | replacement_right.end(), | |
557 | left.iter_idx(pivot_idx), | |
558 | left.end()); | |
559 | ||
560 | replacement_right.set_size(left.get_size() - pivot_idx); | |
561 | replacement_right.copy_from_foreign( | |
562 | replacement_right.end(), | |
563 | right.begin(), | |
564 | right.end()); | |
565 | replacement_right.set_size(total - pivot_idx); | |
566 | } else { | |
567 | replacement_left.copy_from_foreign( | |
568 | replacement_left.end(), | |
569 | left.begin(), | |
570 | left.end()); | |
571 | replacement_left.set_size(left.get_size()); | |
572 | ||
573 | replacement_left.copy_from_foreign( | |
574 | replacement_left.end(), | |
575 | right.begin(), | |
576 | right.iter_idx(pivot_idx - left.get_size())); | |
577 | replacement_left.set_size(pivot_idx); | |
578 | ||
579 | replacement_right.copy_from_foreign( | |
580 | replacement_right.end(), | |
581 | right.iter_idx(pivot_idx - left.get_size()), | |
582 | right.end()); | |
583 | replacement_right.set_size(total - pivot_idx); | |
584 | } | |
585 | ||
586 | auto [lmeta, rmeta] = Meta::rebalance( | |
587 | left.get_meta(), right.get_meta(), replacement_pivot); | |
588 | replacement_left.set_meta(lmeta); | |
589 | replacement_right.set_meta(rmeta); | |
590 | return replacement_pivot; | |
591 | } | |
592 | ||
593 | private: | |
594 | void insert( | |
595 | iterator iter, | |
596 | const K &key, | |
597 | const V &val) { | |
598 | if (VALIDATE_INVARIANTS) { | |
599 | if (iter != begin()) { | |
600 | assert((iter - 1)->get_key() < key); | |
601 | } | |
602 | if (iter != end()) { | |
603 | assert(iter->get_key() > key); | |
604 | } | |
605 | assert(get_size() < CAPACITY); | |
606 | } | |
607 | copy_from_local(iter + 1, iter, end()); | |
608 | iter->set_key(key); | |
609 | iter->set_val(val); | |
610 | set_size(get_size() + 1); | |
611 | } | |
612 | ||
613 | void update( | |
614 | iterator iter, | |
615 | V val) { | |
616 | assert(iter != end()); | |
617 | iter->set_val(val); | |
618 | } | |
619 | ||
620 | void replace( | |
621 | iterator iter, | |
622 | const K &key, | |
623 | const V &val) { | |
624 | assert(iter != end()); | |
625 | if (VALIDATE_INVARIANTS) { | |
626 | if (iter != begin()) { | |
627 | assert((iter - 1)->get_key() < key); | |
628 | } | |
629 | if ((iter + 1) != end()) { | |
630 | assert((iter + 1)->get_key() > key); | |
631 | } | |
632 | } | |
633 | iter->set_key(key); | |
634 | iter->set_val(val); | |
635 | } | |
636 | ||
637 | void remove(iterator iter) { | |
638 | assert(iter != end()); | |
639 | copy_from_local(iter, iter + 1, end()); | |
640 | set_size(get_size() - 1); | |
641 | } | |
642 | ||
643 | /** | |
644 | * get_key_ptr | |
645 | * | |
646 | * Get pointer to start of key array | |
647 | */ | |
648 | KINT *get_key_ptr() { | |
649 | return layout.template Pointer<2>(buf); | |
650 | } | |
651 | const KINT *get_key_ptr() const { | |
652 | return layout.template Pointer<2>(buf); | |
653 | } | |
654 | ||
655 | /** | |
656 | * get_val_ptr | |
657 | * | |
658 | * Get pointer to start of val array | |
659 | */ | |
660 | VINT *get_val_ptr() { | |
661 | return layout.template Pointer<3>(buf); | |
662 | } | |
663 | const VINT *get_val_ptr() const { | |
664 | return layout.template Pointer<3>(buf); | |
665 | } | |
666 | ||
667 | /** | |
668 | * node_resolve/unresolve_vals | |
669 | * | |
670 | * If the representation for values depends in some way on the | |
671 | * node in which they are located, users may implement | |
672 | * resolve/unresolve to enable copy_from_foreign to handle that | |
673 | * transition. | |
674 | */ | |
675 | virtual void node_resolve_vals(iterator from, iterator to) const {} | |
676 | virtual void node_unresolve_vals(iterator from, iterator to) const {} | |
677 | ||
678 | /** | |
679 | * copy_from_foreign | |
680 | * | |
681 | * Copies entries from [from_src, to_src) to tgt. | |
682 | * | |
683 | * tgt and from_src must be from different nodes. | |
684 | * from_src and to_src must be from the same node. | |
685 | */ | |
686 | static void copy_from_foreign( | |
687 | iterator tgt, | |
688 | const_iterator from_src, | |
689 | const_iterator to_src) { | |
690 | assert(tgt->node != from_src->node); | |
691 | assert(to_src->node == from_src->node); | |
692 | memcpy( | |
693 | tgt->get_val_ptr(), from_src->get_val_ptr(), | |
694 | to_src->get_val_ptr() - from_src->get_val_ptr()); | |
695 | memcpy( | |
696 | tgt->get_key_ptr(), from_src->get_key_ptr(), | |
697 | to_src->get_key_ptr() - from_src->get_key_ptr()); | |
698 | from_src->node->node_resolve_vals(tgt, tgt + (to_src - from_src)); | |
699 | tgt->node->node_unresolve_vals(tgt, tgt + (to_src - from_src)); | |
700 | } | |
701 | ||
702 | /** | |
703 | * copy_from_local | |
704 | * | |
705 | * Copies entries from [from_src, to_src) to tgt. | |
706 | * | |
707 | * tgt, from_src, and to_src must be from the same node. | |
708 | */ | |
709 | static void copy_from_local( | |
710 | iterator tgt, | |
711 | iterator from_src, | |
712 | iterator to_src) { | |
713 | assert(tgt->node == from_src->node); | |
714 | assert(to_src->node == from_src->node); | |
715 | memmove( | |
716 | tgt->get_val_ptr(), from_src->get_val_ptr(), | |
717 | to_src->get_val_ptr() - from_src->get_val_ptr()); | |
718 | memmove( | |
719 | tgt->get_key_ptr(), from_src->get_key_ptr(), | |
720 | to_src->get_key_ptr() - from_src->get_key_ptr()); | |
721 | } | |
722 | }; | |
723 | ||
724 | } |