Ray: /ray/src/vm/imaptable.h Source File

00001 /*
00002  * vm/imaptable.h
00003  * 
00004  * B-tree based O(log(n)) implicit map ("index" into data). 
00005  * 
00006  * Copyright (c) 2004 by Wolfgang Wieser ] wwieser (a) gmx <*> de [ 
00007  * 
00008  * This file may be distributed and/or modified under the terms of the 
00009  * GNU General Public License version 2 as published by the Free Software 
00010  * Foundation. (See COPYING.GPL for details.)
00011  * 
00012  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
00013  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
00014  * 
00015  */
00016 
00017 #ifndef _VM_IMAPTABLE_H_
00018 #define _VM_IMAPTABLE_H_ 1
00019 
00027 #include <vm/vmconfig.h>    /* MUST be first */
00028 
00029 #include <lib/tl/tlbtree.h>
00030 
00031 
00043 template<typename T,typename ID,typename ORD>struct ImplicitMapOperators : 
00044     TLDefaultOperators_Construct_PDT<T*>,
00045     TLDefaultOperators_Allocation
00046 {
00047     // Compare two T's. 
00048     static inline bool lt(T* const &a,T* const &b)
00049         {  return(ORD::ord(a)<ORD::ord(b));   }
00050     static inline bool le(T* const &a,T* const &b)
00051         {  return(ORD::ord(a)<=ORD::ord(b));  }
00052     static inline bool gt(T* const &a,T* const &b)
00053         {  return(ORD::ord(a)>ORD::ord(b));   }
00054     static inline bool ge(T* const &a,T* const &b)
00055         {  return(ORD::ord(a)>=ORD::ord(b));  }
00056     static inline bool eq(T* const &a,T* const &b)
00057         {  return(ORD::ord(a)==ORD::ord(b));  }
00058     static inline bool ne(T* const &a,T* const &b)
00059         {  return(ORD::ord(a)!=ORD::ord(b));  }
00060 
00061     // Compare T to ID. 
00062     static inline bool lt(T* const &a,ID const &b)
00063         {  return(ORD::ord(a)<b);   }
00064     static inline bool le(T* const &a,ID const &b)
00065         {  return(ORD::ord(a)<=b);  }
00066     static inline bool gt(T* const &a,ID const &b)
00067         {  return(ORD::ord(a)>b);   }
00068     static inline bool ge(T* const &a,ID const &b)
00069         {  return(ORD::ord(a)>=b);  }
00070     static inline bool eq(T* const &a,ID const &b)
00071         {  return(ORD::ord(a)==b);  }
00072     static inline bool ne(T* const &a,ID const &b)
00073         {  return(ORD::ord(a)!=b);  }
00074 };
00075 
00076 
00096 template<typename T,typename ID,typename OP>class ImplicitMapTable
00097 {
00098     public:
00099         
00100     private:
00102         TLBTree<T*,OP> map;
00103         
00105         ImplicitMapTable(const ImplicitMapTable &);
00107         void operator=(const ImplicitMapTable &);
00108     public:
00110         inline ImplicitMapTable() : map(/*m=16 (default)*/) {}
00112         inline ImplicitMapTable(uint m) : map(m) {}
00114         inline ~ImplicitMapTable() {}
00115         
00121         T *AddNode(T *n)
00122         {
00123             T *old_val=NULL;
00124             if(map.store(n,/*allow_update=*/0,&old_val))
00125             {  return(old_val);  }
00126             return(NULL);
00127         }
00128         
00134         T *lookup(ID k)
00135         {
00136             T **known=map.search(k);
00137             return(known ? *known : NULL);
00138         }
00139         
00141         inline void clear()
00142             {  map.clear();  }
00143 };
00144 
00145 #endif  /* _VM_IMAPTABLE_H_ */