ut_hash.h

Go to the documentation of this file.

/* -*- mode: C++; tab-width: 4; c-basic-offset: 4; -*- */

/* AbiSource Program Utilities
 *
 * Copyright (C) 2001 Mike Nordell <tamlin@alogonet.se>
 * Copyright (C) 2001 Dom Lachowicz <cinamod@hotmail.com>
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301 USA.
 */

#ifndef UT_HASH_H
#define UT_HASH_H

#include <string.h>

/* pre-emptive dismissal; ut_types.h is needed by just about everything,
 * so even if it's commented out in-file that's still a lot of work for
 * the preprocessor to do...
 */
#ifndef UT_TYPES_H
#include "ut_types.h"
#endif

#ifndef UTVECTOR_H
#include "ut_vector.h"
#endif

#include "ut_debugmsg.h"
#include "ut_string_class.h"

#if _MSC_VER >= 1310
// MSVC++ 7.1 warns about debug output limitations.
#pragma warning(disable: 4292)
#endif

// fwd. decl.
template <class T> class hash_slot;

template <class T> class UT_GenericStringMap;

template <class T> class UT_GenericStringMap
{
public:
    UT_GenericStringMap(size_t expected_cardinality = 11);
    virtual ~UT_GenericStringMap();

    // insertion/addition
    bool insert(const char* key, T value);
    bool insert(const UT_String & key, T value);

    void set (const char* key, T val);
    void set (const UT_String & key, T val);

    // "find"
    T pick(const char* key) const;
    T pick(const UT_String & key) const;

    // contains - if contains(key) val will be the result of the lookup
    bool contains(const char* key, T val) const;
    bool contains(const UT_String & key, T val) const;

    // these are for removal
    void remove(const char* key, T /* ignored */);
    void remove(const UT_String & key, T /* ignored */);
    void clear();

    /* IMPORTANT: list() is for use only with <XML_C/char*> maps
     */
    const gchar ** list ();

    UT_GenericVector<T>* enumerate(bool strip_null_values = true) const;
    UT_GenericVector<const UT_String*>* keys(bool strip_null_values = true) const;

    // getting the # keys
    inline size_t size() const { return n_keys; }

    class UT_Cursor
    {
        friend class UT_GenericStringMap<T>;

    public:
        UT_Cursor(const UT_GenericStringMap<T> * owner)
            :   m_d(owner), m_index(-1)
            {
                //m_d._first(this);
            }

        ~UT_Cursor() { }

        // these can't be const since we're passing a non-const this ptr
        inline const UT_String  &key()
            {return m_d->_key(*this); }
        inline void make_deleted()
            {m_d->_make_deleted(*this); }
        inline const T  first()
            { return m_d->_first(*this); }
        inline const T  next()
            { return m_d->_next(*this); }
        inline const T  prev()
            { return m_d->_prev(*this); }
        inline bool is_valid()
            { return (m_index != -1); }

    private:

        inline void _set_index(UT_sint32 i)
            { m_index = i; }
        inline UT_sint32 _get_index()
            { return m_index; }

        const UT_GenericStringMap<T>*   m_d;
        UT_sint32               m_index;
    };

    friend class UT_Cursor;

    /* purge objects by deleting them */
    void purgeData(void)
        {
            UT_Cursor hc1(this);
            for ( T hval1 = hc1.first(); hc1.is_valid(); hval1 = hc1.next() ) {
                if (hval1) {
                    hc1.make_deleted();
                    delete hval1;
                }
            }
        };

    /* purge objects by freeing them */
    void freeData(void)
        {
            UT_Cursor hc1(this);
            for ( T hval1 = hc1.first(); hc1.is_valid(); hval1 = hc1.next() ) {
                if (hval1) {
                    hc1.make_deleted();
                    g_free((gpointer)(hval1));
                }
            }
        }

private:
    UT_GenericStringMap(const UT_GenericStringMap<T>&); // no impl
    void operator=(const UT_GenericStringMap<T>&);      // no impl


    enum SM_search_type
    {
        SM_INSERT,
        SM_LOOKUP,
        SM_REORG
    };

    void reorg(size_t slots_to_allocate);
    void grow();

    void assign_slots(hash_slot<T>* p, size_t old_num_slots);

    static size_t compute_reorg_threshold(size_t nslots);

    bool too_full() const
        { return (n_keys + n_deleted) >= reorg_threshold; }

    bool too_many_deleted() const
        { return n_deleted > (reorg_threshold / 4); }

    bool exceeds_n_delete_threshold() const
        { return n_deleted > (reorg_threshold / 2); }

    hash_slot<T>* find_slot(const UT_String&        k,
                         SM_search_type     search_type,
                         size_t&            slot,
                         bool&              key_found,
                         size_t&            hashval,
                         const void*        v,
                         bool*              v_found,
                         void*              vi,
                         size_t             hashval_in) const;

    hash_slot<T>* find_slot(const char *        k,
                         SM_search_type     search_type,
                         size_t&            slot,
                         bool&              key_found,
                         size_t&            hashval,
                         const void*        v,
                         bool*              v_found,
                         void*              vi,
                         size_t             hashval_in) const;

    // enumeration of the elements
    const T _first(UT_Cursor& c) const;
    const T _next(UT_Cursor& c) const;
    const T _prev(UT_Cursor& c) const;
    const UT_String& _key(UT_Cursor& c) const;
    void _make_deleted(UT_Cursor& c) const;

    // data
    hash_slot<T>* m_pMapping;

    size_t n_keys;
    size_t n_deleted;
    size_t m_nSlots;
    size_t reorg_threshold;
    size_t flags;

    gchar ** m_list;
};

