<commit_before>#ifndef _NDB_BTREE_H_
#define _NDB_BTREE_H_

#include <assert.h>
#include <malloc.h>
#include <pthread.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
#include <vector>
#include <utility>

#include "varkey.h"
#include "counter.h"
#include "macros.h"
#include "prefetch.h"
#include "amd64.h"
#include "rcu.h"
#include "static_assert.h"
#include "util.h"
#include "small_vector.h"

/** options */

//#define LOCK_OWNERSHIP_CHECKING

/**
 * A concurrent, variable key length b+-tree, optimized for read heavy
 * workloads.
 *
 * This b+-tree maps uninterpreted binary strings (key_type) of arbitrary
 * length to a single pointer (value_type). Binary string values are copied
 * into the b+-tree, so the caller does not have to worry about preserving
 * memory for key values.
 *
 * This b+-tree does not manage the memory pointed to by value_type. The
 * pointer is treated completely opaquely.
 *
 * So far, this b+-tree has only been tested on 64-bit intel x86 processors.
 * It's correctness, as it is implemented (not conceptually), requires the
 * semantics of total store order (TSO) for correctness. To fix this, we would
 * change compiler fences into actual memory fences, at the very least.
 */
class btree : public rcu_enabled {
  friend class txn_btree;
public:
  typedef varkey key_type;
  typedef std::string string_type;
  //typedef xbuf string_type;
  typedef uint64_t key_slice;
  typedef uint8_t* value_type;

  // public to assist in testing
  // WARNING: if you want to increase NKeysPerNode beyond 15, must also
  // increase the # of size bits in the header
  static const unsigned int NKeysPerNode = 14;
  static const unsigned int NMinKeysPerNode = NKeysPerNode / 2;

private:

  static const uint64_t HDR_TYPE_MASK = 0x1;

  // 0xf = (1 << ceil(log2(NKeysPerNode))) - 1
  static const uint64_t HDR_KEY_SLOTS_SHIFT = 1;
  static const uint64_t HDR_KEY_SLOTS_MASK = 0xf << HDR_KEY_SLOTS_SHIFT;

  static const uint64_t HDR_LOCKED_SHIFT = 5;
  static const uint64_t HDR_LOCKED_MASK = 0x1 << HDR_LOCKED_SHIFT;

  static const uint64_t HDR_IS_ROOT_SHIFT = 6;
  static const uint64_t HDR_IS_ROOT_MASK = 0x1 << HDR_IS_ROOT_SHIFT;

  static const uint64_t HDR_MODIFYING_SHIFT = 7;
  static const uint64_t HDR_MODIFYING_MASK = 0x1 << HDR_MODIFYING_SHIFT;
<commit_msg>btree: bump keys/node to 15<commit_after>#ifndef _NDB_BTREE_H_
#define _NDB_BTREE_H_

#include <assert.h>
#include <malloc.h>
#include <pthread.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#include <iostream>
#include <string>
#include <vector>
#include <utility>

#include "varkey.h"
#include "counter.h"
#include "macros.h"
#include "prefetch.h"
#include "amd64.h"
#include "rcu.h"
#include "static_assert.h"
#include "util.h"
#include "small_vector.h"

/** options */

//#define LOCK_OWNERSHIP_CHECKING

/**
 * A concurrent, variable key length b+-tree, optimized for read heavy
 * workloads.
 *
 * This b+-tree maps uninterpreted binary strings (key_type) of arbitrary
 * length to a single pointer (value_type). Binary string values are copied
 * into the b+-tree, so the caller does not have to worry about preserving
 * memory for key values.
 *
 * This b+-tree does not manage the memory pointed to by value_type. The
 * pointer is treated completely opaquely.
 *
 * So far, this b+-tree has only been tested on 64-bit intel x86 processors.
 * It's correctness, as it is implemented (not conceptually), requires the
 * semantics of total store order (TSO) for correctness. To fix this, we would
 * change compiler fences into actual memory fences, at the very least.
 */
class btree : public rcu_enabled {
  friend class txn_btree;
public:
  typedef varkey key_type;
  typedef std::string string_type;
  //typedef xbuf string_type;
  typedef uint64_t key_slice;
  typedef uint8_t* value_type;

  // public to assist in testing
  // WARNING: if you want to increase NKeysPerNode beyond 15, must also
  // increase the # of size bits in the header
  static const unsigned int NKeysPerNode = 15;
  static const unsigned int NMinKeysPerNode = NKeysPerNode / 2;

private:

  static const uint64_t HDR_TYPE_MASK = 0x1;

  // 0xf = (1 << ceil(log2(NKeysPerNode))) - 1
  static const uint64_t HDR_KEY_SLOTS_SHIFT = 1;
  static const uint64_t HDR_KEY_SLOTS_MASK = 0xf << HDR_KEY_SLOTS_SHIFT;

  static const uint64_t HDR_LOCKED_SHIFT = 5;
  static const uint64_t HDR_LOCKED_MASK = 0x1 << HDR_LOCKED_SHIFT;

  static const uint64_t HDR_IS_ROOT_SHIFT = 6;
  static const uint64_t HDR_IS_ROOT_MASK = 0x1 << HDR_IS_ROOT_SHIFT;

  static const uint64_t HDR_MODIFYING_SHIFT = 7;
  static const uint64_t HDR_MODIFYING_MASK = 0x1 << HDR_MODIFYING_SHIFT;

{'fraction_non_alphanumeric': 0.08867204072974119, 'fraction_numerical': 0.021213406873143825, 'mean_word_length': 4.394736842105263, 'pattern_counts': {'":': 0, '<': 43, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4747024', 'n_tokens_mistral': 1711, 'n_tokens_neox': 1608, 'n_words': 546}