Thanks for using Compiler Explorer
Sponsors
Jakt
C++
Ada
Analysis
Android Java
Android Kotlin
Assembly
C
C3
Carbon
C++ (Circle)
CIRCT
Clean
CMake
CMakeScript
COBOL
C++ for OpenCL
MLIR
Cppx
Cppx-Blue
Cppx-Gold
Cpp2-cppfront
Crystal
C#
CUDA C++
D
Dart
Elixir
Erlang
Fortran
F#
Go
Haskell
HLSL
Hook
Hylo
ispc
Java
Julia
Kotlin
LLVM IR
LLVM MIR
Modula-2
Nim
Objective-C
Objective-C++
OCaml
OpenCL C
Pascal
Pony
Python
Racket
Ruby
Rust
Snowball
Scala
Solidity
Spice
Swift
LLVM TableGen
Toit
TypeScript Native
V
Vala
Visual Basic
Zig
Javascript
GIMPLE
d source #1
Output
Compile to binary object
Link to binary
Execute the code
Intel asm syntax
Demangle identifiers
Verbose demangling
Filters
Unused labels
Library functions
Directives
Comments
Horizontal whitespace
Debug intrinsics
Compiler
dmd 2.078.3
dmd 2.079.0
dmd 2.079.1
dmd 2.080.1
dmd 2.081.2
dmd 2.082.0
dmd 2.089.0
dmd 2.092.0
dmd 2.094.2
dmd nightly
gdc (trunk)
gdc 10.1
gdc 10.2
gdc 10.5
gdc 11.1
gdc 11.3
gdc 11.4
gdc 12.1
gdc 12.2
gdc 12.3
gdc 13.1
gdc 13.2
gdc 14.1
gdc 9.2
gdc 9.3
gdc 9.5
gdc arm 12.2.0
gdc arm 12.3.0
gdc arm 13.1.0
gdc arm 13.2.0
gdc arm 14.1.0
gdc arm64 12.2.0
gdc arm64 12.3.0
gdc arm64 13.1.0
gdc arm64 13.2.0
gdc arm64 14.1.0
gdc mips 12.1.0
gdc mips 12.2.0
gdc mips 12.3.0
gdc mips 13.1.0
gdc mips 13.2.0
gdc mips 14.1.0
gdc mips64 12.1.0
gdc mips64 12.2.0
gdc mips64 12.3.0
gdc mips64 13.1.0
gdc mips64 13.2.0
gdc mips64 14.1.0
gdc mipsel 12.1.0
gdc mipsel 12.2.0
gdc mipsel 12.3.0
gdc mipsel 13.1.0
gdc mipsel 13.2.0
gdc mipsel 14.1.0
gdc powerpc 12.1.0
gdc powerpc 12.2.0
gdc powerpc 12.3.0
gdc powerpc 13.1.0
gdc powerpc 13.2.0
gdc powerpc 14.1.0
gdc powerpc64 12.1.0
gdc powerpc64 12.2.0
gdc powerpc64 12.3.0
gdc powerpc64 13.1.0
gdc powerpc64 13.2.0
gdc powerpc64 14.1.0
gdc powerpc64 trunk
gdc powerpc64le 12.1.0
gdc powerpc64le 12.2.0
gdc powerpc64le 12.3.0
gdc powerpc64le 13.1.0
gdc powerpc64le 13.2.0
gdc powerpc64le 14.1.0
gdc powerpc64le trunk
gdc riscv32 12.2.0
gdc riscv32 12.3.0
gdc riscv32 13.1.0
gdc riscv32 13.2.0
gdc riscv32 14.1.0
gdc riscv32 trunk
gdc riscv64 12.2.0
gdc riscv64 12.3.0
gdc riscv64 13.1.0
gdc riscv64 13.2.0
gdc riscv64 14.1.0
gdc riscv64 trunk
gdc s390x 12.1.0
gdc s390x 12.2.0
gdc s390x 12.3.0
gdc s390x 13.1.0
gdc s390x 13.2.0
gdc s390x 14.1.0
ldc 0.17.2
ldc 1.0.0
ldc 1.1.0
ldc 1.10.0
ldc 1.11.0
ldc 1.12.0
ldc 1.13.0
ldc 1.14.0
ldc 1.15.0
ldc 1.16.0
ldc 1.17.0
ldc 1.18.0
ldc 1.19.0
ldc 1.2.0
ldc 1.20.0
ldc 1.21.0
ldc 1.22.0
ldc 1.23.0
ldc 1.24.0
ldc 1.25.1
ldc 1.26.0
ldc 1.27.1
ldc 1.28.1
ldc 1.29.0
ldc 1.3.0
ldc 1.30.0
ldc 1.31.0
ldc 1.32.1
ldc 1.33.0
ldc 1.34.0
ldc 1.35.0
ldc 1.36.0
ldc 1.37.0
ldc 1.4.0
ldc 1.5.0
ldc 1.6.0
ldc 1.7.0
ldc 1.8.0
ldc 1.9.0
ldc beta
ldc latest CI
Options
Source code
import std.algorithm; import std.container; import std.conv; import std.file; import std.format; import std.path; import std.range; import std.stdio; import std.typecons; import core.stdc.string; import core.sys.posix.unistd; import core.sys.posix.fcntl; import core.sys.linux.sys.mman; //////////////////////////////////////////// // CONSTANTS //////////////////////////////////////////// enum PAGE_SIZE = 4096; enum BUF_POOL_NUM_PAGES = 1024; //////////////////////////////////////////// // TYPEDEFS //////////////////////////////////////////// alias Page = ubyte[PAGE_SIZE]; // A view of the bytes in a page alias lsn_t = uint64_t; // A log sequence number alias frame_idx_t = size_t; // A frame index alias db_id_t = uint32_t; // A database ID alias table_id_t = uint32_t; // A table ID alias page_num_t = uint32_t; // A page number alias slot_num_t = uint32_t; // A slot number //////////////////////////////////////////// // HELPER FUNCTIONS //////////////////////////////////////////// struct TableLocation { db_id_t db_id; table_id_t table_id; } // Equivalent to "RelFileLocator" in PostgreSQL, where "page_num" is the "block number" struct PageLocation { db_id_t db_id; table_id_t table_id; page_num_t page_num; } struct RecordID { page_num_t page_num; slot_num_t slot_num; } //////////////////////////////////////////// // HEAP PAGE LAYOUT //////////////////////////////////////////// enum HEAP_PAGE_MAX_SLOTS = (PAGE_SIZE - HeapPageHeader.sizeof) / HeapPageSlot.sizeof; struct HeapPageHeader { lsn_t lsn; page_num_t page_id; uint32_t num_slots; uint32_t free_space; uint32_t num_records; } struct HeapPageSlot { uint16_t offset; uint32_t length; } align(PAGE_SIZE) union HeapPage { ubyte[PAGE_SIZE] data; struct { HeapPageHeader header; HeapPageSlot[HEAP_PAGE_MAX_SLOTS] slots; } } static assert(HeapPage.sizeof == PAGE_SIZE); //////////////////////////////////////////// // B+ TREE PAGE LAYOUT //////////////////////////////////////////// union DatabasePage { HeapPage heap_page; } //////////////////////////////////////////// // DISK MANAGER //////////////////////////////////////////// interface IDiskManager { void read_page(PageLocation page_location, DatabasePage* page); void write_page(PageLocation page_location, DatabasePage* page); } class DiskManager { private { // Map of (database ID, table ID) to file descriptor int[TableLocation] fd_map; } private int open_table(TableLocation table_location) { auto db_dir = format("db/%d", table_location.db_id); auto table_file = format("db/%d/%d", table_location.db_id, table_location.table_id); mkdirRecurse(db_dir); auto fd = open(table_file.ptr, O_RDWR | O_CREAT | O_CLOEXEC | O_DIRECT, octal!644); assert(fd != -1); return fd; } void read_page(PageLocation page_location, DatabasePage* page) { auto table_location = TableLocation(page_location.db_id, page_location.table_id); auto page_num = page_location.page_num; if (table_location !in fd_map) { fd_map[table_location] = open_table(table_location); } auto fd = fd_map[table_location]; auto offset = page_num * PAGE_SIZE; auto bytes_read = pread(fd, page, PAGE_SIZE, offset); assert(bytes_read == PAGE_SIZE); } void write_page(PageLocation page_location, DatabasePage* page) { auto table_location = TableLocation(page_location.db_id, page_location.table_id); auto page_num = page_location.page_num; if (table_location !in fd_map) { fd_map[table_location] = open_table(table_location); } auto fd = fd_map[table_location]; auto offset = page_num * PAGE_SIZE; auto bytes_written = pwrite(fd, page, PAGE_SIZE, offset); assert(bytes_written == PAGE_SIZE); } unittest { auto disk_manager = new DiskManager(); auto page_location = PageLocation(0u, 0u, 0u); auto page = DatabasePage.init; disk_manager.read_page(page_location, &page); disk_manager.write_page(page_location, &page); } } //////////////////////////////////////////// // BUFFER POOL //////////////////////////////////////////// interface IBufferPool { Page* fetch_page(PageLocation page_location); void unpin_page(PageLocation page_location, bool is_dirty = false); void flush_page(PageLocation page_location); void flush_all_pages(); } class BufferPool { private { align(PAGE_SIZE) ubyte[PAGE_SIZE * BUF_POOL_NUM_PAGES] data; // Struct-of-Arrays for the buffer pool frames metadata int[BUF_POOL_NUM_PAGES] pin_count; bool[BUF_POOL_NUM_PAGES] is_dirty; bool[BUF_POOL_NUM_PAGES] ref_bit; // Free list frame_idx_t[] free_list; // Lookup tables for page IDs to frame indices frame_idx_t[PageLocation] page_loc_to_frame_idx; PageLocation[frame_idx_t] frame_idx_to_page_id; } this() { mmap(&data, data.sizeof, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0); // Initialize the free list foreach (i; 0 .. BUF_POOL_NUM_PAGES) { free_list ~= i; } } ~this() { munmap(&data, data.sizeof); } invariant { // Pin count is non-negative foreach (i; 0 .. BUF_POOL_NUM_PAGES) { assert(pin_count[i] >= 0); } // Free list is never empty, and never greater than the number of pages assert(free_list.length > 0); assert(free_list.length <= BUF_POOL_NUM_PAGES); // Free list is disjoint from the lookup tables (and vice versa) foreach (frame_idx; 0 .. BUF_POOL_NUM_PAGES) { bool in_free_list = canFind(free_list, frame_idx) != -1; assert(in_free_list == (frame_idx !in frame_idx_to_page_id)); } // Lookup tables are consistent foreach (frame_idx; 0 .. BUF_POOL_NUM_PAGES) { PageLocation page_loc = frame_idx_to_page_id[frame_idx]; assert(page_loc_to_frame_idx[page_loc] == frame_idx); } } Page* get_frame(frame_idx_t frame_idx) in (frame_idx < BUF_POOL_NUM_PAGES) { auto ptr = data.ptr + (frame_idx * PAGE_SIZE); return cast(Page*) ptr; } // Test "get_frame" unittest { BufferPool bp = new BufferPool(); ubyte[PAGE_SIZE]* frame = bp.get_frame(0); // Check that the frame is the right size assert(frame.length == PAGE_SIZE); // Check that the frame is zeroed out assert(frame[0 .. PAGE_SIZE].all!(x => "x == 0")); } frame_idx_t get_free_frame() in (!free_list.empty) { auto frame_idx = free_list.back; free_list.popBack(); return frame_idx; } // Test "get_free_frame" unittest { BufferPool bp = new BufferPool(); frame_idx_t frame_idx = bp.get_free_frame(); assert(frame_idx == 0); } void free_frame(frame_idx_t frame_idx) in (frame_idx < BUF_POOL_NUM_PAGES) { free_list ~= frame_idx; } // Test "free_frame" unittest { BufferPool bp = new BufferPool(); frame_idx_t frame_idx = bp.get_free_frame(); bp.free_frame(frame_idx); assert(bp.free_list.back == frame_idx); } Page* fetch_page(PageLocation page_location) { frame_idx_t frame_idx; if (page_location in page_loc_to_frame_idx) { // Page is already in the buffer pool pin_count[frame_idx]++; return get_frame(frame_idx); } else { // Page is not in the buffer pool frame_idx = get_free_frame(); Page* frame = get_frame(frame_idx); // Read the page from disk // ... // Update the buffer pool frame metadata is_dirty[frame_idx] = false; pin_count[frame_idx] = 1; ref_bit[frame_idx] = false; page_loc_to_frame_idx[page_location] = frame_idx; frame_idx_to_page_id[frame_idx] = page_location; return frame; } } // Test "fetch_page" unittest { BufferPool bp = new BufferPool(); PageLocation page_location = PageLocation(0, 0, 0); Page* frame = bp.fetch_page(page_location); // Check that the frame is the right size assert(frame.length == PAGE_SIZE); // Check that the frame is zeroed out assert(frame[0 .. PAGE_SIZE].all!(x => "x == 0")); // Check that the frame is pinned assert(bp.pin_count[0] == 1); // Check that the frame is not dirty assert(!bp.is_dirty[0]); // Check that the frame is not referenced assert(!bp.ref_bit[0]); // Check that the page ID to frame index lookup table is correct assert(bp.page_loc_to_frame_idx[page_location] == 0); // Check that the frame index to page ID lookup table is correct assert(bp.frame_idx_to_page_id[0] == page_location); } void unpin_page(PageLocation page_location, bool is_dirty = false) in (page_location in page_loc_to_frame_idx) { frame_idx_t frame_idx = page_loc_to_frame_idx[page_location]; pin_count[frame_idx]--; if (is_dirty) { this.is_dirty[frame_idx] = true; } } // Test "unpin_page" unittest { BufferPool bp = new BufferPool(); PageLocation page_location = PageLocation(0, 0, 0); Page* frame = bp.fetch_page(page_location); bp.unpin_page(page_location); // Check that the frame is unpinned assert(bp.pin_count[0] == 0); } void flush_page(PageLocation page_location) in (page_location in page_loc_to_frame_idx) { frame_idx_t frame_idx = page_loc_to_frame_idx[page_location]; Page* frame = get_frame(frame_idx); // Write the page to disk // ... is_dirty[frame_idx] = false; } // Test "flush_page" unittest { BufferPool bp = new BufferPool(); PageLocation page_location = PageLocation(0, 0, 0); Page* frame = bp.fetch_page(page_location); bp.flush_page(page_location); // Check that the frame is not dirty assert(!bp.is_dirty[0]); } void flush_all_pages() { foreach (page_location; page_loc_to_frame_idx.byKey) { flush_page(page_location); } } // Test "flush_all_pages" unittest { BufferPool bp = new BufferPool(); PageLocation page_location = PageLocation(0, 0, 0); Page* frame = bp.fetch_page(page_location); bp.flush_all_pages(); // Check that the frame is not dirty assert(!bp.is_dirty[0]); } } //////////////////////////////////////////// // MAIN //////////////////////////////////////////// void main() { }
Become a Patron
Sponsor on GitHub
Donate via PayPal
Source on GitHub
Mailing list
Installed libraries
Wiki
Report an issue
How it works
Contact the author
CE on Mastodon
About the author
Statistics
Changelog
Version tree