sbindtbl.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_SBINDTBL_HPP_SENTRY
#define INTELIB_SBINDTBL_HPP_SENTRY

#include "sexpress.hpp"

static const unsigned long not_a_key = ~(0L);

static const unsigned long bind_table_sizes[] = {
    6, 12, 18, 38, 68, 132, 258, 522, 1032, 2054, 4100, 8210, 16412, 0
};


class IntelibBindTable {
    struct Item {
        union {
            unsigned long key;
            struct {
                unsigned int size : 8;
                unsigned int fill : 24;
            };
        };
        SReference binding;
        Item() : key(not_a_key), binding() {}
    };
    Item *array;

    static unsigned long hash(unsigned long key)
    { return 0x9c406bb5 * ((key >> 2) ^ 0x12fade34); }

    void Resize() {
        if(!array) {
            array = new Item[bind_table_sizes[0]];
            array[0].size = 0;
            array[0].fill = 0;
            return;
        }
        int size = array[0].size;
        if(!bind_table_sizes[size+1]) return; // in fact this is error
        Item *tmp = array;
        size++;
        array = new Item[bind_table_sizes[size]];
        array[0].size = size;
        array[0].fill = 0;
        for(unsigned int i=1; i<bind_table_sizes[size-1]; i++) {
            if(tmp[i].key != not_a_key)
                *(AddBinding(tmp[i].key)) = tmp[i].binding;
        }
        delete[] tmp;
    }
public:
    IntelibBindTable() : array(0) {}
    ~IntelibBindTable() { if(array && array!=(Item*)-1) delete[] array; }


    SReference *GetBinding(unsigned long key) const {
        if(!array) return 0;
        unsigned int pos = hash(key)%(bind_table_sizes[array[0].size]-1)+1;
        do {
            if(array[pos].key == key)
                return &(array[pos].binding);
            if(array[pos].key == not_a_key)
                return 0;
            pos++;
            if(pos >= bind_table_sizes[array[0].size]) pos = 1;
        } while(1);
    }

    SReference *AddBinding(unsigned long key) {
        if(!array || array[0].fill * 2 > bind_table_sizes[array[0].size])
            Resize();
        unsigned int pos = hash(key)%(bind_table_sizes[array[0].size]-1)+1;
        do {
            if(array[pos].key == not_a_key) {
                array[pos].key = key;
                array[0].fill++;
                return &(array[pos].binding);
            }
            if(array[pos].key == key)
                return &(array[pos].binding);
            pos++;
            if(pos >= bind_table_sizes[array[0].size]) pos = 1;
        } while(1);
    }


    void Invalidate() {
        if(array && array!=(Item*)-1) delete[] array;
        array = (Item*)-1;
    }
    void DeInvalidate() { if(array == (Item*)-1) array = 0; }
    bool IsInvalid() const { return array == (Item*)-1; }

    class Iterator;
    friend class IntelibBindTable::Iterator;

    class Iterator {
        unsigned int idx;
        Item *array;
    public:
        Iterator(const IntelibBindTable &master)
            : idx(1), array(master.array) {}
        bool GetNext(unsigned long &key, SReference &ret) {
            if(!array) return false;
            unsigned int arrlen = bind_table_sizes[array[0].size];
            while(idx<arrlen && array[idx].key==not_a_key) idx++;
            if(idx>=arrlen) return false;
            key = array[idx].key;
            ret = array[idx].binding;
            idx++;
            return true;
        }
    };

private:
    IntelibBindTable(const IntelibBindTable &) {}
    void operator =(const IntelibBindTable &) {}
};


#endif

---