<|start_filename|>error.cpp<|end_filename|>
// Copyright (C) 2014-2015 <NAME> <<EMAIL>>
// This file is subject to the license terms in the LICENSE file
// found in the top-level directory of this distribution.

#include "error.hpp"

#include <atomic>
#include <sstream>

namespace sid = foonathan::string_id;

namespace
{    
    void default_collision_handler(sid::hash_type hash, const char *a, const char *b)
    {
        throw sid::collision_error(hash, a, b);
    }
    
#if FOONATHAN_STRING_ID_ATOMIC_HANDLER
    std::atomic<sid::collision_handler> collision_h(default_collision_handler);
#else
    sid::collision_handler collision_h(default_collision_handler);
#endif
}

sid::collision_handler sid::set_collision_handler(collision_handler h)
{
#if FOONATHAN_STRING_ID_ATOMIC_HANDLER
    return collision_h.exchange(h);
#else
    auto val = collision_h;
    collision_h = h;
    return val;
#endif
}

sid::collision_handler sid::get_collision_handler()
{
    return collision_h;
}

const char* sid::collision_error::what() const FOONATHAN_NOEXCEPT try
{
    return what_.c_str();
}
catch (...)
{
    return "foonathan::string_id::collision_error: two different strings are producing the same value";
}

namespace
{
    FOONATHAN_CONSTEXPR auto no_tries_generation = 8u;
    
    bool default_generation_error_handler(std::size_t no, const char *generator_name,
                                          sid::hash_type, const char *)
    {
        if (no >= no_tries_generation)
            throw sid::generation_error(generator_name);
        return true;
    }
    
#if FOONATHAN_STRING_ID_ATOMIC_HANDLER
    std::atomic<sid::generation_error_handler> generation_error_h(default_generation_error_handler);
#else
    sid::generation_error_handler generation_error_h(default_generation_error_handler);
#endif
}

sid::generation_error_handler sid::set_generation_error_handler(generation_error_handler h)
{
#if FOONATHAN_STRING_ID_ATOMIC_HANDLER
    return generation_error_h.exchange(h);
#else
    auto val = generation_error_h;
    generation_error_h = h;
    return val;
#endif
}

sid::generation_error_handler sid::get_generation_error_handler()
{
    return generation_error_h;
}

const char* sid::generation_error::what() const FOONATHAN_NOEXCEPT try
{
    return what_.c_str();
}
catch (...)
{
    return "foonathan::string_id::generation_error: unable to generate new string id.";
}


<|start_filename|>example/main.cpp<|end_filename|>
// Copyright (C) 2014-2015 <NAME> <<EMAIL>>
// This file is subject to the license terms in the LICENSE file
// found in the top-level directory of this distribution.

#include <ctime> // std::time
#include <iostream>
#include <random> // std::mt19937
#include <vector>

#include "../database.hpp" // for the databases
#include "../error.hpp" // for error handling
#include "../generator.hpp" // for the generator classes
#include "../string_id.hpp" // for the string_id

// namespace alias
namespace sid = foonathan::string_id;

