1 // Copyright 2016 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include <stdlib.h> 6 7 #include "src/globals.h" 8 #include "src/utils.h" 9 #include "src/zone/zone.h" 10 11 #ifndef V8_SRC_ZONE_ZONE_CHUNK_LIST_H_ 12 #define V8_SRC_ZONE_ZONE_CHUNK_LIST_H_ 13 14 namespace v8 { 15 namespace internal { 16 17 template <typename T> 18 class ZoneChunkListIterator; 19 template <typename T> 20 class ForwardZoneChunkListIterator; 21 template <typename T> 22 class ReverseZoneChunkListIterator; 23 24 // A zone-backed hybrid of a vector and a linked list. Use it if you need a 25 // collection that 26 // * needs to grow indefinitely, 27 // * will mostly grow at the back, but may sometimes grow in front as well 28 // (preferrably in batches), 29 // * needs to have very low overhead, 30 // * offers forward- and backwards-iteration, 31 // * offers relatively fast seeking, 32 // * offers bidirectional iterators, 33 // * can be rewound without freeing the backing store. 34 // This list will maintain a doubly-linked list of chunks. When a chunk is 35 // filled up, a new one gets appended. New chunks appended at the end will 36 // grow in size up to a certain limit to avoid over-allocation and to keep 37 // the zone clean. 38 template <typename T> 39 class ZoneChunkList : public ZoneObject { 40 public: 41 enum class StartMode { 42 // The list will not allocate a starting chunk. Use if you expect your 43 // list to remain empty in many cases. 44 kEmpty = 0, 45 // The list will start with a small initial chunk. Subsequent chunks will 46 // get bigger over time. 47 kSmall = 8, 48 // The list will start with one chunk at maximum size. Use this if you 49 // expect your list to contain many items to avoid growing chunks. 50 kBig = 256 51 }; 52 53 explicit ZoneChunkList(Zone* zone, StartMode start_mode = StartMode::kEmpty) 54 : zone_(zone) { 55 if (start_mode != StartMode::kEmpty) { 56 front_ = NewChunk(static_cast<uint32_t>(start_mode)); 57 back_ = front_; 58 } 59 } 60 61 size_t size() const; 62 63 T& front() const; 64 T& back() const; 65 66 void push_back(const T& item); 67 void pop_back(); 68 69 // Will push a separate chunk to the front of the chunk-list. 70 // Very memory-inefficient. Do only use sparsely! If you have many items to 71 // add in front, consider using 'push_front_many'. 72 void push_front(const T& item); 73 // TODO(heimbuef): Add 'push_front_many'. 74 75 // Cuts the last list elements so at most 'limit' many remain. Does not 76 // free the actual memory, since it is zone allocated. 77 void Rewind(const size_t limit = 0); 78 79 // Quickly scans the list to retrieve the element at the given index. Will 80 // *not* check bounds. 81 ForwardZoneChunkListIterator<T> Find(const size_t index); 82 ForwardZoneChunkListIterator<const T> Find(const size_t index) const; 83 // TODO(heimbuef): Add 'rFind', seeking from the end and returning a 84 // reverse iterator. 85 86 void CopyTo(T* ptr); 87 88 ForwardZoneChunkListIterator<T> begin(); 89 ForwardZoneChunkListIterator<T> end(); 90 ReverseZoneChunkListIterator<T> rbegin(); 91 ReverseZoneChunkListIterator<T> rend(); 92 ForwardZoneChunkListIterator<const T> begin() const; 93 ForwardZoneChunkListIterator<const T> end() const; 94 ReverseZoneChunkListIterator<const T> rbegin() const; 95 ReverseZoneChunkListIterator<const T> rend() const; 96 97 private: 98 friend class ZoneChunkListIterator<T>; 99 friend class ForwardZoneChunkListIterator<T>; 100 friend class ReverseZoneChunkListIterator<T>; 101 static const uint32_t kMaxChunkCapacity = 256u; 102 103 STATIC_ASSERT(kMaxChunkCapacity == static_cast<uint32_t>(StartMode::kBig)); 104 105 struct Chunk { 106 uint32_t capacity_ = 0; 107 uint32_t position_ = 0; 108 Chunk* next_ = nullptr; 109 Chunk* previous_ = nullptr; 110 T* items() { return reinterpret_cast<T*>(this + 1); } 111 }; 112 113 Chunk* NewChunk(const uint32_t capacity) { 114 Chunk* chunk = 115 new (zone_->New(sizeof(Chunk) + capacity * sizeof(T))) Chunk(); 116 chunk->capacity_ = capacity; 117 return chunk; 118 } 119 120 struct SeekResult { 121 Chunk* chunk_; 122 uint32_t chunk_index_; 123 }; 124 125 // Returns the chunk and relative index of the element at the given global 126 // index. Will skip entire chunks and is therefore faster than iterating. 127 SeekResult SeekIndex(size_t index) const; 128 129 Zone* zone_; 130 131 size_t size_ = 0; 132 Chunk* front_ = nullptr; 133 Chunk* back_ = nullptr; 134 135 DISALLOW_COPY_AND_ASSIGN(ZoneChunkList); 136 }; 137 138 template <typename T> 139 class ZoneChunkListIterator { 140 public: 141 T& operator*() { return current_->items()[position_]; } 142 bool operator==(const ZoneChunkListIterator& other) { 143 return other.current_ == current_ && other.position_ == position_; 144 } 145 bool operator!=(const ZoneChunkListIterator& other) { 146 return !operator==(other); 147 } 148 149 protected: 150 ZoneChunkListIterator(typename ZoneChunkList<T>::Chunk* current, 151 size_t position) 152 : current_(current), position_(position) {} 153 154 void MoveNext() { 155 ++position_; 156 if (position_ >= current_->capacity_) { 157 current_ = current_->next_; 158 position_ = 0; 159 } 160 } 161 162 void MoveRNext() { 163 if (position_ == 0) { 164 current_ = current_->previous_; 165 position_ = current_ ? current_->capacity_ - 1 : 0; 166 } else { 167 --position_; 168 } 169 } 170 171 typename ZoneChunkList<T>::Chunk* current_; 172 size_t position_; 173 }; 174 175 template <typename T> 176 class ForwardZoneChunkListIterator : public ZoneChunkListIterator<T> { 177 using ZoneChunkListIterator<T>::current_; 178 using ZoneChunkListIterator<T>::position_; 179 using ZoneChunkListIterator<T>::MoveNext; 180 using ZoneChunkListIterator<T>::MoveRNext; 181 182 public: 183 ForwardZoneChunkListIterator(typename ZoneChunkList<T>::Chunk* current, 184 size_t position) 185 : ZoneChunkListIterator<T>(current, position) {} 186 187 ForwardZoneChunkListIterator& operator++() { 188 MoveNext(); 189 return *this; 190 } 191 192 ForwardZoneChunkListIterator operator++(int) { 193 ForwardZoneChunkListIterator<T> clone(*this); 194 MoveNext(); 195 return clone; 196 } 197 198 ForwardZoneChunkListIterator& operator--() { 199 MoveRNext(); 200 return *this; 201 } 202 203 ForwardZoneChunkListIterator operator--(int) { 204 ForwardZoneChunkListIterator<T> clone(*this); 205 MoveRNext(); 206 return clone; 207 } 208 209 private: 210 friend class ZoneChunkList<T>; 211 static ForwardZoneChunkListIterator<T> Begin(ZoneChunkList<T>* list) { 212 return ForwardZoneChunkListIterator<T>(list->front_, 0); 213 } 214 static ForwardZoneChunkListIterator<T> End(ZoneChunkList<T>* list) { 215 if (list->back_ == nullptr) return Begin(list); 216 217 DCHECK_LE(list->back_->position_, list->back_->capacity_); 218 if (list->back_->position_ == list->back_->capacity_) { 219 return ForwardZoneChunkListIterator<T>(nullptr, 0); 220 } 221 222 return ForwardZoneChunkListIterator<T>(list->back_, list->back_->position_); 223 } 224 }; 225 226 template <typename T> 227 class ReverseZoneChunkListIterator : public ZoneChunkListIterator<T> { 228 using ZoneChunkListIterator<T>::current_; 229 using ZoneChunkListIterator<T>::position_; 230 using ZoneChunkListIterator<T>::MoveNext; 231 using ZoneChunkListIterator<T>::MoveRNext; 232 233 public: 234 ReverseZoneChunkListIterator(typename ZoneChunkList<T>::Chunk* current, 235 size_t position) 236 : ZoneChunkListIterator<T>(current, position) {} 237 238 ReverseZoneChunkListIterator& operator++() { 239 MoveRNext(); 240 return *this; 241 } 242 243 ReverseZoneChunkListIterator operator++(int) { 244 ReverseZoneChunkListIterator<T> clone(*this); 245 MoveRNext(); 246 return clone; 247 } 248 249 ReverseZoneChunkListIterator& operator--() { 250 MoveNext(); 251 return *this; 252 } 253 254 ReverseZoneChunkListIterator operator--(int) { 255 ForwardZoneChunkListIterator<T> clone(*this); 256 MoveNext(); 257 return clone; 258 } 259 260 private: 261 friend class ZoneChunkList<T>; 262 static ReverseZoneChunkListIterator<T> Begin(ZoneChunkList<T>* list) { 263 if (list->back_ == nullptr) return End(list); 264 if (list->back_->position_ == 0) { 265 if (list->back_->previous_ != nullptr) { 266 return ReverseZoneChunkListIterator<T>( 267 list->back_->previous_, list->back_->previous_->capacity_ - 1); 268 } else { 269 return End(list); 270 } 271 } 272 return ReverseZoneChunkListIterator<T>(list->back_, 273 list->back_->position_ - 1); 274 } 275 static ReverseZoneChunkListIterator<T> End(ZoneChunkList<T>* list) { 276 return ReverseZoneChunkListIterator<T>(nullptr, 0); 277 } 278 }; 279 280 template <typename T> 281 size_t ZoneChunkList<T>::size() const { 282 return size_; 283 } 284 285 template <typename T> 286 T& ZoneChunkList<T>::front() const { 287 DCHECK_LT(size_t(0), size()); 288 return front_->items()[0]; 289 } 290 291 template <typename T> 292 T& ZoneChunkList<T>::back() const { 293 DCHECK_LT(size_t(0), size()); 294 295 if (back_->position_ == 0) { 296 return back_->previous_->items()[back_->previous_->position_ - 1]; 297 } else { 298 return back_->items()[back_->position_ - 1]; 299 } 300 } 301 302 template <typename T> 303 void ZoneChunkList<T>::push_back(const T& item) { 304 if (back_ == nullptr) { 305 front_ = NewChunk(static_cast<uint32_t>(StartMode::kSmall)); 306 back_ = front_; 307 } 308 309 DCHECK_LE(back_->position_, back_->capacity_); 310 if (back_->position_ == back_->capacity_) { 311 if (back_->next_ == nullptr) { 312 Chunk* chunk = NewChunk(Min(back_->capacity_ << 1, kMaxChunkCapacity)); 313 back_->next_ = chunk; 314 chunk->previous_ = back_; 315 } 316 back_ = back_->next_; 317 } 318 back_->items()[back_->position_] = item; 319 ++back_->position_; 320 ++size_; 321 } 322 323 template <typename T> 324 void ZoneChunkList<T>::pop_back() { 325 DCHECK_LT(size_t(0), size()); 326 if (back_->position_ == 0) { 327 back_ = back_->previous_; 328 } 329 --back_->position_; 330 } 331 332 template <typename T> 333 void ZoneChunkList<T>::push_front(const T& item) { 334 Chunk* chunk = NewChunk(1); // Yes, this gets really inefficient. 335 chunk->next_ = front_; 336 if (front_) { 337 front_->previous_ = chunk; 338 } else { 339 back_ = chunk; 340 } 341 front_ = chunk; 342 343 chunk->items()[0] = item; 344 chunk->position_ = 1; 345 ++size_; 346 } 347 348 template <typename T> 349 typename ZoneChunkList<T>::SeekResult ZoneChunkList<T>::SeekIndex( 350 size_t index) const { 351 DCHECK_LT(index, size()); 352 Chunk* current = front_; 353 while (index > current->capacity_) { 354 index -= current->capacity_; 355 current = current->next_; 356 } 357 return {current, static_cast<uint32_t>(index)}; 358 } 359 360 template <typename T> 361 void ZoneChunkList<T>::Rewind(const size_t limit) { 362 if (limit >= size()) return; 363 364 SeekResult seek_result = SeekIndex(limit); 365 DCHECK_NOT_NULL(seek_result.chunk_); 366 367 // Do a partial rewind of the chunk containing the index. 368 seek_result.chunk_->position_ = seek_result.chunk_index_; 369 370 // Set back_ so iterators will work correctly. 371 back_ = seek_result.chunk_; 372 373 // Do full rewind of all subsequent chunks. 374 for (Chunk* current = seek_result.chunk_->next_; current != nullptr; 375 current = current->next_) { 376 current->position_ = 0; 377 } 378 379 size_ = limit; 380 } 381 382 template <typename T> 383 ForwardZoneChunkListIterator<T> ZoneChunkList<T>::Find(const size_t index) { 384 SeekResult seek_result = SeekIndex(index); 385 return ForwardZoneChunkListIterator<T>(seek_result.chunk_, 386 seek_result.chunk_index_); 387 } 388 389 template <typename T> 390 ForwardZoneChunkListIterator<const T> ZoneChunkList<T>::Find( 391 const size_t index) const { 392 SeekResult seek_result = SeekIndex(index); 393 return ForwardZoneChunkListIterator<const T>(seek_result.chunk_, 394 seek_result.chunk_index_); 395 } 396 397 template <typename T> 398 void ZoneChunkList<T>::CopyTo(T* ptr) { 399 for (Chunk* current = front_; current != nullptr; current = current->next_) { 400 void* start = current->items(); 401 void* end = current->items() + current->position_; 402 size_t bytes = static_cast<size_t>(reinterpret_cast<uintptr_t>(end) - 403 reinterpret_cast<uintptr_t>(start)); 404 405 MemCopy(ptr, current->items(), bytes); 406 ptr += current->position_; 407 } 408 } 409 410 template <typename T> 411 ForwardZoneChunkListIterator<T> ZoneChunkList<T>::begin() { 412 return ForwardZoneChunkListIterator<T>::Begin(this); 413 } 414 415 template <typename T> 416 ForwardZoneChunkListIterator<T> ZoneChunkList<T>::end() { 417 return ForwardZoneChunkListIterator<T>::End(this); 418 } 419 420 template <typename T> 421 ReverseZoneChunkListIterator<T> ZoneChunkList<T>::rbegin() { 422 return ReverseZoneChunkListIterator<T>::Begin(this); 423 } 424 425 template <typename T> 426 ReverseZoneChunkListIterator<T> ZoneChunkList<T>::rend() { 427 return ReverseZoneChunkListIterator<T>::End(this); 428 } 429 430 template <typename T> 431 ForwardZoneChunkListIterator<const T> ZoneChunkList<T>::begin() const { 432 return ForwardZoneChunkListIterator<const T>::Begin(this); 433 } 434 435 template <typename T> 436 ForwardZoneChunkListIterator<const T> ZoneChunkList<T>::end() const { 437 return ForwardZoneChunkListIterator<const T>::End(this); 438 } 439 440 template <typename T> 441 ReverseZoneChunkListIterator<const T> ZoneChunkList<T>::rbegin() const { 442 return ReverseZoneChunkListIterator<const T>::Begin(this); 443 } 444 445 template <typename T> 446 ReverseZoneChunkListIterator<const T> ZoneChunkList<T>::rend() const { 447 return ReverseZoneChunkListIterator<const T>::End(this); 448 } 449 450 } // namespace internal 451 } // namespace v8 452 453 #endif // V8_SRC_ZONE_ZONE_CHUNK_LIST_H_ 454