VRS - The Virtual Rendering System

version 3.3

hashtable.h

Go to the documentation of this file.

 /**********************************************************************
 VRS - The Virtual Rendering System
 Copyright (C) 2001 Computer Graphics Systems Group at the 
 Hasso-Plattner-Institute, Potsdam, Germany.
 This library is free software; you can redistribute it and/or 
 modify it under the terms of the GNU Lesser General Public 
 License as published by the Free Software Foundation; either 
 version 2.1 of the License, or (at your option) any later version.
 This library 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 Lesser General Public License for more details.
 You should have received a copy of the GNU Lesser+ General Public
 License along with this library; if not, write to the FreeSoftware 
 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA, 02111-1307, USA.
 **********************************************************************/
// $Id: hashtable.h 6189 2007-12-17 07:43:04Z Steffen_Schmidt $
// $Date: 2007-12-17 08:43:04 +0100 (Mon, 17 Dec 2007) $
// $Revision: 6189 $
// $State$
// $Author: Steffen_Schmidt $
//
// $Log$
// Revision 1.21  2005/07/12 12:53:12  baumann
// 64 bit issue fixed (reinterpret_cast)
//
// Revision 1.20  2005/06/10 14:43:32  baumann
// added hash code for std::wstring
//
// Revision 1.19  2004/11/09 15:04:55  kirsch
// further changes to class comments due to doxygen
//
// Revision 1.18  2004/11/03 10:58:28  saar
// Class comment changed (Doxygen style)
//
// Revision 1.17  2004/05/27 11:56:48  kirsch
// - allow dictionary with less than 113 value-slots
// - do not use pointer to std::vector<T> anymore
//
// Revision 1.16  2004/03/12 16:28:39  baumann
// macros VRS_NAMESPACE_BEGIN/_END expanded and removed
//
// Revision 1.15  2004/01/27 13:39:46  buchholz
// HashValue for strings moved here from config.h
// HashValue for pairs added
//
// Revision 1.14  2004/01/19 11:43:57  baumann
// serialization mechanism improved
//
// Revision 1.13  2003/11/07 14:19:24  kirsch
// removed leading underscore from include guards
//
// Revision 1.12  2003/07/10 11:07:56  baumann
// code cleanup
//
// Revision 1.11  2002/11/26 15:02:18  baumann
// typo fixed
//
// Revision 1.10  2002/11/26 14:41:51  baumann
// HashValue() functions rewritten; most recursions removed
//
// Revision 1.9  2002/11/25 10:00:03  baumann
// changed return type of HashValue() to UINT
//
// Revision 1.8  2002/08/06 16:24:01  baumann
// VRS_API removed for template classes
//
// Revision 1.7  2002/07/03 15:52:50  baumann
// several changes for iterator code
// most iterators are now serializable again
//
// Revision 1.6  2002/07/03 09:58:05  baumann
// serialization added for iterator
// added hash value functions for most of the builtin types
// perfromance improvements for iterator
//
// Revision 1.5  2002/07/02 15:23:48  baumann
// non-persistent containers now have the prefix NonPersistent, e.g. NonPersistentArray<T>
// persistent containers now have no prefix, e.g. Array<T>
//
// Revision 1.4  2002/07/02 06:12:34  baumann
// VRS::Iterator<T> completely rewritten
//
// Revision 1.3  2002/06/28 07:08:14  baumann
// new method isEmpty() added
//
// Revision 1.2  2002/04/09 10:00:40  kersting
// added dtor
//
// Revision 1.1  2002/03/04 12:03:54  kersting
// directory structure changes
//
// Revision 1.12  2002/03/03 21:44:24  kosta
// VRS_TYPEINFO-macro rewritten
//
// Revision 1.11  2002/02/19 10:34:08  kosta
// undone all changes since 2002-02-15
//
// Revision 1.8  2002/02/14 09:37:20  kosta
// automatic serialization registration for template classes implemented
//
// Revision 1.7  2002/02/11 14:35:15  kosta
// implementation improved
//
// Revision 1.6  2002/02/05 15:50:24  kosta
// typo fixed
//
// Revision 1.5  2002/02/05 15:47:15  kosta
// Hashtable<T> split into 2 classes:
//     Hashtable<T>> (which cannot be serialized)
//     PersistentHashtable<T> (which can be serialized)
//
// Revision 1.4  2002/02/04 11:54:37  kosta
// persistency rewritten (for better namespace support)
//
// Revision 1.3  2002/01/15 16:25:53  kosta
// macros rewritten for a better namespace support
//
// Revision 1.2  2001/11/13 16:36:30  kirsch
// changed line feed to unix style (removed control-M)
//
// Revision 1.1.1.1  2001/06/08 08:09:20  kirsch
// imported alpha-version by olli 
//