int main() try
{
    // this allows using the literal
    using namespace sid::literals;
    
    // create database to store the strings in
    // it must stay valid as long as each string_id using it
    sid::default_database database;
    
    //=== string_id usage ===//
    // create an id
    sid::string_id sid("Test0815", database);
    std::cout << "Hash code " << sid.hash_code() << " belongs to string \"" << sid.string() << "\"\n";
    // Output (Database supports retrieving): Hash code 16741300784925887095 belongs to string "Test0815"
    // Output (Database doesn't): Hash code 16741300784925887095 belongs to string "string_id database disabled"
    
    sid::string_id a("Hello", database), b("World", database);
    
    // compare two ids
    std::cout << std::boolalpha << (a == b) << '\n';
    // Output: false
    
    // compare id with constant
#if FOONATHAN_STRING_ID_HAS_LITERAL
    std::cout << (a == "Hello"_id) << '\n';
#else
    std::cout << (a == id("Hello")) << '\n';
#endif
    // Output: true
    
#if FOONATHAN_STRING_ID_HAS_LITERAL
    // literal is compile-time
    switch (b.hash_code())
    {
    case "Hello"_id:
        std::cout << "Hello\n";
        break;
    case "world"_id: // case-sensitive
        std::cout << "world\n";
        break;
    case "World"_id:
        std::cout << "World\n";
        break;
    }
#endif
    
    //=== generation ===//
    // the prefix for all generated ids
    sid::string_id prefix("entity-", database);
    try
    {
        // a generator type appending 8 random characters to the prefix
        // it uses the std::mt19937 generator for the actual generation
        typedef sid::random_generator<std::mt19937, 8> generator_t;
        // create a generator, seed the random number generator with the current time
        generator_t generator(prefix, std::mt19937(std::int_fast32_t(std::time(nullptr))));
        
        std::vector<sid::string_id> ids;
        for (auto i = 0; i != 10; ++i)
            // generate new identifier
            // it is guaranteed unique and will be stored in the database of the prefix
            ids.push_back(generator());
        
        // print the name of all the ids
        for (auto &id : ids)
            std::cout << id.string() << '\n';
        // possible generated name: entity-jXRnZAVG
    }
    catch (sid::generation_error &ex)
    {
        // the generator was unable to generate a new unique identifier (very unlikely)
        std::cerr << "[ERROR] " << ex.what() << '\n';
    }
    
    try
    {
        // a generator appending an increasing number to the prefix
        typedef sid::counter_generator generator_t;
        
        // create a generator starting with 0, each number will be 4 digits long
        generator_t generator(prefix, 0, 4);
        
        std::vector<sid::string_id> ids;
        for (auto i = 0; i != 10; ++i)
            // generate new identifier
            // it is guaranteed unique and will be stored in the database of the prefix
            ids.push_back(generator());
        
        // print the name of all the ids
        for (auto &id : ids)
            std::cout << id.string() << '\n';
        // possible generated name: entity-0006
    }
    catch (sid::generation_error &ex)
    {
        // the generator was unable to generate a new unique identifier (very unlikely)
        std::cerr << "[ERROR] " << ex.what() << '\n';
    }
}
catch (sid::collision_error &ex)
{
    // two different strings are resulting in the same hash value (very unlikely)
    std::cerr << "[ERROR] " << ex.what() << '\n';
}


<|start_filename|>config.hpp<|end_filename|>
// Copyright (C) 2014-2015 <NAME> <<EMAIL>>
// This file is subject to the license terms in the LICENSE file
// found in the top-level directory of this distribution.

// dummy header including the real config file from the CMake binary dir

#ifndef FOONATHAN_STRING_ID_CONFIG_HPP_INCLUDED
#define FOONATHAN_STRING_ID_CONFIG_HPP_INCLUDED

#include "config_impl.hpp"

#endif // FOONATHAN_STRING_ID_CONFIG_HPP_INCLUDED


<|start_filename|>basic_database.hpp<|end_filename|>
// Copyright (C) 2014-2015 <NAME> <<EMAIL>>
// This file is subject to the license terms in the LICENSE file
// found in the top-level directory of this distribution.

#ifndef FOONATHAN_STRING_ID_BASIC_DATABASE_HPP_INCLUDED
#define FOONATHAN_STRING_ID_BASIC_DATABASE_HPP_INCLUDED

#include "config.hpp"
#include "hash.hpp"

namespace foonathan { namespace string_id
{
	/// \brief The interface for all databases.
    /// \detail You can derive own databases from it.
    class basic_database
    {
    public:        
        /// @{
        /// \brief Databases are not copy- or moveable.
        /// \detail You must not write a swap function either!<br>
        /// This has implementation reasons.
        basic_database(const basic_database &) = delete;
        basic_database(basic_database &&) = delete;
        /// @}

        virtual ~basic_database() = default;
        
        /// \brief The status of an insert operation.
        enum insert_status
        {
            /// \brief Two different strings collide on the same value.
            collision,
            /// \brief A new string was inserted.
            new_string,
            /// \brief The string already existed inside the database.
            old_string
        };
        
        /// \brief Should insert a new hash-string-pair with prefix (optional) into the internal database.
        /// \detail The string must be copied prior to storing, it may not stay valid.
        /// \arg \c hash is the hash of the string.
        /// \arg \c str is the string which does not need to be null-terminated.
        /// \arg \c length is the length of the string.
        /// \return The \ref insert_status.
        virtual insert_status insert(hash_type hash, const char* str, std::size_t length) = 0;
        
        /// \brief Inserts a hash-string-pair with given prefix into the internal database.
        /// \detail The default implementation performs a lookup of the prefix string and appends it,
        /// then it calls \ref insert.<br>
        /// Override it if you can do it more efficiently.
        /// \arg \c hash is the hash of the string plus prefix.
        /// \arg \c prefix is the hash of the prefix-string.
        /// \arg \c str is the suffix which does not need to be null-terminated.
        /// \arg \c length is the length of the suffix.
        /// \return The \ref insert_status.
        virtual insert_status insert_prefix(hash_type hash, hash_type prefix,
                                            const char *str, std::size_t length);
        