#if 0 //def _MSC_VER // have to intialise the templates in order to have class exported

struct _dataItemPair;
template class ABI_EXPORT UT_GenericStringMap<struct _dataItemPair*>;

class UT_UTF8String;
template class ABI_EXPORT UT_GenericStringMap<UT_UTF8String *>;

class PD_Style;
template class ABI_EXPORT UT_GenericStringMap<PD_Style *>;

class GR_Font;
template class ABI_EXPORT UT_GenericStringMap<GR_Font *>;

template class ABI_EXPORT UT_GenericStringMap<char *>;

//template class ABI_EXPORT UT_GenericStringMap<void const*>;
#endif

// TODO Rob: try to export like this once plugin loading is fixed:
// template class ABI_EXPORT UT_GenericStringMap<void const *>;
class ABI_EXPORT UT_StringPtrMap : public UT_GenericStringMap<void const *> {
public:
    UT_StringPtrMap(size_t expected_cardinality = 11)
    : UT_GenericStringMap<void const *>(expected_cardinality)
    {}
};

// Template implementation

// fwd. decls.
ABI_EXPORT UT_uint32 _Recommended_hash_size(UT_uint32   size);


// wrapper class for keys
class ABI_EXPORT key_wrapper
{
public:
    key_wrapper()
        : m_hashval(0) { }

    void die()
        { m_val.clear(); }

    bool eq(const UT_String &key) const
    {
        return (m_val == key);
    }

    bool eq(const char *key) const
    {
        return (!strcmp(m_val.c_str(),key));
    }

    void operator=(const UT_String &k)
        { m_val = k; }

    UT_uint32 hashval() const
        { return m_hashval; }
    void set_hashval(UT_uint32 h)
        { m_hashval = h; }

    UT_String &value(void)
        {return m_val;}

    void operator=(const key_wrapper& rhs)
        { m_val = rhs.m_val; m_hashval = rhs.m_hashval; }

    static UT_uint32 compute_hash(const UT_String &key)
        {
            return hashcode(key); // UT_String::hashcode
        }

    static UT_uint32 compute_hash(const char *key)
        {
            return hashcode(key);
        }

private:
    UT_String m_val;
    UT_uint32 m_hashval;
};




// bucket for data
template <class T> class hash_slot
{
public:
    hash_slot()
        : m_value(0) { }

    void make_deleted()
        {
            // this is a HACK: if the value of the slot is this, then slot is empty.
            m_value = reinterpret_cast<T>(this);
            m_key.die();
        }
    void make_empty()
        { m_value = 0; }

    const T value() const
        { return m_value; }

    void insert(const T v, const UT_String &k, UT_uint32 h)
        {
            m_value = v;
            m_key = k;
            m_key.set_hashval(h);
        }

    void assign(hash_slot<T>* s)
        {
            m_value = s->value();
            m_key = s->m_key;
        }

    bool empty() const
        { return (m_value == 0); }

    bool deleted() const
        {
            return static_cast<const void*>(this) == m_value;
        }

    bool key_eq(const UT_String &test, size_t h) const
        {
#if 1
            UT_UNUSED(h);
            return m_key.eq(test);
#else
            return m_key.hashval() == h;
#endif
        }

    bool key_eq(const char  *test, size_t h) const
        {
#if 1
            UT_UNUSED(h);
            return m_key.eq(test);
#else
            return m_key.hashval() == h;
#endif
        }

    T   m_value;
    key_wrapper m_key;
};