#ifndef VRS_HASHTABLE_H
#define VRS_HASHTABLE_H

#include <vrs/color.h>
#include <vrs/container/iterator.h>
#include <vector>
#include <utility>

namespace VRS {

template<typename T> class HashTableIterator;

template<typename T>
class NonPersistentHashTable : public SharedObj {
public:
    NonPersistentHashTable(unsigned int noOfElements = 113);
    bool contains(const T& t) const;
    const T* find(const T& t) const;
    unsigned int size() const;

    bool isEmpty() const;

    bool insert(const T& t);
    bool erase(const T& t);
    void clear();
    Iterator<T>* newIterator() const;
    VRS_TYPEINFO(NonPersistentHashTable, SharedObj);
    VRS_SERIALIZABLE_ABSTRACT_CLASS(NonPersistentHashTable); // not supported (throws exception); use HashTable<T> instead

private:
    unsigned int getHashValue(const T& t) const;
    static unsigned int nextPrimeAfter(unsigned int);
    static bool isPrime(unsigned int);

    std::vector<std::vector<T> > hash_;
    unsigned int count_;

protected:
    friend class HashTableIterator<T>;
    mutable Iterator<T>* iterator_; // no SO-ptr!!! will be set/unset by HashTableIterator's ctor/dtor

    const T& get(unsigned int index) const; // used by the HashTableIterator
    mutable unsigned int cachedAccum_; // used for improving the get()-method
    mutable unsigned int cachedSlot_;  // used for improving the get()-method
};

template<class T>
class HashTable : public NonPersistentHashTable<T> {
public:
    HashTable(unsigned int noOfElements = 0) : NonPersistentHashTable<T>(noOfElements) { }

    VRS_TYPEINFO(HashTable, NonPersistentHashTable<T>);
    VRS_SERIALIZABLE(HashTable);
};

VRS_SERIALIZATION_REGISTRATION_TEMPLATE(HashTable)

// hash values for unsigned integral types
inline unsigned int HashValue(unsigned long  t) { return static_cast<unsigned int>(t); }
inline unsigned int HashValue(unsigned int   t) { return static_cast<unsigned int>(t); }
inline unsigned int HashValue(unsigned short t) { return static_cast<unsigned int>(t); }
inline unsigned int HashValue(unsigned char  t) { return static_cast<unsigned int>(t); }

// hash values for signed integral types
inline unsigned int HashValue(long  t) { return static_cast<unsigned int>(t); }
inline unsigned int HashValue(int   t) { return static_cast<unsigned int>(t); }
inline unsigned int HashValue(short t) { return static_cast<unsigned int>(t); }
inline unsigned int HashValue(char  t) { return static_cast<unsigned int>(t); }

// hash values for signed floating point types
inline unsigned int HashValue(double t) { return static_cast<unsigned int>(t); }
inline unsigned int HashValue(float  t) { return static_cast<unsigned int>(t); }

// hash values for strings
inline unsigned int HashValue(const std::string& str) {
    const unsigned int len = static_cast<unsigned int>(str.length());
    if(len == 0) { return 0; }
    return ((str[0]<<24) | (str[len/3]<<16) | (str[2*len/3]<<8) | str[len-1]);
}

// hash values for pointers
template<class T>
  inline unsigned int HashValue(const T*     t) { return static_cast<unsigned int>(t - static_cast<const T*>(NULL)); }
template<class T>
inline unsigned int HashValue(const SO<T>& t) { return HashValue(static_cast<T*>(t)); }

// hash values for combined types
template<typename FIRST, typename SECOND>
inline unsigned int HashValue(const std::pair<FIRST,SECOND>& t) { 
    return ((7 * HashValue(t.first)) ^ (19 * HashValue(t.second))); 
}

#ifdef VRS_HAS_WSTRING
inline unsigned int HashValue(const std::wstring& str) {
    const unsigned int len = static_cast<unsigned int>(str.length());
    if(len == 0) { return 0; }
    return (((str[0]&0xFF)<<24) | ((str[len/3]&0xFF)<<16) | ((str[2*len/3]&0xFF)<<8) | (str[len-1]&0xFF));
}
#endif // VRS_HAS_WSTRING

// hash value for colors
inline unsigned int HashValue(const VRS::Color& color) {
        return   (HashValue(color[0] * 255) + 
                  3 * HashValue(color[1] * 255) + 
                  5 * HashValue(color[2] * 255) + 
                  7 * HashValue(color[3] * 255));
}

} // namespace VRS

#include <vrs/container/hashtable.tli>

#endif // VRS_HASHTABLE_H

---

Generated on Wed May 23 06:00:12 2012 by Doxygen 1.5.6

© 2001-2010 Hasso-Plattner-Institut | Impressum | Contact