        /// \brief Should return the string stored with a given hash.
        /// \detail It is guaranteed that the hash value has been inserted before.
        /// \return A null-terminated string belonging to the hash code or
        /// an error message if the database does not store anything.<br>
        /// The return value must stay valid as long as the database exists.
        virtual const char* lookup(hash_type hash) const FOONATHAN_NOEXCEPT = 0;
        
    protected:
        basic_database() = default;
    };
}} // foonathan::string_id

#endif // FOONATHAN_STRING_ID_BASIC_DATABASE_HPP_INCLUDED


<|start_filename|>string_id.cpp<|end_filename|>
// Copyright (C) 2014-2015 <NAME> <<EMAIL>>
// This file is subject to the license terms in the LICENSE file
// found in the top-level directory of this distribution.

#include "string_id.hpp"

#include "error.hpp"

namespace sid = foonathan::string_id;

namespace
{
    void handle_collision(sid::basic_database &db, sid::hash_type hash, const char *str)
    {
        auto handler = sid::get_collision_handler();
        auto second = db.lookup(hash);
        handler(hash, str, second);
    }
}

sid::string_id::string_id(string_info str, basic_database &db)
{
    basic_database::insert_status status;
    *this = string_id(str, db, status);
    if (!status)
        handle_collision(*db_, id_, str.string);
}

sid::string_id::string_id(string_info str, basic_database &db,
                          basic_database::insert_status &status)
: id_(detail::sid_hash(str.string)), db_(&db)
{
    status = db_->insert(id_, str.string, str.length);
}

sid::string_id::string_id(const string_id &prefix, string_info str)
{
    basic_database::insert_status status;
    *this = string_id(prefix, str, status);
    if (!status)
        handle_collision(*db_, id_, str.string);
}

sid::string_id::string_id(const string_id &prefix, string_info str,
                          basic_database::insert_status &status)
: id_(detail::sid_hash(str.string, prefix.hash_code())), db_(prefix.db_)
{
    status = db_->insert_prefix(id_, prefix.hash_code(), str.string, str.length);
}

const char* sid::string_id::string() const FOONATHAN_NOEXCEPT
{
    return db_->lookup(id_);
}



<|start_filename|>hash.hpp<|end_filename|>
// Copyright (C) 2014-2015 <NAME> <<EMAIL>>
// This file is subject to the license terms in the LICENSE file
// found in the top-level directory of this distribution.

#ifndef FOONATHAN_STRING_ID_HASH_HPP_INCLUDED
#define FOONATHAN_STRING_ID_HASH_HPP_INCLUDED

#include <cstdint>

#include "config.hpp"

namespace foonathan { namespace string_id
{
    /// \brief The type of a hashed string.
    /// \detail This is an unsigned integral type.
    typedef std::uint64_t hash_type;
    
    namespace detail
    {
        FOONATHAN_CONSTEXPR hash_type fnv_basis = 14695981039346656037ull;
        FOONATHAN_CONSTEXPR hash_type fnv_prime = 1099511628211ull;
        
        // FNV-1a 64 bit hash
        FOONATHAN_CONSTEXPR_FNC hash_type sid_hash(const char *str, hash_type hash = fnv_basis)
        {
            return *str ? sid_hash(str + 1, (hash ^ *str) * fnv_prime) : hash;
        }
    } // namespace detail
}} // foonathan::string_id

#endif // FOONATHAN_STRING_ID_DETAIL_HASH_HPP_INCLUDED


<|start_filename|>generator.hpp<|end_filename|>
// Copyright (C) 2014-2015 <NAME> <<EMAIL>>
// This file is subject to the license terms in the LICENSE file
// found in the top-level directory of this distribution.

#ifndef FOONATHAN_STRING_ID_GENERATOR_HPP_INCLUDED
#define FOONATHAN_STRING_ID_GENERATOR_HPP_INCLUDED

#include <atomic>
#include <random>

#include "config.hpp"
#include "string_id.hpp"

namespace foonathan { namespace string_id
{
    namespace detail
    {
        bool handle_generation_error(std::size_t counter, const char *name, const string_id &result);
        
        template <typename Generator>
        string_id try_generate(const char *name, Generator generator, const string_id &prefix)
        {
            basic_database::insert_status status;
            auto result = string_id(prefix, generator(), status);
            for (std::size_t counter = 1;
                 status != basic_database::new_string &&
                 handle_generation_error(counter, name, result);
                 ++counter)
                result = string_id(prefix, generator(), status);
            return result;
        }
    }
    
