TinyTable.h

Go to the documentation of this file.

// -*- mode: C++; c-file-style: "stroustrup"; c-basic-offset: 4; indent-tabs-mode: nil; -*-
////////////////////////////////////////////////////////////////////
//
// Filename : TinyTable.h
//
// This file is a part of the UPPAAL toolkit.
// Copyright (c) 1995 - 2003, Uppsala University and Aalborg University.
// All right reserved.
//
// $Id: TinyTable.h,v 1.1 2005/04/22 15:20:10 adavid Exp $
//
////////////////////////////////////////////////////////////////////

#ifndef INCLUDE_HASH_TINYTABLE_H
#define INCLUDE_HASH_TINYTABLE_H

#include "base/intutils.h"
#include "base/bitstring.h"

/** @file
 * This is a template for tiny hash tables that are:
 * - tiny
 * - allocated on the stack
 * - very fast
 * - not resizable
 * - bounded in the number of elements they can accept
 *   when instantiated
 * - able to store only void* or uint32_t
 * The trick is to allocate on the stack a int[something]
 * and instantiate TinyTable with this int[..]
 * The tiny hash table is a uint32_t[] managed by a few
 * simple functions.
 */

namespace hash
{
    class TinyTable
    {
    public:
        /** Constructor:
         * @param max: size of the table
         * @param mem: the table itself.
         * @pre max is a power of 2
         */
        TinyTable(uint32_t *mem, size_t max)
            : table(mem), mask(max-1)
        {
            base_resetSmall(mem, max);
        }

        /** @return size needed in uint32_t to store n items.
         * Use a power of 2 for speed, and use larger table to
         * reduce collisions.
         * @pre n != 0
         */
        static size_t intsizeFor(size_t n)
        {
            assert(n);
            n = base_fmsb32(n);
            return (1 << (n+3));
        }

        /** Add a pointer = wrap for int. */
        bool add(const void* ptr)
        {
            // 32 bits pointers -> lower bits == 0 so >>2 gives a good hash
            return add(((uintptr_t)ptr) >> 2);
        }

        /** Add an int. You should add at max n items as 
         * used in hash_sizeofTinyTable(n).
         * @return true if it was accepted, or false
         * if it was refused, ie, already present in the table.
         * @param val: int to add.
         * @pre val != 0 -- special value.
         */
        bool add(uint32_t val)
        {
            assert(val);
            // no collision list -> use next entry in table
            for(uint32_t index = val; table[index & mask] != val; ++index)
            {
                if (table[index & mask] == 0)
                {
                    table[index & mask] = val;
                    return true;
                }
            }
            return false;
        }

    private:
        uint32_t *table; ///< hash table
        uint32_t mask;   ///< binary mask = size-1 where size is a power of 2
    };
}

#endif // INCLUDE_HASH_TINYTABLE_H

---