00001 // -*- mode: C++; c-file-style: "stroustrup"; c-basic-offset: 4; indent-tabs-mode: nil; -*- 00002 //////////////////////////////////////////////////////////////////// 00003 // 00004 // Filename : linkable.h (base) 00005 // 00006 // SingleLinkable_t 00007 // | 00008 // +-SingleLinkable<T> 00009 // | 00010 // +-DoubleLinkable_t 00011 // | 00012 // +-DoubleLinkable<T> 00013 // 00014 // This file is a part of the UPPAAL toolkit. 00015 // Copyright (c) 1995 - 2003, Uppsala University and Aalborg University. 00016 // All right reserved. 00017 // 00018 // $Id: linkable.h,v 1.6 2004/04/19 14:47:40 adavid Exp $ 00019 // 00020 /////////////////////////////////////////////////////////////////// 00021 00022 #ifndef INCLUDE_BASE_LINKABLE_H 00023 #define INCLUDE_BASE_LINKABLE_H 00024 00025 #include <assert.h> 00026 00027 /** 00028 * @file 00029 * 00030 * Defines base linkable structures for single and double linked lists. 00031 * struct is used (instead of class) for style reasons (though it's the 00032 * same conceptually): class refers to an object, struct refers to a 00033 * simple data structure made to be stored. 00034 * These structures are defined because it is far more readable to 00035 * have bla->link(somewhere) than the manual pointer link stuff every 00036 * time. This reduces errors. Furthermore the default lists of the 00037 * STL are double linked. 00038 */ 00039 00040 namespace base 00041 { 00042 /** Generic untyped structure 00043 * for generic manipulation. 00044 */ 00045 struct SingleLinkable_t 00046 { 00047 SingleLinkable_t *next; 00048 }; 00049 00050 00051 /** Generic untyped structure 00052 * for generic manipulation. 00053 */ 00054 struct DoubleLinkable_t : public SingleLinkable_t 00055 { 00056 DoubleLinkable_t **previous; 00057 }; 00058 00059 00060 /** Template for typed manipulation. 00061 */ 00062 template<class T> 00063 struct SingleLinkable : public SingleLinkable_t 00064 { 00065 /** Link this linkable node from a given root. 00066 * @pre struct your_struct : publid SingleLinkable<your_struct> 00067 * @param fromWhere: from where the node 00068 * should be linked. 00069 */ 00070 void link(T **fromWhere) 00071 { 00072 assert(fromWhere); 00073 00074 next = *fromWhere; 00075 *fromWhere = static_cast<T*>(this); 00076 } 00077 00078 /** Unlink this linkable node from a given root. 00079 * @pre struct your_struct : publid SingleLinkable<your_struct> 00080 * @param fromWhere: from where the node 00081 * should be unlinked. 00082 */ 00083 void unlink(T **fromWhere) 00084 { 00085 assert(fromWhere && 00086 *fromWhere == static_cast<T*>(this)); 00087 00088 *fromWhere = getNext(); 00089 } 00090 00091 /** Access to the (typed) next linkable element. 00092 * @return pointer to next element 00093 */ 00094 T* getNext() const 00095 { 00096 return static_cast<T*>(next); 00097 } 00098 00099 /** Access to the address of the next pointed element. 00100 * @return address of the pointer to the next element. 00101 */ 00102 T** getAtNext() 00103 { 00104 return reinterpret_cast<T**>(&next); 00105 } 00106 }; 00107 00108 00109 /** Template for typed manipulation. 00110 */ 00111 template<class T> 00112 struct DoubleLinkable : public DoubleLinkable_t 00113 { 00114 /** Link this linkable node from a given root. 00115 * @pre struct your_struct : publid DoubleLinkable<your_struct> 00116 * @param fromWhere: from where the node 00117 * should be linked. 00118 */ 00119 void link(T **fromWhere) 00120 { 00121 assert(fromWhere); 00122 00123 previous = reinterpret_cast<DoubleLinkable_t**>(fromWhere); 00124 next = *fromWhere; 00125 if (next) getNext()->previous = 00126 reinterpret_cast<DoubleLinkable_t**>(&next); 00127 *fromWhere = static_cast<T*>(this); 00128 } 00129 00130 /** Unlink this linkable node from a 00131 * given root. We do not need the argument 00132 * for the root since it is a double linked 00133 * node. 00134 * @pre struct your_struct : publid DoubleLinkable<your_struct> 00135 */ 00136 void unlink() 00137 { 00138 assert(previous && 00139 *previous == static_cast<T*>(this)); 00140 00141 *previous = getNext(); 00142 if (next) getNext()->previous = previous; 00143 } 00144 00145 /** Access to the (typed) next linkable element. 00146 * @return pointer to next element 00147 */ 00148 T* getNext() const 00149 { 00150 return static_cast<T*>(next); 00151 } 00152 00153 /** Access to the address of the next pointed element. 00154 * @return address of the pointer to the next element. 00155 */ 00156 T** getAtNext() 00157 { 00158 return reinterpret_cast<T**>(&next); 00159 } 00160 00161 /** Access to the previous element. 00162 * @pre there is a previous element: previous != NULL 00163 * @return address of previous element. 00164 */ 00165 T* getPrevious() const 00166 { 00167 /* the structure has next* and previous** 00168 * where previous is the address of the previous 00169 * next* == beginning of the previous element. 00170 */ 00171 return reinterpret_cast<T*>(previous); 00172 } 00173 00174 /** Cast access to previous. 00175 * @return typed previous. 00176 */ 00177 T** getPreviousPtr() const 00178 { 00179 return reinterpret_cast<T**>(previous); 00180 } 00181 }; 00182 } 00183 00184 00185 #endif // INCLUDE_BASE_LINKABLE_H