shashtbl.hpp

Go to the documentation of this file.

// +-------------------------------------------------------------------------+
// |               I__n__t__e__L__i__b           0.6.10 development          |
// | Copyright (c) Andrey Vikt. Stolyarov <crocodil_AT_croco.net> 2000-2007. |
// |                                                                         |
// | This is free software. The library part is available under              |
// |                               GNU LESSER GENERAL PUBLIC LICENSE v.2.1.  |
// | GNU LGPL v2.1 is found in docs/gnu_gpl2.txt,  or at  http://www.gnu.org |
// |     Please see also docs/readme.txt and visit http://www.intelib.org    |
// |                                                                         |
// | !!! THERE IS NO WARRANTY OF ANY KIND, NEITHER EXPRESSED NOR IMPLIED !!! |
// +-------------------------------------------------------------------------+




#ifndef INTELIB_SHASHTBL_HPP_SENTRY
#define INTELIB_SHASHTBL_HPP_SENTRY

#include "sexpress.hpp"
#include "iexcept.hpp"
#include "gensref.hpp"

typedef unsigned long intelib_hash_t;

intelib_hash_t UniversalHash(intelib_hash_t l);
intelib_hash_t LispHash(const SReference &ref);

typedef bool (*SEqualityPredicate) (SReference, SReference);
bool SExprsAreEq(SReference l1, SReference l2);
bool SExprsAreEql(SReference l1, SReference l2);
bool SExprsAreEqual(SReference l1, SReference l2);



class SExpressionHashTable : public SExpression {
    unsigned long dim;
    SReference *table; 
    SEqualityPredicate comp;
    unsigned long itemcount;
    long lastfoundpos;
public:
    static IntelibTypeId TypeId;


    static SLabel EmptySlotMark; 


    SExpressionHashTable(SEqualityPredicate eqp = 0); 
protected:
    SExpressionHashTable(const IntelibTypeId &id, 
                         SEqualityPredicate eqp = 0); 
    ~SExpressionHashTable();
    
public:

#if INTELIB_TEXT_REPRESENTATIONS == 1
    virtual class SString TextRepresentation() const;
#endif

    virtual SExpression* Clone() const;
    

    void AddItem(SReference key, SReference val);


    bool SafeAddItem(SReference key, SReference val);


    SReference FindItem(SReference key, 
                const SReference &defval = EmptySlotMark) const; 


    SReference& GetItemPosition(SReference key);


    bool RemoveItem(SReference key);


    long Count() const { return itemcount; }


    void Clear();

    class Iterator {
        SReference *tbl;
        int idx;
        int lim;
    public:
        Iterator(const SExpressionHashTable &tbl);

        SReference& GetNext();        
    };

    friend class Iterator::Iterator;
  
private:
    void DoRemoveItem(long pos);
    void ResizeTable();
    void HandleLastFoundPos() const;

};    

class IntelibX_not_a_hash_table : public IntelibX {
public:
    IntelibX_not_a_hash_table(SReference a_param);
};

typedef GenericSReference<SExpressionHashTable,IntelibX_not_a_hash_table>
SHashTableRef;


class SHashTable : public SHashTableRef {
public:
    SHashTable(SEqualityPredicate pred = SExprsAreEqual)
        : SHashTableRef(new SExpressionHashTable(pred)) {}
};

class IntelibX_hash_table_too_big : public IntelibX {
public:
    IntelibX_hash_table_too_big(SReference a_param);
};

#endif // sentry

---