Began porting source files over from other repository

8 files changed, 519 insertions, 0 deletions

diff --git a/include/util/Cursor.h b/include/util/Cursor.h
new file mode 100644
index 0000000..3f5f20f
--- /dev/null
+++ b/include/util/Cursor.h
@@ -0,0 +1,89 @@
+/*
+ * include/util/Cursor.h
+ *
+ * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> 
+ *                    Dong Xie <dongx@psu.edu>
+ *
+ * All rights reserved. Published under the Modified BSD License.
+ *
+ */
+#pragma once
+
+#include "util/base.h"
+#include "util/record.h"
+#include "io/PagedFile.h"
+
+namespace de {
+struct Cursor {
+    record_t *ptr;
+    const record_t *end;
+    size_t cur_rec_idx;
+    size_t rec_cnt;
+
+    friend bool operator==(const Cursor &a, const Cursor &b) {
+        return a.ptr == b.ptr && a.end == b.end;
+    }
+};
+
+static Cursor g_empty_cursor = {0};
+
+/*
+ * Advance the cursor to the next record. If the cursor is backed by an
+ * iterator, will attempt to advance the iterator once the cursor reaches its
+ * end and reset the cursor to the beginning of the read page.
+ *
+ * If the advance succeeds, ptr will be updated to point to the new record
+ * and true will be returned. If the advance reaches the end, then ptr will
+ * be updated to be equal to end, and false will be returned. Iterators will
+ * not be closed.
+ */
+inline static bool advance_cursor(Cursor *cur, PagedFileIterator *iter = nullptr) {
+    cur->ptr++;
+    cur->cur_rec_idx++;
+
+    if (cur->cur_rec_idx >= cur->rec_cnt) return false;
+
+    if (cur->ptr >= cur->end) {
+        if (iter && iter->next()) {
+            cur->ptr = (record_t*)iter->get_item();
+            cur->end = cur->ptr + (PAGE_SIZE / sizeof(record_t));
+            return true;
+        }
+
+        return false;
+    }
+    return true;
+}
+
+/*
+ *   Process the list of cursors to return the cursor containing the next
+ *   largest element. Does not advance any of the cursors. If current is
+ *   specified, then skip the current head of that cursor during checking. 
+ *   This allows for "peaking" at the next largest element after the current 
+ *   largest is processed.
+ */
+inline static Cursor *get_next(std::vector<Cursor> &cursors, Cursor *current=&g_empty_cursor) {
+    const record_t *min_rec = nullptr;
+    Cursor *result = &g_empty_cursor;
+    for (size_t i=0; i< cursors.size(); i++) {
+        if (cursors[i] == g_empty_cursor) continue;
+
+        const record_t *rec = (&cursors[i] == current) ? cursors[i].ptr + 1 : cursors[i].ptr;
+        if (rec >= cursors[i].end) continue;
+
+        if (min_rec == nullptr) {
+            result = &cursors[i];
+            min_rec = rec;
+            continue;
+        }
+
+        if (*rec < *min_rec) {
+            result = &cursors[i];
+            min_rec = rec;
+        }
+    }
+
+    return result;
+} 
+
+}
diff --git a/include/util/base.h b/include/util/base.h
new file mode 100644
index 0000000..1729687
--- /dev/null
+++ b/include/util/base.h
@@ -0,0 +1,73 @@
+/*
+ * include/util/base.h
+ *
+ * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> 
+ *                    Dong Xie <dongx@psu.edu>
+ *
+ * All rights reserved. Published under the Modified BSD License.
+ *
+ */
+#pragma once
+
+#include <cstdlib>
+#include <cstdint>
+#include <cstddef>
+#include <memory>
+
+namespace de {
+
+// The correct quantity for use in alignment of buffers to be
+// compatible with O_DIRECT
+const size_t SECTOR_SIZE = 512;
+
+// The standard sized block of data (in bytes) for use in IO 
+// operations.
+const size_t PAGE_SIZE = 4096;
+
+// The size of a cacheline, for alignment purposes.
+const size_t CACHELINE_SIZE = 64;
+
+// The largest representable PageNum. A given file cannot
+// have more pages than this.
+const size_t MAX_PAGE_COUNT = UINT32_MAX;
+
+// The largest representable FileId. The file manager cannot
+// manage more files than this.
+const size_t MAX_FILE_COUNT = UINT32_MAX;
+
+// The largest representable FrameId. No buffer can be defined with
+// more frames than this.
+const size_t MAX_FRAME_COUNT = UINT32_MAX;
+
+// The number of bytes of zeroes available in ZEROBUF. Will be
+// a multiple of the parm::PAGE_SIZE.
+constexpr size_t ZEROBUF_SIZE = 8 * PAGE_SIZE;
+
+// A large, preallocated, buffer of zeroes used for pre-allocation
+// of pages in a file.
+alignas(SECTOR_SIZE) const char ZEROBUF[ZEROBUF_SIZE] = {0};
+
+
+// alignment code taken from TacoDB (file: tdb_base.h)
+template<class T>
+constexpr T
+TYPEALIGN(uint64_t ALIGNVAL, T LEN) {
+    return (((uint64_t) (LEN) + ((ALIGNVAL) - 1)) & ~((uint64_t) ((ALIGNVAL) - 1)));
+}
+
+#define SHORTALIGN(LEN)         TYPEALIGN(2, (LEN))
+#define INTALIGN(LEN)           TYPEALIGN(4, (LEN))
+#define LONGALIGN(LEN)          TYPEALIGN(8, (LEN))
+#define DOUBLEALIGN(LEN)        TYPEALIGN(8, (LEN))
+#define MAXALIGN(LEN)           TYPEALIGN(8, (LEN))
+#define CACHELINEALIGN(LEN)     TYPEALIGN(CACHELINE_SIZE, (LEN))
+#define MAXALIGN_OF             8
+
+// Returns a pointer to the idx'th page contained within a multi-page
+// buffer. buffer must be page aligned, and idx must be less than the
+// number of pages within the buffer, or the result is undefined.
+static inline char *get_page(char *buffer, size_t idx) {
+    return buffer + (idx * PAGE_SIZE);
+}
+
+}
diff --git a/include/util/bf_config.h b/include/util/bf_config.h
new file mode 100644
index 0000000..b4d68bc
--- /dev/null
+++ b/include/util/bf_config.h
@@ -0,0 +1,27 @@
+/*
+ * include/util/bf_config.h
+ *
+ * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu> 
+ *                    Dong Xie <dongx@psu.edu>
+ *
+ * All rights reserved. Published under the Modified BSD License.
+ *
+ */
+#pragma once
+
+#include "util/base.h"
+
+namespace de {
+
+static double BF_FPR = .01;
+static size_t BF_HASH_FUNCS = 7;
+
+static void BF_SET_FPR(double fpr) {
+    BF_FPR = fpr;
+}
+
+static void BF_SET_HASHFUNC(size_t func_cnt) {
+    BF_HASH_FUNCS = func_cnt;
+}
+
+}
diff --git a/include/util/hash.h b/include/util/hash.h
new file mode 100644
index 0000000..04871dc
--- /dev/null
+++ b/include/util/hash.h
@@ -0,0 +1,61 @@
+/*
+ * include/util/hash.h
+ *
+ * Copyright (C) 2023 Dong Xie <dongx@psu.edu>
+ *
+ * All rights reserved. Published under the Modified BSD License.
+ *
+ */
+#pragma once
+
+#include <cstdlib>
+#include <cstdint>
+
+namespace de {
+
+// 40343 is a "magic constant" that works well,
+// 38299 is another good value.
+// Both are primes and have a good distribution of bits.
+const uint64_t kHashMagicNum = 40343;
+
+inline uint64_t rotr64(uint64_t x, size_t n) {
+    return (((x) >> n) | ((x) << (64 - n)));
+}
+
+inline uint64_t hash(uint64_t input) {
+    uint64_t local_rand = input;
+    uint64_t local_rand_hash = 8;
+    local_rand_hash = 40343 * local_rand_hash + ((local_rand) & 0xFFFF);
+    local_rand_hash = 40343 * local_rand_hash + ((local_rand >> 16) & 0xFFFF);
+    local_rand_hash = 40343 * local_rand_hash + ((local_rand >> 32) & 0xFFFF);
+    local_rand_hash = 40343 * local_rand_hash + (local_rand >> 48);
+    local_rand_hash = 40343 * local_rand_hash;
+    return rotr64(local_rand_hash, 43);
+}
+
+inline uint64_t hash_bytes(const char* str, size_t len) {
+    uint64_t hashState = len;
+
+    for(size_t idx = 0; idx < len; ++idx) {
+      hashState = kHashMagicNum * hashState + str[idx];
+    }
+
+    // The final scrambling helps with short keys that vary only on the high order bits.
+    // Low order bits are not always well distributed so shift them to the high end, where they'll
+    // form part of the 14-bit tag.
+    return rotr64(kHashMagicNum * hashState, 6);
+}
+
+inline uint64_t hash_bytes_with_salt(const char* str, size_t len, uint16_t salt) {
+    uint64_t hashState = len;
+
+    for(size_t idx = 0; idx < len; ++idx) {
+      hashState = kHashMagicNum * hashState + str[idx];
+    }
+
+    hashState = kHashMagicNum * hashState + salt;
+
+    return rotr64(kHashMagicNum * hashState, 6);
+}
+
+}
diff --git a/include/util/internal_record.h b/include/util/internal_record.h
new file mode 100644
index 0000000..d898b8b
--- /dev/null
+++ b/include/util/internal_record.h
@@ -0,0 +1,96 @@
+/*
+ * include/util/internal_record.h
+ *
+ * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu>
+ *
+ * All rights reserved. Published under the Modified BSD License.
+ *
+ */
+#pragma once
+#pragma once
+
+#include "util/record.h"
+#include "util/types.h"
+
+/*
+ * Utility functions for use in handling internal nodes within an ISAM
+ * tree.
+ */
+
+namespace de {
+
+struct ISAMTreeInternalNodeHeader {
+    PageNum next_sibling; // INVALID_PNUM this is the last node on a level
+    PageNum prev_sibling; // INVALID_PNUM if this is the first node on a level
+    size_t leaf_rec_cnt; // number of records in leaf nodes under this node
+    size_t internal_rec_cnt; // number of internal records in this node
+};
+
+/*
+ * The total (aligned) size of an ISAMTreeInternalNodeHeader object. 
+ */
+static constexpr PageOffset ISAMTreeInternalNodeHeaderSize = MAXALIGN(sizeof(ISAMTreeInternalNodeHeader));
+
+/*
+ * The number of bytes occupied by an ISAM tree internal record, including alignment bytes.
+ */
+static constexpr size_t internal_record_size = sizeof(key_t) + MAXALIGN(sizeof(PageNum));
+
+/*
+ * The maximum number of internal records that can be stored in an internal
+ * node, accounting for alignment and the node header.
+ */
+static constexpr size_t internal_records_per_page = (PAGE_SIZE - ISAMTreeInternalNodeHeaderSize) / internal_record_size;
+
+/*
+ * Format an internal record, starting in the first byte of buffer, with the
+ * specified key and target page number. If either buffer or key refer to
+ * memory regions of insufficient size, the results are undefined.
+ */
+static inline void build_internal_record(char *buffer, const char *key, PageNum target_page) {
+    memcpy(buffer, key, sizeof(key_t));
+    memcpy(buffer + sizeof(key_t), &target_page, sizeof(PageNum));
+}
+
+/*
+ * Return the idx'th internal record within an internal node.
+ * internal_page_buffer must refer to the first byte of a page containing a
+ * full internal node, including the header. The returned value is undefined if
+ * idx is greater than or equal to the number of internal records within the
+ * node.
+ */
+static inline char *get_internal_record(char *internal_page_buffer, size_t idx) {
+    return internal_page_buffer + ISAMTreeInternalNodeHeaderSize + internal_record_size * idx;
+}
+
+/*
+ * Return a pointer to the key contained within an internal record, pointed
+ * to by buffer. Buffer must point to the beginning of a valid internal record,
+ * or the result of this function is undefined.
+ */
+static inline const char *get_internal_key(const char *buffer) {
+    return buffer;
+}
+
+/*
+ * Return the Page Number (value) of an internal record, pointed to by buffer.
+ * Buffer must point to the beginning of a valid internal record, or the result
+ * of this function is undefined.
+ */
+static inline PageNum get_internal_value(const char *buffer) {
+    return *((PageNum *) (buffer + sizeof(key_t)));
+}
+
+/*
+ * Return a pointer to the header of an ISAM Tree internal node, referred to by
+ * buffer. If buffer contains multiple nodes, a specific node can be requested 
+ * using the idx parameter, otherwise the header of the first node will be returned.
+ * Buffer must point to the beginning of a valid ISAM Tree internal node, and idx
+ * must be less than the number of internal nodes within the buffer, or the 
+ * returned value is undefined.
+ */
+static inline ISAMTreeInternalNodeHeader *get_header(char *buffer, size_t idx=0) {
+    return (ISAMTreeInternalNodeHeader *) get_page(buffer, idx);
+}
+
+}
diff --git a/include/util/record.h b/include/util/record.h
new file mode 100644
index 0000000..0ba0f97
--- /dev/null
+++ b/include/util/record.h
@@ -0,0 +1,65 @@
+/*
+ * include/util/record.h
+ *
+ * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu>
+ *                    Dong Xie <dongx@psu.edu>
+ *
+ * All rights reserved. Published under the Modified BSD License.
+ *
+ */
+#pragma once
+
+#include <cstring>
+
+#include "util/base.h"
+
+namespace de {
+
+typedef uint32_t hdr_t;
+typedef uint64_t key_t;
+typedef uint32_t value_t;
+typedef uint64_t weight_t;
+
+struct record_t {
+    key_t key;
+    value_t value;
+    hdr_t header;
+    weight_t weight;
+
+    inline bool match(key_t k, value_t v, bool is_tombstone) const {
+        return (key == k) && (value == v) && ((header & 1) == is_tombstone);
+    }
+
+    inline void set_delete_status() {
+        header |= 2;
+    }
+
+    inline bool get_delete_status() const {
+        return header & 2;
+    }
+
+    inline bool is_tombstone() const {
+        return header & 1;
+    }
+
+    inline int match(const record_t* other) const {
+        return key == other->key && value == other->value;
+    }
+
+    inline bool operator<(const record_t& other) const {
+        return key < other.key || (key == other.key && value < other.value);
+    }
+
+    inline bool lt(const key_t& k, const value_t& v) const {
+        return key < k || (key == k && value < v);
+    }
+};
+
+static_assert(sizeof(record_t) == 24, "Record is not 24 bytes long.");
+
+static bool memtable_record_cmp(const record_t& a, const record_t& b) {
+    return (a.key < b.key) || (a.key == b.key && a.value < b.value)
+        || (a.key == b.key && a.value == b.value && a.header < b.header);
+}
+
+}
diff --git a/include/util/timer.h b/include/util/timer.h
new file mode 100644
index 0000000..a9784a8
--- /dev/null
+++ b/include/util/timer.h
@@ -0,0 +1,37 @@
+/*
+ * include/util/timer.h
+ *
+ * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu>
+ *
+ * All rights reserved. Published under the Modified BSD License.
+ *
+ */
+#pragma once
+
+#include <chrono>
+
+#ifdef ENABLE_TIMER
+#define TIMER_INIT() \
+    auto timer_start = std::chrono::high_resolution_clock::now(); \
+    auto timer_stop = std::chrono::high_resolution_clock::now();
+
+#define TIMER_START() \
+    timer_start = std::chrono::high_resolution_clock::now()
+
+#define TIMER_STOP() \
+    timer_stop = std::chrono::high_resolution_clock::now()
+
+#define TIMER_RESULT() \
+    std::chrono::duration_cast<std::chrono::nanoseconds>(timer_stop - timer_start).count()
+
+#else
+    #define TIMER_INIT() \
+        do {} while(0)
+    #define TIMER_START() \
+        do {} while(0)
+    #define TIMER_STOP() \
+        do {} while(0)
+    #define TIMER_RESULT() \
+        0l
+#endif
+
diff --git a/include/util/types.h b/include/util/types.h
new file mode 100644
index 0000000..63da3fa
--- /dev/null
+++ b/include/util/types.h
@@ -0,0 +1,71 @@
+/*
+ * include/util/types.h
+ *
+ * Copyright (C) 2023 Douglas Rumbaugh <drumbaugh@psu.edu>
+ *
+ * All rights reserved. Published under the Modified BSD License.
+ *
+ * A centralized header file for various datatypes used throughout the
+ * code base. There are a few very specific types, such as header formats,
+ * that are defined within the header files that make direct use of them,
+ * but all generally usable, simple types are defined here.
+ *
+ */
+#pragma once
+
+#include <cstdlib>
+#include <cstdint>
+#include <cstddef>
+#include <string>
+
+#include "util/base.h"
+
+namespace de {
+
+using std::byte;
+
+// Represents a page offset within a specific file (physical or virtual)
+typedef uint32_t PageNum;
+
+// Byte offset within a page. Also used for lengths of records, etc.,
+// within the codebase. size_t isn't necessary, as the maximum offset
+// is only parm::PAGE_SIZE 
+typedef uint16_t PageOffset;
+
+// A unique identifier for a frame within a buffer or cache.
+typedef int32_t FrameId;
+
+// A unique timestamp for use in MVCC concurrency control. Currently stored in
+// record headers, but not used by anything.
+typedef uint32_t Timestamp;
+const Timestamp TIMESTAMP_MIN = 0;
+const Timestamp TIMESTAMP_MAX = UINT32_MAX;
+
+// Invalid values for various IDs. Used throughout the code base to indicate
+// uninitialized values and error conditions.
+const PageNum INVALID_PNUM = 0;
+const FrameId INVALID_Fshid = -1;
+
+// An ID for a given shard within the index. The level_idx is the index
+// in the memory_levels and disk_levels vectors corresponding to the
+// shard, and the shard_idx is the index with the level (always 0 in the
+// case of leveling). Note that the two vectors of levels are treated
+// as a contiguous index space.
+struct ShardID {
+    ssize_t level_idx;
+    ssize_t shard_idx;
+
+    friend bool operator==(const ShardID &shid1, const ShardID &shid2) {
+        return shid1.level_idx == shid2.level_idx && shid1.shard_idx == shid2.shard_idx;
+    }
+};
+
+const ShardID INVALID_SHID = {-1, -1};
+
+struct SampleRange {
+    ShardID run_id;
+    size_t low;
+    size_t high;
+};
+
+}