LinearMap.hxx

Go to the documentation of this file.

 
#ifndef _UTILS_LINEARMAP_HXX_
#define _UTILS_LINEARMAP_HXX_
 
#include <stdio.h>  // for ssize_t
#include <sys/tree.hxx>
 
#include "utils/macros.h"
 
template <typename Key, typename Value> class LinearMap
{
public:
    LinearMap()
        : entries(0),
          used(0),
          list(NULL)
    {
        /* dynamic allocation not supported */
        HASSERT(0);
    }
 
    LinearMap(size_t entries) 
        : entries(entries),
          used(0),
          list(new Element[entries])
    {
    }
 
    ~LinearMap()
    {
        delete [] list;
    }
 
    struct Pair
    {
        Key first; 
        Value second; 
    };
 
private:
    struct Element
    {
        union
        {
            Pair p; 
            struct
            {
                Key key; 
                Value value; 
            };
        };
    }; 
 
public:
 
    class Iterator
    {
    public:
        Iterator() : index(0), m(nullptr)
        {
        }
 
        Iterator(const Iterator &it)
            : index(it.index),
              m(it.m)
        {
        }
 
        Iterator(LinearMap* context, size_t index)
            : index(index),
              m(context)
        {
        }
 
        ~Iterator()
        {
        }
 
        Pair &operator*() const
        {
            return m->list[index].p;
        }
 
        Pair *operator->() const
        {
            return &m->list[index].p;
        }
 
        Iterator &operator ++ ()
        {
            if (index < m->used)
            {
                ++index;
            }
            return *this;
        }
 
        bool operator != (const Iterator& it)
        {
            return m != it.m || index != it.index;
        }
 
        bool operator == (const Iterator& it)
        {
            return m == it.m && index == it.index;
        }
 
    private:
        size_t index;
        
        LinearMap *m;
        
        friend class LinearMap;
    };
 
    void clear()
    {
        used = 0;
    }
 
    size_t erase(Key key)
    {
        for (size_t i = 0; i < used; ++i)
        {
            if (list[i].key == key)
            {
                /* scrunch up the list if we are able */
                if (i != --used)
                {
                    list[i].key = list[used].key;
                    list[i].value = list[used].value;
                }
                return 1;
            }
        }
        return 0;
    }
    
    void erase(Iterator it)
    {
        ssize_t i = it.index;
        HASSERT(i < (ssize_t)used && i >= 0);
 
        /* scrunch up the list if we are able */
        if (i != (ssize_t)--used)
        {
            list[i].key = list[used].key;
            list[i].value = list[used].value;
        }
    }
    
    Value &operator[](const Key &key)
    {
        for (size_t i = 0; i < used; ++i)
        {
            if (list[i].key == key)
            {
                return list[i].value;
            }
        }
        
        HASSERT(used < entries);
        
        list[used].key = key;
        list[used].value = 0;
        
        return list[used++].value;
    }
 
    size_t size()
    {
        return used;
    }
 
    size_t max_size()
    {
        return entries;
    }
 
    Iterator find(const Key &key)
    {
        for (size_t i = 0; i < used; ++i)
        {
            if (list[i].key == key)
            {
                return Iterator(this, i);
            }
        }
        return end();
    }
    
    Iterator end()
    {
        return Iterator(this, size());
    }
 
    Iterator begin()
    {
        return Iterator(this, 0);
    }
 
private:
    size_t entries;
 
    size_t used;
 
    Element *list;
    
    DISALLOW_COPY_AND_ASSIGN(LinearMap);
};
 
#endif /* _UTILS_LINEARMAP_HXX_ */