Mercurial > repos > rliterman > csp2

annotate CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/include/kj/table.h @ 69:33d812a61356

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
planemo upload commit 2e9511a184a1ca667c7be0c6321a36dc4e3d116d
author jpayne
date Tue, 18 Mar 2025 17:55:14 -0400
parents
children
rev   line source
jpayne@69 1 // Copyright (c) 2018 Kenton Varda and contributors
jpayne@69 2 // Licensed under the MIT License:
jpayne@69 3 //
jpayne@69 4 // Permission is hereby granted, free of charge, to any person obtaining a copy
jpayne@69 5 // of this software and associated documentation files (the "Software"), to deal
jpayne@69 6 // in the Software without restriction, including without limitation the rights
jpayne@69 7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
jpayne@69 8 // copies of the Software, and to permit persons to whom the Software is
jpayne@69 9 // furnished to do so, subject to the following conditions:
jpayne@69 10 //
jpayne@69 11 // The above copyright notice and this permission notice shall be included in
jpayne@69 12 // all copies or substantial portions of the Software.
jpayne@69 13 //
jpayne@69 14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
jpayne@69 15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
jpayne@69 16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
jpayne@69 17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
jpayne@69 18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
jpayne@69 19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
jpayne@69 20 // THE SOFTWARE.
jpayne@69 21
jpayne@69 22 #pragma once
jpayne@69 23
jpayne@69 24 #include "common.h"
jpayne@69 25 #include "tuple.h"
jpayne@69 26 #include "vector.h"
jpayne@69 27 #include "function.h"
jpayne@69 28
jpayne@69 29 #if _MSC_VER
jpayne@69 30 // Need _ReadWriteBarrier
jpayne@69 31 #if _MSC_VER < 1910
jpayne@69 32 #include <intrin.h>
jpayne@69 33 #else
jpayne@69 34 #include <intrin0.h>
jpayne@69 35 #endif
jpayne@69 36 #endif
jpayne@69 37
jpayne@69 38 #if KJ_DEBUG_TABLE_IMPL
jpayne@69 39 #include "debug.h"
jpayne@69 40 #define KJ_TABLE_IREQUIRE KJ_REQUIRE
jpayne@69 41 #define KJ_TABLE_IASSERT KJ_ASSERT
jpayne@69 42 #else
jpayne@69 43 #define KJ_TABLE_IREQUIRE KJ_IREQUIRE
jpayne@69 44 #define KJ_TABLE_IASSERT KJ_IASSERT
jpayne@69 45 #endif
jpayne@69 46
jpayne@69 47 KJ_BEGIN_HEADER
jpayne@69 48
jpayne@69 49 namespace kj {
jpayne@69 50
jpayne@69 51 class String;
jpayne@69 52
jpayne@69 53 namespace _ { // private
jpayne@69 54
jpayne@69 55 template <typename Row>
jpayne@69 56 class TableMapping;
jpayne@69 57 template <typename Row, typename Inner>
jpayne@69 58 using TableIterable = MappedIterable<Inner, TableMapping<Row>>;
jpayne@69 59 template <typename Row, typename Inner>
jpayne@69 60 using TableIterator = MappedIterator<Inner, TableMapping<Row>>;
jpayne@69 61
jpayne@69 62 } // namespace _ (private)
jpayne@69 63
jpayne@69 64 template <typename Row, typename... Indexes>
jpayne@69 65 class Table {
jpayne@69 66 // A table with one or more indexes. This is the KJ alternative to map, set, unordered_map, and
jpayne@69 67 // unordered_set.
jpayne@69 68 //
jpayne@69 69 // Unlike a traditional map, which explicitly stores key/value pairs, a Table simply stores
jpayne@69 70 // "rows" of arbitrary type, and then lets the application specify how these should be indexed.
jpayne@69 71 // Rows could be indexed on a specific struct field, or they could be indexed based on a computed
jpayne@69 72 // property. An index could be hash-based or tree-based. Multiple indexes are supported, making
jpayne@69 73 // it easy to construct a "bimap".
jpayne@69 74 //
jpayne@69 75 // The table has deterministic iteration order based on the sequence of insertions and deletions.
jpayne@69 76 // In the case of only insertions, the iteration order is the order of insertion. If deletions
jpayne@69 77 // occur, then the current last row is moved to occupy the deleted slot. This determinism is
jpayne@69 78 // intended to be reliable for the purpose of testing, etc.
jpayne@69 79 //
jpayne@69 80 // Each index is a class that looks like:
jpayne@69 81 //
jpayne@69 82 // class Index {
jpayne@69 83 // public:
jpayne@69 84 // void reserve(size_t size);
jpayne@69 85 // // Called when Table::reserve() is called.
jpayne@69 86 //
jpayne@69 87 // SearchParam& keyForRow(const Row& row) const;
jpayne@69 88 // // Given a row, return a value appropriate to pass as SearchParams to the other functions.
jpayne@69 89 //
jpayne@69 90 // // In all function calls below, `SearchPrams` refers to whatever parameters the index
jpayne@69 91 // // supports for looking up a row in the table.
jpayne@69 92 //
jpayne@69 93 // template <typename... SearchParams>
jpayne@69 94 // kj::Maybe<size_t> insert(kj::ArrayPtr<const Row> table, size_t pos, SearchParams&&...);
jpayne@69 95 // // Called to indicate that we're about to insert a new row which will match the given
jpayne@69 96 // // search parameters, and will be located at the given position. If this index disallows
jpayne@69 97 // // duplicates and some other matching row already exists, then insert() returns the index
jpayne@69 98 // // of that row without modifying the index. If the row does not exist, then insert()
jpayne@69 99 // // updates the index to note that the new row is located at `pos`. Note that `table[pos]`
jpayne@69 100 // // may not be valid yet at the time of this call; the index must go on the search params
jpayne@69 101 // // alone.
jpayne@69 102 // //
jpayne@69 103 // // Insert may throw an exception, in which case the table will roll back insertion.
jpayne@69 104 //
jpayne@69 105 // template <typename... SearchParams>
jpayne@69 106 // void erase(kj::ArrayPtr<const Row> table, size_t pos, SearchParams&&...);
jpayne@69 107 // // Called to indicate that the index must remove references to row number `pos`. The
jpayne@69 108 // // index must not attempt to access table[pos] directly -- in fact, `pos` may be equal to
jpayne@69 109 // // `table.size()`, i.e., may be out-of-bounds (this happens when rolling back a failed
jpayne@69 110 // // insertion). Instead, the index can use the search params to search for the row -- they
jpayne@69 111 // // will either be the same as the params passed to insert(), or will be a single value of
jpayne@69 112 // // type `Row&`.
jpayne@69 113 // //
jpayne@69 114 // // erase() called immediately after a successful insert() must not throw an exception, as
jpayne@69 115 // // it may be called during unwind.
jpayne@69 116 //
jpayne@69 117 // template <typename... SearchParams>
jpayne@69 118 // void move(kj::ArrayPtr<const Row> table, size_t oldPos, size_t newPos, SearchParams&&...);
jpayne@69 119 // // Called when a row is about to be moved from `oldPos` to `newPos` in the table. The
jpayne@69 120 // // index should update it to the new location. Neither `table[oldPos]` nor `table[newPos]`
jpayne@69 121 // // is valid during the call -- use the search params to find the row. Before this call
jpayne@69 122 // // `oldPos` is indexed and `newPos` is not -- after the call, the opposite is true.
jpayne@69 123 // //
jpayne@69 124 // // This should never throw; if it does the table may be corrupted.
jpayne@69 125 //
jpayne@69 126 // class Iterator; // Behaves like a C++ iterator over size_t values.
jpayne@69 127 // class Iterable; // Has begin() and end() methods returning iterators.
jpayne@69 128 //
jpayne@69 129 // template <typename... SearchParams>
jpayne@69 130 // Maybe<size_t> find(kj::ArrayPtr<const Row> table, SearchParams&&...) const;
jpayne@69 131 // // Optional. Implements Table::find<Index>(...).
jpayne@69 132 //
jpayne@69 133 // template <typename... SearchParams>
jpayne@69 134 // Iterator seek(kj::ArrayPtr<const Row> table, SearchParams&&...) const;
jpayne@69 135 // // Optional. Implements Table::seek<Index>() and Table::range<Index>(...).
jpayne@69 136 //
jpayne@69 137 // Iterator begin() const;
jpayne@69 138 // Iterator end() const;
jpayne@69 139 // // Optional. Implements Table::ordered<Index>().
jpayne@69 140 // };
jpayne@69 141
jpayne@69 142 public:
jpayne@69 143 Table();
jpayne@69 144 Table(Indexes&&... indexes);
jpayne@69 145
jpayne@69 146 void reserve(size_t size);
jpayne@69 147 // Pre-allocates space for a table of the given size. Normally a Table grows by re-allocating
jpayne@69 148 // its backing array whenever more space is needed. Reserving in advance avoids redundantly
jpayne@69 149 // re-allocating as the table grows.
jpayne@69 150
jpayne@69 151 size_t size() const;
jpayne@69 152 size_t capacity() const;
jpayne@69 153
jpayne@69 154 void clear();
jpayne@69 155
jpayne@69 156 Row* begin();
jpayne@69 157 Row* end();
jpayne@69 158 const Row* begin() const;
jpayne@69 159 const Row* end() const;
jpayne@69 160
jpayne@69 161 Row& insert(Row&& row);
jpayne@69 162 Row& insert(const Row& row);
jpayne@69 163 // Inserts a new row. Throws an exception if this would violate the uniqueness constraints of any
jpayne@69 164 // of the indexes.
jpayne@69 165
jpayne@69 166 template <typename Collection>
jpayne@69 167 void insertAll(Collection&& collection);
jpayne@69 168 template <typename Collection>
jpayne@69 169 void insertAll(Collection& collection);
jpayne@69 170 // Given an iterable collection of Rows, inserts all of them into this table. If the input is
jpayne@69 171 // an rvalue, the rows will be moved rather than copied.
jpayne@69 172 //
jpayne@69 173 // If an insertion throws (e.g. because it violates a uniqueness constraint of some index),
jpayne@69 174 // subsequent insertions do not occur, but previous insertions remain inserted.
jpayne@69 175
jpayne@69 176 template <typename UpdateFunc>
jpayne@69 177 Row& upsert(Row&& row, UpdateFunc&& update);
jpayne@69 178 template <typename UpdateFunc>
jpayne@69 179 Row& upsert(const Row& row, UpdateFunc&& update);
jpayne@69 180 // Tries to insert a new row. However, if a duplicate already exists (according to some index),
jpayne@69 181 // then update(Row& existingRow, Row&& newRow) is called to modify the existing row.
jpayne@69 182
jpayne@69 183 template <typename Index, typename... Params>
jpayne@69 184 kj::Maybe<Row&> find(Params&&... params);
jpayne@69 185 template <typename Index, typename... Params>
jpayne@69 186 kj::Maybe<const Row&> find(Params&&... params) const;
jpayne@69 187 // Using the given index, search for a matching row. What parameters are accepted depends on the
jpayne@69 188 // index. Not all indexes support this method -- "multimap" indexes may support only range().
jpayne@69 189
jpayne@69 190 template <typename Index, typename... Params, typename Func>
jpayne@69 191 Row& findOrCreate(Params&&... params, Func&& createFunc);
jpayne@69 192 // Like find(), but if the row doesn't exist, call a function to create it. createFunc() must
jpayne@69 193 // return `Row` or something that implicitly converts to `Row`.
jpayne@69 194 //
jpayne@69 195 // NOTE: C++ doesn't actually properly support inferring types of a parameter pack at the
jpayne@69 196 // beginning of an argument list, but we define a hack to support it below. Don't worry about
jpayne@69 197 // it.
jpayne@69 198
jpayne@69 199 template <typename Index, typename BeginKey, typename EndKey>
jpayne@69 200 auto range(BeginKey&& begin, EndKey&& end);
jpayne@69 201 template <typename Index, typename BeginKey, typename EndKey>
jpayne@69 202 auto range(BeginKey&& begin, EndKey&& end) const;
jpayne@69 203 // Using the given index, look up a range of values, returning an iterable. What parameters are
jpayne@69 204 // accepted depends on the index. Not all indexes support this method (in particular, unordered
jpayne@69 205 // indexes normally don't).
jpayne@69 206
jpayne@69 207 template <typename Index>
jpayne@69 208 _::TableIterable<Row, Index&> ordered();
jpayne@69 209 template <typename Index>
jpayne@69 210 _::TableIterable<const Row, const Index&> ordered() const;
jpayne@69 211 // Returns an iterable over the whole table ordered using the given index. Not all indexes
jpayne@69 212 // support this method.
jpayne@69 213
jpayne@69 214 template <typename Index, typename... Params>
jpayne@69 215 auto seek(Params&&... params);
jpayne@69 216 template <typename Index, typename... Params>
jpayne@69 217 auto seek(Params&&... params) const;
jpayne@69 218 // Takes same parameters as find(), but returns an iterator at the position where the search
jpayne@69 219 // key should go. That is, this returns an iterator that points to the matching entry or, if
jpayne@69 220 // there is no matching entry, points at the next entry after the key, in order. Or, if there
jpayne@69 221 // is no such entry, the returned iterator is the same as ordered().end().
jpayne@69 222 //
jpayne@69 223 // seek() is only supported by indexes that support ordered(). It returns the same kind of
jpayne@69 224 // iterator that ordered() uses.
jpayne@69 225
jpayne@69 226 template <typename Index, typename... Params>
jpayne@69 227 bool eraseMatch(Params&&... params);
jpayne@69 228 // Erase the row that would be matched by `find<Index>(params)`. Returns true if there was a
jpayne@69 229 // match.
jpayne@69 230
jpayne@69 231 template <typename Index, typename BeginKey, typename EndKey>
jpayne@69 232 size_t eraseRange(BeginKey&& begin, EndKey&& end);
jpayne@69 233 // Erase the row that would be matched by `range<Index>(params)`. Returns the number of
jpayne@69 234 // elements erased.
jpayne@69 235
jpayne@69 236 void erase(Row& row);
jpayne@69 237 // Erase the given row.
jpayne@69 238 //
jpayne@69 239 // WARNING: This invalidates all iterators, so you can't iterate over rows and erase them this
jpayne@69 240 // way. Use `eraseAll()` for that.
jpayne@69 241
jpayne@69 242 Row release(Row& row);
jpayne@69 243 // Remove the given row from the table and return it in one operation.
jpayne@69 244 //
jpayne@69 245 // WARNING: This invalidates all iterators, so you can't iterate over rows and release them this
jpayne@69 246 // way.
jpayne@69 247
jpayne@69 248 template <typename Predicate, typename = decltype(instance<Predicate>()(instance<Row&>()))>
jpayne@69 249 size_t eraseAll(Predicate&& predicate);
jpayne@69 250 // Erase all rows for which predicate(row) returns true. This scans over the entire table.
jpayne@69 251
jpayne@69 252 template <typename Collection, typename = decltype(instance<Collection>().begin()), bool = true>
jpayne@69 253 size_t eraseAll(Collection&& collection);
jpayne@69 254 // Erase all rows in the given iterable collection of rows. This carefully marks rows for
jpayne@69 255 // deletion in a first pass then deletes them in a second.
jpayne@69 256
jpayne@69 257 template <size_t index = 0, typename... Params>
jpayne@69 258 kj::Maybe<Row&> find(Params&&... params);
jpayne@69 259 template <size_t index = 0, typename... Params>
jpayne@69 260 kj::Maybe<const Row&> find(Params&&... params) const;
jpayne@69 261 template <size_t index = 0, typename... Params, typename Func>
jpayne@69 262 Row& findOrCreate(Params&&... params, Func&& createFunc);
jpayne@69 263 template <size_t index = 0, typename BeginKey, typename EndKey>
jpayne@69 264 auto range(BeginKey&& begin, EndKey&& end);
jpayne@69 265 template <size_t index = 0, typename BeginKey, typename EndKey>
jpayne@69 266 auto range(BeginKey&& begin, EndKey&& end) const;
jpayne@69 267 template <size_t index = 0>
jpayne@69 268 _::TableIterable<Row, TypeOfIndex<index, Tuple<Indexes...>>&> ordered();
jpayne@69 269 template <size_t index = 0>
jpayne@69 270 _::TableIterable<const Row, const TypeOfIndex<index, Tuple<Indexes...>>&> ordered() const;
jpayne@69 271 template <size_t index = 0, typename... Params>
jpayne@69 272 auto seek(Params&&... params);
jpayne@69 273 template <size_t index = 0, typename... Params>
jpayne@69 274 auto seek(Params&&... params) const;
jpayne@69 275 template <size_t index = 0, typename... Params>
jpayne@69 276 bool eraseMatch(Params&&... params);
jpayne@69 277 template <size_t index = 0, typename BeginKey, typename EndKey>
jpayne@69 278 size_t eraseRange(BeginKey&& begin, EndKey&& end);
jpayne@69 279 // Methods which take an index type as a template parameter can also take an index number. This
jpayne@69 280 // is useful particularly when you have multiple indexes of the same type but different runtime
jpayne@69 281 // properties. Additionally, you can omit the template parameter altogether to use the first
jpayne@69 282 // index.
jpayne@69 283
jpayne@69 284 template <size_t index = 0>
jpayne@69 285 void verify();
jpayne@69 286 // Checks the integrity of indexes, throwing an exception if there are any problems. This is
jpayne@69 287 // intended to be called within the unit test for an index.
jpayne@69 288
jpayne@69 289 template <typename Index, typename First, typename... Rest>
jpayne@69 290 Row& findOrCreate(First&& first, Rest&&... rest);
jpayne@69 291 template <size_t index = 0, typename First, typename... Rest>
jpayne@69 292 Row& findOrCreate(First&& first, Rest&&... rest);
jpayne@69 293 // HACK: A parameter pack can only be inferred if it lives at the end of the argument list, so
jpayne@69 294 // the findOrCreate() definitions from earlier won't actually work. These ones will, but we
jpayne@69 295 // have to do some annoying things inside to regroup the arguments.
jpayne@69 296
jpayne@69 297 private:
jpayne@69 298 Vector<Row> rows;
jpayne@69 299 Tuple<Indexes...> indexes;
jpayne@69 300
jpayne@69 301 template <size_t index = 0, bool final = (index >= sizeof...(Indexes))>
jpayne@69 302 class Impl;
jpayne@69 303 template <typename Func, typename... Params>
jpayne@69 304 class FindOrCreateImpl;
jpayne@69 305
jpayne@69 306 template <typename ParamsTuple, typename... Params>
jpayne@69 307 struct FindOrCreateHack;
jpayne@69 308
jpayne@69 309 void eraseImpl(size_t pos);
jpayne@69 310 template <typename Collection>
jpayne@69 311 size_t eraseAllImpl(Collection&& collection);
jpayne@69 312 };
jpayne@69 313
jpayne@69 314 template <typename Callbacks>
jpayne@69 315 class HashIndex;
jpayne@69 316 // A Table index based on a hash table.
jpayne@69 317 //
jpayne@69 318 // This implementation:
jpayne@69 319 // * Is based on linear probing, not chaining. It is important to use a high-quality hash function.
jpayne@69 320 // Use the KJ hashing library if possible.
jpayne@69 321 // * Is limited to tables of 2^30 rows or less, mainly to allow for tighter packing with 32-bit
jpayne@69 322 // integers instead of 64-bit.
jpayne@69 323 // * Caches hash codes so that each table row need only be hashed once, and never checks equality
jpayne@69 324 // unless hash codes have already been determined to be equal.
jpayne@69 325 //
jpayne@69 326 // The `Callbacks` type defines how to compute hash codes and equality. It should be defined like:
jpayne@69 327 //
jpayne@69 328 // class Callbacks {
jpayne@69 329 // public:
jpayne@69 330 // // In this interface, `SearchParams...` means whatever parameters you want to support in
jpayne@69 331 // // a call to table.find(...). By overloading the calls to support various inputs, you can
jpayne@69 332 // // affect what table.find(...) accepts.
jpayne@69 333 //
jpayne@69 334 // SearchParam& keyForRow(const Row& row);
jpayne@69 335 // // Given a row of the table, return the SearchParams that might be passed to the other
jpayne@69 336 // // methods to match this row.
jpayne@69 337 //
jpayne@69 338 // bool matches(const Row&, SearchParams&&...) const;
jpayne@69 339 // // Returns true if the row on the left matches the search params on the right.
jpayne@69 340 //
jpayne@69 341 // uint hashCode(SearchParams&&...) const;
jpayne@69 342 // // Computes the hash code of the given search params. Matching rows (as determined by
jpayne@69 343 // // matches()) must have the same hash code. Non-matching rows should have different hash
jpayne@69 344 // // codes, to the maximum extent possible. Non-matching rows with the same hash code hurt
jpayne@69 345 // // performance.
jpayne@69 346 // };
jpayne@69 347 //
jpayne@69 348 // If your `Callbacks` type has dynamic state, you may pass its constructor parameters as the
jpayne@69 349 // constructor parameters to `HashIndex`.
jpayne@69 350
jpayne@69 351 template <typename Callbacks>
jpayne@69 352 class TreeIndex;
jpayne@69 353 // A Table index based on a B-tree.
jpayne@69 354 //
jpayne@69 355 // This allows sorted iteration over rows.
jpayne@69 356 //
jpayne@69 357 // The `Callbacks` type defines how to compare rows. It should be defined like:
jpayne@69 358 //
jpayne@69 359 // class Callbacks {
jpayne@69 360 // public:
jpayne@69 361 // // In this interface, `SearchParams...` means whatever parameters you want to support in
jpayne@69 362 // // a call to table.find(...). By overloading the calls to support various inputs, you can
jpayne@69 363 // // affect what table.find(...) accepts.
jpayne@69 364 //
jpayne@69 365 // SearchParam& keyForRow(const Row& row);
jpayne@69 366 // // Given a row of the table, return the SearchParams that might be passed to the other
jpayne@69 367 // // methods to match this row.
jpayne@69 368 //
jpayne@69 369 // bool isBefore(const Row&, SearchParams&&...) const;
jpayne@69 370 // // Returns true if the row on the left comes before the search params on the right.
jpayne@69 371 //
jpayne@69 372 // bool matches(const Row&, SearchParams&&...) const;
jpayne@69 373 // // Returns true if the row "matches" the search params.
jpayne@69 374 // };
jpayne@69 375
jpayne@69 376 // =======================================================================================
jpayne@69 377 // inline implementation details
jpayne@69 378
jpayne@69 379 namespace _ { // private
jpayne@69 380
jpayne@69 381 KJ_NORETURN(void throwDuplicateTableRow());
jpayne@69 382
jpayne@69 383 template <typename Dst, typename Src, typename = decltype(instance<Src>().size())>
jpayne@69 384 inline void tryReserveSize(Dst& dst, Src&& src) { dst.reserve(dst.size() + src.size()); }
jpayne@69 385 template <typename... Params>
jpayne@69 386 inline void tryReserveSize(Params&&...) {}
jpayne@69 387 // If `src` has a `.size()` method, call dst.reserve(dst.size() + src.size()).
jpayne@69 388 // Otherwise, do nothing.
jpayne@69 389
jpayne@69 390 template <typename Row>
jpayne@69 391 class TableMapping {
jpayne@69 392 public:
jpayne@69 393 TableMapping(Row* table): table(table) {}
jpayne@69 394 Row& map(size_t i) const { return table[i]; }
jpayne@69 395
jpayne@69 396 private:
jpayne@69 397 Row* table;
jpayne@69 398 };
jpayne@69 399
jpayne@69 400 template <typename Row>
jpayne@69 401 class TableUnmapping {
jpayne@69 402 public:
jpayne@69 403 TableUnmapping(Row* table): table(table) {}
jpayne@69 404 size_t map(Row& row) const { return &row - table; }
jpayne@69 405 size_t map(Row* row) const { return row - table; }
jpayne@69 406
jpayne@69 407 private:
jpayne@69 408 Row* table;
jpayne@69 409 };
jpayne@69 410
jpayne@69 411 template <typename Iterator>
jpayne@69 412 class IterRange {
jpayne@69 413 public:
jpayne@69 414 inline IterRange(Iterator b, Iterator e): b(b), e(e) {}
jpayne@69 415
jpayne@69 416 inline Iterator begin() const { return b; }
jpayne@69 417 inline Iterator end() const { return e; }
jpayne@69 418 private:
jpayne@69 419 Iterator b;
jpayne@69 420 Iterator e;
jpayne@69 421 };
jpayne@69 422
jpayne@69 423 template <typename Iterator>
jpayne@69 424 inline IterRange<Decay<Iterator>> iterRange(Iterator b, Iterator e) {
jpayne@69 425 return { b, e };
jpayne@69 426 }
jpayne@69 427
jpayne@69 428 } // namespace _ (private)
jpayne@69 429
jpayne@69 430 template <typename Row, typename... Indexes>
jpayne@69 431 template <size_t index>
jpayne@69 432 class Table<Row, Indexes...>::Impl<index, false> {
jpayne@69 433 public:
jpayne@69 434 static void reserve(Table<Row, Indexes...>& table, size_t size) {
jpayne@69 435 get<index>(table.indexes).reserve(size);
jpayne@69 436 Impl<index + 1>::reserve(table, size);
jpayne@69 437 }
jpayne@69 438
jpayne@69 439 static void clear(Table<Row, Indexes...>& table) {
jpayne@69 440 get<index>(table.indexes).clear();
jpayne@69 441 Impl<index + 1>::clear(table);
jpayne@69 442 }
jpayne@69 443
jpayne@69 444 static kj::Maybe<size_t> insert(Table<Row, Indexes...>& table, size_t pos, Row& row, uint skip) {
jpayne@69 445 if (skip == index) {
jpayne@69 446 return Impl<index + 1>::insert(table, pos, row, skip);
jpayne@69 447 }
jpayne@69 448 auto& indexObj = get<index>(table.indexes);
jpayne@69 449 KJ_IF_MAYBE(existing, indexObj.insert(table.rows.asPtr(), pos, indexObj.keyForRow(row))) {
jpayne@69 450 return *existing;
jpayne@69 451 }
jpayne@69 452
jpayne@69 453 bool success = false;
jpayne@69 454 KJ_DEFER(if (!success) {
jpayne@69 455 indexObj.erase(table.rows.asPtr(), pos, indexObj.keyForRow(row));
jpayne@69 456 });
jpayne@69 457 auto result = Impl<index + 1>::insert(table, pos, row, skip);
jpayne@69 458 success = result == nullptr;
jpayne@69 459 return result;
jpayne@69 460 }
jpayne@69 461
jpayne@69 462 static void erase(Table<Row, Indexes...>& table, size_t pos, Row& row) {
jpayne@69 463 auto& indexObj = get<index>(table.indexes);
jpayne@69 464 indexObj.erase(table.rows.asPtr(), pos, indexObj.keyForRow(row));
jpayne@69 465 Impl<index + 1>::erase(table, pos, row);
jpayne@69 466 }
jpayne@69 467
jpayne@69 468 static void move(Table<Row, Indexes...>& table, size_t oldPos, size_t newPos, Row& row) {
jpayne@69 469 auto& indexObj = get<index>(table.indexes);
jpayne@69 470 indexObj.move(table.rows.asPtr(), oldPos, newPos, indexObj.keyForRow(row));
jpayne@69 471 Impl<index + 1>::move(table, oldPos, newPos, row);
jpayne@69 472 }
jpayne@69 473 };
jpayne@69 474
jpayne@69 475 template <typename Row, typename... Indexes>
jpayne@69 476 template <size_t index>
jpayne@69 477 class Table<Row, Indexes...>::Impl<index, true> {
jpayne@69 478 public:
jpayne@69 479 static void reserve(Table<Row, Indexes...>& table, size_t size) {}
jpayne@69 480 static void clear(Table<Row, Indexes...>& table) {}
jpayne@69 481 static kj::Maybe<size_t> insert(Table<Row, Indexes...>& table, size_t pos, Row& row, uint skip) {
jpayne@69 482 return nullptr;
jpayne@69 483 }
jpayne@69 484 static void erase(Table<Row, Indexes...>& table, size_t pos, Row& row) {}
jpayne@69 485 static void move(Table<Row, Indexes...>& table, size_t oldPos, size_t newPos, Row& row) {}
jpayne@69 486 };
jpayne@69 487
jpayne@69 488 template <typename Row, typename... Indexes>
jpayne@69 489 Table<Row, Indexes...>::Table() {}
jpayne@69 490
jpayne@69 491 template <typename Row, typename... Indexes>
jpayne@69 492 Table<Row, Indexes...>::Table(Indexes&&... indexes)
jpayne@69 493 : indexes(tuple(kj::fwd<Indexes&&>(indexes)...)) {}
jpayne@69 494
jpayne@69 495 template <typename Row, typename... Indexes>
jpayne@69 496 void Table<Row, Indexes...>::reserve(size_t size) {
jpayne@69 497 rows.reserve(size);
jpayne@69 498 Impl<>::reserve(*this, size);
jpayne@69 499 }
jpayne@69 500
jpayne@69 501 template <typename Row, typename... Indexes>
jpayne@69 502 size_t Table<Row, Indexes...>::size() const {
jpayne@69 503 return rows.size();
jpayne@69 504 }
jpayne@69 505 template <typename Row, typename... Indexes>
jpayne@69 506 void Table<Row, Indexes...>::clear() {
jpayne@69 507 Impl<>::clear(*this);
jpayne@69 508 rows.clear();
jpayne@69 509 }
jpayne@69 510 template <typename Row, typename... Indexes>
jpayne@69 511 size_t Table<Row, Indexes...>::capacity() const {
jpayne@69 512 return rows.capacity();
jpayne@69 513 }
jpayne@69 514
jpayne@69 515 template <typename Row, typename... Indexes>
jpayne@69 516 Row* Table<Row, Indexes...>::begin() {
jpayne@69 517 return rows.begin();
jpayne@69 518 }
jpayne@69 519 template <typename Row, typename... Indexes>
jpayne@69 520 Row* Table<Row, Indexes...>::end() {
jpayne@69 521 return rows.end();
jpayne@69 522 }
jpayne@69 523 template <typename Row, typename... Indexes>
jpayne@69 524 const Row* Table<Row, Indexes...>::begin() const {
jpayne@69 525 return rows.begin();
jpayne@69 526 }
jpayne@69 527 template <typename Row, typename... Indexes>
jpayne@69 528 const Row* Table<Row, Indexes...>::end() const {
jpayne@69 529 return rows.end();
jpayne@69 530 }
jpayne@69 531
jpayne@69 532 template <typename Row, typename... Indexes>
jpayne@69 533 Row& Table<Row, Indexes...>::insert(Row&& row) {
jpayne@69 534 KJ_IF_MAYBE(existing, Impl<>::insert(*this, rows.size(), row, kj::maxValue)) {
jpayne@69 535 _::throwDuplicateTableRow();
jpayne@69 536 } else {
jpayne@69 537 return rows.add(kj::mv(row));
jpayne@69 538 }
jpayne@69 539 }
jpayne@69 540 template <typename Row, typename... Indexes>
jpayne@69 541 Row& Table<Row, Indexes...>::insert(const Row& row) {
jpayne@69 542 return insert(kj::cp(row));
jpayne@69 543 }
jpayne@69 544
jpayne@69 545 template <typename Row, typename... Indexes>
jpayne@69 546 template <typename Collection>
jpayne@69 547 void Table<Row, Indexes...>::insertAll(Collection&& collection) {
jpayne@69 548 _::tryReserveSize(*this, collection);
jpayne@69 549 for (auto& row: collection) {
jpayne@69 550 insert(kj::mv(row));
jpayne@69 551 }
jpayne@69 552 }
jpayne@69 553
jpayne@69 554 template <typename Row, typename... Indexes>
jpayne@69 555 template <typename Collection>
jpayne@69 556 void Table<Row, Indexes...>::insertAll(Collection& collection) {
jpayne@69 557 _::tryReserveSize(*this, collection);
jpayne@69 558 for (auto& row: collection) {
jpayne@69 559 insert(row);
jpayne@69 560 }
jpayne@69 561 }
jpayne@69 562
jpayne@69 563 template <typename Row, typename... Indexes>
jpayne@69 564 template <typename UpdateFunc>
jpayne@69 565 Row& Table<Row, Indexes...>::upsert(Row&& row, UpdateFunc&& update) {
jpayne@69 566 KJ_IF_MAYBE(existing, Impl<>::insert(*this, rows.size(), row, kj::maxValue)) {
jpayne@69 567 update(rows[*existing], kj::mv(row));
jpayne@69 568 return rows[*existing];
jpayne@69 569 } else {
jpayne@69 570 return rows.add(kj::mv(row));
jpayne@69 571 }
jpayne@69 572 }
jpayne@69 573 template <typename Row, typename... Indexes>
jpayne@69 574 template <typename UpdateFunc>
jpayne@69 575 Row& Table<Row, Indexes...>::upsert(const Row& row, UpdateFunc&& update) {
jpayne@69 576 return upsert(kj::cp(row), kj::fwd<UpdateFunc>(update));
jpayne@69 577 }
jpayne@69 578
jpayne@69 579 template <typename Row, typename... Indexes>
jpayne@69 580 template <typename Index, typename... Params>
jpayne@69 581 kj::Maybe<Row&> Table<Row, Indexes...>::find(Params&&... params) {
jpayne@69 582 return find<indexOfType<Index, Tuple<Indexes...>>()>(kj::fwd<Params>(params)...);
jpayne@69 583 }
jpayne@69 584 template <typename Row, typename... Indexes>
jpayne@69 585 template <size_t index, typename... Params>
jpayne@69 586 kj::Maybe<Row&> Table<Row, Indexes...>::find(Params&&... params) {
jpayne@69 587 KJ_IF_MAYBE(pos, get<index>(indexes).find(rows.asPtr(), kj::fwd<Params>(params)...)) {
jpayne@69 588 return rows[*pos];
jpayne@69 589 } else {
jpayne@69 590 return nullptr;
jpayne@69 591 }
jpayne@69 592 }
jpayne@69 593 template <typename Row, typename... Indexes>
jpayne@69 594 template <typename Index, typename... Params>
jpayne@69 595 kj::Maybe<const Row&> Table<Row, Indexes...>::find(Params&&... params) const {
jpayne@69 596 return find<indexOfType<Index, Tuple<Indexes...>>()>(kj::fwd<Params>(params)...);
jpayne@69 597 }
jpayne@69 598 template <typename Row, typename... Indexes>
jpayne@69 599 template <size_t index, typename... Params>
jpayne@69 600 kj::Maybe<const Row&> Table<Row, Indexes...>::find(Params&&... params) const {
jpayne@69 601 KJ_IF_MAYBE(pos, get<index>(indexes).find(rows.asPtr(), kj::fwd<Params>(params)...)) {
jpayne@69 602 return rows[*pos];
jpayne@69 603 } else {
jpayne@69 604 return nullptr;
jpayne@69 605 }
jpayne@69 606 }
jpayne@69 607
jpayne@69 608 template <typename Row, typename... Indexes>
jpayne@69 609 template <typename Func, typename... Params>
jpayne@69 610 class Table<Row, Indexes...>::FindOrCreateImpl {
jpayne@69 611 public:
jpayne@69 612 template <size_t index>
jpayne@69 613 static Row& apply(Table<Row, Indexes...>& table, Params&&... params, Func&& createFunc) {
jpayne@69 614 auto pos = table.rows.size();
jpayne@69 615 KJ_IF_MAYBE(existing, get<index>(table.indexes).insert(table.rows.asPtr(), pos, params...)) {
jpayne@69 616 return table.rows[*existing];
jpayne@69 617 } else {
jpayne@69 618 bool success = false;
jpayne@69 619 KJ_DEFER({
jpayne@69 620 if (!success) {
jpayne@69 621 get<index>(table.indexes).erase(table.rows.asPtr(), pos, params...);
jpayne@69 622 }
jpayne@69 623 });
jpayne@69 624 auto& newRow = table.rows.add(createFunc());
jpayne@69 625 KJ_DEFER({
jpayne@69 626 if (!success) {
jpayne@69 627 table.rows.removeLast();
jpayne@69 628 }
jpayne@69 629 });
jpayne@69 630 if (Table<Row, Indexes...>::template Impl<>::insert(table, pos, newRow, index) == nullptr) {
jpayne@69 631 success = true;
jpayne@69 632 } else {
jpayne@69 633 _::throwDuplicateTableRow();
jpayne@69 634 }
jpayne@69 635 return newRow;
jpayne@69 636 }
jpayne@69 637 }
jpayne@69 638 };
jpayne@69 639
jpayne@69 640 template <typename Row, typename... Indexes>
jpayne@69 641 template <typename... T, typename U, typename V, typename... W>
jpayne@69 642 struct Table<Row, Indexes...>::FindOrCreateHack<_::Tuple<T...>, U, V, W...>
jpayne@69 643 : public FindOrCreateHack<_::Tuple<T..., U>, V, W...> {};
jpayne@69 644 template <typename Row, typename... Indexes>
jpayne@69 645 template <typename... T, typename U>
jpayne@69 646 struct Table<Row, Indexes...>::FindOrCreateHack<_::Tuple<T...>, U>
jpayne@69 647 : public FindOrCreateImpl<U, T...> {};
jpayne@69 648 // This awful hack works around C++'s lack of support for parameter packs anywhere other than at
jpayne@69 649 // the end of an argument list. We accumulate all of the types except for the last one into a
jpayne@69 650 // Tuple, then forward to FindOrCreateImpl with the last parameter as the Func.
jpayne@69 651
jpayne@69 652 template <typename Row, typename... Indexes>
jpayne@69 653 template <typename Index, typename First, typename... Rest>
jpayne@69 654 Row& Table<Row, Indexes...>::findOrCreate(First&& first, Rest&&... rest) {
jpayne@69 655 return findOrCreate<indexOfType<Index, Tuple<Indexes...>>()>(
jpayne@69 656 kj::fwd<First>(first), kj::fwd<Rest>(rest)...);
jpayne@69 657 }
jpayne@69 658 template <typename Row, typename... Indexes>
jpayne@69 659 template <size_t index, typename First, typename... Rest>
jpayne@69 660 Row& Table<Row, Indexes...>::findOrCreate(First&& first, Rest&&... rest) {
jpayne@69 661 return FindOrCreateHack<_::Tuple<>, First, Rest...>::template apply<index>(
jpayne@69 662 *this, kj::fwd<First>(first), kj::fwd<Rest>(rest)...);
jpayne@69 663 }
jpayne@69 664
jpayne@69 665 template <typename Row, typename... Indexes>
jpayne@69 666 template <typename Index, typename BeginKey, typename EndKey>
jpayne@69 667 auto Table<Row, Indexes...>::range(BeginKey&& begin, EndKey&& end) {
jpayne@69 668 return range<indexOfType<Index, Tuple<Indexes...>>()>(
jpayne@69 669 kj::fwd<BeginKey>(begin), kj::fwd<EndKey>(end));
jpayne@69 670 }
jpayne@69 671 template <typename Row, typename... Indexes>
jpayne@69 672 template <size_t index, typename BeginKey, typename EndKey>
jpayne@69 673 auto Table<Row, Indexes...>::range(BeginKey&& begin, EndKey&& end) {
jpayne@69 674 auto inner = _::iterRange(get<index>(indexes).seek(rows.asPtr(), kj::fwd<BeginKey>(begin)),
jpayne@69 675 get<index>(indexes).seek(rows.asPtr(), kj::fwd<EndKey>(end)));
jpayne@69 676 return _::TableIterable<Row, decltype(inner)>(kj::mv(inner), rows.begin());
jpayne@69 677 }
jpayne@69 678 template <typename Row, typename... Indexes>
jpayne@69 679 template <typename Index, typename BeginKey, typename EndKey>
jpayne@69 680 auto Table<Row, Indexes...>::range(BeginKey&& begin, EndKey&& end) const {
jpayne@69 681 return range<indexOfType<Index, Tuple<Indexes...>>()>(
jpayne@69 682 kj::fwd<BeginKey>(begin), kj::fwd<EndKey>(end));
jpayne@69 683 }
jpayne@69 684 template <typename Row, typename... Indexes>
jpayne@69 685 template <size_t index, typename BeginKey, typename EndKey>
jpayne@69 686 auto Table<Row, Indexes...>::range(BeginKey&& begin, EndKey&& end) const {
jpayne@69 687 auto inner = _::iterRange(get<index>(indexes).seek(rows.asPtr(), kj::fwd<BeginKey>(begin)),
jpayne@69 688 get<index>(indexes).seek(rows.asPtr(), kj::fwd<EndKey>(end)));
jpayne@69 689 return _::TableIterable<const Row, decltype(inner)>(kj::mv(inner), rows.begin());
jpayne@69 690 }
jpayne@69 691
jpayne@69 692 template <typename Row, typename... Indexes>
jpayne@69 693 template <typename Index>
jpayne@69 694 _::TableIterable<Row, Index&> Table<Row, Indexes...>::ordered() {
jpayne@69 695 return ordered<indexOfType<Index, Tuple<Indexes...>>()>();
jpayne@69 696 }
jpayne@69 697 template <typename Row, typename... Indexes>
jpayne@69 698 template <size_t index>
jpayne@69 699 _::TableIterable<Row, TypeOfIndex<index, Tuple<Indexes...>>&> Table<Row, Indexes...>::ordered() {
jpayne@69 700 return { get<index>(indexes), rows.begin() };
jpayne@69 701 }
jpayne@69 702 template <typename Row, typename... Indexes>
jpayne@69 703 template <typename Index>
jpayne@69 704 _::TableIterable<const Row, const Index&> Table<Row, Indexes...>::ordered() const {
jpayne@69 705 return ordered<indexOfType<Index, Tuple<Indexes...>>()>();
jpayne@69 706 }
jpayne@69 707 template <typename Row, typename... Indexes>
jpayne@69 708 template <size_t index>
jpayne@69 709 _::TableIterable<const Row, const TypeOfIndex<index, Tuple<Indexes...>>&>
jpayne@69 710 Table<Row, Indexes...>::ordered() const {
jpayne@69 711 return { get<index>(indexes), rows.begin() };
jpayne@69 712 }
jpayne@69 713
jpayne@69 714 template <typename Row, typename... Indexes>
jpayne@69 715 template <typename Index, typename... Params>
jpayne@69 716 auto Table<Row, Indexes...>::seek(Params&&... params) {
jpayne@69 717 return seek<indexOfType<Index, Tuple<Indexes...>>()>(kj::fwd<Params>(params)...);
jpayne@69 718 }
jpayne@69 719 template <typename Row, typename... Indexes>
jpayne@69 720 template <size_t index, typename... Params>
jpayne@69 721 auto Table<Row, Indexes...>::seek(Params&&... params) {
jpayne@69 722 auto inner = get<index>(indexes).seek(rows.asPtr(), kj::fwd<Params>(params)...);
jpayne@69 723 return _::TableIterator<Row, decltype(inner)>(kj::mv(inner), rows.begin());
jpayne@69 724 }
jpayne@69 725 template <typename Row, typename... Indexes>
jpayne@69 726 template <typename Index, typename... Params>
jpayne@69 727 auto Table<Row, Indexes...>::seek(Params&&... params) const {
jpayne@69 728 return seek<indexOfType<Index, Tuple<Indexes...>>()>(kj::fwd<Params>(params)...);
jpayne@69 729 }
jpayne@69 730 template <typename Row, typename... Indexes>
jpayne@69 731 template <size_t index, typename... Params>
jpayne@69 732 auto Table<Row, Indexes...>::seek(Params&&... params) const {
jpayne@69 733 auto inner = get<index>(indexes).seek(rows.asPtr(), kj::fwd<Params>(params)...);
jpayne@69 734 return _::TableIterator<Row, decltype(inner)>(kj::mv(inner), rows.begin());
jpayne@69 735 }
jpayne@69 736
jpayne@69 737 template <typename Row, typename... Indexes>
jpayne@69 738 template <typename Index, typename... Params>
jpayne@69 739 bool Table<Row, Indexes...>::eraseMatch(Params&&... params) {
jpayne@69 740 return eraseMatch<indexOfType<Index, Tuple<Indexes...>>()>(kj::fwd<Params>(params)...);
jpayne@69 741 }
jpayne@69 742 template <typename Row, typename... Indexes>
jpayne@69 743 template <size_t index, typename... Params>
jpayne@69 744 bool Table<Row, Indexes...>::eraseMatch(Params&&... params) {
jpayne@69 745 KJ_IF_MAYBE(pos, get<index>(indexes).find(rows.asPtr(), kj::fwd<Params>(params)...)) {
jpayne@69 746 eraseImpl(*pos);
jpayne@69 747 return true;
jpayne@69 748 } else {
jpayne@69 749 return false;
jpayne@69 750 }
jpayne@69 751 }
jpayne@69 752
jpayne@69 753 template <typename Row, typename... Indexes>
jpayne@69 754 template <typename Index, typename BeginKey, typename EndKey>
jpayne@69 755 size_t Table<Row, Indexes...>::eraseRange(BeginKey&& begin, EndKey&& end) {
jpayne@69 756 return eraseRange<indexOfType<Index, Tuple<Indexes...>>()>(
jpayne@69 757 kj::fwd<BeginKey>(begin), kj::fwd<EndKey>(end));
jpayne@69 758 }
jpayne@69 759 template <typename Row, typename... Indexes>
jpayne@69 760 template <size_t index, typename BeginKey, typename EndKey>
jpayne@69 761 size_t Table<Row, Indexes...>::eraseRange(BeginKey&& begin, EndKey&& end) {
jpayne@69 762 auto inner = _::iterRange(get<index>(indexes).seek(rows.asPtr(), kj::fwd<BeginKey>(begin)),
jpayne@69 763 get<index>(indexes).seek(rows.asPtr(), kj::fwd<EndKey>(end)));
jpayne@69 764 return eraseAllImpl(inner);
jpayne@69 765 }
jpayne@69 766
jpayne@69 767 template <typename Row, typename... Indexes>
jpayne@69 768 template <size_t index>
jpayne@69 769 void Table<Row, Indexes...>::verify() {
jpayne@69 770 get<index>(indexes).verify(rows.asPtr());
jpayne@69 771 }
jpayne@69 772
jpayne@69 773 template <typename Row, typename... Indexes>
jpayne@69 774 void Table<Row, Indexes...>::erase(Row& row) {
jpayne@69 775 KJ_TABLE_IREQUIRE(&row >= rows.begin() && &row < rows.end(), "row is not a member of this table");
jpayne@69 776 eraseImpl(&row - rows.begin());
jpayne@69 777 }
jpayne@69 778 template <typename Row, typename... Indexes>
jpayne@69 779 void Table<Row, Indexes...>::eraseImpl(size_t pos) {
jpayne@69 780 Impl<>::erase(*this, pos, rows[pos]);
jpayne@69 781 size_t back = rows.size() - 1;
jpayne@69 782 if (pos != back) {
jpayne@69 783 Impl<>::move(*this, back, pos, rows[back]);
jpayne@69 784 rows[pos] = kj::mv(rows[back]);
jpayne@69 785 }
jpayne@69 786 rows.removeLast();
jpayne@69 787 }
jpayne@69 788
jpayne@69 789 template <typename Row, typename... Indexes>
jpayne@69 790 Row Table<Row, Indexes...>::release(Row& row) {
jpayne@69 791 KJ_TABLE_IREQUIRE(&row >= rows.begin() && &row < rows.end(), "row is not a member of this table");
jpayne@69 792 size_t pos = &row - rows.begin();
jpayne@69 793 Impl<>::erase(*this, pos, row);
jpayne@69 794 Row result = kj::mv(row);
jpayne@69 795 size_t back = rows.size() - 1;
jpayne@69 796 if (pos != back) {
jpayne@69 797 Impl<>::move(*this, back, pos, rows[back]);
jpayne@69 798 row = kj::mv(rows[back]);
jpayne@69 799 }
jpayne@69 800 rows.removeLast();
jpayne@69 801 return result;
jpayne@69 802 }
jpayne@69 803
jpayne@69 804 template <typename Row, typename... Indexes>
jpayne@69 805 template <typename Predicate, typename>
jpayne@69 806 size_t Table<Row, Indexes...>::eraseAll(Predicate&& predicate) {
jpayne@69 807 size_t count = 0;
jpayne@69 808 for (size_t i = 0; i < rows.size();) {
jpayne@69 809 if (predicate(rows[i])) {
jpayne@69 810 eraseImpl(i);
jpayne@69 811 ++count;
jpayne@69 812 // eraseImpl() replaces the erased row with the last row, so don't increment i here; repeat
jpayne@69 813 // with the same i.
jpayne@69 814 } else {
jpayne@69 815 ++i;
jpayne@69 816 }
jpayne@69 817 }
jpayne@69 818 return count;
jpayne@69 819 }
jpayne@69 820
jpayne@69 821 template <typename Row, typename... Indexes>
jpayne@69 822 template <typename Collection, typename, bool>
jpayne@69 823 size_t Table<Row, Indexes...>::eraseAll(Collection&& collection) {
jpayne@69 824 return eraseAllImpl(MappedIterable<Collection&, _::TableUnmapping<Row>>(
jpayne@69 825 collection, rows.begin()));
jpayne@69 826 }
jpayne@69 827
jpayne@69 828 template <typename Row, typename... Indexes>
jpayne@69 829 template <typename Collection>
jpayne@69 830 size_t Table<Row, Indexes...>::eraseAllImpl(Collection&& collection) {
jpayne@69 831 // We need to transform the collection of row numbers into a sequence of erasures, accounting
jpayne@69 832 // for the fact that each erasure re-positions the last row into its slot.
jpayne@69 833 Vector<size_t> erased;
jpayne@69 834 _::tryReserveSize(erased, collection);
jpayne@69 835 for (size_t pos: collection) {
jpayne@69 836 while (pos >= rows.size() - erased.size()) {
jpayne@69 837 // Oops, the next item to be erased is already scheduled to be moved to a different location
jpayne@69 838 // due to a previous erasure. Figure out where it will be at this point.
jpayne@69 839 size_t erasureNumber = rows.size() - pos - 1;
jpayne@69 840 pos = erased[erasureNumber];
jpayne@69 841 }
jpayne@69 842 erased.add(pos);
jpayne@69 843 }
jpayne@69 844
jpayne@69 845 // Now we can execute the sequence of erasures.
jpayne@69 846 for (size_t pos: erased) {
jpayne@69 847 eraseImpl(pos);
jpayne@69 848 }
jpayne@69 849
jpayne@69 850 return erased.size();
jpayne@69 851 }
jpayne@69 852
jpayne@69 853 // -----------------------------------------------------------------------------
jpayne@69 854 // Hash table index
jpayne@69 855
jpayne@69 856 namespace _ { // private
jpayne@69 857
jpayne@69 858 void logHashTableInconsistency();
jpayne@69 859
jpayne@69 860 struct HashBucket {
jpayne@69 861 uint hash;
jpayne@69 862 uint value;
jpayne@69 863
jpayne@69 864 HashBucket() = default;
jpayne@69 865 HashBucket(uint hash, uint pos)
jpayne@69 866 : hash(hash), value(pos + 2) {}
jpayne@69 867
jpayne@69 868 inline bool isEmpty() const { return value == 0; }
jpayne@69 869 inline bool isErased() const { return value == 1; }
jpayne@69 870 inline bool isOccupied() const { return value >= 2; }
jpayne@69 871 template <typename Row>
jpayne@69 872 inline Row& getRow(ArrayPtr<Row> table) const { return table[getPos()]; }
jpayne@69 873 template <typename Row>
jpayne@69 874 inline const Row& getRow(ArrayPtr<const Row> table) const { return table[getPos()]; }
jpayne@69 875 inline bool isPos(uint pos) const { return pos + 2 == value; }
jpayne@69 876 inline uint getPos() const {
jpayne@69 877 KJ_TABLE_IASSERT(value >= 2);
jpayne@69 878 return value - 2;
jpayne@69 879 }
jpayne@69 880 inline void setEmpty() { value = 0; }
jpayne@69 881 inline void setErased() { value = 1; }
jpayne@69 882 inline void setPos(uint pos) { value = pos + 2; }
jpayne@69 883 };
jpayne@69 884
jpayne@69 885 inline size_t probeHash(const kj::Array<HashBucket>& buckets, size_t i) {
jpayne@69 886 // TODO(perf): Is linear probing OK or should we do something fancier?
jpayne@69 887 if (++i == buckets.size()) {
jpayne@69 888 return 0;
jpayne@69 889 } else {
jpayne@69 890 return i;
jpayne@69 891 }
jpayne@69 892 }
jpayne@69 893
jpayne@69 894 kj::Array<HashBucket> rehash(kj::ArrayPtr<const HashBucket> oldBuckets, size_t targetSize);
jpayne@69 895
jpayne@69 896 uint chooseBucket(uint hash, uint count);
jpayne@69 897
jpayne@69 898 } // namespace _ (private)
jpayne@69 899
jpayne@69 900 template <typename Callbacks>
jpayne@69 901 class HashIndex {
jpayne@69 902 public:
jpayne@69 903 HashIndex() = default;
jpayne@69 904 template <typename... Params>
jpayne@69 905 HashIndex(Params&&... params): cb(kj::fwd<Params>(params)...) {}
jpayne@69 906
jpayne@69 907 size_t capacity() {
jpayne@69 908 // This method is for testing.
jpayne@69 909 return buckets.size();
jpayne@69 910 }
jpayne@69 911
jpayne@69 912 void reserve(size_t size) {
jpayne@69 913 if (buckets.size() < size * 2) {
jpayne@69 914 rehash(size);
jpayne@69 915 }
jpayne@69 916 }
jpayne@69 917
jpayne@69 918 void clear() {
jpayne@69 919 erasedCount = 0;
jpayne@69 920 if (buckets.size() > 0) memset(buckets.begin(), 0, buckets.asBytes().size());
jpayne@69 921 }
jpayne@69 922
jpayne@69 923 template <typename Row>
jpayne@69 924 decltype(auto) keyForRow(Row&& row) const {
jpayne@69 925 return cb.keyForRow(kj::fwd<Row>(row));
jpayne@69 926 }
jpayne@69 927
jpayne@69 928 template <typename Row, typename... Params>
jpayne@69 929 kj::Maybe<size_t> insert(kj::ArrayPtr<Row> table, size_t pos, Params&&... params) {
jpayne@69 930 if (buckets.size() * 2 < (table.size() + 1 + erasedCount) * 3) {
jpayne@69 931 // Load factor is more than 2/3, let's rehash so that it's 1/3, i.e. double the buckets.
jpayne@69 932 // Note that rehashing also cleans up erased entries, so we may not actually be doubling if
jpayne@69 933 // there are a lot of erasures. Nevertheless, this gives us amortized constant time -- it
jpayne@69 934 // would take at least O(table.size()) more insertions (whether or not erasures occur)
jpayne@69 935 // before another rehash is needed.
jpayne@69 936 rehash((table.size() + 1) * 3);
jpayne@69 937 }
jpayne@69 938
jpayne@69 939 uint hashCode = cb.hashCode(params...);
jpayne@69 940 Maybe<_::HashBucket&> erasedSlot;
jpayne@69 941 for (uint i = _::chooseBucket(hashCode, buckets.size());; i = _::probeHash(buckets, i)) {
jpayne@69 942 auto& bucket = buckets[i];
jpayne@69 943 if (bucket.isEmpty()) {
jpayne@69 944 // no duplicates found
jpayne@69 945 KJ_IF_MAYBE(s, erasedSlot) {
jpayne@69 946 --erasedCount;
jpayne@69 947 *s = { hashCode, uint(pos) };
jpayne@69 948 } else {
jpayne@69 949 bucket = { hashCode, uint(pos) };
jpayne@69 950 }
jpayne@69 951 return nullptr;
jpayne@69 952 } else if (bucket.isErased()) {
jpayne@69 953 // We can fill in the erased slot. However, we have to keep searching to make sure there
jpayne@69 954 // are no duplicates before we do that.
jpayne@69 955 if (erasedSlot == nullptr) {
jpayne@69 956 erasedSlot = bucket;
jpayne@69 957 }
jpayne@69 958 } else if (bucket.hash == hashCode &&
jpayne@69 959 cb.matches(bucket.getRow(table), params...)) {
jpayne@69 960 // duplicate row
jpayne@69 961 return size_t(bucket.getPos());
jpayne@69 962 }
jpayne@69 963 }
jpayne@69 964 }
jpayne@69 965
jpayne@69 966 template <typename Row, typename... Params>
jpayne@69 967 void erase(kj::ArrayPtr<Row> table, size_t pos, Params&&... params) {
jpayne@69 968 uint hashCode = cb.hashCode(params...);
jpayne@69 969 for (uint i = _::chooseBucket(hashCode, buckets.size());; i = _::probeHash(buckets, i)) {
jpayne@69 970 auto& bucket = buckets[i];
jpayne@69 971 if (bucket.isPos(pos)) {
jpayne@69 972 // found it
jpayne@69 973 ++erasedCount;
jpayne@69 974 bucket.setErased();
jpayne@69 975 return;
jpayne@69 976 } else if (bucket.isEmpty()) {
jpayne@69 977 // can't find the bucket, something is very wrong
jpayne@69 978 _::logHashTableInconsistency();
jpayne@69 979 return;
jpayne@69 980 }
jpayne@69 981 }
jpayne@69 982 }
jpayne@69 983
jpayne@69 984 template <typename Row, typename... Params>
jpayne@69 985 void move(kj::ArrayPtr<Row> table, size_t oldPos, size_t newPos, Params&&... params) {
jpayne@69 986 uint hashCode = cb.hashCode(params...);
jpayne@69 987 for (uint i = _::chooseBucket(hashCode, buckets.size());; i = _::probeHash(buckets, i)) {
jpayne@69 988 auto& bucket = buckets[i];
jpayne@69 989 if (bucket.isPos(oldPos)) {
jpayne@69 990 // found it
jpayne@69 991 bucket.setPos(newPos);
jpayne@69 992 return;
jpayne@69 993 } else if (bucket.isEmpty()) {
jpayne@69 994 // can't find the bucket, something is very wrong
jpayne@69 995 _::logHashTableInconsistency();
jpayne@69 996 return;
jpayne@69 997 }
jpayne@69 998 }
jpayne@69 999 }
jpayne@69 1000
jpayne@69 1001 template <typename Row, typename... Params>
jpayne@69 1002 Maybe<size_t> find(kj::ArrayPtr<Row> table, Params&&... params) const {
jpayne@69 1003 if (buckets.size() == 0) return nullptr;
jpayne@69 1004
jpayne@69 1005 uint hashCode = cb.hashCode(params...);
jpayne@69 1006 for (uint i = _::chooseBucket(hashCode, buckets.size());; i = _::probeHash(buckets, i)) {
jpayne@69 1007 auto& bucket = buckets[i];
jpayne@69 1008 if (bucket.isEmpty()) {
jpayne@69 1009 // not found.
jpayne@69 1010 return nullptr;
jpayne@69 1011 } else if (bucket.isErased()) {
jpayne@69 1012 // skip, keep searching
jpayne@69 1013 } else if (bucket.hash == hashCode &&
jpayne@69 1014 cb.matches(bucket.getRow(table), params...)) {
jpayne@69 1015 // found
jpayne@69 1016 return size_t(bucket.getPos());
jpayne@69 1017 }
jpayne@69 1018 }
jpayne@69 1019 }
jpayne@69 1020
jpayne@69 1021 // No begin() nor end() because hash tables are not usefully ordered.
jpayne@69 1022
jpayne@69 1023 private:
jpayne@69 1024 Callbacks cb;
jpayne@69 1025 size_t erasedCount = 0;
jpayne@69 1026 Array<_::HashBucket> buckets;
jpayne@69 1027
jpayne@69 1028 void rehash(size_t targetSize) {
jpayne@69 1029 buckets = _::rehash(buckets, targetSize);
jpayne@69 1030 erasedCount = 0;
jpayne@69 1031 }
jpayne@69 1032 };
jpayne@69 1033
jpayne@69 1034 // -----------------------------------------------------------------------------
jpayne@69 1035 // BTree index
jpayne@69 1036
jpayne@69 1037 namespace _ { // private
jpayne@69 1038
jpayne@69 1039 KJ_ALWAYS_INLINE(void compilerBarrier());
jpayne@69 1040 void compilerBarrier() {
jpayne@69 1041 // Make sure that reads occurring before this call cannot be re-ordered to happen after
jpayne@69 1042 // writes that occur after this call. We need this in a couple places below to prevent C++
jpayne@69 1043 // strict aliasing rules from breaking things.
jpayne@69 1044 #if _MSC_VER
jpayne@69 1045 _ReadWriteBarrier();
jpayne@69 1046 #else
jpayne@69 1047 __asm__ __volatile__("": : :"memory");
jpayne@69 1048 #endif
jpayne@69 1049 }
jpayne@69 1050
jpayne@69 1051 template <typename T>
jpayne@69 1052 inline void acopy(T* to, T* from, size_t size) { memcpy(to, from, size * sizeof(T)); }
jpayne@69 1053 template <typename T>
jpayne@69 1054 inline void amove(T* to, T* from, size_t size) { memmove(to, from, size * sizeof(T)); }
jpayne@69 1055 template <typename T>
jpayne@69 1056 inline void azero(T* ptr, size_t size) { memset(ptr, 0, size * sizeof(T)); }
jpayne@69 1057 // memcpy/memmove/memset variants that count size in elements, not bytes.
jpayne@69 1058 //
jpayne@69 1059 // TODO(cleanup): These are generally useful, put them somewhere.
jpayne@69 1060
jpayne@69 1061 class BTreeImpl {
jpayne@69 1062 public:
jpayne@69 1063 class Iterator;
jpayne@69 1064 class MaybeUint;
jpayne@69 1065 struct NodeUnion;
jpayne@69 1066 struct Leaf;
jpayne@69 1067 struct Parent;
jpayne@69 1068 struct Freelisted;
jpayne@69 1069
jpayne@69 1070 class SearchKey {
jpayne@69 1071 // Passed to methods that need to search the tree. This class allows most of the B-tree
jpayne@69 1072 // implementation to be kept out of templates, avoiding code bloat, at the cost of some
jpayne@69 1073 // performance trade-off. In order to lessen the performance cost of virtual calls, we design
jpayne@69 1074 // this interface so that it only needs to be called once per tree node, rather than once per
jpayne@69 1075 // comparison.
jpayne@69 1076
jpayne@69 1077 public:
jpayne@69 1078 virtual uint search(const Parent& parent) const = 0;
jpayne@69 1079 virtual uint search(const Leaf& leaf) const = 0;
jpayne@69 1080 // Binary search for the first key/row in the parent/leaf that is equal to or comes after the
jpayne@69 1081 // search key.
jpayne@69 1082
jpayne@69 1083 virtual bool isAfter(uint rowIndex) const = 0;
jpayne@69 1084 // Returns true if the key comes after the value in the given row.
jpayne@69 1085 };
jpayne@69 1086
jpayne@69 1087 BTreeImpl();
jpayne@69 1088 ~BTreeImpl() noexcept(false);
jpayne@69 1089
jpayne@69 1090 KJ_DISALLOW_COPY(BTreeImpl);
jpayne@69 1091 BTreeImpl(BTreeImpl&& other);
jpayne@69 1092 BTreeImpl& operator=(BTreeImpl&& other);
jpayne@69 1093
jpayne@69 1094 void logInconsistency() const;
jpayne@69 1095
jpayne@69 1096 void reserve(size_t size);
jpayne@69 1097
jpayne@69 1098 void clear();
jpayne@69 1099
jpayne@69 1100 Iterator begin() const;
jpayne@69 1101 Iterator end() const;
jpayne@69 1102
jpayne@69 1103 Iterator search(const SearchKey& searchKey) const;
jpayne@69 1104 // Find the "first" row (in sorted order) for which searchKey.isAfter(rowNumber) returns true.
jpayne@69 1105
jpayne@69 1106 Iterator insert(const SearchKey& searchKey);
jpayne@69 1107 // Like search() but ensures that there is room in the leaf node to insert a new row.
jpayne@69 1108
jpayne@69 1109 void erase(uint row, const SearchKey& searchKey);
jpayne@69 1110 // Erase the given row number from the tree. searchKey.isAfter() returns true for the given row
jpayne@69 1111 // and all rows after it.
jpayne@69 1112
jpayne@69 1113 void renumber(uint oldRow, uint newRow, const SearchKey& searchKey);
jpayne@69 1114 // Renumber the given row from oldRow to newRow. searchKey.isAfter() returns true for oldRow and
jpayne@69 1115 // all rows after it. (It will not be called on newRow.)
jpayne@69 1116
jpayne@69 1117 void verify(size_t size, FunctionParam<bool(uint, uint)>);
jpayne@69 1118
jpayne@69 1119 private:
jpayne@69 1120 NodeUnion* tree; // allocated with aligned_alloc aligned to cache lines
jpayne@69 1121 uint treeCapacity;
jpayne@69 1122 uint height; // height of *parent* tree -- does not include the leaf level
jpayne@69 1123 uint freelistHead;
jpayne@69 1124 uint freelistSize;
jpayne@69 1125 uint beginLeaf;
jpayne@69 1126 uint endLeaf;
jpayne@69 1127 void growTree(uint minCapacity = 0);
jpayne@69 1128
jpayne@69 1129 template <typename T>
jpayne@69 1130 struct AllocResult;
jpayne@69 1131
jpayne@69 1132 template <typename T>
jpayne@69 1133 inline AllocResult<T> alloc();
jpayne@69 1134 inline void free(uint pos);
jpayne@69 1135
jpayne@69 1136 inline uint split(Parent& src, uint srcPos, Parent& dst, uint dstPos);
jpayne@69 1137 inline uint split(Leaf& dst, uint dstPos, Leaf& src, uint srcPos);
jpayne@69 1138 inline void merge(Parent& dst, uint dstPos, uint pivot, Parent& src);
jpayne@69 1139 inline void merge(Leaf& dst, uint dstPos, uint pivot, Leaf& src);
jpayne@69 1140 inline void move(Parent& dst, uint dstPos, Parent& src);
jpayne@69 1141 inline void move(Leaf& dst, uint dstPos, Leaf& src);
jpayne@69 1142 inline void rotateLeft(
jpayne@69 1143 Parent& left, Parent& right, Parent& parent, uint indexInParent, MaybeUint*& fixup);
jpayne@69 1144 inline void rotateLeft(
jpayne@69 1145 Leaf& left, Leaf& right, Parent& parent, uint indexInParent, MaybeUint*& fixup);
jpayne@69 1146 inline void rotateRight(Parent& left, Parent& right, Parent& parent, uint indexInParent);
jpayne@69 1147 inline void rotateRight(Leaf& left, Leaf& right, Parent& parent, uint indexInParent);
jpayne@69 1148
jpayne@69 1149 template <typename Node>
jpayne@69 1150 inline Node& insertHelper(const SearchKey& searchKey,
jpayne@69 1151 Node& node, Parent* parent, uint indexInParent, uint pos);
jpayne@69 1152
jpayne@69 1153 template <typename Node>
jpayne@69 1154 inline Node& eraseHelper(
jpayne@69 1155 Node& node, Parent* parent, uint indexInParent, uint pos, MaybeUint*& fixup);
jpayne@69 1156
jpayne@69 1157 size_t verifyNode(size_t size, FunctionParam<bool(uint, uint)>&,
jpayne@69 1158 uint pos, uint height, MaybeUint maxRow);
jpayne@69 1159
jpayne@69 1160 static const NodeUnion EMPTY_NODE;
jpayne@69 1161 };
jpayne@69 1162
jpayne@69 1163 class BTreeImpl::MaybeUint {
jpayne@69 1164 // A nullable uint, using the value zero to mean null and shifting all other values up by 1.
jpayne@69 1165 public:
jpayne@69 1166 MaybeUint() = default;
jpayne@69 1167 inline MaybeUint(uint i): i(i - 1) {}
jpayne@69 1168 inline MaybeUint(decltype(nullptr)): i(0) {}
jpayne@69 1169
jpayne@69 1170 inline bool operator==(decltype(nullptr)) const { return i == 0; }
jpayne@69 1171 inline bool operator==(uint j) const { return i == j + 1; }
jpayne@69 1172 inline bool operator==(const MaybeUint& other) const { return i == other.i; }
jpayne@69 1173 inline bool operator!=(decltype(nullptr)) const { return i != 0; }
jpayne@69 1174 inline bool operator!=(uint j) const { return i != j + 1; }
jpayne@69 1175 inline bool operator!=(const MaybeUint& other) const { return i != other.i; }
jpayne@69 1176
jpayne@69 1177 inline MaybeUint& operator=(decltype(nullptr)) { i = 0; return *this; }
jpayne@69 1178 inline MaybeUint& operator=(uint j) { i = j + 1; return *this; }
jpayne@69 1179
jpayne@69 1180 inline uint operator*() const { KJ_TABLE_IREQUIRE(i != 0); return i - 1; }
jpayne@69 1181
jpayne@69 1182 template <typename Func>
jpayne@69 1183 inline bool check(Func& func) const { return i != 0 && func(i - 1); }
jpayne@69 1184 // Equivalent to *this != nullptr && func(**this)
jpayne@69 1185
jpayne@69 1186 kj::String toString() const;
jpayne@69 1187
jpayne@69 1188 private:
jpayne@69 1189 uint i;
jpayne@69 1190 };
jpayne@69 1191
jpayne@69 1192 struct BTreeImpl::Leaf {
jpayne@69 1193 uint next;
jpayne@69 1194 uint prev;
jpayne@69 1195 // Pointers to next and previous nodes at the same level, used for fast iteration.
jpayne@69 1196
jpayne@69 1197 static constexpr size_t NROWS = 14;
jpayne@69 1198 MaybeUint rows[NROWS];
jpayne@69 1199 // Pointers to table rows, offset by 1 so that 0 is an empty value.
jpayne@69 1200
jpayne@69 1201 inline bool isFull() const;
jpayne@69 1202 inline bool isMostlyFull() const;
jpayne@69 1203 inline bool isHalfFull() const;
jpayne@69 1204
jpayne@69 1205 inline void insert(uint i, uint newRow) {
jpayne@69 1206 KJ_TABLE_IREQUIRE(rows[Leaf::NROWS - 1] == nullptr); // check not full
jpayne@69 1207
jpayne@69 1208 amove(rows + i + 1, rows + i, Leaf::NROWS - (i + 1));
jpayne@69 1209 rows[i] = newRow;
jpayne@69 1210 }
jpayne@69 1211
jpayne@69 1212 inline void erase(uint i) {
jpayne@69 1213 KJ_TABLE_IREQUIRE(rows[0] != nullptr); // check not empty
jpayne@69 1214
jpayne@69 1215 amove(rows + i, rows + i + 1, Leaf::NROWS - (i + 1));
jpayne@69 1216 rows[Leaf::NROWS - 1] = nullptr;
jpayne@69 1217 }
jpayne@69 1218
jpayne@69 1219 inline uint size() const {
jpayne@69 1220 static_assert(Leaf::NROWS == 14, "logic here needs updating");
jpayne@69 1221
jpayne@69 1222 // Binary search for first empty element in `rows`, or return 14 if no empty elements. We do
jpayne@69 1223 // this in a branch-free manner. Since there are 15 possible results (0 through 14, inclusive),
jpayne@69 1224 // this isn't a perfectly balanced binary search. We carefully choose the split points so that
jpayne@69 1225 // there's no way we'll try to dereference row[14] or later (which would be a buffer overflow).
jpayne@69 1226 uint i = (rows[6] != nullptr) * 7;
jpayne@69 1227 i += (rows[i + 3] != nullptr) * 4;
jpayne@69 1228 i += (rows[i + 1] != nullptr) * 2;
jpayne@69 1229 i += (rows[i ] != nullptr);
jpayne@69 1230 return i;
jpayne@69 1231 }
jpayne@69 1232
jpayne@69 1233 template <typename Func>
jpayne@69 1234 inline uint binarySearch(Func& predicate) const {
jpayne@69 1235 // Binary search to find first row for which predicate(row) is false.
jpayne@69 1236
jpayne@69 1237 static_assert(Leaf::NROWS == 14, "logic here needs updating");
jpayne@69 1238
jpayne@69 1239 // See comments in size().
jpayne@69 1240 uint i = (rows[6].check(predicate)) * 7;
jpayne@69 1241 i += (rows[i + 3].check(predicate)) * 4;
jpayne@69 1242 i += (rows[i + 1].check(predicate)) * 2;
jpayne@69 1243 if (i != 6) { // don't redundantly check row 6
jpayne@69 1244 i += (rows[i ].check(predicate));
jpayne@69 1245 }
jpayne@69 1246 return i;
jpayne@69 1247 }
jpayne@69 1248 };
jpayne@69 1249
jpayne@69 1250 struct BTreeImpl::Parent {
jpayne@69 1251 uint unused;
jpayne@69 1252 // Not used. May be arbitrarily non-zero due to overlap with Freelisted::nextOffset.
jpayne@69 1253
jpayne@69 1254 static constexpr size_t NKEYS = 7;
jpayne@69 1255 MaybeUint keys[NKEYS];
jpayne@69 1256 // Pointers to table rows, offset by 1 so that 0 is an empty value.
jpayne@69 1257 //
jpayne@69 1258 // Each keys[i] specifies the table row which is the "last" row found under children[i].
jpayne@69 1259 //
jpayne@69 1260 // Note that `keys` has size 7 but `children` has size 8. `children[8]`'s "last row" is not
jpayne@69 1261 // recorded here, because the Parent's Parent records it instead. (Or maybe the Parent's Parent's
jpayne@69 1262 // Parent, if this Parent is `children[8]` of its own Parent. And so on.)
jpayne@69 1263
jpayne@69 1264 static constexpr size_t NCHILDREN = NKEYS + 1;
jpayne@69 1265 uint children[NCHILDREN];
jpayne@69 1266 // Pointers to children. Not offset because the root is always at position 0, and a pointer
jpayne@69 1267 // to the root would be nonsensical.
jpayne@69 1268
jpayne@69 1269 inline bool isFull() const;
jpayne@69 1270 inline bool isMostlyFull() const;
jpayne@69 1271 inline bool isHalfFull() const;
jpayne@69 1272 inline void initRoot(uint key, uint leftChild, uint rightChild);
jpayne@69 1273 inline void insertAfter(uint i, uint splitKey, uint child);
jpayne@69 1274 inline void eraseAfter(uint i);
jpayne@69 1275
jpayne@69 1276 inline uint keyCount() const {
jpayne@69 1277 static_assert(Parent::NKEYS == 7, "logic here needs updating");
jpayne@69 1278
jpayne@69 1279 // Binary search for first empty element in `keys`, or return 7 if no empty elements. We do
jpayne@69 1280 // this in a branch-free manner. Since there are 8 possible results (0 through 7, inclusive),
jpayne@69 1281 // this is a perfectly balanced binary search.
jpayne@69 1282 uint i = (keys[3] != nullptr) * 4;
jpayne@69 1283 i += (keys[i + 1] != nullptr) * 2;
jpayne@69 1284 i += (keys[i ] != nullptr);
jpayne@69 1285 return i;
jpayne@69 1286 }
jpayne@69 1287
jpayne@69 1288 template <typename Func>
jpayne@69 1289 inline uint binarySearch(Func& predicate) const {
jpayne@69 1290 // Binary search to find first key for which predicate(key) is false.
jpayne@69 1291
jpayne@69 1292 static_assert(Parent::NKEYS == 7, "logic here needs updating");
jpayne@69 1293
jpayne@69 1294 // See comments in size().
jpayne@69 1295 uint i = (keys[3].check(predicate)) * 4;
jpayne@69 1296 i += (keys[i + 1].check(predicate)) * 2;
jpayne@69 1297 i += (keys[i ].check(predicate));
jpayne@69 1298 return i;
jpayne@69 1299 }
jpayne@69 1300 };
jpayne@69 1301
jpayne@69 1302 struct BTreeImpl::Freelisted {
jpayne@69 1303 int nextOffset;
jpayne@69 1304 // The next node in the freelist is at: this + 1 + nextOffset
jpayne@69 1305 //
jpayne@69 1306 // Hence, newly-allocated space can initialize this to zero.
jpayne@69 1307
jpayne@69 1308 uint zero[15];
jpayne@69 1309 // Freelisted entries are always zero'd.
jpayne@69 1310 };
jpayne@69 1311
jpayne@69 1312 struct BTreeImpl::NodeUnion {
jpayne@69 1313 union {
jpayne@69 1314 Freelisted freelist;
jpayne@69 1315 // If this node is in the freelist.
jpayne@69 1316
jpayne@69 1317 Leaf leaf;
jpayne@69 1318 // If this node is a leaf.
jpayne@69 1319
jpayne@69 1320 Parent parent;
jpayne@69 1321 // If this node is not a leaf.
jpayne@69 1322 };
jpayne@69 1323
jpayne@69 1324 inline operator Leaf&() { return leaf; }
jpayne@69 1325 inline operator Parent&() { return parent; }
jpayne@69 1326 inline operator const Leaf&() const { return leaf; }
jpayne@69 1327 inline operator const Parent&() const { return parent; }
jpayne@69 1328 };
jpayne@69 1329
jpayne@69 1330 static_assert(sizeof(BTreeImpl::Parent) == 64,
jpayne@69 1331 "BTreeImpl::Parent should be optimized to fit a cache line");
jpayne@69 1332 static_assert(sizeof(BTreeImpl::Leaf) == 64,
jpayne@69 1333 "BTreeImpl::Leaf should be optimized to fit a cache line");
jpayne@69 1334 static_assert(sizeof(BTreeImpl::Freelisted) == 64,
jpayne@69 1335 "BTreeImpl::Freelisted should be optimized to fit a cache line");
jpayne@69 1336 static_assert(sizeof(BTreeImpl::NodeUnion) == 64,
jpayne@69 1337 "BTreeImpl::NodeUnion should be optimized to fit a cache line");
jpayne@69 1338
jpayne@69 1339 bool BTreeImpl::Leaf::isFull() const {
jpayne@69 1340 return rows[Leaf::NROWS - 1] != nullptr;
jpayne@69 1341 }
jpayne@69 1342 bool BTreeImpl::Leaf::isMostlyFull() const {
jpayne@69 1343 return rows[Leaf::NROWS / 2] != nullptr;
jpayne@69 1344 }
jpayne@69 1345 bool BTreeImpl::Leaf::isHalfFull() const {
jpayne@69 1346 KJ_TABLE_IASSERT(rows[Leaf::NROWS / 2 - 1] != nullptr);
jpayne@69 1347 return rows[Leaf::NROWS / 2] == nullptr;
jpayne@69 1348 }
jpayne@69 1349
jpayne@69 1350 bool BTreeImpl::Parent::isFull() const {
jpayne@69 1351 return keys[Parent::NKEYS - 1] != nullptr;
jpayne@69 1352 }
jpayne@69 1353 bool BTreeImpl::Parent::isMostlyFull() const {
jpayne@69 1354 return keys[Parent::NKEYS / 2] != nullptr;
jpayne@69 1355 }
jpayne@69 1356 bool BTreeImpl::Parent::isHalfFull() const {
jpayne@69 1357 KJ_TABLE_IASSERT(keys[Parent::NKEYS / 2 - 1] != nullptr);
jpayne@69 1358 return keys[Parent::NKEYS / 2] == nullptr;
jpayne@69 1359 }
jpayne@69 1360
jpayne@69 1361 class BTreeImpl::Iterator {
jpayne@69 1362 public:
jpayne@69 1363 Iterator(const NodeUnion* tree, const Leaf* leaf, uint row)
jpayne@69 1364 : tree(tree), leaf(leaf), row(row) {}
jpayne@69 1365
jpayne@69 1366 size_t operator*() const {
jpayne@69 1367 KJ_TABLE_IREQUIRE(row < Leaf::NROWS && leaf->rows[row] != nullptr,
jpayne@69 1368 "tried to dereference end() iterator");
jpayne@69 1369 return *leaf->rows[row];
jpayne@69 1370 }
jpayne@69 1371
jpayne@69 1372 inline Iterator& operator++() {
jpayne@69 1373 KJ_TABLE_IREQUIRE(leaf->rows[row] != nullptr, "B-tree iterator overflow");
jpayne@69 1374 ++row;
jpayne@69 1375 if (row >= Leaf::NROWS || leaf->rows[row] == nullptr) {
jpayne@69 1376 if (leaf->next == 0) {
jpayne@69 1377 // at end; stay on current leaf
jpayne@69 1378 } else {
jpayne@69 1379 leaf = &tree[leaf->next].leaf;
jpayne@69 1380 row = 0;
jpayne@69 1381 }
jpayne@69 1382 }
jpayne@69 1383 return *this;
jpayne@69 1384 }
jpayne@69 1385 inline Iterator operator++(int) {
jpayne@69 1386 Iterator other = *this;
jpayne@69 1387 ++*this;
jpayne@69 1388 return other;
jpayne@69 1389 }
jpayne@69 1390
jpayne@69 1391 inline Iterator& operator--() {
jpayne@69 1392 if (row == 0) {
jpayne@69 1393 KJ_TABLE_IREQUIRE(leaf->prev != 0, "B-tree iterator underflow");
jpayne@69 1394 leaf = &tree[leaf->prev].leaf;
jpayne@69 1395 row = leaf->size() - 1;
jpayne@69 1396 } else {
jpayne@69 1397 --row;
jpayne@69 1398 }
jpayne@69 1399 return *this;
jpayne@69 1400 }
jpayne@69 1401 inline Iterator operator--(int) {
jpayne@69 1402 Iterator other = *this;
jpayne@69 1403 --*this;
jpayne@69 1404 return other;
jpayne@69 1405 }
jpayne@69 1406
jpayne@69 1407 inline bool operator==(const Iterator& other) const {
jpayne@69 1408 return leaf == other.leaf && row == other.row;
jpayne@69 1409 }
jpayne@69 1410 inline bool operator!=(const Iterator& other) const {
jpayne@69 1411 return leaf != other.leaf || row != other.row;
jpayne@69 1412 }
jpayne@69 1413
jpayne@69 1414 bool isEnd() {
jpayne@69 1415 return row == Leaf::NROWS || leaf->rows[row] == nullptr;
jpayne@69 1416 }
jpayne@69 1417
jpayne@69 1418 void insert(BTreeImpl& impl, uint newRow) {
jpayne@69 1419 KJ_TABLE_IASSERT(impl.tree == tree);
jpayne@69 1420 const_cast<Leaf*>(leaf)->insert(row, newRow);
jpayne@69 1421 }
jpayne@69 1422
jpayne@69 1423 void erase(BTreeImpl& impl) {
jpayne@69 1424 KJ_TABLE_IASSERT(impl.tree == tree);
jpayne@69 1425 const_cast<Leaf*>(leaf)->erase(row);
jpayne@69 1426 }
jpayne@69 1427
jpayne@69 1428 void replace(BTreeImpl& impl, uint newRow) {
jpayne@69 1429 KJ_TABLE_IASSERT(impl.tree == tree);
jpayne@69 1430 const_cast<Leaf*>(leaf)->rows[row] = newRow;
jpayne@69 1431 }
jpayne@69 1432
jpayne@69 1433 private:
jpayne@69 1434 const NodeUnion* tree;
jpayne@69 1435 const Leaf* leaf;
jpayne@69 1436 uint row;
jpayne@69 1437 };
jpayne@69 1438
jpayne@69 1439 inline BTreeImpl::Iterator BTreeImpl::begin() const {
jpayne@69 1440 return { tree, &tree[beginLeaf].leaf, 0 };
jpayne@69 1441 }
jpayne@69 1442 inline BTreeImpl::Iterator BTreeImpl::end() const {
jpayne@69 1443 auto& leaf = tree[endLeaf].leaf;
jpayne@69 1444 return { tree, &leaf, leaf.size() };
jpayne@69 1445 }
jpayne@69 1446
jpayne@69 1447 } // namespace _ (private)
jpayne@69 1448
jpayne@69 1449 template <typename Callbacks>
jpayne@69 1450 class TreeIndex {
jpayne@69 1451 public:
jpayne@69 1452 TreeIndex() = default;
jpayne@69 1453 template <typename... Params>
jpayne@69 1454 TreeIndex(Params&&... params): cb(kj::fwd<Params>(params)...) {}
jpayne@69 1455
jpayne@69 1456 template <typename Row>
jpayne@69 1457 void verify(kj::ArrayPtr<Row> table) {
jpayne@69 1458 impl.verify(table.size(), [&](uint i, uint j) {
jpayne@69 1459 return cb.isBefore(table[i], table[j]);
jpayne@69 1460 });
jpayne@69 1461 }
jpayne@69 1462
jpayne@69 1463 inline void reserve(size_t size) { impl.reserve(size); }
jpayne@69 1464 inline void clear() { impl.clear(); }
jpayne@69 1465 inline auto begin() const { return impl.begin(); }
jpayne@69 1466 inline auto end() const { return impl.end(); }
jpayne@69 1467
jpayne@69 1468 template <typename Row>
jpayne@69 1469 decltype(auto) keyForRow(Row&& row) const {
jpayne@69 1470 return cb.keyForRow(kj::fwd<Row>(row));
jpayne@69 1471 }
jpayne@69 1472
jpayne@69 1473 template <typename Row, typename... Params>
jpayne@69 1474 kj::Maybe<size_t> insert(kj::ArrayPtr<Row> table, size_t pos, Params&&... params) {
jpayne@69 1475 auto iter = impl.insert(searchKey(table, params...));
jpayne@69 1476
jpayne@69 1477 if (!iter.isEnd() && cb.matches(table[*iter], params...)) {
jpayne@69 1478 return *iter;
jpayne@69 1479 } else {
jpayne@69 1480 iter.insert(impl, pos);
jpayne@69 1481 return nullptr;
jpayne@69 1482 }
jpayne@69 1483 }
jpayne@69 1484
jpayne@69 1485 template <typename Row, typename... Params>
jpayne@69 1486 void erase(kj::ArrayPtr<Row> table, size_t pos, Params&&... params) {
jpayne@69 1487 impl.erase(pos, searchKeyForErase(table, pos, params...));
jpayne@69 1488 }
jpayne@69 1489
jpayne@69 1490 template <typename Row, typename... Params>
jpayne@69 1491 void move(kj::ArrayPtr<Row> table, size_t oldPos, size_t newPos, Params&&... params) {
jpayne@69 1492 impl.renumber(oldPos, newPos, searchKey(table, params...));
jpayne@69 1493 }
jpayne@69 1494
jpayne@69 1495 template <typename Row, typename... Params>
jpayne@69 1496 Maybe<size_t> find(kj::ArrayPtr<Row> table, Params&&... params) const {
jpayne@69 1497 auto iter = impl.search(searchKey(table, params...));
jpayne@69 1498
jpayne@69 1499 if (!iter.isEnd() && cb.matches(table[*iter], params...)) {
jpayne@69 1500 return size_t(*iter);
jpayne@69 1501 } else {
jpayne@69 1502 return nullptr;
jpayne@69 1503 }
jpayne@69 1504 }
jpayne@69 1505
jpayne@69 1506 template <typename Row, typename... Params>
jpayne@69 1507 _::BTreeImpl::Iterator seek(kj::ArrayPtr<Row> table, Params&&... params) const {
jpayne@69 1508 return impl.search(searchKey(table, params...));
jpayne@69 1509 }
jpayne@69 1510
jpayne@69 1511 private:
jpayne@69 1512 Callbacks cb;
jpayne@69 1513 _::BTreeImpl impl;
jpayne@69 1514
jpayne@69 1515 template <typename Predicate>
jpayne@69 1516 class SearchKeyImpl: public _::BTreeImpl::SearchKey {
jpayne@69 1517 public:
jpayne@69 1518 SearchKeyImpl(Predicate&& predicate)
jpayne@69 1519 : predicate(kj::mv(predicate)) {}
jpayne@69 1520
jpayne@69 1521 uint search(const _::BTreeImpl::Parent& parent) const override {
jpayne@69 1522 return parent.binarySearch(predicate);
jpayne@69 1523 }
jpayne@69 1524 uint search(const _::BTreeImpl::Leaf& leaf) const override {
jpayne@69 1525 return leaf.binarySearch(predicate);
jpayne@69 1526 }
jpayne@69 1527 bool isAfter(uint rowIndex) const override {
jpayne@69 1528 return predicate(rowIndex);
jpayne@69 1529 }
jpayne@69 1530
jpayne@69 1531 private:
jpayne@69 1532 Predicate predicate;
jpayne@69 1533 };
jpayne@69 1534
jpayne@69 1535 template <typename Row, typename... Params>
jpayne@69 1536 inline auto searchKey(kj::ArrayPtr<Row>& table, Params&... params) const {
jpayne@69 1537 auto predicate = [&](uint i) { return cb.isBefore(table[i], params...); };
jpayne@69 1538 return SearchKeyImpl<decltype(predicate)>(kj::mv(predicate));
jpayne@69 1539 }
jpayne@69 1540
jpayne@69 1541 template <typename Row, typename... Params>
jpayne@69 1542 inline auto searchKeyForErase(kj::ArrayPtr<Row>& table, uint pos, Params&... params) const {
jpayne@69 1543 // When erasing, the table entry for the erased row may already be invalid, so we must avoid
jpayne@69 1544 // accessing it.
jpayne@69 1545 auto predicate = [&,pos](uint i) {
jpayne@69 1546 return i != pos && cb.isBefore(table[i], params...);
jpayne@69 1547 };
jpayne@69 1548 return SearchKeyImpl<decltype(predicate)>(kj::mv(predicate));
jpayne@69 1549 }
jpayne@69 1550 };
jpayne@69 1551
jpayne@69 1552 // -----------------------------------------------------------------------------
jpayne@69 1553 // Insertion order index
jpayne@69 1554
jpayne@69 1555 class InsertionOrderIndex {
jpayne@69 1556 // Table index which allows iterating over elements in order of insertion. This index cannot
jpayne@69 1557 // be used for Table::find(), but can be used for Table::ordered().
jpayne@69 1558
jpayne@69 1559 struct Link;
jpayne@69 1560 public:
jpayne@69 1561 InsertionOrderIndex();
jpayne@69 1562 InsertionOrderIndex(const InsertionOrderIndex&) = delete;
jpayne@69 1563 InsertionOrderIndex& operator=(const InsertionOrderIndex&) = delete;
jpayne@69 1564 InsertionOrderIndex(InsertionOrderIndex&& other);
jpayne@69 1565 InsertionOrderIndex& operator=(InsertionOrderIndex&& other);
jpayne@69 1566 ~InsertionOrderIndex() noexcept(false);
jpayne@69 1567
jpayne@69 1568 class Iterator {
jpayne@69 1569 public:
jpayne@69 1570 Iterator(const Link* links, uint pos)
jpayne@69 1571 : links(links), pos(pos) {}
jpayne@69 1572
jpayne@69 1573 inline size_t operator*() const {
jpayne@69 1574 KJ_TABLE_IREQUIRE(pos != 0, "can't dereference end() iterator");
jpayne@69 1575 return pos - 1;
jpayne@69 1576 };
jpayne@69 1577
jpayne@69 1578 inline Iterator& operator++() {
jpayne@69 1579 pos = links[pos].next;
jpayne@69 1580 return *this;
jpayne@69 1581 }
jpayne@69 1582 inline Iterator operator++(int) {
jpayne@69 1583 Iterator result = *this;
jpayne@69 1584 ++*this;
jpayne@69 1585 return result;
jpayne@69 1586 }
jpayne@69 1587 inline Iterator& operator--() {
jpayne@69 1588 pos = links[pos].prev;
jpayne@69 1589 return *this;
jpayne@69 1590 }
jpayne@69 1591 inline Iterator operator--(int) {
jpayne@69 1592 Iterator result = *this;
jpayne@69 1593 --*this;
jpayne@69 1594 return result;
jpayne@69 1595 }
jpayne@69 1596
jpayne@69 1597 inline bool operator==(const Iterator& other) const {
jpayne@69 1598 return pos == other.pos;
jpayne@69 1599 }
jpayne@69 1600 inline bool operator!=(const Iterator& other) const {
jpayne@69 1601 return pos != other.pos;
jpayne@69 1602 }
jpayne@69 1603
jpayne@69 1604 private:
jpayne@69 1605 const Link* links;
jpayne@69 1606 uint pos;
jpayne@69 1607 };
jpayne@69 1608
jpayne@69 1609 template <typename Row>
jpayne@69 1610 Row& keyForRow(Row& row) const { return row; }
jpayne@69 1611
jpayne@69 1612 void reserve(size_t size);
jpayne@69 1613 void clear();
jpayne@69 1614 inline Iterator begin() const { return Iterator(links, links[0].next); }
jpayne@69 1615 inline Iterator end() const { return Iterator(links, 0); }
jpayne@69 1616
jpayne@69 1617 template <typename Row>
jpayne@69 1618 kj::Maybe<size_t> insert(kj::ArrayPtr<Row> table, size_t pos, const Row& row) {
jpayne@69 1619 return insertImpl(pos);
jpayne@69 1620 }
jpayne@69 1621
jpayne@69 1622 template <typename Row>
jpayne@69 1623 void erase(kj::ArrayPtr<Row> table, size_t pos, const Row& row) {
jpayne@69 1624 eraseImpl(pos);
jpayne@69 1625 }
jpayne@69 1626
jpayne@69 1627 template <typename Row>
jpayne@69 1628 void move(kj::ArrayPtr<Row> table, size_t oldPos, size_t newPos, const Row& row) {
jpayne@69 1629 return moveImpl(oldPos, newPos);
jpayne@69 1630 }
jpayne@69 1631
jpayne@69 1632 private:
jpayne@69 1633 struct Link {
jpayne@69 1634 uint next;
jpayne@69 1635 uint prev;
jpayne@69 1636 };
jpayne@69 1637
jpayne@69 1638 uint capacity;
jpayne@69 1639 Link* links;
jpayne@69 1640 // links[0] is special: links[0].next points to the first link, links[0].prev points to the last.
jpayne@69 1641 // links[n+1] corresponds to row n.
jpayne@69 1642
jpayne@69 1643 kj::Maybe<size_t> insertImpl(size_t pos);
jpayne@69 1644 void eraseImpl(size_t pos);
jpayne@69 1645 void moveImpl(size_t oldPos, size_t newPos);
jpayne@69 1646
jpayne@69 1647 static const Link EMPTY_LINK;
jpayne@69 1648 };
jpayne@69 1649
jpayne@69 1650 } // namespace kj
jpayne@69 1651
jpayne@69 1652 KJ_END_HEADER