Lines Matching defs:Cell
57 cells_(static_cast<Cell*>(
58 AllocateGuardedVirtualMemory(num_cells_ * sizeof(Cell)))),
65 FreeGuardedVirtualMemory(cells_, num_cells_ * sizeof(Cell));
70 Cell** p_cell = Lookup(key);
71 Cell* cell = *p_cell;
72 if (cell) {
73 return {static_cast<KVIndex>(cell - cells_), false}; // not inserted
76 // Get a free cell and link it.
77 *p_cell = cell = GetFreeCell();
78 cell->p_prev = p_cell;
79 cell->next = nullptr;
83 new (&cell->kv) KVPair(key, value);
85 return {static_cast<KVIndex>(cell - cells_), true}; // inserted
91 Cell* cell = &cells_[index];
93 // Unlink the cell.
94 *cell->p_prev = cell->next;
95 if (cell->next) {
96 cell->next->p_prev = cell->p_prev;
98 cell->p_prev = nullptr; // mark as free
101 cell->next = free_list_;
102 free_list_ = cell;
106 Cell* cell = *Lookup(key);
107 return cell ? static_cast<KVIndex>(cell - cells_) : kInvalidKVIndex;
134 // |next_unused_cell_| is the first cell that wasn't touched, i.e.
136 return bits::Align(sizeof(Cell) * next_unused_cell_, page_size) +
143 struct Cell {
145 Cell* next;
148 // also participate in the bucket's cell list - they point to the list's
150 // cases uniformly, instead of |prev| we're storing "pointer to a Cell*
151 // that points to this Cell" kind of thing. So |p_prev| points to a bucket
152 // for the first cell in a list, and points to |next| of the previous cell
153 // for any other cell. With that Lookup() is the only function that handles
155 // If |p_prev| is nullptr, the cell is in the free list.
156 Cell** p_prev;
159 using Bucket = Cell*;
161 // Returns a pointer to the cell that contains or should contain the entry
164 Cell** Lookup(const Key& key) const {
166 Cell** p_cell = &buckets_[Hash(key)];
168 // Chase down the list until the cell that holds |key| is found,
177 // Returns a cell that is not being used to store an entry (either by
178 // recycling from the free list or by taking a fresh cell).
179 Cell* GetFreeCell() {
180 // First try to re-use a cell from the free list.
182 Cell* cell = free_list_;
183 free_list_ = cell->next;
184 return cell;
187 // Otherwise pick the next cell that has not been touched before.
223 Cell* const cells_;
231 Cell* free_list_;
234 // If the free list is empty and a new cell is needed, the cell at this index
