linmap.cpp

Go to the documentation of this file.

#ifndef LINMAP_CPP_050402
#define LINMAP_CPP_050402

#include <inttypes.h>
#include "common/allocators.hpp"

namespace bracz {

template<class key, class value> class linmap {
public:
  typedef key key_type;
  typedef value data_type;
  typedef std::pair<key_type, data_type> value_type;

  //  **** I have no idea if and why this is required
  typedef std::allocator<linmap<key_type,value_type> > allocator;

  linmap() {
    clear();
  }

  void clear() {
    data=NULL;
    size=0;
    logsize=-1;
  }

  data_type & DINLINE  operator[](key_type k) {
    unsigned int pos=0;
    while((pos<size)&&(data[pos].first!=k)) {
      pos++;
    }
    if (pos>=size) {
      //insert
      size_t dlen=size?myallocator.BLOCKLEN(logsize):0;
      if (pos>=dlen) {
        //realloc
        value_type *nd=myallocator.allocate(logsize+1);
        if (size) {
          //sort(data,data+size);
          memcpy(nd,data,size*sizeof(value_type));
          myallocator.free(data,logsize);
        }
        logsize++;
        data=nd;
      }
      data[pos].first=k;
      data[pos].second=data_type();
      size++;
    }
    //swap with the previous
    /*if (pos) {
      swap(data[pos-1],data[pos]);
      pos--;
      }*/
    return data[pos].second;
  }

  template<class CmpFn> void sort(CmpFn fn=CmpFn()) {
    if (size>0) {
      std::sort(data,data+size,fn);
    }
  }

  class iterator {
  private:
    size_t pos;
    linmap<key_type,data_type> *parent;
  public:
    value_type& DINLINE operator*() const {
      return parent->data[pos];
    }
    
    value_type* DINLINE operator->() const {
      return parent->data+pos;
    }

    void DINLINE operator++ ()  {
      pos++;
      //return *this;
    }
    bool DINLINE  operator==(const iterator &o) const {
      return pos==o.pos;
    }

    bool DINLINE operator!=(const iterator &o) const {
      return pos!=o.pos;
    }
    
    inline iterator(linmap<key_type,data_type> *p,size_t s){
      parent=p;
      pos=s;
    }
    inline iterator() {
      parent=NULL;
      pos=0;
    }
  };
  friend class iterator;

  iterator DINLINE begin()  {
    return iterator(this,0);
  }

  iterator DINLINE end()  {
    return iterator(this,size);
  }

private:
  uint32_t size;
  
  int logsize;

  value_type *data;

  typedef arrayalloc<value_type,1,100000> myallocator_t;

  static myallocator_t myallocator;

};

template<class key, class value> TYPENAME linmap<key,value>::myallocator_t linmap<key,value>::myallocator;


} //namespace bracz

#endif //LINMAP_CPP_050402

---