template <class T>
UT_GenericStringMap<T>::UT_GenericStringMap(size_t expected_cardinality)
:   n_keys(0),
    n_deleted(0),
    m_nSlots(_Recommended_hash_size(expected_cardinality)),
    reorg_threshold(compute_reorg_threshold(m_nSlots)),
    flags(0),
    m_list(0)
{
    m_pMapping = new hash_slot<T>[m_nSlots];
}


template <class T>
UT_GenericStringMap<T>::~UT_GenericStringMap()
{
    DELETEPV(m_pMapping);
    FREEP(m_list);
}

/* IMPORTANT: for use only with <char*> -> <char*> maps
   TODO: make this a specialized method.
 */
template <class T>
const gchar ** UT_GenericStringMap<T>::list()
{
    if (!m_list)
    {
        m_list = reinterpret_cast<gchar **>(g_try_malloc (2 * (n_keys + 1) * sizeof (gchar *)));
        if (m_list == 0)
            return 0;

        UT_uint32 index = 0;

        UT_Cursor c(this);

        for (const gchar * value = (gchar*)(c.first ());
             c.is_valid ();
             value = (gchar*)(c.next ()))
        {
            const char * key = c.key().c_str ();

            if (!key || !value)
                continue;

            m_list[index++] = static_cast<gchar *>(const_cast<char *>(key));
            m_list[index++] = static_cast<gchar *>(const_cast<char *>(value));
        }
        m_list[index++] = NULL;
        m_list[index  ] = NULL;
    }
    return const_cast<const gchar **>(m_list);
}

template <class T>
T UT_GenericStringMap<T>::pick(const char* k) const
{
    hash_slot<T>*       sl = 0;
    bool            key_found = false;
    size_t          slot;
    size_t          hashval;

    sl = find_slot(k, SM_LOOKUP, slot, key_found, hashval, 0, 0, 0, 0);
    return key_found ? sl->value() : 0;
}

template <class T>
T UT_GenericStringMap<T>::pick(const UT_String & k) const
{
  return pick (k.c_str());
}

template <class T>
bool UT_GenericStringMap<T>::contains(const char* k, T v) const
{
  UT_String aKey(k);
  return contains (aKey, v);
}

template <class T>
bool UT_GenericStringMap<T>::contains(const UT_String& k, T v) const
{
    //  hash_slot<T> * sl;
    bool key_found = false;
    bool v_found   = false;
    size_t slot    = 0;
    size_t hashval = 0;

    // DOM: TODO: make this call work
    /*sl =*/ find_slot (k, SM_LOOKUP, slot, key_found,
            hashval, v, &v_found, 0, 0);
    return v_found;
}


template <class T>
bool UT_GenericStringMap<T>::insert(const char* key, T value)
{
  UT_String aKey(key);
  return insert (aKey, value);
}

template <class T>
bool UT_GenericStringMap<T>::insert(const UT_String& key, T value)
{
    FREEP(m_list);

    size_t      slot = 0;
    bool        key_found = false;
    size_t      hashval = 0;

    hash_slot<T>* sl = find_slot(key, SM_INSERT, slot, key_found,
                  hashval, 0, 0, 0, 0);

    if(key_found)
        return false;

    sl->insert(value, key, hashval);
    ++n_keys;

    if (too_full())
    {
        if (too_many_deleted())
        {
            reorg(m_nSlots);
        }
        else
        {
            grow();
        }
    }

    return true;
}

template <class T>
void UT_GenericStringMap<T>::set(const char* key, T value)
{
    UT_String aKey(key);
    set (aKey, value);
}

template <class T>
void UT_GenericStringMap<T>::set(const UT_String& key, T value)
{
    FREEP(m_list);

    size_t      slot = 0;
    bool        key_found = false;
    size_t      hashval = 0;

    hash_slot<T>* sl = find_slot(key, SM_LOOKUP, slot, key_found,
                              hashval, 0, 0, 0, 0);

    if (!sl || !key_found) // TODO: should we insert or just return?
    {
        insert(key, value);
        return;

    }

    sl->insert(value, key, hashval);
}

template <class T>
UT_GenericVector<T>* UT_GenericStringMap<T>::enumerate (bool strip_null_values) const
{
    UT_GenericVector<T> * pVec = new UT_GenericVector<T>(size());

    UT_Cursor cursor(this);

    T val = NULL;

    for (val = cursor.first(); cursor.is_valid(); val = cursor.next ())
    {
        // we don't allow nulls since so much of our code depends on this
        // behavior
        if (!strip_null_values || val)
        {
            pVec->addItem (val);
        }
    }

    return pVec;
}

