MB-24055: Reduce HashTable::defaultNumBuckets from 1531 to 3
[ep-engine.git] / src / hash_table.cc
1 /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /*
3  *     Copyright 2016 Couchbase, Inc
4  *
5  *   Licensed under the Apache License, Version 2.0 (the "License");
6  *   you may not use this file except in compliance with the License.
7  *   You may obtain a copy of the License at
8  *
9  *       http://www.apache.org/licenses/LICENSE-2.0
10  *
11  *   Unless required by applicable law or agreed to in writing, software
12  *   distributed under the License is distributed on an "AS IS" BASIS,
13  *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14  *   See the License for the specific language governing permissions and
15  *   limitations under the License.
16  */
17
18 #include "hash_table.h"
19
20 #include "stored_value_factories.h"
21
22 #include <cstring>
23
24 // Given we default to 1024 vBuckets, set default HT buckets to lowest
25 // prime in our table - this still gives space for 3072 HT slots but
26 // minimizes fixed overheads.
27 size_t HashTable::defaultNumBuckets = 3;
28 size_t HashTable::defaultNumLocks = 193;
29
30 static ssize_t prime_size_table[] = {
31     3, 7, 13, 23, 47, 97, 193, 383, 769, 1531, 3079, 6143, 12289, 24571, 49157,
32     98299, 196613, 393209, 786433, 1572869, 3145721, 6291449, 12582917,
33     25165813, 50331653, 100663291, 201326611, 402653189, 805306357,
34     1610612741, -1
35 };
36
37
38 std::ostream& operator<<(std::ostream& os, const HashTable::Position& pos) {
39     os << "{lock:" << pos.lock << " bucket:" << pos.hash_bucket << "/" << pos.ht_size << "}";
40     return os;
41 }
42
43 HashTable::HashTable(EPStats& st,
44                      std::unique_ptr<AbstractStoredValueFactory> svFactory,
45                      size_t s, size_t l)
46     : maxDeletedRevSeqno(0),
47       numTotalItems(0),
48       numNonResidentItems(0),
49       numDeletedItems(0),
50       datatypeCounts(),
51       numEjects(0),
52       memSize(0),
53       cacheSize(0),
54       metaDataMemory(0),
55       stats(st),
56       valFact(std::move(svFactory)),
57       visitors(0),
58       numItems(0),
59       numResizes(0),
60       numTempItems(0) {
61     size = HashTable::getNumBuckets(s);
62     n_locks = HashTable::getNumLocks(l);
63     values.resize(size);
64     mutexes = new std::mutex[n_locks];
65     activeState = true;
66 }
67
68 HashTable::~HashTable() {
69     clear(true);
70     // Wait for any outstanding visitors to finish.
71     while (visitors > 0) {
72 #ifdef _MSC_VER
73         Sleep(1);
74 #else
75         usleep(100);
76 #endif
77     }
78     delete []mutexes;
79 }
80
81 void HashTable::clear(bool deactivate) {
82     if (!deactivate) {
83         // If not deactivating, assert we're already active.
84         if (!isActive()) {
85             throw std::logic_error("HashTable::clear: Cannot call on a "
86                     "non-active object");
87         }
88     }
89     MultiLockHolder mlh(mutexes, n_locks);
90     if (deactivate) {
91         setActiveState(false);
92     }
93     size_t clearedMemSize = 0;
94     size_t clearedValSize = 0;
95     for (int i = 0; i < (int)size; i++) {
96         while (values[i]) {
97             // Take ownership of the StoredValue from the vector, update
98             // statistics and release it.
99             auto v = std::move(values[i]);
100             clearedMemSize += v->size();
101             clearedValSize += v->valuelen();
102             values[i] = std::move(v->next);
103         }
104     }
105
106     stats.currentSize.fetch_sub(clearedMemSize - clearedValSize);
107
108     datatypeCounts.fill(0);
109     numTotalItems.store(0);
110     numItems.store(0);
111     numTempItems.store(0);
112     numNonResidentItems.store(0);
113     memSize.store(0);
114     cacheSize.store(0);
115 }
116
117 static size_t distance(size_t a, size_t b) {
118     return std::max(a, b) - std::min(a, b);
119 }
120
121 static size_t nearest(size_t n, size_t a, size_t b) {
122     return (distance(n, a) < distance(b, n)) ? a : b;
123 }
124
125 static bool isCurrently(size_t size, ssize_t a, ssize_t b) {
126     ssize_t current(static_cast<ssize_t>(size));
127     return (current == a || current == b);
128 }
129
130 void HashTable::resize() {
131     size_t ni = getNumInMemoryItems();
132     int i(0);
133     size_t new_size(0);
134
135     // Figure out where in the prime table we are.
136     ssize_t target(static_cast<ssize_t>(ni));
137     for (i = 0; prime_size_table[i] > 0 && prime_size_table[i] < target; ++i) {
138         // Just looking...
139     }
140
141     if (prime_size_table[i] == -1) {
142         // We're at the end, take the biggest
143         new_size = prime_size_table[i-1];
144     } else if (prime_size_table[i] < static_cast<ssize_t>(defaultNumBuckets)) {
145         // Was going to be smaller than the configured ht_size.
146         new_size = defaultNumBuckets;
147     } else if (0 == i) {
148         new_size = prime_size_table[i];
149     }else if (isCurrently(size, prime_size_table[i-1], prime_size_table[i])) {
150         // If one of the candidate sizes is the current size, maintain
151         // the current size in order to remain stable.
152         new_size = size;
153     } else {
154         // Somewhere in the middle, use the one we're closer to.
155         new_size = nearest(ni, prime_size_table[i-1], prime_size_table[i]);
156     }
157
158     resize(new_size);
159 }
160
161 void HashTable::resize(size_t newSize) {
162     if (!isActive()) {
163         throw std::logic_error("HashTable::resize: Cannot call on a "
164                 "non-active object");
165     }
166
167     // Due to the way hashing works, we can't fit anything larger than
168     // an int.
169     if (newSize > static_cast<size_t>(std::numeric_limits<int>::max())) {
170         return;
171     }
172
173     // Don't resize to the same size, either.
174     if (newSize == size) {
175         return;
176     }
177
178     MultiLockHolder mlh(mutexes, n_locks);
179     if (visitors.load() > 0) {
180         // Do not allow a resize while any visitors are actually
181         // processing.  The next attempt will have to pick it up.  New
182         // visitors cannot start doing meaningful work (we own all
183         // locks at this point).
184         return;
185     }
186
187     // Get a place for the new items.
188     table_type newValues(newSize);
189
190     stats.memOverhead->fetch_sub(memorySize());
191     ++numResizes;
192
193     // Set the new size so all the hashy stuff works.
194     size_t oldSize = size;
195     size.store(newSize);
196
197     // Move existing records into the new space.
198     for (size_t i = 0; i < oldSize; i++) {
199         while (values[i]) {
200             // unlink the front element from the hash chain at values[i].
201             auto v = std::move(values[i]);
202             values[i] = std::move(v->next);
203
204             // And re-link it into the correct place in newValues.
205             int newBucket = getBucketForHash(v->getKey().hash());
206             v->next = std::move(newValues[newBucket]);
207             newValues[newBucket] = std::move(v);
208         }
209     }
210
211     // Finally assign the new table to values.
212     values = std::move(newValues);
213
214     stats.memOverhead->fetch_add(memorySize());
215 }
216
217 StoredValue* HashTable::find(const DocKey& key,
218                              TrackReference trackReference,
219                              WantsDeleted wantsDeleted) {
220     if (!isActive()) {
221         throw std::logic_error("HashTable::find: Cannot call on a "
222                 "non-active object");
223     }
224     HashBucketLock hbl = getLockedBucket(key);
225     return unlocked_find(key, hbl.getBucketNum(), wantsDeleted, trackReference);
226 }
227
228 std::unique_ptr<Item> HashTable::getRandomKey(long rnd) {
229     /* Try to locate a partition */
230     size_t start = rnd % size;
231     size_t curr = start;
232     std::unique_ptr<Item> ret;
233
234     do {
235         ret = getRandomKeyFromSlot(curr++);
236         if (curr == size) {
237             curr = 0;
238         }
239     } while (ret == NULL && curr != start);
240
241     return ret;
242 }
243
244 MutationStatus HashTable::set(Item& val) {
245     if (!StoredValue::hasAvailableSpace(stats, val, false)) {
246         return MutationStatus::NoMem;
247     }
248
249     HashBucketLock hbl = getLockedBucket(val.getKey());
250     StoredValue* v = unlocked_find(val.getKey(),
251                                    hbl.getBucketNum(),
252                                    WantsDeleted::Yes,
253                                    TrackReference::No);
254     if (v) {
255         return unlocked_updateStoredValue(hbl.getHTLock(), *v, val);
256     } else {
257         unlocked_addNewStoredValue(hbl, val);
258         return MutationStatus::WasClean;
259     }
260 }
261
262 MutationStatus HashTable::unlocked_updateStoredValue(
263         const std::unique_lock<std::mutex>& htLock,
264         StoredValue& v,
265         const Item& itm) {
266     if (!htLock) {
267         throw std::invalid_argument(
268                 "HashTable::unlocked_updateStoredValue: htLock "
269                 "not held");
270     }
271
272     if (!isActive()) {
273         throw std::logic_error(
274                 "HashTable::unlocked_updateStoredValue: Cannot "
275                 "call on a non-active HT object");
276     }
277
278     MutationStatus status =
279             v.isDirty() ? MutationStatus::WasDirty : MutationStatus::WasClean;
280     if (!v.isResident() && !v.isDeleted() && !v.isTempItem()) {
281         decrNumNonResidentItems();
282     }
283
284     if (v.isTempItem()) {
285         --numTempItems;
286         ++numItems;
287         ++numTotalItems;
288     }
289
290     if (v.isDeleted() && !itm.isDeleted()) {
291         --numDeletedItems;
292     }
293     if (!v.isDeleted() && itm.isDeleted()) {
294         ++numDeletedItems;
295     }
296
297     // If the item we are replacing is resident then we need to make sure we
298     // appropriately alter the datatype stats.
299     if (v.getDatatype() != itm.getDataType()) {
300         --datatypeCounts[v.getDatatype()];
301         ++datatypeCounts[itm.getDataType()];
302     }
303
304     /* setValue() will mark v as undeleted if required */
305     v.setValue(itm, *this);
306     return status;
307 }
308
309 StoredValue* HashTable::unlocked_addNewStoredValue(const HashBucketLock& hbl,
310                                                    const Item& itm) {
311     if (!hbl.getHTLock()) {
312         throw std::invalid_argument(
313                 "HashTable::unlocked_addNewStoredValue: htLock "
314                 "not held");
315     }
316
317     if (!isActive()) {
318         throw std::invalid_argument(
319                 "HashTable::unlocked_addNewStoredValue: Cannot "
320                 "call on a non-active HT object");
321     }
322
323     // Create a new StoredValue and link it into the head of the bucket chain.
324     auto v = (*valFact)(itm, std::move(values[hbl.getBucketNum()]), *this);
325     if (v->isTempItem()) {
326         ++numTempItems;
327     } else {
328         ++numItems;
329         ++numTotalItems;
330         ++datatypeCounts[v->getDatatype()];
331     }
332     if (v->isDeleted()) {
333         ++numDeletedItems;
334     }
335     values[hbl.getBucketNum()] = std::move(v);
336
337     return values[hbl.getBucketNum()].get();
338 }
339
340 std::pair<StoredValue*, StoredValue::UniquePtr>
341 HashTable::unlocked_replaceByCopy(const HashBucketLock& hbl,
342                                   const StoredValue& vToCopy) {
343     if (!hbl.getHTLock()) {
344         throw std::invalid_argument(
345                 "HashTable::unlocked_replaceByCopy: htLock "
346                 "not held");
347     }
348
349     if (!isActive()) {
350         throw std::invalid_argument(
351                 "HashTable::unlocked_replaceByCopy: Cannot "
352                 "call on a non-active HT object");
353     }
354
355     /* Release (remove) the StoredValue from the hash table */
356     auto releasedSv = unlocked_release(hbl, vToCopy.getKey());
357
358     /* Copy the StoredValue and link it into the head of the bucket chain. */
359     auto newSv = valFact->copyStoredValue(
360             vToCopy, std::move(values[hbl.getBucketNum()]), *this);
361     if (newSv->isTempItem()) {
362         ++numTempItems;
363     } else {
364         ++numItems;
365         ++numTotalItems;
366     }
367     values[hbl.getBucketNum()] = std::move(newSv);
368
369     return {values[hbl.getBucketNum()].get(), std::move(releasedSv)};
370 }
371
372 void HashTable::unlocked_softDelete(const std::unique_lock<std::mutex>& htLock,
373                                     StoredValue& v,
374                                     bool onlyMarkDeleted) {
375     const bool alreadyDeleted = v.isDeleted();
376     if (!v.isResident() && !v.isDeleted() && !v.isTempItem()) {
377         decrNumNonResidentItems();
378     }
379
380     --datatypeCounts[v.getDatatype()];
381
382     if (onlyMarkDeleted) {
383         v.markDeleted();
384     } else {
385         if (v.isTempItem()) {
386             --numTempItems;
387             ++numItems;
388             ++numTotalItems;
389         }
390         v.del(*this);
391     }
392     if (!alreadyDeleted) {
393         ++numDeletedItems;
394     }
395 }
396
397 StoredValue* HashTable::unlocked_find(const DocKey& key,
398                                       int bucket_num,
399                                       WantsDeleted wantsDeleted,
400                                       TrackReference trackReference) {
401     for (StoredValue* v = values[bucket_num].get(); v; v = v->next.get()) {
402         if (v->hasKey(key)) {
403             if (trackReference == TrackReference::Yes && !v->isDeleted()) {
404                 v->referenced();
405             }
406             if (wantsDeleted == WantsDeleted::Yes || !v->isDeleted()) {
407                 return v;
408             } else {
409                 return NULL;
410             }
411         }
412     }
413     return NULL;
414 }
415
416 void HashTable::unlocked_del(const HashBucketLock& hbl, const DocKey& key) {
417     unlocked_release(hbl, key).reset();
418 }
419
420 StoredValue::UniquePtr HashTable::unlocked_release(
421         const HashBucketLock& hbl, const DocKey& key) {
422     if (!hbl.getHTLock()) {
423         throw std::invalid_argument(
424                 "HashTable::unlocked_remove: htLock "
425                 "not held");
426     }
427
428     if (!isActive()) {
429         throw std::logic_error(
430                 "HashTable::unlocked_remove: Cannot call on a "
431                 "non-active object");
432     }
433
434     // Remove the first (should only be one) StoredValue with the given key.
435     auto released = hashChainRemoveFirst(
436             values[hbl.getBucketNum()],
437             [key](const StoredValue* v) { return v->hasKey(key); });
438
439     if (!released) {
440         /* We shouldn't reach here, we must delete the StoredValue in the
441            HashTable */
442         throw std::logic_error(
443                 "HashTable::unlocked_del: StoredValue to be deleted "
444                 "not found in HashTable; possibly HashTable leak");
445     }
446
447     // Update statistics now the item has been removed.
448     StoredValue::reduceCacheSize(*this, released->size());
449     StoredValue::reduceMetaDataSize(*this, stats, released->metaDataSize());
450     if (released->isTempItem()) {
451         --numTempItems;
452     } else {
453         decrNumItems();
454         decrNumTotalItems();
455         --datatypeCounts[released->getDatatype()];
456         if (released->isDeleted()) {
457             --numDeletedItems;
458         }
459     }
460     return released;
461 }
462
463 void HashTable::visit(HashTableVisitor &visitor) {
464     if ((numItems.load() + numTempItems.load()) == 0 || !isActive()) {
465         return;
466     }
467
468     // Acquire one (any) of the mutexes before incrementing {visitors}, this
469     // prevents any race between this visitor and the HashTable resizer.
470     // See comments in pauseResumeVisit() for further details.
471     std::unique_lock<std::mutex> lh(mutexes[0]);
472     VisitorTracker vt(&visitors);
473     lh.unlock();
474
475     bool aborted = !visitor.shouldContinue();
476     size_t visited = 0;
477     for (int l = 0; isActive() && !aborted && l < static_cast<int>(n_locks);
478          l++) {
479         for (int i = l; i < static_cast<int>(size); i+= n_locks) {
480             // (re)acquire mutex on each HashBucket, to minimise any impact
481             // on front-end threads.
482             HashBucketLock lh(i, mutexes[l]);
483
484             StoredValue* v = values[i].get();
485             if (v) {
486                 // TODO: Perf: This check seems costly - do we think it's still
487                 // worth keeping?
488                 auto hashbucket = getBucketForHash(v->getKey().hash());
489                 if (i != hashbucket) {
490                     throw std::logic_error("HashTable::visit: inconsistency "
491                             "between StoredValue's calculated hashbucket "
492                             "(which is " + std::to_string(hashbucket) +
493                             ") and bucket is is located in (which is " +
494                             std::to_string(i) + ")");
495                 }
496             }
497             while (v) {
498                 StoredValue* tmp = v->next.get();
499                 visitor.visit(lh, v);
500                 v = tmp;
501             }
502             ++visited;
503         }
504         aborted = !visitor.shouldContinue();
505     }
506 }
507
508 void HashTable::visitDepth(HashTableDepthVisitor &visitor) {
509     if (numItems.load() == 0 || !isActive()) {
510         return;
511     }
512     size_t visited = 0;
513     VisitorTracker vt(&visitors);
514
515     for (int l = 0; l < static_cast<int>(n_locks); l++) {
516         LockHolder lh(mutexes[l]);
517         for (int i = l; i < static_cast<int>(size); i+= n_locks) {
518             size_t depth = 0;
519             StoredValue* p = values[i].get();
520             if (p) {
521                 // TODO: Perf: This check seems costly - do we think it's still
522                 // worth keeping?
523                 auto hashbucket = getBucketForHash(p->getKey().hash());
524                 if (i != hashbucket) {
525                     throw std::logic_error("HashTable::visit: inconsistency "
526                             "between StoredValue's calculated hashbucket "
527                             "(which is " + std::to_string(hashbucket) +
528                             ") and bucket it is located in (which is " +
529                             std::to_string(i) + ")");
530                 }
531             }
532             size_t mem(0);
533             while (p) {
534                 depth++;
535                 mem += p->size();
536                 p = p->next.get();
537             }
538             visitor.visit(i, depth, mem);
539             ++visited;
540         }
541     }
542 }
543
544 HashTable::Position
545 HashTable::pauseResumeVisit(PauseResumeHashTableVisitor& visitor,
546                             Position& start_pos) {
547     if ((numItems.load() + numTempItems.load()) == 0 || !isActive()) {
548         // Nothing to visit
549         return endPosition();
550     }
551
552     bool paused = false;
553
554     // To attempt to minimize the impact the visitor has on normal frontend
555     // operations, we deliberately acquire (and release) the mutex between
556     // each hash_bucket - see `lh` in the inner for() loop below. This means we
557     // hold a given mutex for a large number of short durations, instead of just
558     // one single, long duration.
559     // *However*, there is a potential race with this approach - the {size} of
560     // the HashTable may be changed (by the Resizer task) between us first
561     // reading it to calculate the starting hash_bucket, and then reading it
562     // inside the inner for() loop. To prevent this race, we explicitly acquire
563     // (any) mutex, increment {visitors} and then release the mutex. This
564     //avoids the race as if visitors >0 then Resizer will not attempt to resize.
565     std::unique_lock<std::mutex> lh(mutexes[0]);
566     VisitorTracker vt(&visitors);
567     lh.unlock();
568
569     // Start from the requested lock number if in range.
570     size_t lock = (start_pos.lock < n_locks) ? start_pos.lock : 0;
571     size_t hash_bucket = 0;
572
573     for (; isActive() && !paused && lock < n_locks; lock++) {
574
575         // If the bucket position is *this* lock, then start from the
576         // recorded bucket (as long as we haven't resized).
577         hash_bucket = lock;
578         if (start_pos.lock == lock &&
579             start_pos.ht_size == size &&
580             start_pos.hash_bucket < size) {
581             hash_bucket = start_pos.hash_bucket;
582         }
583
584         // Iterate across all values in the hash buckets owned by this lock.
585         // Note: we don't record how far into the bucket linked-list we
586         // pause at; so any restart will begin from the next bucket.
587         for (; !paused && hash_bucket < size; hash_bucket += n_locks) {
588             LockHolder lh(mutexes[lock]);
589
590             StoredValue* v = values[hash_bucket].get();
591             while (!paused && v) {
592                 StoredValue* tmp = v->next.get();
593                 paused = !visitor.visit(*v);
594                 v = tmp;
595             }
596         }
597
598         // If the visitor paused us before we visited all hash buckets owned
599         // by this lock, we don't want to skip the remaining hash buckets, so
600         // stop the outer for loop from advancing to the next lock.
601         if (paused && hash_bucket < size) {
602             break;
603         }
604
605         // Finished all buckets owned by this lock. Set hash_bucket to 'size'
606         // to give a consistent marker for "end of lock".
607         hash_bucket = size;
608     }
609
610     // Return the *next* location that should be visited.
611     return HashTable::Position(size, lock, hash_bucket);
612 }
613
614 HashTable::Position HashTable::endPosition() const  {
615     return HashTable::Position(size, n_locks, size);
616 }
617
618 static inline size_t getDefault(size_t x, size_t d) {
619     return x == 0 ? d : x;
620 }
621
622 size_t HashTable::getNumBuckets(size_t n) {
623     return getDefault(n, defaultNumBuckets);
624 }
625
626 size_t HashTable::getNumLocks(size_t n) {
627     return getDefault(n, defaultNumLocks);
628 }
629
630 void HashTable::setDefaultNumBuckets(size_t to) {
631     if (to != 0) {
632         defaultNumBuckets = to;
633     }
634 }
635
636 void HashTable::setDefaultNumLocks(size_t to) {
637     if (to != 0) {
638         defaultNumLocks = to;
639     }
640 }
641
642 bool HashTable::unlocked_ejectItem(StoredValue*& vptr,
643                                    item_eviction_policy_t policy) {
644     if (vptr == nullptr) {
645         throw std::invalid_argument("HashTable::unlocked_ejectItem: "
646                 "Unable to delete NULL StoredValue");
647     }
648     if (policy == VALUE_ONLY) {
649         bool rv = vptr->ejectValue(*this, policy);
650         if (rv) {
651             ++stats.numValueEjects;
652             ++numNonResidentItems;
653             ++numEjects;
654             return true;
655         } else {
656             ++stats.numFailedEjects;
657             return false;
658         }
659     } else { // full eviction.
660         if (vptr->eligibleForEviction(policy)) {
661             StoredValue::reduceMetaDataSize(*this, stats,
662                                             vptr->metaDataSize());
663             StoredValue::reduceCacheSize(*this, vptr->size());
664             int bucket_num = getBucketForHash(vptr->getKey().hash());
665
666             // Remove the item from the hash table.
667             auto removed = hashChainRemoveFirst(
668                     values[bucket_num],
669                     [vptr](const StoredValue* v) { return v == vptr; });
670
671             if (removed->isResident()) {
672                 ++stats.numValueEjects;
673             }
674             if (!removed->isResident() && !removed->isTempItem()) {
675                 decrNumNonResidentItems(); // Decrement because the item is
676                                            // fully evicted.
677             }
678             decrNumItems(); // Decrement because the item is fully evicted.
679             --datatypeCounts[vptr->getDatatype()];
680             ++numEjects;
681             updateMaxDeletedRevSeqno(vptr->getRevSeqno());
682
683             return true;
684         } else {
685             ++stats.numFailedEjects;
686             return false;
687         }
688     }
689 }
690
691 std::unique_ptr<Item> HashTable::getRandomKeyFromSlot(int slot) {
692     auto lh = getLockedBucket(slot);
693     for (StoredValue* v = values[slot].get(); v; v = v->next.get()) {
694         if (!v->isTempItem() && !v->isDeleted() && v->isResident()) {
695             return v->toItem(false, 0);
696         }
697     }
698
699     return nullptr;
700 }
701
702 bool HashTable::unlocked_restoreValue(
703         const std::unique_lock<std::mutex>& htLock,
704         const Item& itm,
705         StoredValue& v) {
706     if (!htLock || !isActive() || v.isResident()) {
707         return false;
708     }
709
710     if (v.isTempInitialItem()) { // Regular item with the full eviction
711         --numTempItems;
712         ++numItems;
713         /* set it back to false as we created a temp item by setting it to true
714            when bg fetch is scheduled (full eviction mode). */
715         v.setNewCacheItem(false);
716         ++datatypeCounts[itm.getDataType()];
717     } else {
718         decrNumNonResidentItems();
719     }
720
721     v.restoreValue(itm);
722
723     StoredValue::increaseCacheSize(*this, v.getValue()->length());
724     return true;
725 }
726
727 void HashTable::unlocked_restoreMeta(const std::unique_lock<std::mutex>& htLock,
728                                      const Item& itm,
729                                      StoredValue& v) {
730     if (!htLock) {
731         throw std::invalid_argument(
732                 "HashTable::unlocked_restoreMeta: htLock "
733                 "not held");
734     }
735
736     if (!isActive()) {
737         throw std::logic_error(
738                 "HashTable::unlocked_restoreMeta: Cannot "
739                 "call on a non-active HT object");
740     }
741
742     v.restoreMeta(itm);
743     if (!itm.isDeleted()) {
744         --numTempItems;
745         ++numItems;
746         ++numNonResidentItems;
747         ++datatypeCounts[v.getDatatype()];
748     }
749 }
750
751 std::ostream& operator<<(std::ostream& os, const HashTable& ht) {
752     os << "HashTable[" << &ht << "] with"
753        << " numInMemory:" << ht.getNumInMemoryItems()
754        << " numDeleted:" << ht.getNumDeletedItems()
755        << " values: " << std::endl;
756     for (const auto& chain : ht.values) {
757         if (chain) {
758             for (StoredValue* sv = chain.get(); sv != nullptr;
759                  sv = sv->next.get()) {
760                 os << "    " << *sv << std::endl;
761             }
762         }
763     }
764     return os;
765 }