/ray/src/vm/maptable.h

Go to the documentation of this file.

/*
 * vm/maptable.h
 * 
 * B-tree based O(log(n)) ID-to-INFO map. 
 * 
 * Copyright (c) 2004 by Wolfgang Wieser ] wwieser (a) gmx <*> de [ 
 * 
 * This file may be distributed and/or modified under the terms of the 
 * GNU General Public License version 2 as published by the Free Software 
 * Foundation. (See COPYING.GPL for details.)
 * 
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 * 
 */

#ifndef _VM_MAPTABLE_H_
#define _VM_MAPTABLE_H_ 1

#include <vm/vmconfig.h>    /* MUST be first */

#include <lib/tl/tlbtree.h>


template<typename ID,typename INFO>struct IDMapTableNode
{
    ID id;
    INFO info;
    
    inline IDMapTableNode() : id(0),info((INFO)0) {}
    inline IDMapTableNode(ID _tid,INFO _info) : 
        id(_tid),info(_info) {}
    inline IDMapTableNode(const IDMapTableNode &n) : 
        id(n.id),info(n.info) {}
    inline ~IDMapTableNode() { info=(INFO)0; }
    
    inline IDMapTableNode &operator=(const IDMapTableNode &n)
        {  id=n.id;  info=n.info;  return(*this);  }
    
    inline bool operator==(const IDMapTableNode &n) const  { return(id==n.id); }
    inline bool operator!=(const IDMapTableNode &n) const  { return(id!=n.id); }
    inline bool operator<(const IDMapTableNode &n)  const  { return(id<n.id);  }
    inline bool operator>(const IDMapTableNode &n)  const  { return(id>n.id);  }
    inline bool operator<=(const IDMapTableNode &n) const  { return(id<=n.id); }
    inline bool operator>=(const IDMapTableNode &n) const  { return(id>=n.id); }
    inline bool operator==(const ID &b) const  { return(id==b); }
    inline bool operator!=(const ID &b) const  { return(id!=b); }
    inline bool operator<(const ID &b) const   { return(id<b);  }
    inline bool operator>(const ID &b) const   { return(id>b);  }
    inline bool operator<=(const ID &b) const  { return(id<=b); }
    inline bool operator>=(const ID &b) const  { return(id>=b); }
};


template<typename ID,typename INFO>class IDMapTable
{
    public:
        typedef IDMapTableNode<ID,INFO> Node;
        
    private:
        TLBTree< Node,TLDefaultOperators_CDT<Node> > map;
        
        IDMapTable(const IDMapTable &);
        void operator=(const IDMapTable &);
    public:
        inline IDMapTable() : map(/*m=16 (default)*/) {}
        inline IDMapTable(uint m) : map(m) {}
        inline ~IDMapTable() {}
        
        INFO AddNode(ID id,INFO info,bool *is_known=NULL)
        {
            Node tmp(id,info);
            Node old_val;
            if(map.store(tmp,/*allow_update=*/0,&old_val))
            {
                if(is_known)  *is_known=1;
                return(old_val.info);
            }
            if(is_known)  *is_known=0;
            return((INFO)0);
        }
        
        INFO lookup(ID id,bool *was_found=NULL)
        {
            Node *tmp=map.search(id);
            if(was_found)  *was_found=tmp;
            return(tmp ? tmp->info : (INFO)0);
        }
        
        inline void clear()
            {  map.clear();  }
};

#endif  /* _VM_MAPTABLE_H_ */

---