    /// \brief A generator that generates string ids with a prefix followed by a number.
    /// \detail It can be used by multiple threads at the same time.
    class counter_generator
    {
    public:
        /// \brief The type of the internal state, an unsigned integer.
        typedef unsigned long long state;
        
        /// \brief Creates a new generator with given prefix.
        /// \arg \c counter is the start value for the counter.
        /// \arg \c length is the length of the number appended.If it is \c 0,
        /// there are no restrictions. Else it will either prepend zeros to the number
        /// or cut the number to \c length digits. 
        /// \note For implementation reasons, \c length can't be higher than a certain value.
        /// If it is, it behaves as if \c length has this certain value.
        explicit counter_generator(const string_id &prefix,
                                   state counter = 0, std::size_t length = 0)
        : prefix_(prefix), counter_(counter), length_(length) {}
        
        /// \brief Generates a new \ref string_id.
        /// \detail If it was already generated previously, the \ref generator_error_handler will be called in a loop as described there.
        string_id operator()();
        
        /// \brief Discards a number of states by advancing the counter.
        void discard(unsigned long long n) FOONATHAN_NOEXCEPT;
        
    private:
        string_id prefix_;
        std::atomic<state> counter_;
        std::size_t length_;
    };
    
    /// \brief Information about the characters used by \ref random_generator.
    struct character_table
    {
        /// \brief A pointer to an array of characters.
        const char* characters;
        /// \brief The length of it.
        std::size_t no_characters;
        
        /// \brief Creates a new table.
        character_table(const char* chars, std::size_t no) FOONATHAN_NOEXCEPT
        : characters(chars), no_characters(no) {}
        
        /// \brief A table with all English letters (both cases) and digits.
        static character_table alnum() FOONATHAN_NOEXCEPT;
        
        /// \brief A table with all English letters (both cases).
        static character_table alpha() FOONATHAN_NOEXCEPT;
    };
    
    /// \brief A generator that generates string ids by appendending random characters to a prefix.
    /// \detail This class is thread safe if the random number generator is thread safe.
    template <class RandomNumberGenerator, std::size_t Length>
    class random_generator
    {        
    public:        
        /// \brief The state of generator, a random number generator like \c std::mt19937.
        typedef RandomNumberGenerator state;
        
        /// \brief The number of characters appended.
        static FOONATHAN_CONSTEXPR_FNC std::size_t length() FOONATHAN_NOEXCEPT
        {
            return Length;
        }
        
        /// \brief Creates a new generator with given prefix, random number generator and character table.
        /// \detail By default is uses the table \ref character_table::alnum().
        explicit random_generator(const string_id &prefix,
                                  state s = state(),
                                  character_table table = character_table::alnum())
        : prefix_(prefix), state_(std::move(s)),
          table_(table) {}
        
        /// \brief Generates a new \ref string_id.
        /// \detail If it was already generated previously, the \ref generator_error_handler will be called in a loop as described there.
        string_id operator()()
        {
            std::uniform_int_distribution<std::size_t>
                dist(0, table_.no_characters - 1);
            char random[Length];
            return detail::try_generate("foonathan::string_id::random_generator",
                    [&]()
                    {
                        for (std::size_t i = 0u; i != Length; ++i)
                            random[i] = table_.characters[dist(state_)];
                        return string_info(random, Length);
                    }, prefix_);
        }
        
        /// \brief Discards a certain number of states, this forwards to the random number generator.
        void discard(unsigned long long n)
        {
            state_.discard(n);
        }
        
    private:
        string_id prefix_;
        state state_;
        character_table table_;
    };
}} // namespace foonathan::string_id

#endif // FOONATHAN_STRING_ID_GENERATOR_HPP_INCLUDED


<|start_filename|>database.cpp<|end_filename|>
// Copyright (C) 2014-2015 <NAME> <<EMAIL>>
// This file is subject to the license terms in the LICENSE file
// found in the top-level directory of this distribution.

#include "database.hpp"

#include <cassert>
#include <cmath>
#include <cstring>
#include <string>

namespace sid = foonathan::string_id;

sid::basic_database::insert_status sid::basic_database::insert_prefix(hash_type hash, hash_type prefix,
                                                                      const char *str, std::size_t length)
{
    std::string prefix_str = lookup(prefix);
    return insert(hash, (prefix_str + str).c_str(), prefix_str.size() + length);
}

