1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the class library */ 4 /* SoPlex --- the Sequential object-oriented simPlex. */ 5 /* */ 6 /* Copyright (c) 1996-2023 Zuse Institute Berlin (ZIB) */ 7 /* */ 8 /* Licensed under the Apache License, Version 2.0 (the "License"); */ 9 /* you may not use this file except in compliance with the License. */ 10 /* You may obtain a copy of the License at */ 11 /* */ 12 /* http://www.apache.org/licenses/LICENSE-2.0 */ 13 /* */ 14 /* Unless required by applicable law or agreed to in writing, software */ 15 /* distributed under the License is distributed on an "AS IS" BASIS, */ 16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */ 17 /* See the License for the specific language governing permissions and */ 18 /* limitations under the License. */ 19 /* */ 20 /* You should have received a copy of the Apache-2.0 license */ 21 /* along with SoPlex; see the file LICENSE. If not email to soplex@zib.de. */ 22 /* */ 23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 24 25 /**@file islist.h 26 * @brief Generic single linked list. 27 */ 28 #ifndef _ISLIST_H_ 29 #define _ISLIST_H_ 30 31 #include <assert.h> 32 #include <stddef.h> 33 #include <iostream> 34 35 36 namespace soplex 37 { 38 39 //--------------------------------------------------------------------- 40 // class IsElement<T> 41 //--------------------------------------------------------------------- 42 43 /**@brief Elements for \ref soplex::IsList "IsList"s. 44 @ingroup Elementary 45 46 Class IsElement allows to easily construct list elements for an intrusive 47 single linked list IsList out of a template class T. It adds a next 48 pointer to each element. An instance of IdElement<T> a can be used just 49 like an instance of T itself, except that method next() has been 50 added (thereby overriding any method next() defined in T). 51 */ 52 template < class T > 53 class IsElement : public T 54 { 55 protected: 56 57 //-------------------------- 58 /**@name Data */ 59 ///@{ 60 IsElement<T>* the_next; ///< pointer to next element in the IsList. 61 ///@} 62 63 public: 64 65 //--------------------------------- 66 /**@name Successor */ 67 ///@{ 68 /// 69 IsElement<T>*& next() 70 { 71 return the_next; 72 } 73 /// returns the next element in the IsList. 74 IsElement<T>* next() const 75 { 76 return the_next; 77 } 78 ///@} 79 80 //------------------------------------ 81 /**@name Constructors / destructors */ 82 ///@{ 83 84 /// default constructor. 85 IsElement() 86 {} 87 88 /// 89 explicit 90 IsElement(const T& old) 91 : T(old) 92 , the_next(0) 93 {} 94 95 /// copy constructor. 96 /** Only the element itself is copied, while the link to the next list 97 element is set to a zero pointer. 98 */ 99 IsElement(const IsElement<T>& old) 100 : T(old) 101 , the_next(0) 102 {} 103 }; 104 105 //--------------------------------------------------------------------- 106 // class IsList<T> 107 //--------------------------------------------------------------------- 108 109 /**@brief Generic single linked list. 110 @ingroup Elementary 111 112 Class IsList implements an intrusive single linked list of elements of a 113 template class T. As an \em intrusive list, the objects of type T 114 must provide methods next() for setting and inquiring a pointer to the 115 next element in a list. The user is responsible for not modifying the 116 next() pointer of elements currently residing in a list, which may destroy 117 the lists integrity. For this, class IsList provides enough methods for 118 modifying a list in a save way. See the method list for a description. 119 */ 120 template < class T > 121 class IsList 122 { 123 protected: 124 T* the_first; ///< the first element in the IsList. 125 T* the_last; ///< the last element in the IsList. 126 bool destroyElements; 127 ///< should the destructor be called for each element when the list is destroyed? 128 129 public: 130 typedef IsElement<T> Element; 131 132 //-------------------------- 133 /**@name Extension */ 134 ///@{ 135 /// appends \p elem to IsList. 136 void append(T* elem) 137 { 138 if(the_last) 139 the_last->next() = elem; 140 else 141 the_first = elem; 142 143 the_last = elem; 144 } 145 146 /// prepends \p elem to IsList. 147 void prepend(T* elem) 148 { 149 if(the_first) 150 elem->next() = the_first; 151 else 152 the_last = elem; 153 154 the_first = elem; 155 } 156 157 /// inserts \p elem to IsList after its element \p after. 158 void insert(T* elem, T* after) 159 { 160 assert(find(after)); 161 162 if(after == the_last) 163 append(elem); 164 else 165 { 166 elem->next() = after->next(); 167 after->next() = elem; 168 } 169 } 170 171 /// appends all elements of \p list to IsList. 172 /** Appending one list to another keeps the appended \p list. Instead, 173 \p list remains an own IsList which is then part of the 174 concatenated list. This means that modifying \p list will modify the 175 concateneted list as well and vice versa. The programmer is 176 responsible for such changes not to yield inconsistent lists. 177 */ 178 void append(IsList<T>& list) 179 { 180 if(list.the_first) 181 { 182 append(list.the_first); 183 the_last = list.the_last; 184 } 185 } 186 187 /// prepends all elements of \p list to IsList. 188 /** Appending one list to another keeps the appended \p list. Instead, 189 \p list remains an own IsList which is then part of the 190 concatenated list. This means that modifying \p list will modify the 191 concateneted list as well and vice versa. The programmer is 192 responsible for such changes not to yield inconsistent lists. 193 */ 194 void prepend(IsList<T>& list) 195 { 196 if(list.the_first) 197 { 198 prepend(list.the_last); 199 the_first = list.the_first; 200 } 201 } 202 203 /// inserts all elements of \p list after element \p after of an IsList. 204 /** Inserting one list into another keeps the appended \p list. Instead, 205 \p list remains an own IsList which is then part of the 206 concatenated list. This means that modifying \p list will modify the 207 concateneted list as well and vice versa. The programmer is 208 responsible for such changes not to yield inconsistent lists. 209 */ 210 void insert(IsList<T>& list, T* after) 211 { 212 assert(find(after)); 213 214 if(list.the_first) 215 { 216 list.the_last->next() = after->next(); 217 after->next() = list.first(); 218 219 if(after == last()) 220 the_last = list.last(); 221 } 222 } 223 ///@} 224 225 //-------------------------- 226 /**@name Removal */ 227 ///@{ 228 /// removes the successor of \p after from an IsList. 229 void remove_next(T* after) 230 { 231 assert(find(after)); 232 233 if(after->next()) 234 { 235 if(after->next() == last()) 236 the_last = after; 237 238 after->next() = after->next()->next(); 239 } 240 } 241 242 /// removes element \p elem from an IsList. 243 void remove(const T* elem) 244 { 245 if(the_first) 246 { 247 if(elem == the_first) 248 { 249 the_first = next(elem); 250 251 if(the_first == 0) 252 the_last = 0; 253 } 254 else 255 { 256 T* after = the_first; 257 258 for(; after != the_last; after = after->next()) 259 if(after->next() == elem) 260 { 261 remove_next(after); 262 return; 263 } 264 } 265 } 266 } 267 268 /// removes all elements of \p list from an IsList. 269 /** Removing \p list from an IsList requires \p list to be part of the 270 IsList. Such a situation can be achieved by previously adding 271 (i.e., #append%ing, #insert%ing or #prepend%ing) a list or 272 explicitely constructing a sublist with method sublist(). 273 */ 274 void remove(IsList<T>& list) 275 { 276 if(the_first != 0 && list.the_first != 0) 277 { 278 assert(find(list.first())); 279 assert(find(list.last())); 280 281 if(the_first == list.the_first) 282 { 283 if(the_last == list.the_last) 284 the_first = the_last = 0; 285 else 286 the_first = list.the_last->next(); 287 } 288 else 289 { 290 T* after = the_first; 291 292 for(; after->next() != list.the_first; after = after->next()) 293 ; 294 295 if(the_last == list.the_last) 296 the_last = after; 297 else 298 after->next() = list.the_last->next(); 299 } 300 } 301 } 302 303 /// removes all elements from an IsList. 304 void clear(bool pDestroyElements = false) 305 { 306 if(pDestroyElements) 307 { 308 T* nextElement; 309 310 for(T* it = the_first; it; it = nextElement) 311 { 312 nextElement = next(it); 313 it->~T(); 314 spx_free(it); 315 } 316 } 317 318 the_first = the_last = 0; 319 } 320 ///@} 321 322 //-------------------------- 323 /**@name Access */ 324 ///@{ 325 /// returns the IsList's first element. 326 T* first() const 327 { 328 return the_first; 329 } 330 331 /// returns the IsList's last element. 332 T* last() const 333 { 334 return the_last; 335 } 336 337 /// returns successor of \p elem in an IsList. 338 /** The successor of \p elem in a list generally corresponds to the 339 element returned by elem->next(). However, if \p elem is the last 340 element in an IsList, this method will return 0, whereas 341 elem->next() may yield an arbitrary value. For example, if the 342 current list is actually a sublist of another, larger IsList, 343 elem->next() returns the successor of \p elem in this larger 344 IsList. 345 */ 346 T* next(const T* elem) const 347 { 348 return (elem == the_last) ? 0 : elem->next(); 349 } 350 351 /// returns the number of elements in IsList. 352 int length() const 353 { 354 int num; 355 356 if(the_first) 357 { 358 T* test = the_first; 359 360 for(num = 1; test != the_last; test = test->next()) 361 ++num; 362 363 return num; 364 } 365 366 return 0; 367 } 368 369 /// returns the position of element \p elem within IsList. 370 int find(const T* elem) const 371 { 372 const T* test; 373 374 assert(elem != 0); 375 376 for(test = the_first; test != 0; test = next(test)) 377 if(test == elem) 378 return 1; 379 380 return 0; 381 } 382 383 /// constructs sublist of an IsList. 384 /** Returns a new IsList containing a sublist of an IsList starting 385 with element \p start and reaching up to element \p end. Both must be 386 members of the IsList or 0, in which case the first and last 387 element are used, respectively. 388 */ 389 IsList<T>sublist(const T* start = 0, const T* end = 0) const 390 { 391 IsList<T>part = *this; 392 393 if(start) 394 { 395 assert(find(start)); 396 part.the_first = const_cast<T*>(start); 397 } 398 399 if(end) 400 { 401 assert(part.find(end)); 402 part.the_last = const_cast<T*>(end); 403 } 404 405 return part; 406 } 407 ///@} 408 409 //-------------------------- 410 /**@name Miscellaneous */ 411 ///@{ 412 /// adjusts list pointers to a new memory address. 413 /** This method is of a rather technical nature. If all list elements 414 are taken form one array of elements, in certain circumstances the 415 user may be forced to realloc this array. As a consequence all 416 next() pointers of the list elements would become invalid. 417 However, all addresses will be changed by a constant offset \p delta. 418 Then move( \p delta ) may be called, which adjusts the next() 419 pointers of all elements in the list. 420 */ 421 void move(ptrdiff_t delta) 422 { 423 if(the_first) 424 { 425 T* elem; 426 the_last = reinterpret_cast<T*>(reinterpret_cast<char*>(the_last) + delta); 427 the_first = reinterpret_cast<T*>(reinterpret_cast<char*>(the_first) + delta); 428 429 for(elem = first(); elem; elem = next(elem)) 430 if(elem != last()) 431 elem->next() = reinterpret_cast<T*>(reinterpret_cast<char*>(elem->next()) + delta); 432 } 433 } 434 435 /// consistency check. 436 bool isConsistent() const 437 { 438 #ifdef ENABLE_CONSISTENCY_CHECKS 439 440 if(first() != 0 && last() == 0) 441 return SPX_MSG_INCONSISTENT("IsList"); 442 443 if(first() == 0 && last() != 0) 444 return SPX_MSG_INCONSISTENT("IsList"); 445 446 if(first() && find(last()) == 0) 447 return SPX_MSG_INCONSISTENT("IsList"); 448 449 #endif 450 451 return true; 452 } 453 ///@} 454 455 //------------------------------------ 456 /**@name Constructors / Destructors */ 457 ///@{ 458 /// default constructor. 459 /** The default constructor may be used to setup a (sub-)list, by 460 specifying a \p first and \p last element. Then \p last must be a 461 successor of \p first. 462 */ 463 explicit 464 IsList(T* pfirst = 0, T* plast = 0, bool pDestroyElements = false) 465 : the_first(pfirst) 466 , the_last(plast) 467 , destroyElements(pDestroyElements) 468 { 469 if(pfirst) 470 { 471 assert(plast != 0); 472 assert(find(plast)); 473 } 474 475 assert(isConsistent()); 476 } 477 478 /// Assignment operator and copy constructor should be deleted to avoid memory problems 479 IsList(const IsList<T>&) = delete; 480 IsList<T>& operator=(const IsList<T>& old) = delete; 481 482 /// destructor 483 ~IsList() 484 { 485 clear(destroyElements); 486 } 487 ///@} 488 }; 489 490 } // namespace soplex 491 #endif // _ISLIST_H_ 492