btree_ondisk.h

Go to the documentation of this file.

#pragma once

#include "mongo/base/static_assert.h"
#include "mongo/db/jsobj.h"
#include "mongo/db/storage/mmap_v1/btree/key.h"
#include "mongo/db/storage/mmap_v1/diskloc.h"

namespace mongo {

const int OldBucketSize = 8192;

//
// On-disk index format
//

#pragma pack(1)

template <class LocType>
struct FixedWidthKey {
    //
    // Data
    //

    LocType prevChildBucket;

    LocType recordLoc;

    unsigned short _kdo;

    //
    // Accessors / mutators
    //

    short keyDataOfs() const {
        return static_cast<short>(_kdo);
    }

    void setKeyDataOfs(short s) {
        _kdo = s;
        invariant(s >= 0);
    }

    void setKeyDataOfsSavingUse(short s) {
        // XXX kill this func
        setKeyDataOfs(s);
    }

    void setUnused() {
        recordLoc.GETOFS() |= 1;
    }

    void setUsed() {
        recordLoc.GETOFS() &= ~1;
    }

    int isUnused() const {
        return recordLoc.getOfs() & 1;
    }

    int isUsed() const {
        return !isUnused();
    }
};

struct BtreeBucketV0 {
    DiskLoc parent;

    DiskLoc nextChild;

    unsigned short _wasSize;

    unsigned short _reserved1;

    int flags;

    int emptySize;

    int topSize;

    /* Number of keys in the bucket. */
    int n;

    int reserved;

    /* Beginning of the bucket's body */
    char data[4];

    // Precalculated size constants
    enum { HeaderSize = 40 };
};

// BtreeBucketV0 is part of the on-disk format, so it should never be changed
MONGO_STATIC_ASSERT(sizeof(BtreeBucketV0) - sizeof(static_cast<BtreeBucketV0*>(NULL)->data) ==
                    BtreeBucketV0::HeaderSize);

struct DiskLoc56Bit {
    //
    // Data
    //

    int ofs;

    unsigned char _a[3];

    //
    // Accessors XXX rename these, this is terrible
    //

    int& GETOFS() {
        return ofs;
    }

    int getOfs() const {
        return ofs;
    }

    //
    // Comparison
    //

    bool isNull() const {
        return ofs < 0;
    }

    unsigned long long toLongLong() const {
        // endian
        unsigned long long result = ofs;
        char* cursor = reinterpret_cast<char*>(&result);
        *reinterpret_cast<uint16_t*>(cursor + 4) = *reinterpret_cast<const uint16_t*>(&_a[0]);
        *reinterpret_cast<uint8_t*>(cursor + 6) = *reinterpret_cast<const uint8_t*>(&_a[2]);
        *reinterpret_cast<uint8_t*>(cursor + 7) = uint8_t(0);
        return result;
    }

    bool operator<(const DiskLoc56Bit& rhs) const {
        // the orderering of dup keys in btrees isn't too critical, but we'd like to put items
        // that are close together on disk close together in the tree, so we do want the file #
        // to be the most significant bytes
        return toLongLong() < rhs.toLongLong();
    }

    int compare(const DiskLoc56Bit& rhs) const {
        unsigned long long a = toLongLong();
        unsigned long long b = rhs.toLongLong();
        if (a < b) {
            return -1;
        } else {
            return a == b ? 0 : 1;
        }
    }

    bool operator==(const DiskLoc56Bit& rhs) const {
        return toLongLong() == rhs.toLongLong();
    }

    bool operator!=(const DiskLoc56Bit& rhs) const {
        return toLongLong() != rhs.toLongLong();
    }

    bool operator==(const DiskLoc& rhs) const {
        return DiskLoc(*this) == rhs;
    }

    bool operator!=(const DiskLoc& rhs) const {
        return !(*this == rhs);
    }

    //
    // Mutation
    //

    enum {
        OurNullOfs = -2,     // first bit of offsets used in _KeyNode we don't use -1 here
        OurMaxA = 0xffffff,  // highest 3-byte value
    };

    void Null() {
        ofs = OurNullOfs;
        _a[0] = _a[1] = _a[2] = 0;
    }

    void operator=(const DiskLoc& loc);

    //
    // Type Conversion
    //

    RecordId toRecordId() const {
        return DiskLoc(*this).toRecordId();
    }

    operator DiskLoc() const {
        // endian
        if (isNull())
            return DiskLoc();
        unsigned a = *((unsigned*)(_a - 1));
        return DiskLoc(a >> 8, ofs);
    }

    std::string toString() const {
        return DiskLoc(*this).toString();
    }
};

struct BtreeBucketV1 {
    DiskLoc56Bit parent;

    DiskLoc56Bit nextChild;

    unsigned short flags;

    unsigned short emptySize;

    unsigned short topSize;

    /* Number of keys in the bucket. */
    unsigned short n;

    /* Beginning of the bucket's body */
    char data[4];

    // Precalculated size constants
    enum { HeaderSize = 22 };
};

// BtreeBucketV1 is part of the on-disk format, so it should never be changed
MONGO_STATIC_ASSERT(sizeof(BtreeBucketV1) - sizeof(static_cast<BtreeBucketV1*>(NULL)->data) ==
                    BtreeBucketV1::HeaderSize);

enum Flags { Packed = 1 };

struct BtreeLayoutV0 {
    typedef FixedWidthKey<DiskLoc> FixedWidthKeyType;
    typedef DiskLoc LocType;
    typedef KeyBson KeyType;
    typedef KeyBson KeyOwnedType;
    typedef BtreeBucketV0 BucketType;

    enum { BucketSize = 8192, BucketBodySize = BucketSize - BucketType::HeaderSize };

    // largest key size we allow.  note we very much need to support bigger keys (somehow) in
    // the future.

    static const int KeyMax = OldBucketSize / 10;

    // A sentinel value sometimes used to identify a deallocated bucket.
    static const int INVALID_N_SENTINEL = -1;

    static void initBucket(BucketType* bucket) {
        bucket->_reserved1 = 0;
        bucket->_wasSize = BucketSize;
        bucket->reserved = 0;
    }
};

struct BtreeLayoutV1 {
    typedef FixedWidthKey<DiskLoc56Bit> FixedWidthKeyType;
    typedef KeyV1 KeyType;
    typedef KeyV1Owned KeyOwnedType;
    typedef DiskLoc56Bit LocType;
    typedef BtreeBucketV1 BucketType;

    enum {
        BucketSize = 8192 - 16,  // The -16 is to leave room for the MmapV1RecordHeader header
        BucketBodySize = BucketSize - BucketType::HeaderSize
    };

    static const int KeyMax = 1024;

    // A sentinel value sometimes used to identify a deallocated bucket.
    static const unsigned short INVALID_N_SENTINEL = 0xffff;

    static void initBucket(BucketType* bucket) {}
};

#pragma pack()

}  // namespace mongo