namespace
{
    // equivalent to prefix + str == other_str for std::string
    // prefix and other_str are null-terminated
    bool strequal(const char *prefix,
                  const char *str, std::size_t length, const char *other_str) FOONATHAN_NOEXCEPT
    {
        assert(prefix);
        while (*prefix)
            if (*prefix++ != *other_str++)
                return false;
        return std::strncmp(str, other_str, length) == 0;
    }
}

/// \cond impl
class sid::map_database::node_list
{    
    struct node
    {
        std::size_t length; // length of string
        hash_type hash;
        node *next;
        
        node(const char *str, std::size_t length,
             hash_type h, node *next) FOONATHAN_NOEXCEPT
        : length(length), hash(h), next(next)
        {
            void* mem = this;
            auto dest = static_cast<char*>(mem) + sizeof(node);
            std::strncpy(dest, str, length);
            dest[length] = 0;
        }
        
        node(const char *prefix, std::size_t length_prefix,
             const char *str, std::size_t length_string,
             hash_type h, node *next) FOONATHAN_NOEXCEPT
        : length(length_prefix + length_string), hash(h), next(next)
        {
            void* mem = this;
            auto dest = static_cast<char*>(mem) + sizeof(node);
            std::strncpy(dest, prefix, length_prefix);
            dest += length_prefix;
            std::strncpy(dest, str, length_string);
            dest[length_string] = 0;
        }
        
        const char* get_str() const FOONATHAN_NOEXCEPT
        {
            const void *mem = this;
            return static_cast<const char*>(mem) + sizeof(node);
        }
    };
    
    struct insert_pos_t
    {        
        bool exists; // if true: cur set, else: prev and next set
        
        node*& prev;
        node* next;
        
        node* cur;
        
        insert_pos_t(node*& prev, node *next) FOONATHAN_NOEXCEPT
        : exists(false), prev(prev), next(next), cur(nullptr) {}
        
        insert_pos_t(node *cur) FOONATHAN_NOEXCEPT
        : exists(true), prev(this->cur), next(nullptr), cur(cur) {}
    };
    
public:
    node_list() FOONATHAN_NOEXCEPT
    : head_(nullptr) {}
    
    ~node_list() FOONATHAN_NOEXCEPT
    {
        auto cur = head_;
        while (cur)
        {
            auto next = cur->next;
            ::operator delete(cur);
            cur = next;
        }
    }
    
    basic_database::insert_status insert(hash_type hash, const char *str, std::size_t length)
    {
        auto pos = insert_pos(hash);
        if (pos.exists)
            return std::strncmp(str, pos.cur->get_str(), length) == 0 ?
                   basic_database::old_string : basic_database::collision;
        auto mem = ::operator new(sizeof(node) + length + 1);
        auto n = ::new(mem) node(str, length, hash, pos.next);
        pos.prev = n;
        return basic_database::new_string;
    }
    
    basic_database::insert_status insert_prefix(node_list &prefix_bucket, hash_type prefix,
                                                hash_type hash, const char *str, std::size_t length)
    {
        auto prefix_node = prefix_bucket.find_node(prefix);
        auto pos = insert_pos(hash);
        if (pos.exists)
            return strequal(prefix_node->get_str(), str, length, pos.cur->get_str()) ?
                   basic_database::old_string : basic_database::collision;
        auto mem = ::operator new(sizeof(node) + prefix_node->length + length + 1);
        auto n = ::new(mem) node(prefix_node->get_str(), prefix_node->length,
                                 str, length, hash, pos.next);
        pos.prev = n;
        return basic_database::new_string;
    }
    
    // inserts all nodes into new buckets, this list is empty afterwards
    void rehash(node_list *buckets, std::size_t size) FOONATHAN_NOEXCEPT
    {
        auto cur = head_;
        while (cur)
        {
            auto next = cur->next;
            auto pos = buckets[cur->hash % size].insert_pos(cur->hash);
            assert(!pos.exists && "element can't be there already");
            pos.prev = cur;
            cur->next = pos.next;
            cur = next;
        }
        head_ = nullptr;
    }
    
    // returns element with hash, there must be one
    const char* lookup(hash_type h) const FOONATHAN_NOEXCEPT
    {
        return find_node(h)->get_str();
    }
    
private:
    node* find_node(hash_type h) const FOONATHAN_NOEXCEPT
    {
        assert(head_ && "hash not inserted");
        auto cur = head_;
        while (cur->hash < h)
        {
            cur = cur->next;
            assert(cur && "hash not inserted");
        }
        assert(cur->hash == h && "hash not inserted");
        return cur;
    }
    