template <class T>
UT_GenericVector<const UT_String*>* UT_GenericStringMap<T>::keys (bool strip_null_values) const
{
    UT_GenericVector<const UT_String*>* pVec = new UT_GenericVector<const UT_String*>(size());

    UT_Cursor cursor(this);

    T val = NULL;

    for (val = cursor.first(); cursor.is_valid(); val = cursor.next ())
    {
        // we don't allow nulls since so much of our code depends on this
        // behavior
        if (!strip_null_values || val)
        {
            pVec->addItem (&cursor.key());
        }
    }

    return pVec;
}


template <class T>
void UT_GenericStringMap<T>::remove(const char* key, T)
{
    UT_String aKey(key);
    remove (aKey, 0);
}

template <class T>
void UT_GenericStringMap<T>::remove(const UT_String& key, T)
{
    FREEP(m_list);

    size_t slot = 0, hashval;
    bool bFound = false;
    hash_slot<T>* sl = find_slot(key, SM_LOOKUP, slot, bFound,
                              hashval, 0, 0, 0, 0);

    if (bFound)
    {
        sl->make_deleted();
        --n_keys;
        ++n_deleted;
        if (m_nSlots > 11 && m_nSlots / 4 >= n_keys)
        {
            reorg(_Recommended_hash_size(m_nSlots/2));
        }
    }
}

template <class T>
void UT_GenericStringMap<T>::clear()
{
    FREEP(m_list);

    hash_slot<T>* the_slots = m_pMapping;
    for (size_t x=0; x < m_nSlots; x++)
    {
        hash_slot<T>& this_slot = the_slots[x];
        if (!this_slot.empty())
        {
            if (!this_slot.deleted())
            {
                this_slot.make_deleted();
            }
            this_slot.make_empty();
        }
    }
    n_keys = 0;
    n_deleted = 0;
}


/*********************************************************************/
/*********************************************************************/

template <class T>
void UT_GenericStringMap<T>::assign_slots(hash_slot<T>* p, size_t old_num_slot)
{
    size_t target_slot = 0;

    for (size_t slot_num=0; slot_num < old_num_slot; ++slot_num, ++p)
    {
        if (!p->empty() && !p->deleted())
        {
            bool kf = false;

            size_t hv;
            hash_slot<T>* sl = find_slot(p->m_key.value(),
                                      SM_REORG,
                                      target_slot,
                                      kf,
                                      hv,
                                      0,
                                      0,
                                      NULL,
                                      p->m_key.hashval());
            sl->assign(p);
        }
    }
}

template <class T>
size_t UT_GenericStringMap<T>::compute_reorg_threshold(size_t nSlots)
{
    return nSlots * 7 / 10; // reorg threshold = 70% of nSlots
}


template <class T> hash_slot<T>*
UT_GenericStringMap<T>::find_slot(const UT_String& k,
                            SM_search_type  search_type,
                            size_t&         slot,
                            bool&           key_found,
                            size_t&         hashval,
                            const void*     v,
                            bool*           v_found,
                            void*           vi,
                            size_t          hashval_in) const
{
 return find_slot( k.c_str(), search_type, slot, key_found, hashval, v, v_found, vi, hashval_in);
}

