OILS / vendor / souffle / datastructure / Table.h View on Github | oilshell.org

151 lines, 78 significant
1/*
2 * Souffle - A Datalog Compiler
3 * Copyright (c) 2013, 2015, Oracle and/or its affiliates. All rights reserved
4 * Licensed under the Universal Permissive License v 1.0 as shown at:
5 * - https://opensource.org/licenses/UPL
6 * - <souffle root>/licenses/SOUFFLE-UPL.txt
7 */
8
9/************************************************************************
10 *
11 * @file Table.h
12 *
13 * An implementation of a generic Table storing a position-fixed collection
14 * of objects in main memory.
15 *
16 ***********************************************************************/
17
18#pragma once
19
20#include <iosfwd>
21#include <iterator>
22
23namespace souffle {
24
25template <typename T, unsigned blockSize = 4096>
26class Table {
27 struct Block {
28 Block* next;
29 std::size_t used = 0;
30 T data[blockSize];
31
32 Block() : next(nullptr) {}
33
34 bool isFull() const {
35 return used == blockSize;
36 }
37
38 const T& append(const T& element) {
39 const T& res = data[used];
40 data[used] = element;
41 used++;
42 return res;
43 }
44 };
45
46 Block* head;
47 Block* tail;
48
49 std::size_t count = 0;
50
51public:
52 class iterator {
53 Block* block;
54 unsigned pos;
55
56 public:
57 using iterator_category = std::forward_iterator_tag;
58 using value_type = T;
59 using difference_type = void;
60 using pointer = T*;
61 using reference = T&;
62
63 iterator(Block* block = nullptr, unsigned pos = 0) : block(block), pos(pos) {}
64
65 iterator(const iterator&) = default;
66 iterator(iterator&&) = default;
67 iterator& operator=(const iterator&) = default;
68
69 // the equality operator as required by the iterator concept
70 bool operator==(const iterator& other) const {
71 return (block == nullptr && other.block == nullptr) || (block == other.block && pos == other.pos);
72 }
73
74 // the not-equality operator as required by the iterator concept
75 bool operator!=(const iterator& other) const {
76 return !(*this == other);
77 }
78
79 // the deref operator as required by the iterator concept
80 const T& operator*() const {
81 return block->data[pos];
82 }
83
84 // the increment operator as required by the iterator concept
85 iterator& operator++() {
86 // move on in block
87 if (++pos < block->used) {
88 return *this;
89 }
90 // or to next block
91 block = block->next;
92 pos = 0;
93 return *this;
94 }
95 };
96
97 Table() : head(nullptr), tail(nullptr) {}
98
99 ~Table() {
100 clear();
101 }
102
103 bool empty() const {
104 return (!head);
105 }
106
107 std::size_t size() const {
108 return count;
109 }
110
111 const T& insert(const T& element) {
112 // check whether the head is initialized
113 if (!head) {
114 head = new Block();
115 tail = head;
116 }
117
118 // check whether tail is full
119 if (tail->isFull()) {
120 tail->next = new Block();
121 tail = tail->next;
122 }
123
124 // increment counter
125 count++;
126
127 // add another element
128 return tail->append(element);
129 }
130
131 iterator begin() const {
132 return iterator(head);
133 }
134
135 iterator end() const {
136 return iterator();
137 }
138
139 void clear() {
140 while (head != nullptr) {
141 auto cur = head;
142 head = head->next;
143 delete cur;
144 }
145 count = 0;
146 head = nullptr;
147 tail = nullptr;
148 }
149};
150
151} // end namespace souffle