    insert_pos_t insert_pos(hash_type hash) FOONATHAN_NOEXCEPT
    {
        node *cur = head_, *prev = nullptr;
        while (cur && cur->hash <= hash)
        {
            if (cur->hash < hash)
            {
                prev = cur;
                cur = cur->next;
            }
            else if (cur->hash == hash)
                return {cur};
        }
        return {prev ? prev->next : head_, cur};
    }
    
    node *head_;
};
/// \endcond

sid::map_database::map_database(std::size_t size, double max_load_factor)
: buckets_(new node_list[size]),
  no_items_(0u), no_buckets_(size),
  max_load_factor_(max_load_factor),
  next_resize_(static_cast<std::size_t>(std::floor(no_buckets_ * max_load_factor_)))
{}

sid::map_database::~map_database() FOONATHAN_NOEXCEPT {}

sid::basic_database::insert_status sid::map_database::insert(hash_type hash, const char *str, std::size_t length)
{
    if (no_items_ + 1 >= next_resize_)
        rehash();
    auto status = buckets_[hash % no_buckets_].insert(hash, str, length);
    if (status == insert_status::new_string)
        ++no_items_;
    return status;
}

sid::basic_database::insert_status sid::map_database::insert_prefix(hash_type hash, hash_type prefix,
                                                                    const char *str, std::size_t length)
{
    if (no_items_ + 1 >= next_resize_)
        rehash();
    auto status = buckets_[hash % no_buckets_].insert_prefix(buckets_[prefix % no_buckets_], prefix,
                                                             hash, str, length);
    if (status == insert_status::new_string)
        ++no_items_;
    return status;
}

const char* sid::map_database::lookup(hash_type hash) const FOONATHAN_NOEXCEPT
{
    return buckets_[hash % no_buckets_].lookup(hash);
}

void sid::map_database::rehash()
{
    static FOONATHAN_CONSTEXPR auto growth_factor = 2;
    auto new_size = growth_factor * no_buckets_;
    auto buckets = new node_list[new_size]();
    auto end = buckets_.get() + no_buckets_;
    for (auto list = buckets_.get(); list != end; ++list)
        list->rehash(buckets, new_size);
    buckets_.reset(buckets);
    no_buckets_ = new_size;
    next_resize_ = static_cast<std::size_t>(std::floor(no_buckets_ * max_load_factor_));
}


<|start_filename|>generator.cpp<|end_filename|>
// Copyright (C) 2014-2015 <NAME> <<EMAIL>>
// This file is subject to the license terms in the LICENSE file
// found in the top-level directory of this distribution.

#include "generator.hpp"

#include <cassert>
#include <cstring>
#include <utility>

#include "error.hpp"

namespace sid = foonathan::string_id;

bool sid::detail::handle_generation_error(std::size_t counter, const char *name, const string_id &result)
{
    return get_generation_error_handler()(counter, name, result.hash_code(), result.string());
}

namespace
{    
    sid::string_info to_string(sid::counter_generator::state s, char *begin, char *end,
                               std::size_t length)
    {
        auto cur = end;
        std::size_t i = 0;
        
        do
        {
            *--cur = '0' + (s % 10);
            s /= 10;
            ++i;
        } while (s != 0u);
        
        if (i < length)
            for (; cur - 1 != begin && i < length; ++i)
                *--cur = '0';
        else if (length && i > length)
            cur += i - length;
            
        return sid::string_info(cur, end - cur);
    }
}

sid::string_id sid::counter_generator::operator()()
{
    // 4 times sizeof(state) is enough for the integer representation
    static FOONATHAN_CONSTEXPR auto max_size = 4 * sizeof(state);
    char string[max_size];
    return detail::try_generate("foonathan::string_id::counter_generator",
                                [&]()
                                {
                                    return to_string(counter_++, string, string + max_size, length_);
                                }, prefix_);
}

void sid::counter_generator::discard(unsigned long long n) FOONATHAN_NOEXCEPT
{
    counter_ += n;
}

namespace
{
    static FOONATHAN_CONSTEXPR char table[]
    = "ABCDEFGHIJKLMNOPQRSTUVW<KEY>";
}

sid::character_table sid::character_table::alnum() FOONATHAN_NOEXCEPT
{
    return {table, sizeof(table) - 1};
}

sid::character_table sid::character_table::alpha() FOONATHAN_NOEXCEPT
{
    return {table, sizeof(table) - 1 - 10};
}


<|start_filename|>database.hpp<|end_filename|>
// Copyright (C) 2014-2015 <NAME> <<EMAIL>>
// This file is subject to the license terms in the LICENSE file
// found in the top-level directory of this distribution.