template <class T> hash_slot<T>*
UT_GenericStringMap<T>::find_slot(const char *k,
                            SM_search_type  search_type,
                            size_t&         slot,
                            bool&           key_found,
                            size_t&         hashval,
                            const void*     v,
                            bool*           v_found,
                            void*           /*vi*/,
                            size_t          hashval_in) const
{
    if ( m_nSlots == 0 )
      {
        key_found = false ; return NULL ;
      }

    hashval = (hashval_in ? hashval_in : key_wrapper::compute_hash(k));
    int nSlot = hashval % m_nSlots;

    xxx_UT_DEBUGMSG(("DOM: hashval for \"%s\" is %d (#%dth slot)\n", k, hashval, nSlot));

    hash_slot<T>* sl = &m_pMapping[nSlot];

    if (sl->empty())
    {

        xxx_UT_DEBUGMSG(("DOM: empty slot\n"));

        slot = nSlot;
        key_found = false;
        return sl;
    }
    else
    {
        if (search_type != SM_REORG &&
            !sl->deleted() &&
            sl->key_eq(k, hashval))
        {
            slot = nSlot;
            key_found = true;

            if (v_found)
            {
                // so, if v_found is non-null, we should set it.
                // if v is also non-null, sl->value() must match v
                // otherwise we already have a key match, so we win!
                if (v)
                {
                    *v_found = (sl->value() == v);
                } else {
                    *v_found = true;
                }
            }

            xxx_UT_DEBUGMSG(("DOM: found something #1\n"));

            return sl;
        }
    }

    int delta = (nSlot ? (m_nSlots - nSlot) : 1);
    hash_slot<T>* tmp_sl = sl;
    sl = 0;
    size_t s = 0;
    key_found = false;

    while (1)
    {
        nSlot -= delta;
        if (nSlot < 0)
        {
            nSlot += m_nSlots;
            tmp_sl += (m_nSlots - delta);
        }
        else
        {
            tmp_sl -= delta;
        }

        if (tmp_sl->empty())
        {
            if (!s)
            {
                s = nSlot;
                sl = tmp_sl;
            }
            break;

        }

        if (tmp_sl->deleted())
        {
            if (!s)
            {
                s = nSlot;
                sl = tmp_sl;
            }
        }
        else if (search_type != SM_REORG && tmp_sl->key_eq(k, hashval))
        {
            s = nSlot;
            sl = tmp_sl;
            key_found = true;

            if (v_found)
            {
                if (v)
                {
                    *v_found = (sl->value() == v);
                } else {
                    *v_found = true;
                }
            }
            break;
        }
    }

    slot = s;
    return sl;
}


template <class T>
void UT_GenericStringMap<T>::grow()
{
    size_t slots_to_allocate = ::_Recommended_hash_size(m_nSlots / 2 + m_nSlots);
    reorg(slots_to_allocate);
}


template <class T>
void UT_GenericStringMap<T>::reorg(size_t slots_to_allocate)
{
    hash_slot<T>* pOld = m_pMapping;

    if (slots_to_allocate < 11)
    {
        slots_to_allocate = 11;
    }

    m_pMapping = new hash_slot<T>[slots_to_allocate];

    const size_t old_num_slot = m_nSlots;

    m_nSlots = slots_to_allocate;
    reorg_threshold = compute_reorg_threshold(m_nSlots);

    assign_slots(pOld, old_num_slot);
    DELETEPV(pOld);

    n_deleted = 0;
}


template <class T> const T
UT_GenericStringMap<T>::_first(UT_Cursor& c) const
{
    const hash_slot<T>* map = m_pMapping;
    size_t x;
    for (x=0; x < m_nSlots; ++x)
    {
        if (!map[x].empty() && !map[x].deleted())
        {
            break;
        }
    }
    if (x < m_nSlots)
    {
        c._set_index(x);    // c = 'UT_Cursor etc'
        return map[x].value();
    }

    c._set_index(-1);
    return 0;
}

template <class T>
const UT_String& UT_GenericStringMap<T>::_key(UT_Cursor& c) const
{
    hash_slot<T> & slot = m_pMapping[c._get_index()];

    // we used to return a reference to a static variable here in case the
    // following conditions failed, but that breaks some compilers (the
    // variable has to be instantiated somewhere for each template instance
    // and this can lead to multiple instances of it in different abi
    // modules (for example with the cs2005q3.2 compiler for Maemo 2) --
    // the caller must ensure that the cursor is valid; that is not that
    // much to ask
    UT_ASSERT_HARMLESS(!slot.empty() && !slot.deleted());

    return slot.m_key.value();
}

template <class T>
void UT_GenericStringMap<T>::_make_deleted(UT_Cursor& c) const
{
    hash_slot<T> & slot = m_pMapping[c._get_index()];

    if (!slot.empty() && !slot.deleted())
    {
        slot.make_deleted();
    }
}

template <class T> const T
UT_GenericStringMap<T>::_next(UT_Cursor& c) const
{
    const hash_slot<T>* map = m_pMapping;
    size_t x;
    for (x = c._get_index() + 1; x < m_nSlots; ++x)
    {
        if (!map[x].empty() && !map[x].deleted())
        {
            break;
        }
    }
    if (x < m_nSlots)
    {
        c._set_index(x);
        return map[x].value();
    }

    c._set_index(-1);
    return 0;
}


template <class T> const T
UT_GenericStringMap<T>::_prev(UT_Cursor& c) const
{
    const hash_slot<T>* map = m_pMapping;
    UT_sint32 x;
    for (x = c._get_index() - 1; x >= 0; --x)
    {
        if (!map[x].empty() && !map[x].deleted())
        {
            break;
        }
    }
    if (x >= 0)
    {
        c._set_index(x);
        return map[x].value();
    }

    c._set_index(-1);
    return 0;
}


#endif /* UT_HASH_H */