omap

An omap is a container for storing objrefs, indexed by ID.

  class omap: public MAP
  {
  public:
    objref& operator[](GraphID_t i);
    omap& operator=(omap& x);
  };

There are a few different possible ways of implementing omaps, with differing performance characteristics. Graphcode provides two different models, vmap and hmap that may be readily deployed by the user, however users can fairly easily provide their own implementation if desired. Different implementations can be selected by defining the MAP macro to be the desired omap implementation before including graphcode.h. This will declare everything in the namespace graphcode_vmap or graphcode_hmap as appropriate. Using this scheme, it is possible to have two different omap types in the one object file, by including graphcode.h twice. However, if you do this, you will need to #undef GRAPHCODE_H guard variable prior to subsequent includes.

vmap is intended for use with contiguous GraphID ranges. If there are holes in the identifier range, then the iterator will return invalid references for these holes, and the size() method will be incorrect.

If you need to have non-contiguous ID ranges (perhaps for dynamic graph management -- note this is not currently supported), then please use the hmap implementation instead (which will have some performance penalty).

MAP must provide the following members:

class MAP
{
  protected:
    objref& at(GraphID_t i);
  public:
    MAP();
    MAP(const MAP&)
    class iterator
     {
       iterator();
       iterator(const iterator&);
       iterator& operator=(const iterator&); 
       iterator operator++(int);
       iterator operator++();
       iterator operator--(int);
       iterator operator--();
       bool operator==(const iterator& x) const;
       bool operator!=(const iterator& x) const;
       objref& operator*();
       objref* operator->();
     };
    iterator begin();
    iterator end();
    unsigned size();
}

The at method is essentially a replacement for operator[](). A simple example of an omap implementation is provided by vmap:

class vmap: public std::vector<objref>
{
protected:
  objref& at(GraphID_t i) 
  {
    if (i>=size()) resize(i+1);
    return std::vector<objref>::operator[](i);
  }
};

hmap is a hash map implementation. With all hash maps, performance of the map is critically dependent upon the choice of hash function, which is application dependent. hmap is simply defined as:

class hmap: public hashmap<simple_hash> {};

You can provide your own omap definition (umap, say), with your own user defined hash function in the following way:

1. Create a file “umap” somewhere in the default search path with the following:

   #include "hashmap.h"
   struct myhash
   {
     unsigned operator()(GraphID_t i) {...}
   };
   class umap: public hashmap<myhash> {};
   

2. Add the new omap definitions to the Graphcode library:

   make MAP=umap
   

3. Include the declarations of the graphcode_umap namespace in your application source file:

   #define MAP umap
   #undef GRAPHCODE_H
   #include <graphcode.h>