#ifndef FOONATHAN_STRING_ID_DATABASE_HPP_INCLUDED
#define FOONATHAN_STRING_ID_DATABASE_HPP_INCLUDED

#include <memory>
#include <mutex>

#include "basic_database.hpp"
#include "config.hpp"

namespace foonathan { namespace string_id
{    
    /// \brief A database that doesn't store the string-values.
    /// \detail It does not detect collisions or allows retrieving,
    /// \c lookup() returns "string_id database disabled".
    class dummy_database : public basic_database
    {
    public:        
        insert_status insert(hash_type, const char *, std::size_t) FOONATHAN_OVERRIDE
        {
            return new_string;
        }
        
        insert_status insert_prefix(hash_type, hash_type, const char *, std::size_t) FOONATHAN_OVERRIDE
        {
            return new_string;
        }
        
        const char* lookup(hash_type) const FOONATHAN_NOEXCEPT FOONATHAN_OVERRIDE
        {
            return "string_id database disabled";
        }
    };
    
    /// \brief A database that uses a highly optimized hash table.
    class map_database : public basic_database
    {
    public:        
        /// \brief Creates a new database with given number of buckets and maximum load factor.
        explicit map_database(std::size_t size = 1024, double max_load_factor = 1.0);
        ~map_database() FOONATHAN_NOEXCEPT;
        
        insert_status insert(hash_type hash, const char *str, std::size_t length) FOONATHAN_OVERRIDE;
        insert_status insert_prefix(hash_type hash, hash_type prefix,
                                    const char *str, std::size_t length) FOONATHAN_OVERRIDE;
        const char* lookup(hash_type hash) const FOONATHAN_NOEXCEPT FOONATHAN_OVERRIDE;
        
    private:        
        void rehash();
        
        class node_list;
        std::unique_ptr<node_list[]> buckets_;
        std::size_t no_items_, no_buckets_;
        double max_load_factor_;
        std::size_t next_resize_;
    };
    
    /// \brief A thread-safe database adapter.
    /// \detail It derives from any database type and synchronizes access via \c std::mutex.
    template <class Database>
    class thread_safe_database : public Database
    {
    public:
        /// \brief The base database.
        typedef Database base_database;
        
        // workaround of lacking inheriting constructors
		template <typename ... Args>
        explicit thread_safe_database(Args&&... args)
		: base_database(std::forward<Args>(args)...) {}
        
        typename Database::insert_status
            insert(hash_type hash, const char *str, std::size_t length) FOONATHAN_OVERRIDE
        {
            std::lock_guard<std::mutex> lock(mutex_);
            return Database::insert(hash, str, length);
        }
        
        typename Database::insert_status
            insert_prefix(hash_type hash, hash_type prefix, const char *str, std::size_t length) FOONATHAN_OVERRIDE
        {
            std::lock_guard<std::mutex> lock(mutex_);
            return Database::insert_prefix(hash, prefix, str, length);
        }
        
        const char* lookup(hash_type hash) const FOONATHAN_NOEXCEPT FOONATHAN_OVERRIDE
        {
            std::lock_guard<std::mutex> lock(mutex_);
            return Database::lookup(hash);
        }
        
    private:
        mutable std::mutex mutex_;
    };
    
    /// \brief The default database where the strings are stored.
    /// \detail Its exact type is one of the previous listed databases.
    /// You can control its selection via the macros listed in config.hpp.in.
#if FOONATHAN_STRING_ID_DATABASE && FOONATHAN_STRING_ID_MULTITHREADED
    typedef thread_safe_database<map_database> default_database;
#elif FOONATHAN_STRING_ID_DATABASE
    typedef map_database default_database;
#else
    typedef dummy_database default_database;
#endif
}} // namespace foonathan::string_id

#endif // FOONATHAN_STRING_ID_DATABASE_HPP_INCLUDED


<|start_filename|>string_id.hpp<|end_filename|>
// Copyright (C) 2014-2015 <NAME> <<EMAIL>>
// This file is subject to the license terms in the LICENSE file
// found in the top-level directory of this distribution.

#ifndef FOONATHAN_STRING_ID_HPP_INCLUDED
#define FOONATHAN_STRING_ID_HPP_INCLUDED

#include <cstring>
#include <functional>

#include "basic_database.hpp"
#include "config.hpp"
#include "hash.hpp"

namespace foonathan { namespace string_id
{
    /// \brief Information about a string.
    /// \detail It is used to reduce the number of constructors of \ref string_id.
    struct string_info
    {
        /// \brief A pointer to a null-terminated string.
        const char *string;
        /// \brief The length of this string.
        std::size_t length;
        
