DEBUG: Add HashTable::operator<<, expand StoredValue::operator<<
[ep-engine.git] / src / stored-value.h
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 #pragma once
19
20 #include "config.h"
21
22 #include "item.h"
23 #include "item_pager.h"
24 #include "utility.h"
25
26 #include <boost/intrusive/list.hpp>
27
28 class HashTable;
29 class OrderedStoredValue;
30
31 /**
32  * In-memory storage for an item.
33  *
34  * This class represents a single document which is present in the HashTable -
35  * essentially this is value_type used by HashTable.
36  *
37  * It contains the documents' key, related metadata (CAS, rev, seqno, ...).
38  * It also has a pointer to the documents' value - which may be null if the
39  * value of the item is not currently resident (for example it's been evicted to
40  * save memory).
41  * Additionally it contains flags to help HashTable manage the state of the
42  * item - such as dirty flag, NRU bits, and a `next` pointer to support
43  * chaining of StoredValues which hash to the same hash bucket.
44  *
45  * The key of the item is of variable length (from 1 to ~256 bytes). As an
46  * optimization, we allocate the key directly after the fixed size of
47  * StoredValue, so StoredValue and its key are contiguous in memory. This saves
48  * us the cost of an indirection compared to storing the key out-of-line, and
49  * the space of a pointer in StoredValue to point to the out-of-line
50  * allocation. It does, however complicate the management of StoredValue
51  * objects as they are now variable-sized - they must be created using a
52  * factory method (StoredValueFactory) and must be heap-allocated, managed
53  * using a unique_ptr (StoredValue::UniquePtr).
54  *
55  * Graphically the looks like:
56  *
57  *              StoredValue::UniquePtr
58  *                          |
59  *                          V
60  *               .-------------------.
61  *               | StoredValue       |
62  *               +-------------------+
63  *           {   | value [ptr]       | ======> Blob (nullptr if evicted)
64  *           {   | next  [ptr]       | ======> StoredValue (next in hash chain).
65  *     fixed {   | CAS               |
66  *    length {   | revSeqno          |
67  *           {   | ...               |
68  *           {   | datatype          |
69  *           {   | internal flags: isDirty, deleted, isOrderedStoredValue ...
70  *               + - - - - - - - - - +
71  *  variable {   | key[]             |
72  *   length  {   | ...               |
73  *               +-------------------+
74  *
75  * OrderedStoredValue is a "subclass" of StoredValue, which is used by
76  * Ephemeral buckets as it supports maintaining a seqno ordering of items in
77  * memory (for Persistent buckets this ordering is maintained on-disk).
78  *
79  * The implementation of OrderedStoredValue is tightly coupled to StoredValue
80  * so it will be described here:
81  *
82  * OrderedStoredValue has the fixed length members of StoredValue, then it's
83  * own fixed length fields (seqno list), followed finally by the variable
84  * length key (again, allocated contiguously):
85  *
86  *              StoredValue::UniquePtr
87  *                          |
88  *                          V
89  *               .--------------------.
90  *               | OrderedStoredValue |
91  *               +--------------------+
92  *           {   | value [ptr]        | ======> Blob (nullptr if evicted)
93  *           {   | next  [ptr]        | ======> StoredValue (next in hash chain).
94  *     fixed {   | StoredValue fixed ...
95  *    length {   + - - - - - - - - - -+
96  *           {   | seqno next [ptr]   |
97  *           {   | seqno prev [ptr]   |
98  *               + - - - - - - - - - -+
99  *  variable {   | key[]              |
100  *   length  {   | ...                |
101  *               +--------------------+
102  *
103  * To support dynamic dispatch (for example to lookup the key, whose location
104  * varies depending if it's StoredValue or OrderedStoredValue), we choose to
105  * use a manual flag-based dispatching (as opposed to a normal vTable based
106  * approach) as the per-object costs are much cheaper - 1 bit for the flag vs.
107  * 8 bytes for a vTable ptr.
108  * StoredValue::isOrderedStoredValue is set to false for StoredValue objects,
109  * and true for OrderedStoredValue objects, and then any methods
110  * needing dynamic dispatch read the value of the flag. Note this means that
111  * the 'base' class (StoredValue) needs to know about all possible subclasses
112  * (only one currently) and what class-specific code to call.
113  * Similary, deletion of OrderedStoredValue objects is delicate - we cannot
114  * safely delete via the base-class pointer directly, as that would only run
115  * ~StoredValue and not the members of the derived class. Instead a custom
116  * deleter is associated with StoredValue::UniquePtr, which checks the flag
117  * and dispatches to the correct destructor.
118  */
119 class StoredValue {
120 public:
121     // Custom deleter for StoredValue objects.
122     struct Deleter {
123         void operator()(StoredValue* val);
124     };
125
126     // Owning pointer type for StoredValue objects.
127     using UniquePtr = std::unique_ptr<StoredValue, Deleter>;
128
129     uint8_t getNRUValue() const;
130
131     void setNRUValue(uint8_t nru_val);
132
133     uint8_t incrNRUValue();
134
135     void referenced();
136
137     /**
138      * Mark this item as needing to be persisted.
139      */
140     void markDirty() {
141         _isDirty = 1;
142     }
143
144     /**
145      * Mark this item as clean.
146      */
147     void markClean() {
148         _isDirty = 0;
149     }
150
151     /**
152      * True if this object is dirty.
153      */
154     bool isDirty() const {
155         return _isDirty;
156     }
157
158     bool eligibleForEviction(item_eviction_policy_t policy) {
159         if (policy == VALUE_ONLY) {
160             return isResident() && !isDirty() && !isDeleted();
161         } else {
162             return !isDirty() && !isDeleted();
163         }
164     }
165
166     /**
167      * Check if this item is expired or not.
168      *
169      * @param asOf the time to be compared with this item's expiry time
170      * @return true if this item's expiry time < asOf
171      */
172     bool isExpired(time_t asOf) const {
173         if (getExptime() != 0 && getExptime() < asOf) {
174             return true;
175         }
176         return false;
177     }
178
179     /**
180      * True if this item is for the given key.
181      *
182      * @param k the key we're checking
183      * @return true if this item's key is equal to k
184      */
185     bool hasKey(const DocKey& k) const {
186         return getKey() == k;
187     }
188
189     /**
190      * Get this item's key.
191      */
192     const SerialisedDocKey& getKey() const {
193         return *const_cast<const SerialisedDocKey*>(
194                 const_cast<StoredValue&>(*this).key());
195     }
196
197     /**
198      * Get this item's value.
199      */
200     const value_t &getValue() const {
201         return value;
202     }
203
204     /**
205      * Get the expiration time of this item.
206      *
207      * @return the expiration time.
208      */
209     time_t getExptime() const {
210         return exptime;
211     }
212
213     void setExptime(time_t tim) {
214         exptime = tim;
215         markDirty();
216     }
217
218     /**
219      * Get the client-defined flags of this item.
220      *
221      * @return the flags.
222      */
223     uint32_t getFlags() const {
224         return flags;
225     }
226
227     /**
228      * Set the client-defined flags for this item.
229      */
230     void setFlags(uint32_t fl) {
231         flags = fl;
232     }
233
234     /**
235      * get the items datatype
236      */
237     protocol_binary_datatype_t getDatatype() const {
238         return datatype;
239     }
240
241     /**
242      * Set the items datatype
243      */
244     void setDatatype(protocol_binary_datatype_t type) {
245         datatype = type;
246     }
247
248     /**
249      * Set a new value for this item.
250      *
251      * @param itm the item with a new value
252      * @param ht the hashtable that contains this StoredValue instance
253      */
254     void setValue(const Item& itm, HashTable& ht) {
255         size_t currSize = size();
256         reduceCacheSize(ht, currSize);
257         value = itm.getValue();
258         deleted = itm.isDeleted();
259         flags = itm.getFlags();
260         datatype = itm.getDataType();
261         bySeqno = itm.getBySeqno();
262
263         cas = itm.getCas();
264         lock_expiry_or_delete_time = 0;
265         exptime = itm.getExptime();
266         revSeqno = itm.getRevSeqno();
267
268         nru = itm.getNRUValue();
269
270         if (isTempInitialItem()) {
271             markClean();
272         } else {
273             markDirty();
274         }
275
276         if (isTempItem()) {
277             markNotResident();
278         }
279
280         size_t newSize = size();
281         increaseCacheSize(ht, newSize);
282     }
283
284     void markDeleted() {
285         deleted = true;
286         markDirty();
287     }
288
289     /**
290      * Reset the value of this item.
291      */
292     void resetValue() {
293         if (isDeleted()) {
294             throw std::logic_error("StoredValue::resetValue: Not possible to "
295                     "reset the value of a deleted item");
296         }
297         markNotResident();
298         // item no longer resident once reset the value
299         deleted = true;
300     }
301
302     /**
303      * Eject an item value from memory.
304      * @param ht the hashtable that contains this StoredValue instance
305      */
306     bool ejectValue(HashTable &ht, item_eviction_policy_t policy);
307
308     /**
309      * Restore the value for this item.
310      *
311      * @param itm the item to be restored
312      */
313     void restoreValue(const Item& itm);
314
315     /**
316      * Restore the metadata of of a temporary item upon completion of a
317      * background fetch assuming the hashtable bucket is locked.
318      *
319      * @param itm the Item whose metadata is being restored
320      */
321     void restoreMeta(const Item& itm);
322
323     /**
324      * Get this item's CAS identifier.
325      *
326      * @return the cas ID
327      */
328     uint64_t getCas() const {
329         return cas;
330     }
331
332     /**
333      * Set a new CAS ID.
334      */
335     void setCas(uint64_t c) {
336         cas = c;
337     }
338
339     /**
340      * Lock this item until the given time.
341      */
342     void lock(rel_time_t expiry) {
343         if (isDeleted()) {
344             // Cannot lock Deleted items.
345             throw std::logic_error(
346                     "StoredValue::lock: Called on Deleted item");
347         }
348         lock_expiry_or_delete_time = expiry;
349     }
350
351     /**
352      * Unlock this item.
353      */
354     void unlock() {
355         if (isDeleted()) {
356             // Deleted items are not locked - just skip.
357             return;
358         }
359         lock_expiry_or_delete_time = 0;
360     }
361
362     /**
363      * True if this item has an ID.
364      *
365      * An item always has an ID after it's been persisted.
366      */
367     bool hasBySeqno() {
368         return bySeqno > 0;
369     }
370
371     /**
372      * Get this item's ID.
373      *
374      * @return the ID for the item; 0 if the item has no ID
375      */
376     int64_t getBySeqno() const {
377         return bySeqno;
378     }
379
380     /**
381      * Set the ID for this item.
382      *
383      * This is used by the persistene layer.
384      *
385      * It is an error to set an ID on an item that already has one.
386      */
387     void setBySeqno(int64_t to) {
388         if (to <= 0) {
389             throw std::invalid_argument("StoredValue::setBySeqno: to "
390                     "(which is " + std::to_string(to) + ") must be positive");
391         }
392         bySeqno = to;
393     }
394
395     // Marks the stored item as deleted.
396     void setDeleted()
397     {
398         bySeqno = state_deleted_key;
399     }
400
401     // Marks the stored item as non-existent.
402     void setNonExistent()
403     {
404         bySeqno = state_non_existent_key;
405     }
406
407     /**
408      * Is this a temporary item created for processing a get-meta request?
409      */
410     bool isTempItem() const {
411         return (isTempNonExistentItem() || isTempDeletedItem() ||
412                 isTempInitialItem());
413
414      }
415
416     /**
417      * Is this an initial temporary item?
418      */
419      bool isTempInitialItem() const {
420          return bySeqno == state_temp_init;
421     }
422
423     /**
424      * Is this a temporary item created for a non-existent key?
425      */
426     bool isTempNonExistentItem() const {
427          return bySeqno == state_non_existent_key;
428     }
429
430     /**
431      * Is this a temporary item created for a deleted key?
432      */
433     bool isTempDeletedItem() const {
434         return bySeqno == state_deleted_key;
435
436      }
437
438     size_t valuelen() const {
439         if (!isResident()) {
440             return 0;
441         }
442         return value->length();
443     }
444
445     /**
446      * Get the total size of this item.
447      *
448      * @return the amount of memory used by this item.
449      */
450     size_t size() const {
451         return getObjectSize() + valuelen();
452     }
453
454     size_t metaDataSize() const {
455         return getObjectSize();
456     }
457
458     /**
459      * Return true if this item is locked as of the given timestamp.
460      *
461      * @param curtime lock expiration marker (usually the current time)
462      * @return true if the item is locked
463      */
464     bool isLocked(rel_time_t curtime) const {
465         if (isDeleted()) {
466             // Deleted items cannot be locked.
467             return false;
468         }
469
470         if (lock_expiry_or_delete_time == 0 ||
471             (curtime > lock_expiry_or_delete_time)) {
472             return false;
473         }
474         return true;
475     }
476
477     /**
478      * True if this value is resident in memory currently.
479      */
480     bool isResident() const {
481         return value.get() != NULL;
482     }
483
484     void markNotResident() {
485         value.reset();
486     }
487
488     /**
489      * True if this object is logically deleted.
490      */
491     bool isDeleted() const {
492         return deleted;
493     }
494
495     /**
496      * Logically delete this object.
497      */
498     void del(HashTable &ht);
499
500     uint64_t getRevSeqno() const {
501         return revSeqno;
502     }
503
504     /**
505      * Set a new revision sequence number.
506      */
507     void setRevSeqno(uint64_t s) {
508         revSeqno = s;
509     }
510
511     /**
512      * Return true if this is a new cache item.
513      */
514     bool isNewCacheItem() const {
515         return newCacheItem;
516     }
517
518     /**
519      * Set / reset a new cache item flag.
520      */
521     void setNewCacheItem(bool newitem) {
522         newCacheItem = newitem;
523     }
524
525     /**
526      * Generate a new Item out of this object.
527      *
528      * @param lck if true, the new item will return a locked CAS ID.
529      * @param vbucket the vbucket containing this item.
530      */
531     std::unique_ptr<Item> toItem(bool lck, uint16_t vbucket) const;
532
533     /**
534      * Generate a new Item with only key and metadata out of this object.
535      * The item generated will not contain value
536      *
537      * @param vbucket the vbucket containing this item.
538      */
539     std::unique_ptr<Item> toItemWithNoValue(uint16_t vbucket) const;
540
541     /**
542      * Set the memory threshold on the current bucket quota for accepting a new mutation
543      */
544     static void setMutationMemoryThreshold(double memThreshold);
545
546     /**
547      * Return the memory threshold for accepting a new mutation
548      */
549     static double getMutationMemThreshold() {
550         return mutation_mem_threshold;
551     }
552
553     /*
554      * Values of the bySeqno attribute used by temporarily created StoredValue
555      * objects.
556      * state_deleted_key: represents an item that's deleted from memory but
557      *                    present in the persistent store.
558      * state_non_existent_key: represents a non existent item
559      * state_collection_open: a special value used by collections to help
560      *  represent a collections life-time in sequence-numbers (start to end).
561      *  If a collection has no end, it's termed open and has an end
562      *  sequence-number of StoredValue::state_collection_open. We do not
563      *  actually assign this value to StoredValue objects, but it's here in
564      *  this "number space" of special sequence numbers to help ensure it's
565      *  different to the other special sequence numbers we define.
566      *
567      */
568     static const int64_t state_deleted_key;
569     static const int64_t state_non_existent_key;
570     static const int64_t state_temp_init;
571     static const int64_t state_collection_open;
572
573     /**
574      * Return the size in byte of this object; both the fixed fields and the
575      * variable-length key. Doesn't include value size (allocated externally).
576      */
577     inline size_t getObjectSize() const;
578
579     /**
580      * Reallocates the dynamic members of StoredValue. Used as part of
581      * defragmentation.
582      */
583     void reallocate();
584
585     /**
586      * Returns pointer to the subclass OrderedStoredValue if it the object is
587      * of the type, if not throws a bad_cast.
588      *
589      * Equivalent to dynamic cast, but done manually as we wanted to avoid
590      * vptr per object.
591      */
592     OrderedStoredValue* toOrderedStoredValue();
593     const OrderedStoredValue* toOrderedStoredValue() const;
594
595     /**
596      * Check if the contents of the StoredValue is same as that of the other
597      * one. Does not consider the intrusive hash bucket link.
598      *
599      * @param other The StoredValue to be compared with
600      */
601     bool operator==(const StoredValue& other) const;
602
603     /* [TBD] : Move this function out of StoredValue class */
604     static bool hasAvailableSpace(EPStats&,
605                                   const Item& item,
606                                   bool isReplication = false);
607
608     /// Return how many bytes are need to store Item as a StoredValue
609     static size_t getRequiredStorage(const Item& item) {
610         return sizeof(StoredValue) +
611                SerialisedDocKey::getObjectSize(item.getKey().size());
612     }
613
614 protected:
615     /**
616      * Constructor - protected as allocation needs to be done via
617      * StoredValueFactory.
618      *
619      * @param itm Item to base this StoredValue on.
620      * @param n The StoredValue which will follow the new stored value in
621      *           the hash bucket chain, which this new item will take
622      *           ownership of. (Typically the top of the hash bucket into
623      *           which the new item is being inserted).
624      * @param stats EPStats to update for this new StoredValue
625      * @param ht HashTable to update stats for this new StoredValue.
626      * @param isOrdered Are we constructing an OrderedStoredValue?
627      */
628     StoredValue(const Item& itm,
629                 UniquePtr n,
630                 EPStats& stats,
631                 HashTable& ht,
632                 bool isOrdered)
633         : value(itm.getValue()),
634           next(std::move(n)),
635           cas(itm.getCas()),
636           revSeqno(itm.getRevSeqno()),
637           bySeqno(itm.getBySeqno()),
638           lock_expiry_or_delete_time(0),
639           exptime(itm.getExptime()),
640           flags(itm.getFlags()),
641           datatype(itm.getDataType()),
642           deleted(itm.isDeleted()),
643           newCacheItem(true),
644           isOrdered(isOrdered),
645           nru(itm.getNRUValue()),
646           stale(false) {
647         // Placement-new the key which lives in memory directly after this
648         // object.
649         new (key()) SerialisedDocKey(itm.getKey());
650
651         if (isTempInitialItem()) {
652             markClean();
653         } else {
654             markDirty();
655         }
656
657         if (isTempItem()) {
658             markNotResident();
659         }
660
661         increaseMetaDataSize(ht, stats, metaDataSize());
662         increaseCacheSize(ht, size());
663
664         ObjectRegistry::onCreateStoredValue(this);
665     }
666
667     // Destructor. protected, as needs to be carefully deleted (via
668     // StoredValue::Destructor) depending on the value of isOrdered flag.
669     ~StoredValue() {
670         ObjectRegistry::onDeleteStoredValue(this);
671     }
672
673     /**
674      * Copy constructor - protected as allocation needs to be done via
675      * StoredValueFactory.
676      *
677      * @param other StoredValue being copied
678      * @param n The StoredValue which will follow the new stored value in
679      *           the hash bucket chain, which this new item will take
680      *           ownership of. (Typically the top of the hash bucket into
681      *           which the new item is being inserted).
682      * @param stats EPStats to update for this new StoredValue
683      * @param ht HashTable to update stats for this new StoredValue.
684      */
685     StoredValue(const StoredValue& other,
686                 UniquePtr n,
687                 EPStats& stats,
688                 HashTable& ht)
689         : value(other.value),
690           next(std::move(n)),
691           cas(other.cas),
692           revSeqno(other.revSeqno),
693           bySeqno(other.bySeqno),
694           lock_expiry_or_delete_time(other.lock_expiry_or_delete_time),
695           exptime(other.exptime),
696           flags(other.flags),
697           datatype(other.datatype),
698           _isDirty(other._isDirty),
699           deleted(other.deleted),
700           newCacheItem(other.newCacheItem),
701           isOrdered(other.isOrdered),
702           nru(other.nru),
703           stale(false) {
704         // Placement-new the key which lives in memory directly after this
705         // object.
706         StoredDocKey sKey(other.getKey());
707         new (key()) SerialisedDocKey(sKey);
708
709         increaseMetaDataSize(ht, stats, metaDataSize());
710         increaseCacheSize(ht, size());
711
712         ObjectRegistry::onCreateStoredValue(this);
713     }
714
715     /* Do not allow assignment */
716     StoredValue& operator=(const StoredValue& other) = delete;
717
718     /**
719      * Get the address of item's key .
720      */
721     inline SerialisedDocKey* key();
722
723     /**
724      * Logically mark this SV as deleted.
725      * Implementation for StoredValue instances (dispatched to by del() based
726      * on isOrdered==false).
727      */
728     void deleteImpl(HashTable& ht);
729
730     friend class HashTable;
731     friend class StoredValueFactory;
732     friend std::ostream& operator<<(std::ostream& os, const HashTable& ht);
733
734     value_t            value;          // 8 bytes
735     // Used to implement HashTable chaining (for elements hashing to the same
736     // bucket).
737     UniquePtr next; // 8 bytes
738     uint64_t           cas;            //!< CAS identifier.
739     uint64_t           revSeqno;       //!< Revision id sequence number
740     int64_t            bySeqno;        //!< By sequence id number
741     /// For alive items: GETL lock expiration. For deleted items: delete time.
742     rel_time_t         lock_expiry_or_delete_time;
743     uint32_t           exptime;        //!< Expiration time of this item.
744     uint32_t           flags;          // 4 bytes
745     protocol_binary_datatype_t datatype; // 1 byte
746     bool               _isDirty  :  1; // 1 bit
747     bool               deleted   :  1;
748     bool               newCacheItem : 1;
749     const bool isOrdered : 1; //!< Is this an instance of OrderedStoredValue?
750     uint8_t            nru       :  2; //!< True if referenced since last sweep
751     bool unused : 2; // Unused bits in first byte of bitfields.
752
753     // Indicates if a newer instance of the item is added. Logically part of
754     // OSV, but is physically located in SV as there are spare bytes here.
755     // Guarded by the SequenceList's writeLock.
756     // NOTE: As this is guarded by a different lock to the rest of the SV,
757     // it *must* be in a different byte than any other data not guarded by
758     // writeLock (Hence why this isn't in the same byte as _isDirty, deleted,
759     // newCacheItem etc). To achieve this std::atomic is used to ensure accesses
760     // are not "optimized" and merged with the previous byte. The thread-safety
761     // of std::atomic is not actually used/needed; we just need the no-merge
762     // guarantee.
763     // Note (2): Only 1 bit of this is currently used; rest is "spare".
764     std::atomic<bool> stale;
765
766     static void increaseMetaDataSize(HashTable &ht, EPStats &st, size_t by);
767     static void reduceMetaDataSize(HashTable &ht, EPStats &st, size_t by);
768     static void increaseCacheSize(HashTable &ht, size_t by);
769     static void reduceCacheSize(HashTable &ht, size_t by);
770     static double mutation_mem_threshold;
771
772     friend std::ostream& operator<<(std::ostream& os, const StoredValue& sv);
773 };
774
775 std::ostream& operator<<(std::ostream& os, const StoredValue& sv);
776
777 /**
778  * Subclass of StoredValue which additionally supports sequence number ordering.
779  *
780  * See StoredValue for implementation details.
781  */
782 class OrderedStoredValue : public StoredValue {
783 public:
784     // Intrusive linked-list for sequence number ordering.
785     // Guarded by the SequenceList's writeLock.
786     boost::intrusive::list_member_hook<> seqno_hook;
787
788     /**
789      * True if a newer version of the same key exists in the HashTable.
790      * Note: Only true for OrderedStoredValues which are no longer in the
791      *       HashTable (and only live in SequenceList)
792      * @param writeGuard The locked SeqList writeLock which guards the stale
793      * param.
794      */
795     bool isStale(std::lock_guard<std::mutex>& writeGuard) const {
796         return stale;
797     }
798
799     /**
800      * Marks that newer instance of this item is added in the HashTable
801      * @param writeLock The SeqList writeLock which guards the stale param.
802      */
803     void markStale(std::lock_guard<std::mutex>& writeGuard) {
804         stale = true;
805     }
806
807     /**
808      * Check if the contents of the StoredValue is same as that of the other
809      * one. Does not consider the intrusive hash bucket link.
810      *
811      * @param other The StoredValue to be compared with
812      */
813     bool operator==(const OrderedStoredValue& other) const;
814
815     /// Return how many bytes are need to store Item as an OrderedStoredValue
816     static size_t getRequiredStorage(const Item& item) {
817         return sizeof(OrderedStoredValue) +
818                SerialisedDocKey::getObjectSize(item.getKey());
819     }
820
821     /**
822      * Return the time the item was deleted. Only valid for deleted items.
823      */
824     rel_time_t getDeletedTime() const;
825
826 protected:
827     SerialisedDocKey* key() {
828         return reinterpret_cast<SerialisedDocKey*>(this + 1);
829     }
830
831     /**
832      * Logically mark this OSV as deleted. Implementation for
833      * OrderedStoredValue instances (dispatched to by del() based on
834      * isOrdered==true).
835      */
836     void deleteImpl(HashTable& ht);
837
838     /**
839      * Set the time the item was deleted to the specified time.
840      */
841     inline void setDeletedTime(rel_time_t time);
842
843 private:
844     // Constructor. Private, as needs to be carefully created via
845     // OrderedStoredValueFactory.
846     OrderedStoredValue(const Item& itm,
847                        UniquePtr n,
848                        EPStats& stats,
849                        HashTable& ht)
850         : StoredValue(itm, std::move(n), stats, ht, /*isOrdered*/ true) {
851     }
852
853     // Copy Constructor. Private, as needs to be carefully created via
854     // OrderedStoredValueFactory.
855     //
856     // Only StoredValue part (Hash Chain included) is copied. Hence the copied
857     // StoredValue will be in the HashTable, but not in the ordered
858     // data structure.
859     OrderedStoredValue(const StoredValue& other,
860                        UniquePtr n,
861                        EPStats& stats,
862                        HashTable& ht)
863         : StoredValue(other, std::move(n), stats, ht) {
864     }
865
866     /* Do not allow assignment */
867     OrderedStoredValue& operator=(const OrderedStoredValue& other) = delete;
868
869     // Grant friendship so our factory can call our (private) constructor.
870     friend class OrderedStoredValueFactory;
871
872     // Grant friendship to base class so it can perform flag dispatch to our
873     // overridden protected methods.
874     friend class StoredValue;
875 };
876
877 SerialisedDocKey* StoredValue::key() {
878     // key is located immediately following the object.
879     if (isOrdered) {
880         return static_cast<OrderedStoredValue*>(this)->key();
881     } else {
882         return reinterpret_cast<SerialisedDocKey*>(this + 1);
883     }
884 }
885
886 size_t StoredValue::getObjectSize() const {
887     // Size of fixed part of OrderedStoredValue or StoredValue, plus size of
888     // (variable) key.
889     if (isOrdered) {
890         return sizeof(OrderedStoredValue) + getKey().getObjectSize();
891     }
892     return sizeof(*this) + getKey().getObjectSize();
893 }