hash.h

来自「A*算法 A*算法 A*算法 A*算法A*算法A*算法」· C头文件 代码 · 共 635 行 · 第 1/2 页

/////////////////////////////////////////////////////////////////////////////
// Name:        wx/hash.h
// Purpose:     wxHashTable class
// Author:      Julian Smart
// Modified by: VZ at 25.02.00: type safe hashes with WX_DECLARE_HASH()
// Created:     01/02/97
// RCS-ID:      $Id: hash.h,v 1.42 2005/06/08 15:17:42 ABX Exp $
// Copyright:   (c) Julian Smart
// Licence:     wxWindows licence
/////////////////////////////////////////////////////////////////////////////

#ifndef _WX_HASH_H__
#define _WX_HASH_H__

#if defined(__GNUG__) && !defined(NO_GCC_PRAGMA)
#pragma interface "hash.h"
#endif

#include "wx/defs.h"

#if !wxUSE_STL && WXWIN_COMPATIBILITY_2_4
    #define wxUSE_OLD_HASH_TABLE 1
#else
    #define wxUSE_OLD_HASH_TABLE 0
#endif

#if !wxUSE_STL
    #include "wx/object.h"
#else
    class WXDLLIMPEXP_BASE wxObject;
#endif
#if wxUSE_OLD_HASH_TABLE
    #include "wx/list.h"
#endif
#if WXWIN_COMPATIBILITY_2_4
    #include "wx/dynarray.h"
#endif

// the default size of the hash
#define wxHASH_SIZE_DEFAULT     (1000)

/*
 * A hash table is an array of user-definable size with lists
 * of data items hanging off the array positions.  Usually there'll
 * be a hit, so no search is required; otherwise we'll have to run down
 * the list to find the desired item.
*/

// ----------------------------------------------------------------------------
// this is the base class for object hashes: hash tables which contain
// pointers to objects
// ----------------------------------------------------------------------------

#if wxUSE_OLD_HASH_TABLE

class WXDLLIMPEXP_BASE wxHashTableBase : public wxObject
{
public:
    wxHashTableBase();

    void Create(wxKeyType keyType = wxKEY_INTEGER,
                size_t size = wxHASH_SIZE_DEFAULT);
    void Destroy();

    size_t GetSize() const { return m_hashSize; }
    size_t GetCount() const { return m_count; }

    void DeleteContents(bool flag);

protected:
    // find the node for (key, value)
    wxNodeBase *GetNode(long key, long value) const;

    // the array of lists in which we store the values for given key hash
    wxListBase **m_hashTable;

    // the size of m_lists array
    size_t m_hashSize;

    // the type of indexing we use
    wxKeyType m_keyType;

    // the total number of elements in the hash
    size_t m_count;

    // should we delete our data?
    bool m_deleteContents;

private:
    // no copy ctor/assignment operator (yet)
    DECLARE_NO_COPY_CLASS(wxHashTableBase)
};

#else // if !wxUSE_OLD_HASH_TABLE

#if !defined(wxENUM_KEY_TYPE_DEFINED)
#define wxENUM_KEY_TYPE_DEFINED

enum wxKeyType
{
    wxKEY_NONE,
    wxKEY_INTEGER,
    wxKEY_STRING
};

#endif

union wxHashKeyValue
{
    long integer;
    wxChar *string;
};

// for some compilers (AIX xlC), defining it as friend inside the class is not
// enough, so provide a real forward declaration
class WXDLLIMPEXP_BASE wxHashTableBase;

class WXDLLIMPEXP_BASE wxHashTableBase_Node
{
    friend class WXDLLIMPEXP_BASE wxHashTableBase;
    typedef class WXDLLIMPEXP_BASE wxHashTableBase_Node _Node;
public:
    wxHashTableBase_Node( long key, void* value,
                          wxHashTableBase* table );
    wxHashTableBase_Node( const wxChar* key, void* value,
                          wxHashTableBase* table );
    ~wxHashTableBase_Node();

    long GetKeyInteger() const { return m_key.integer; }
    const wxChar* GetKeyString() const { return m_key.string; }

    void* GetData() const { return m_value; }
    void SetData( void* data ) { m_value = data; }

protected:
    _Node* GetNext() const { return m_next; }

protected:
    // next node in the chain
    wxHashTableBase_Node* m_next;

    // key
    wxHashKeyValue m_key;

    // value
    void* m_value;

    // pointer to the hash containing the node, used to remove the
    // node from the hash when the user deletes the node iterating
    // through it
    // TODO: move it to wxHashTable_Node (only wxHashTable supports
    //       iteration)
    wxHashTableBase* m_hashPtr;
};

