1// 2// This file is part of the aMule Project. 3// 4// Copyright (c) 2004-2011 Mikkel Schubert ( xaignar@users.sourceforge.net ) 5// Copyright (c) 2004-2011 aMule Team ( admin@amule.org / http://www.amule.org ) 6// 7// Any parts of this program derived from the xMule, lMule or eMule project, 8// or contributed by third-party developers are copyrighted by their 9// respective authors. 10// 11// This program is free software; you can redistribute it and/or modify 12// it under the terms of the GNU General Public License as published by 13// the Free Software Foundation; either version 2 of the License, or 14// (at your option) any later version. 15// 16// This program is distributed in the hope that it will be useful, 17// but WITHOUT ANY WARRANTY; without even the implied warranty of 18// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19// GNU General Public License for more details. 20// 21// You should have received a copy of the GNU General Public License 22// along with this program; if not, write to the Free Software 23// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA 24// 25 26#ifndef RANGEMAP_H 27#define RANGEMAP_H 28 29#include <map> 30 31#include <common/MuleDebug.h> 32 33 34 35/** 36 * Default helper structure for normal CRangeMap instantations. 37 * 38 * Specializations should must have the following properties. 39 * - The four value typedefs (see comments for details). 40 * - A template-defined member variable named 'first'. 41 * - A comparison operator that doesn't consider the 'first' field. 42 * 43 * The typedefs are used to specify the return values of iterators. 44 */ 45template <typename VALUE, typename KEYTYPE> 46struct CRangeMapHelper 47{ 48 //! Typedef specifying the type to use when a non-const pointer is expected. 49 typedef VALUE* ValuePtr; 50 //! Typedef specifying the type to use when a non-const referenecs is expected. 51 typedef VALUE& ValueRef; 52 //! Typedef specifying the type to use when a const referenecs is expected. 53 typedef const VALUE& ConstValueRef; 54 //! Typedef specifying the type to use when a const pointer is expected. 55 typedef const VALUE* ConstValuePtr; 56 57 //! Used internally by CRangeMap to specify the end of a range. 58 KEYTYPE first; 59 //! Contains the value of a given range. 60 VALUE second; 61 62 //! Compares the user-values of this range with another. 63 bool operator==(const CRangeMapHelper<VALUE, KEYTYPE>& o) const { 64 return second == o.second; 65 } 66}; 67 68 69/** 70 * Helper structure for CRangeSet (CRangeMap with void as value). 71 */ 72template <typename KEYTYPE> 73struct CRangeMapHelper<void, KEYTYPE> 74{ 75 typedef void ValuePtr; 76 typedef void ValueRef; 77 typedef void ConstValueRef; 78 typedef void ConstValuePtr; 79 80 KEYTYPE first; 81 82 bool operator==(const CRangeMapHelper<void, KEYTYPE>&) const { 83 return true; 84 } 85}; 86 87 88/** 89 * This class represents a map of non-overlapping ranges. 90 * 91 * Each range has a user-specified value associated. The map supports quick 92 * lookup of which range covers a particular key-value, and will merge or 93 * split existing ranges when new ranges are added. 94 * 95 * The decision on whenever to split/resize a range or to merge the two ranges 96 * involved is based on equality of the user-specified value, using the 97 * equality operator. Thus if two ranges with the same user-value are placed 98 * adjacent to each other or partially overlapping each other, then they will 99 * be merged into a single range. If the user-values of the two ranges are 100 * different, then the old range will be either resized or split, based on the 101 * position of the new range. 102 * 103 * In cases where ranges are split into two parts, copies will be made of the 104 * user-specified value, such that each new part contains the same user-value. 105 * 106 * It is currently not possible to manipulate existing ranges by hand, other 107 * than by erasing and then re-inserting them. 108 * 109 * A specialization of this class exists (typedef'd as CRangeSet), which does 110 * not assosiate a value with each range. 111 * 112 * NOTE: KEYTYPE is assumed to be an unsigned integer type! 113 */ 114template <typename VALUE, typename KEYTYPE = uint64> 115class CRangeMap 116{ 117 typedef CRangeMapHelper<VALUE, KEYTYPE> HELPER; 118private: 119 //! The map uses the start-key as key and the User-value and end-key pair as value 120 typedef std::map<KEYTYPE, HELPER> RangeMap; 121 //! Shortcut for the pair used by the RangeMap. 122 typedef std::pair<KEYTYPE, HELPER> RangePair; 123 124 //! Typedefs used to distinguish between our custom iterator and the real ones. 125 typedef typename RangeMap::iterator RangeIterator; 126 typedef typename RangeMap::const_iterator ConstRangeIterator; 127 128 //! The raw map of range values. 129 RangeMap m_ranges; 130 131 /** 132 * This class provides a wrapper around the raw iterators used by CRangeMap. 133 * 134 * It will act as a normal iterator and also give access the the range values. 135 * When used as a per normal, it will return the value specified by the user 136 * for that range. 137 * 138 * Special member-functions are keyStart() and keyEnd(). 139 */ 140 template <typename RealIterator, typename ReturnTypeRef, typename ReturnTypePtr> 141 class iterator_base { 142 friend class CRangeMap<VALUE, KEYTYPE>; 143 public: 144 iterator_base( const RealIterator& it ) 145 : m_it( it ) 146 { 147 } 148 149 //! Equality operator 150 bool operator==( const iterator_base& other ) const { 151 return m_it == other.m_it; 152 } 153 154 //! Non-equality operator 155 bool operator!=( const iterator_base& other ) const { 156 return m_it != other.m_it; 157 } 158 159 160 //! Returns the starting point of the range 161 KEYTYPE keyStart() const { 162 return m_it->first; 163 } 164 165 //! Returns the end-point of the range 166 KEYTYPE keyEnd() const { 167 return m_it->second.first; 168 } 169 170 171 //! Prefix increment. 172 iterator_base& operator++() { 173 ++m_it; 174 175 return *this; 176 } 177 178 //! Postfix increment. 179 iterator_base operator++(int) { 180 return iterator_base( m_it++ ); 181 } 182 183 184 //! Prefix decrement. 185 iterator_base& operator--() { 186 --m_it; 187 188 return *this; 189 } 190 191 //! Postfix decrement. 192 iterator_base operator--(int) { 193 return iterator_base( m_it-- ); 194 } 195 196 197 //! Deference operator, returning the user-specified value. 198 ReturnTypeRef operator*() const { 199 return m_it->second.second; 200 } 201 202 //! Member access operator, returning the user-specified value. 203 ReturnTypePtr operator->() const { 204 return &m_it->second.second; 205 } 206 207 protected: 208 //! The raw iterator 209 RealIterator m_it; 210 }; 211 212 typedef typename HELPER::ValueRef ValueRef; 213 typedef typename HELPER::ValuePtr ValuePtr; 214 typedef typename HELPER::ConstValueRef ConstValueRef; 215 typedef typename HELPER::ConstValuePtr ConstValuePtr; 216 217public: 218 typedef iterator_base<RangeIterator, ValueRef, ValuePtr> iterator; 219 typedef iterator_base<ConstRangeIterator, ConstValueRef, ConstValuePtr> const_iterator; 220 221 //! The type used to specify size, ie size(). 222 typedef typename RangeMap::size_type size_type; 223 224 //! The type of user-data saved with each range. 225 typedef VALUE value_type; 226 227 /** 228 * Default constructor. 229 */ 230 CRangeMap() { 231 } 232 233 /** 234 * Copy-constructor. 235 */ 236 CRangeMap(const CRangeMap<VALUE, KEYTYPE>& other) 237 : m_ranges( other.m_ranges ) 238 { 239 } 240 241 /** 242 * Assignment operator. 243 */ 244 CRangeMap& operator=(const CRangeMap<VALUE, KEYTYPE>& other) { 245 m_ranges = other.m_ranges; 246 247 return *this; 248 } 249 250 /** 251 * Swaps the contents of the two rangemaps. 252 */ 253 void swap(CRangeMap<VALUE, KEYTYPE>& other) { 254 std::swap(m_ranges, other.m_ranges); 255 } 256 257 258 /** 259 * Equality operator for two ranges. 260 * 261 * @returns True if both ranges contain the same ranges and values. 262 */ 263 bool operator==( const CRangeMap<VALUE, KEYTYPE>& other ) const { 264 // Check if we are comparing with ourselves 265 if ( this == &other ) { 266 return true; 267 } 268 269 // Check size, must be the same 270 if ( size() != other.size() ) { 271 return false; 272 } 273 274 return (m_ranges == other.m_ranges); 275 } 276 277 278 /** 279 * Returns an iterator pointing to the first range. 280 */ 281 iterator begin() { 282 return m_ranges.begin(); 283 } 284 285 /** 286 * Returns an iterator pointing past the last range. 287 */ 288 iterator end() { 289 return m_ranges.end(); 290 } 291 292 /** 293 * Returns a const iterator pointing to the first range. 294 */ 295 const_iterator begin() const { 296 return m_ranges.begin(); 297 } 298 299 /** 300 * Returns a const iterator pointing past the last range. 301 */ 302 const_iterator end() const { 303 return m_ranges.end(); 304 } 305 306 307 /** 308 * Erases the specified range and returns the range next to it. 309 * 310 * @param pos The iterator of the range to be erased. 311 * @return The iterator of the range after the erased range. 312 * 313 * Attempting to erase the end() iterator is an invalid operation. 314 */ 315 iterator erase(iterator pos) { 316 MULE_VALIDATE_PARAMS(pos != end(), wxT("Cannot erase 'end'")); 317 318 RangeIterator temp = pos.m_it++; 319 320 m_ranges.erase(temp); 321 322 return pos; 323 } 324 325 326 /** 327 * Returns the number of ranges in the map. 328 */ 329 size_type size() const { 330 return m_ranges.size(); 331 } 332 333 /** 334 * Returns true if the map is empty. 335 */ 336 bool empty() const { 337 return m_ranges.empty(); 338 } 339 340 341 /** 342 * Removes all ranges from the map. 343 */ 344 void clear() { 345 m_ranges.clear(); 346 } 347 348 349 /** 350 * Returns the range covering the specified key-value. 351 * 352 * @param key A value that may or may not be covered by a range. 353 * @return end() or the iterator of the range covering key. 354 * 355 * A range is considered to cover a value if the value is greather than or 356 * equal to the start-key and less than or equal to the end-key. 357 */ 358 // Find the range which contains key (it->first <= key <= it->second->first) 359 iterator find_range( KEYTYPE key ) { 360 if ( !m_ranges.empty() ) { 361 // Find first range whose start comes after key 362 // Thus: key < it->first, but (--it)->first <= key 363 RangeIterator it = m_ranges.upper_bound( key ); 364 365 // Our target range must come before the one we found; does it exist? 366 if ( it != m_ranges.begin() ) { 367 // Go back to the last range which starts at or before key 368 it--; 369 370 // Check if this range covers the key 371 if ( key <= it->second.first ) { 372 return it; 373 } 374 } 375 } 376 377 return end(); 378 } 379 380 381 void erase_range(KEYTYPE startPos, KEYTYPE endPos) { 382 // Create default initialized entry, which ensures that all fields are initialized. 383 HELPER entry = HELPER(); 384 // Need to set the 'end' field. 385 entry.first = endPos; 386 387 // Insert without merging, which forces the creation of an entry that 388 // only covers the specified range, which will crop existing ranges. 389 erase(do_insert(startPos, entry, false)); 390 } 391 392 393 /** 394 * Inserts a new range into the map, potentially erasing/changing old ranges. 395 * 396 * @param startPos The start position of the range, also considered part of the range. 397 * @param endPos The end position of the range, also considered part of the range. 398 * @param object The user-data to be assosiated with the range. 399 * @return An iterator pointing to the resulting range, covering at least the specified range. 400 * 401 * This function inserts the specified range into the map, while overwriting 402 * or resizing existing ranges if there is any conflict. Ranges might also 403 * be merged, if the object of each evaluates to being equal, in which case 404 * the old range will be removed and the new extended to include the old 405 * range. This also includes ranges placed directly after or in front of each 406 * other, which will also be merged if their type is the same. 407 * 408 * This has the result that the iterator returned can point to a range quite 409 * different from what was originally specified. If this is not desired, then 410 * the VALUE type should simply be made to return false on all equality tests. 411 * Otherwise, the only promise that is made is that the resulting range has 412 * the same user-data (based on the equality operator) as the what was specified. 413 * 414 * Note that the start position must be smaller than or equal to the end-position. 415 */ 416 //@{ 417 iterator insert(KEYTYPE startPos, KEYTYPE endPos) { 418 HELPER entry = {endPos}; 419 return do_insert(startPos, entry); 420 } 421 template <typename TYPE> 422 iterator insert(KEYTYPE startPos, KEYTYPE endPos, const TYPE& value) { 423 HELPER entry = {endPos, value}; 424 return do_insert(startPos, entry); 425 } 426 //@} 427 428protected: 429 /** 430 * Inserts the specified range. 431 * 432 * @param start The starting position of the range. 433 * @param entry A helper-struct, containing the end position and possibly user-data. 434 * @param merge Specifies if ranges should be merged when possible. 435 * @return An iterator pointing to the range covering at least the specified range. 436 */ 437 iterator do_insert(KEYTYPE start, HELPER entry, bool merge = true) { 438 MULE_VALIDATE_PARAMS(start <= entry.first, wxT("Not a valid range.")); 439 440 RangeIterator it = get_insert_it(start); 441 while ( it != m_ranges.end() ) { 442 // Begins before the current span 443 if ( start <= it->first ) { 444 // Never touches the current span, it follows that start < it->first 445 // (it->first) is used to avoid checking against (uintXX)-1 by accident 446 if ( entry.first < it->first - 1 && it->first ) { 447 break; 448 } 449 450 // Stops just before the current span, it follows that start < it->first 451 // (it->first) is used to avoid checking against (uintXX)-1 by accident 452 else if ( entry.first == it->first - 1 && it->first ) { 453 // If same type: Merge 454 if (merge && (entry == it->second)) { 455 entry.first = it->second.first; 456 m_ranges.erase( it++ ); 457 } 458 459 break; 460 } 461 462 // Covers part of the span 463 else if ( entry.first < it->second.first ) { 464 // Same type, merge 465 if (merge && (entry == it->second)) { 466 entry.first = it->second.first; 467 m_ranges.erase( it++ ); 468 } else { 469 // Resize the partially covered span and get the next one 470 it = ++resize( entry.first + 1, it->second.first, it ); 471 } 472 473 break; 474 } else { 475 // It covers the entire span 476 m_ranges.erase( it++ ); 477 } 478 } 479 480 // Starts inside the current span or after the current span 481 else { 482 // Starts inside the current span 483 if ( start <= it->second.first ) { 484 // Ends inside the current span 485 if ( entry.first < it->second.first ) { 486 // Adding a span with same type inside a existing span is fruitless 487 if (merge && (entry == it->second)) { 488 return it; 489 } 490 491 // Insert the new span 492 m_ranges.insert(it, RangePair(entry.first + 1, it->second)); 493 494 // Resize the current span to fit before the new span 495 it->second.first = start - 1; 496 497 break; 498 } else { 499 // Ends past the current span, resize or merge 500 if (merge && (entry == it->second)) { 501 start = it->first; 502 m_ranges.erase( it++ ); 503 } else { 504 // Resize the partially covered span and get the next one 505 it = ++resize( it->first, start - 1, it ); 506 } 507 } 508 } else { 509 // Start past the current span 510 if ( start == it->second.first + 1 ) { 511 // Touches the current span 512 if (merge && (entry == it->second)) { 513 start = it->first; 514 m_ranges.erase( it++ ); 515 } else { 516 ++it; 517 } 518 } else { 519 // Starts after the current span, nothing to do 520 ++it; 521 } 522 } 523 } 524 } 525 526 return m_ranges.insert(it, RangePair(start, entry)); 527 } 528 529 530 /** 531 * Finds the optimal location to start looking for insertion points. 532 * 533 * This is the first range whose start comes after the new start. We check 534 * the last element first, since sequential insertions are commen. 535 */ 536 RangeIterator get_insert_it(KEYTYPE start) 537 { 538 if ( m_ranges.empty() ) { 539 return m_ranges.end(); 540 } 541 542 // The start-key of the last element must be smaller than our start-key 543 // Otherwise there is the possibility that we can merge with the one before that 544 RangeIterator it = --m_ranges.end(); 545 if ( start <= it->first ) { 546 // If the two starts are equal, then we only need to go back another 547 // step to see if the range prior to this one is mergeable 548 if ( start != it->first ) { 549 it = m_ranges.lower_bound( start ); 550 } 551 552 if ( it != m_ranges.begin() ) { 553 // Go back to the last range which starts at or before key 554 --it; 555 } 556 } 557 558 return it; 559 } 560 561 562 //! Helper function that resizes an existing range to the specified size. 563 RangeIterator resize( KEYTYPE startPos, KEYTYPE endPos, RangeIterator it ) { 564 HELPER item = it->second; 565 item.first = endPos; 566 567 m_ranges.erase( it++ ); 568 569 return m_ranges.insert(it, RangePair(startPos, item)); 570 } 571}; 572 573 574//! CRangeSet is simply a partial specialization of CRangeMap 575typedef CRangeMap<void> CRangeSet; 576 577 578namespace std 579{ 580 /** @see CRangeMap::swap */ 581 template <typename VALUE_TYPE, typename KEY_TYPE> 582 void swap(CRangeMap<VALUE_TYPE, KEY_TYPE>& a, CRangeMap<VALUE_TYPE, KEY_TYPE>& b) 583 { 584 a.swap(b); 585 } 586} 587 588 589 590#endif 591// File_checked_for_headers 592