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