class WXDLLIMPEXP_BASE wxHashTableBase
#if !wxUSE_STL
    : public wxObject
#endif
{
    friend class WXDLLIMPEXP_BASE wxHashTableBase_Node;
public:
    typedef wxHashTableBase_Node Node;

    wxHashTableBase();
    virtual ~wxHashTableBase() { };

    void Create( wxKeyType keyType = wxKEY_INTEGER,
                 size_t size = wxHASH_SIZE_DEFAULT );
    void Clear();
    void Destroy();

    size_t GetSize() const { return m_size; }
    size_t GetCount() const { return m_count; }

    void DeleteContents( bool flag ) { m_deleteContents = flag; }

    static long MakeKey(const wxChar *string);

protected:
    void DoPut( long key, long hash, void* data );
    void DoPut( const wxChar* key, long hash, void* data );
    void* DoGet( long key, long hash ) const;
    void* DoGet( const wxChar* key, long hash ) const;
    void* DoDelete( long key, long hash );
    void* DoDelete( const wxChar* key, long hash );

private:
    // Remove the node from the hash, *only called from
    // ~wxHashTable*_Node destructor
    void DoRemoveNode( wxHashTableBase_Node* node );

    // destroys data contained in the node if appropriate:
    // deletes the key if it is a string and destrys
    // the value if m_deleteContents is true
    void DoDestroyNode( wxHashTableBase_Node* node );

    // inserts a node in the table (at the end of the chain)
    void DoInsertNode( size_t bucket, wxHashTableBase_Node* node );

    // removes a node from the table (fiven a pointer to the previous
    // but does not delete it (only deletes its contents)
    void DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node,
                       wxHashTableBase_Node* prev );

    // unconditionally deletes node value (invoking the
    // correct destructor)
    virtual void DoDeleteContents( wxHashTableBase_Node* node ) = 0;

protected:
    // number of buckets
    size_t m_size;

    // number of nodes (key/value pairs)
    size_t m_count;

    // table
    Node** m_table;

    // key typ (INTEGER/STRING)
    wxKeyType m_keyType;

    // delete contents when hash is cleared
    bool m_deleteContents;

private:
    DECLARE_NO_COPY_CLASS(wxHashTableBase)
};

#endif // wxUSE_OLD_HASH_TABLE

#if !wxUSE_STL

#if WXWIN_COMPATIBILITY_2_4

// ----------------------------------------------------------------------------
// a hash table which stores longs
// ----------------------------------------------------------------------------

class WXDLLIMPEXP_BASE wxHashTableLong : public wxObject
{
public:
    wxHashTableLong(size_t size = wxHASH_SIZE_DEFAULT)
        { Init(size); }
    virtual ~wxHashTableLong();

    void Create(size_t size = wxHASH_SIZE_DEFAULT);
    void Destroy();

    size_t GetSize() const { return m_hashSize; }
    size_t GetCount() const { return m_count; }

    void Put(long key, long value);
    long Get(long key) const;
    long Delete(long key);

protected:
    void Init(size_t size);

private:
    wxArrayLong **m_values,
                **m_keys;

    // the size of array above
    size_t m_hashSize;

    // the total number of elements in the hash
    size_t m_count;

    // not implemented yet
    DECLARE_NO_COPY_CLASS(wxHashTableLong)
};

// ----------------------------------------------------------------------------
// wxStringHashTable: a hash table which indexes strings with longs
// ----------------------------------------------------------------------------

class WXDLLIMPEXP_BASE wxStringHashTable : public wxObject
{
public:
    wxStringHashTable(size_t sizeTable = wxHASH_SIZE_DEFAULT);
    virtual ~wxStringHashTable();

    // add a string associated with this key to the table
    void Put(long key, const wxString& value);

    // get the string from the key: if not found, an empty string is returned
    // and the wasFound is set to false if not NULL
    wxString Get(long key, bool *wasFound = NULL) const;

    // remove the item, returning true if the item was found and deleted
    bool Delete(long key) const;

    // clean up
    void Destroy();

private:
    wxArrayLong **m_keys;
    wxArrayString **m_values;

    // the size of array above
    size_t m_hashSize;

    DECLARE_NO_COPY_CLASS(wxStringHashTable)
};

#endif // WXWIN_COMPATIBILITY_2_4

#endif // !wxUSE_STL

// ----------------------------------------------------------------------------
// for compatibility only
// ----------------------------------------------------------------------------

#if !wxUSE_OLD_HASH_TABLE

class WXDLLIMPEXP_BASE wxHashTable_Node : public wxHashTableBase_Node
{