blob: 399ca659892764b78415b3c1a7bf39ff27eb6935 [file] [log] [blame]
// Copyright 2016 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include <memory>
#include <vector>
#include <lib/fit/function.h>
#include "peridot/bin/ledger/storage/public/object.h"
#include "peridot/bin/ledger/storage/public/page_storage.h"
#include "peridot/bin/ledger/storage/public/types.h"
#include "peridot/lib/convert/convert.h"
namespace storage {
namespace btree {
// A node of the B-Tree holding the commit contents.
class TreeNode {
// Creates a |TreeNode| object for an existing node and calls the given
// |callback| with the returned status and node.
static void FromIdentifier(
PageStorage* page_storage, ObjectIdentifier identifier,
fit::function<void(Status, std::unique_ptr<const TreeNode>)> callback);
// Creates a |TreeNode| object with the given entries and children. |children|
// is a map from the index of the child to the identfiier of the child. It
// only contains non-empty children. It is expected that all child index are
// between |0| and |size(entries)| (included). The |callback| will be called
// with the success or error status and the id of the new node.
static void FromEntries(
PageStorage* page_storage, uint8_t level,
const std::vector<Entry>& entries,
const std::map<size_t, ObjectIdentifier>& children,
fit::function<void(Status, ObjectIdentifier)> callback);
// Creates an empty node, i.e. a TreeNode with no entries and an empty child
// at index 0 and calls the callback with the result.
static void Empty(PageStorage* page_storage,
fit::function<void(Status, ObjectIdentifier)> callback);
// Returns the number of entries stored in this tree node.
int GetKeyCount() const;
// Finds the entry at position |index| and stores it in |entry|. |index| has
// to be in [0, GetKeyCount() - 1].
Status GetEntry(int index, Entry* entry) const;
// Finds the child node at position |index| and calls the |callback| with the
// result. |index| has to be in [0, GetKeyCount()]. If the child at the given
// index is empty |NO_SUCH_CHILD| is returned and the value of |child| is not
// updated.
void GetChild(int index,
fit::function<void(Status, std::unique_ptr<const TreeNode>)>
callback) const;
// Searches for the given |key| in this node. If it is found, |OK| is
// returned and index contains the index of the entry. If not, |NOT_FOUND|
// is returned and index stores the index of the child node where the key
// might be found.
Status FindKeyOrChild(convert::ExtendedStringView key, int* index) const;
const ObjectIdentifier& GetIdentifier() const;
uint8_t level() const { return level_; }
const std::vector<Entry>& entries() const { return entries_; }
const std::map<size_t, ObjectIdentifier>& children_identifiers() const {
return children_;
TreeNode(PageStorage* page_storage, ObjectIdentifier identifier,
uint8_t level, std::vector<Entry> entries,
std::map<size_t, ObjectIdentifier> children);
// Creates a |TreeNode| object for an existing |object| and stores it in the
// given |node|.
static Status FromObject(PageStorage* page_storage,
ObjectIdentifier identifier,
std::unique_ptr<const Object> object,
std::unique_ptr<const TreeNode>* node);
PageStorage* page_storage_;
ObjectIdentifier identifier_;
const uint8_t level_;
const std::vector<Entry> entries_;
const std::map<size_t, ObjectIdentifier> children_;
} // namespace btree
} // namespace storage