        /// \brief Creates it from a null-terminated string (implicit conversion).
        string_info(const char *str) FOONATHAN_NOEXCEPT
        : string(str), length(std::strlen(str)) {}
        
        /// \brief Creates it from a string with given length.
        /// \arg \c str does not need to be null-terminated.
        string_info(const char *str, std::size_t length)
        : string(str), length(length) {}
    };
    
    /// \brief The string identifier class.
    /// \detail This is a lightweight class to store strings.<br>
    /// It only stores a hash of the string allowing fast copying and comparisons.
    class string_id
    {
    public:
        //=== constructors ===//
        /// \brief Creates a new id by hashing a given string.
        /// \detail It will insert the string into the given \ref database which will copy it.<br>
        /// If it encounters a collision, the \ref collision_handler will be called.
        string_id(string_info str, basic_database &db);
        
        /// \brief Creates a new id with a given prefix.
        /// \detail The new id will be inserted into the same database as the prefix.<br>
        //// Otherwise the same as other constructor.
        string_id(const string_id &prefix, string_info str);
        
        /// @{
        /// \brief Sames as other constructor versions but instead of calling the \ref collision_handler,
        /// they set the output parameter to the appropriate status.
        /// \detail This also allows information whether or not the string was already stored inside the database.
        string_id(string_info str, basic_database &db,
                 basic_database::insert_status &status);
                 
        string_id(const string_id &prefix, string_info str,
                  basic_database::insert_status &status);
        /// @}
        
        //=== accessors ===//
        /// \brief Returns the hashed value of the string.
        hash_type hash_code() const FOONATHAN_NOEXCEPT
        {
            return id_;
        }
        
        /// \brief Returns a reference to the database.
        basic_database& database() const FOONATHAN_NOEXCEPT
        {
            return *db_;
        }
        
        /// \brief Returns the string value itself.
        /// \detail This calls the \c lookup function on the database.
        const char* string() const FOONATHAN_NOEXCEPT;
        
        //=== comparision ===//
        /// @{
        /// \brief Compares string ids with another or hashed values.
        /// \detail Two string ids are equal if they are from the same database and they have the same value.<br>
        /// A hashed value is equal to a string id if it is the same value.
        friend bool operator==(string_id a, string_id b) FOONATHAN_NOEXCEPT
        {
            return a.db_ == b.db_ && a.id_ == b.id_;
        }
        
        friend bool operator==(hash_type a, const string_id &b) FOONATHAN_NOEXCEPT
        {
            return a == b.id_;
        }
        
        friend bool operator==(const string_id &a, hash_type b) FOONATHAN_NOEXCEPT
        {
            return a.id_ == b;
        }
        
        friend bool operator!=(const string_id &a, const string_id &b) FOONATHAN_NOEXCEPT
        {
            return !(a == b);
        }
        
        friend bool operator!=(hash_type a, const string_id &b) FOONATHAN_NOEXCEPT
        {
            return !(a == b);
        }
        
        friend bool operator!=(const string_id &a, hash_type b) FOONATHAN_NOEXCEPT
        {
            return !(a == b);
        }
        /// @}
        
    private:
        hash_type id_;
        basic_database *db_;
    };
    
    namespace literals
    {
        /// \brief Same as the literal version, additional replacement if not supported.
        FOONATHAN_CONSTEXPR_FNC hash_type id(const char *str)
        {
            return detail::sid_hash(str);
        }
        
        /// \brief A useful literal to hash a string.
        /// \detail Since this function does not check for collisions only use it to compare a \ref string_id.<br>
        /// It is also useful in places where a compile-time constant is needed.
    #if FOONATHAN_STRING_ID_HAS_LITERAL
        FOONATHAN_CONSTEXPR_FNC hash_type operator""_id(const char *str, std::size_t)
        {
            return detail::sid_hash(str);
        }
    #endif
    } // namespace literals
}} // namespace foonathan::string_id

namespace std
{
    /// \brief \c std::hash support for \ref string_id.
    template <>
    struct hash<foonathan::string_id::string_id>
    {
        typedef foonathan::string_id::string_id argument_type;
        typedef size_t result_type;        
 
        result_type operator()(const argument_type &arg) const FOONATHAN_NOEXCEPT
        {
            return static_cast<result_type>(arg.hash_code());
        }
    };
} // namspace std

#endif // FOONATHAN_STRING_ID_HPP_INCLUDED 
