CDB++: C++ implementation of Constant Database

static

Fast look-ups. This library implements the data structure of the Constant Database proposed by Daniel J. Bernstein.

Low footprint. A CDB++ database consists of a chunk header (16 bytes), hash tables (2048 bytes and 16 bytes per record), and actual records (8 bytes plus key/value size per record).

Fast hash function. CDB++ incorporates the fast and collision-resistant hash function for strings (MurmurHash 2.0) implemented by Austin Appleby.

Chunk format. The structure of CDB++ is designed to store the data in a chunk of a file; CDB++ database can be embedded into a file with other arbitrary data.

Simple write interface. CDB++ can serialize a hash database to C++ output streams (std::ostream).

Simple read interface. CDB++ can prepare a hash database from an input stream (std::istream) or from a memory block on which a database image is read or memory-mapped from a file.

Cross platform. The source code can be compiled on Microsoft Visual Studio 2008, GNU C Compiler (gcc), etc.

Very simple API. The CDB++ API exposes only a few functions; one can use this library just by looking at the sample code.

Single C++ header implementation. CDB++ is implemented in a single header file (cdbpp.h); one can use the CDB++ API only by including cdbpp.h in a source code.

CDB++ does not support these for simplicity:

modifying associations

checking collisions in keys

compatibility of the database format on different byte-order architectures

Sample code

#include <fstream>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>

#include <cdbpp.h>

#define N       100000
#define DBNAME  "sample.cdb"

// Convert an integer to its string representation.
std::string int2str(int i)
{
    std::stringstream ss;
    ss << std::setfill('0') << std::setw(6) << i;
    return ss.str();
}

bool build()
{
    // Open a database file for writing (with binary mode).
    std::ofstream ofs(DBNAME, std::ios_base::binary);
    if (ofs.fail()) {
        std::cerr << "ERROR: Failed to open a database file." << std::endl;
        return false;
    }

    try {
        // Create an instance of CDB++ writer.
        cdbpp::builder dbw(ofs);

        // Insert key/value pairs to the CDB++ writer.
        for (int i = 0;i < N;++i) {
            std::string key = int2str(i);
            dbw.put(key.c_str(), key.length(), &i, sizeof(i));
        }

        // Destructing the CDB++ writer flushes the database to the stream.

    } catch (const cdbpp::builder_exception& e) {
        // Abort if something went wrong...
        std::cerr << "ERROR: " << e.what() << std::endl;
        return false;
    }

    return true;
}

bool read()
{
    // Open the database file for reading (with binary mode).
    std::ifstream ifs(DBNAME, std::ios_base::binary);
    if (ifs.fail()) {
        std::cerr << "ERROR: Failed to open a database file." << std::endl;
        return false;
    }

    try {
        // Open the database from the input stream.
        cdbpp::cdbpp dbr(ifs);
        if (!dbr.is_open()) {
            std::cerr << "ERROR: Failed to read a database file." << std::endl;
            return false;
        }

        // Issue queries to the database.
        for (int i = 0;i < N;++i) {
            size_t vsize;
            std::string key = int2str(i);
            const int *value = (const int*)dbr.get(key.c_str(), key.length(), &vsize);
            if (value == NULL) {
                std::cerr << "ERROR: The key is not found." << std::endl;
                return false;
            }

            if (vsize != sizeof(int) || *value != i) {
                std::cerr << "ERROR: The key value is wrong." << std::endl;
                return false;
            }
        }

    } catch (const cdbpp::cdbpp_exception& e) {
        // Abort if something went wrong...
        std::cerr << "ERROR: " << e.what() << std::endl;
        return false;
    }

    return true;
}

int main(int argc, char *argv[])
{
    // Build a sample database and test it.
    bool b = build() && read();
    std::cout << (b ? "OK" : "FAIL") << std::endl;
    return b ? 0 : 1;
}

The source code of CDB++ includes the MurmurHash 2.0 implemented by Austin Appleby.

The CDB++ distribution contains "a portable stdint.h", which is released by Paul Hsieh under the term of the modified BSD license, for addressing the compatibility issue of Microsoft Visual Studio 2008. The original code is available at: http://www.azillionmonkeys.com/qed/pstdint.h

C++ implementation of Constant Database (CDB++)

Introduction

Sample code

Download

History

Documentation

Acknowledgements

References