]> git.apps.os.sepia.ceph.com Git - ceph-ci.git/commit
include/cpp-btree: use the same type when allocate/deallocate
authorKefu Chai <kchai@redhat.com>
Sat, 29 Feb 2020 06:51:28 +0000 (14:51 +0800)
committerKefu Chai <kchai@redhat.com>
Mon, 2 Mar 2020 08:27:30 +0000 (16:27 +0800)
commit6b74b68f660c56060d5904c2d2152af986583a35
tree56ad1c2e927e4f49ae99e919b4f9b9e5157638ab
parentfaadaa3155f61bcd5b9dedeebf1c5261062477d9
include/cpp-btree: use the same type when allocate/deallocate

btree_set<> by default uses `std::allocator<Key>`, and btree_map by
default uses `std::allocator<std::pair<Key, Value>>`.

before this change, btree uses the allocator directly for allocating n
elements where element is `Key` or `std::pair<Key, Value>` respectively,
while "n" is actually supposed to be the number of bytes used by each
node which is being allocated.
but, what we need to allocate is actually a "node_type" for holding
multiple slots, and each slot holds an element. in addition to the
slots, a node also keeps track of metadata for btree itself. in short,
what we allocate now is (in bytes):

  alignof(sizeof(node_type)) * sizeof(element)

but what we should allocate is (in bytes):

  alignof(sizeof(node_type))

in this change:

* always rebind the allocator to the correct aligned type with given
  alignment
* extract the allocator related helpers into a template class

Signed-off-by: Kefu Chai <kchai@redhat.com>
src/include/cpp-btree/btree.h