1/* 2 * Copyright 2001-2014 Haiku, Inc. All rights reserved. 3 * Distributed under the terms of the MIT License. 4 * 5 * Authors: 6 * The Storage Kit Team 7 * Stephan Aßmus 8 * Rene Gollent 9 * John Scipione, jscipione@gmail.com 10 * Isaac Yonemoto 11 */ 12 13//! BList class provides storage for pointers. Not thread safe. 14 15 16#include <List.h> 17 18#include <stdio.h> 19#include <stdlib.h> 20#include <string.h> 21 22 23// helper function 24static inline void 25move_items(void** items, int32 offset, int32 count) 26{ 27 if (count > 0 && offset != 0) 28 memmove(items + offset, items, count * sizeof(void*)); 29} 30 31 32BList::BList(int32 count) 33 : 34 fObjectList(NULL), 35 fPhysicalSize(0), 36 fItemCount(0), 37 fBlockSize(count), 38 fResizeThreshold(0) 39{ 40 if (fBlockSize <= 0) 41 fBlockSize = 1; 42 _ResizeArray(fItemCount); 43} 44 45 46BList::BList(const BList& other) 47 : 48 fObjectList(NULL), 49 fPhysicalSize(0), 50 fItemCount(0), 51 fBlockSize(other.fBlockSize) 52{ 53 *this = other; 54} 55 56 57BList::~BList() 58{ 59 free(fObjectList); 60} 61 62 63BList& 64BList::operator=(const BList& other) 65{ 66 if (&other != this) { 67 fBlockSize = other.fBlockSize; 68 if (_ResizeArray(other.fItemCount)) { 69 fItemCount = other.fItemCount; 70 memcpy(fObjectList, other.fObjectList, fItemCount * sizeof(void*)); 71 } 72 } 73 74 return *this; 75} 76 77 78bool 79BList::operator==(const BList& other) const 80{ 81 if (&other == this) 82 return true; 83 84 if (other.fItemCount != fItemCount) 85 return false; 86 87 if (fItemCount > 0) { 88 return memcmp(fObjectList, other.fObjectList, 89 fItemCount * sizeof(void*)) == 0; 90 } 91 92 return true; 93} 94 95 96bool 97BList::operator!=(const BList& other) const 98{ 99 return !(*this == other); 100} 101 102 103bool 104BList::AddItem(void* item, int32 index) 105{ 106 if (index < 0 || index > fItemCount) 107 return false; 108 109 bool result = true; 110 111 if (fItemCount + 1 > fPhysicalSize) 112 result = _ResizeArray(fItemCount + 1); 113 if (result) { 114 ++fItemCount; 115 move_items(fObjectList + index, 1, fItemCount - index - 1); 116 fObjectList[index] = item; 117 } 118 return result; 119} 120 121 122bool 123BList::AddItem(void* item) 124{ 125 bool result = true; 126 if (fPhysicalSize > fItemCount) { 127 fObjectList[fItemCount] = item; 128 ++fItemCount; 129 } else { 130 if ((result = _ResizeArray(fItemCount + 1))) { 131 fObjectList[fItemCount] = item; 132 ++fItemCount; 133 } 134 } 135 return result; 136} 137 138 139bool 140BList::AddList(const BList* list, int32 index) 141{ 142 bool result = (list && index >= 0 && index <= fItemCount); 143 if (result && list->fItemCount > 0) { 144 int32 count = list->fItemCount; 145 if (fItemCount + count > fPhysicalSize) 146 result = _ResizeArray(fItemCount + count); 147 148 if (result) { 149 fItemCount += count; 150 move_items(fObjectList + index, count, fItemCount - index - count); 151 memcpy(fObjectList + index, list->fObjectList, 152 list->fItemCount * sizeof(void*)); 153 } 154 } 155 156 return result; 157} 158 159 160bool 161BList::AddList(const BList* list) 162{ 163 bool result = (list != NULL); 164 if (result && list->fItemCount > 0) { 165 int32 index = fItemCount; 166 int32 count = list->fItemCount; 167 if (fItemCount + count > fPhysicalSize) 168 result = _ResizeArray(fItemCount + count); 169 170 if (result) { 171 fItemCount += count; 172 memcpy(fObjectList + index, list->fObjectList, 173 list->fItemCount * sizeof(void*)); 174 } 175 } 176 177 return result; 178} 179 180 181bool 182BList::RemoveItem(void* item) 183{ 184 int32 index = IndexOf(item); 185 bool result = (index >= 0); 186 if (result) 187 RemoveItem(index); 188 return result; 189} 190 191 192void* 193BList::RemoveItem(int32 index) 194{ 195 void* item = NULL; 196 if (index >= 0 && index < fItemCount) { 197 item = fObjectList[index]; 198 move_items(fObjectList + index + 1, -1, fItemCount - index - 1); 199 --fItemCount; 200 if (fItemCount <= fResizeThreshold) 201 _ResizeArray(fItemCount); 202 } 203 return item; 204} 205 206 207bool 208BList::RemoveItems(int32 index, int32 count) 209{ 210 bool result = (index >= 0 && index <= fItemCount); 211 if (result) { 212 if (index + count > fItemCount) 213 count = fItemCount - index; 214 if (count > 0) { 215 move_items(fObjectList + index + count, -count, 216 fItemCount - index - count); 217 fItemCount -= count; 218 if (fItemCount <= fResizeThreshold) 219 _ResizeArray(fItemCount); 220 } else 221 result = false; 222 } 223 return result; 224} 225 226 227bool 228BList::ReplaceItem(int32 index, void* item) 229{ 230 bool result = false; 231 232 if (index >= 0 && index < fItemCount) { 233 fObjectList[index] = item; 234 result = true; 235 } 236 return result; 237} 238 239 240void 241BList::MakeEmpty() 242{ 243 fItemCount = 0; 244 _ResizeArray(0); 245} 246 247 248// #pragma mark - Reordering items. 249 250 251void 252BList::SortItems(int (*compareFunc)(const void*, const void*)) 253{ 254 if (compareFunc) 255 qsort(fObjectList, fItemCount, sizeof(void*), compareFunc); 256} 257 258 259bool 260BList::SwapItems(int32 indexA, int32 indexB) 261{ 262 bool result = false; 263 264 if (indexA >= 0 && indexA < fItemCount 265 && indexB >= 0 && indexB < fItemCount) { 266 267 void* tmpItem = fObjectList[indexA]; 268 fObjectList[indexA] = fObjectList[indexB]; 269 fObjectList[indexB] = tmpItem; 270 271 result = true; 272 } 273 274 return result; 275} 276 277 278/*! This moves a list item from posititon a to position b, moving the 279 appropriate block of list elements to make up for the move. For example, 280 in the array: 281 A B C D E F G H I J 282 Moveing 1(B)->6(G) would result in this: 283 A C D E F G B H I J 284*/ 285bool 286BList::MoveItem(int32 from, int32 to) 287{ 288 if ((from >= fItemCount) || (to >= fItemCount) || (from < 0) || (to < 0)) 289 return false; 290 291 void* tmpMover = fObjectList[from]; 292 if (from < to) { 293 memmove(fObjectList + from, fObjectList + from + 1, 294 (to - from) * sizeof(void*)); 295 } else if (from > to) { 296 memmove(fObjectList + to + 1, fObjectList + to, 297 (from - to) * sizeof(void*)); 298 } 299 fObjectList[to] = tmpMover; 300 301 return true; 302} 303 304 305// #pragma mark - Retrieving items. 306 307 308void* 309BList::ItemAt(int32 index) const 310{ 311 void* item = NULL; 312 if (index >= 0 && index < fItemCount) 313 item = fObjectList[index]; 314 return item; 315} 316 317 318void* 319BList::FirstItem() const 320{ 321 void* item = NULL; 322 if (fItemCount > 0) 323 item = fObjectList[0]; 324 return item; 325} 326 327 328void* 329BList::ItemAtFast(int32 index) const 330{ 331 return fObjectList[index]; 332} 333 334 335void* 336BList::Items() const 337{ 338 return fObjectList; 339} 340 341 342void* 343BList::LastItem() const 344{ 345 void* item = NULL; 346 if (fItemCount > 0) 347 item = fObjectList[fItemCount - 1]; 348 return item; 349} 350 351 352// #pragma mark - Querying the list. 353 354 355bool 356BList::HasItem(void* item) const 357{ 358 return (IndexOf(item) >= 0); 359} 360 361 362bool 363BList::HasItem(const void* item) const 364{ 365 return (IndexOf(item) >= 0); 366} 367 368 369int32 370BList::IndexOf(void* item) const 371{ 372 for (int32 i = 0; i < fItemCount; i++) { 373 if (fObjectList[i] == item) 374 return i; 375 } 376 return -1; 377} 378 379 380int32 381BList::IndexOf(const void* item) const 382{ 383 for (int32 i = 0; i < fItemCount; i++) { 384 if (fObjectList[i] == item) 385 return i; 386 } 387 return -1; 388} 389 390 391int32 392BList::CountItems() const 393{ 394 return fItemCount; 395} 396 397 398bool 399BList::IsEmpty() const 400{ 401 return fItemCount == 0; 402} 403 404 405// #pragma mark - Iterating over the list. 406 407/*! Iterate a function over the whole list. If the function outputs a true 408 value, then the process is terminated. 409*/ 410void 411BList::DoForEach(bool (*func)(void*)) 412{ 413 if (func == NULL) 414 return; 415 416 bool terminate = false; 417 int32 index = 0; 418 419 while ((!terminate) && (index < fItemCount)) { 420 terminate = func(fObjectList[index]); 421 index++; 422 } 423} 424 425 426/*! Iterate a function over the whole list. If the function outputs a true 427 value, then the process is terminated. This version takes an additional 428 argument which is passed to the function. 429*/ 430void 431BList::DoForEach(bool (*func)(void*, void*), void* arg) 432{ 433 if (func == NULL) 434 return; 435 436 bool terminate = false; int32 index = 0; 437 while ((!terminate) && (index < fItemCount)) { 438 terminate = func(fObjectList[index], arg); 439 index++; 440 } 441} 442 443 444#if (__GNUC__ == 2) 445 446// This is somewhat of a hack for backwards compatibility - 447// the reason these functions are defined this way rather than simply 448// being made private members is that if they are included, then whenever 449// gcc encounters someone calling AddList() with a non-const BList pointer, 450// it will try to use the private version and fail with a compiler error. 451 452// obsolete AddList(BList* list, int32 index) and AddList(BList* list) 453// AddList 454extern "C" bool 455AddList__5BListP5BListl(BList* self, BList* list, int32 index) 456{ 457 return self->AddList((const BList*)list, index); 458} 459 460// AddList 461extern "C" bool 462AddList__5BListP5BList(BList* self, BList* list) 463{ 464 return self->AddList((const BList*)list); 465} 466#endif 467 468// FBC 469void BList::_ReservedList1() {} 470void BList::_ReservedList2() {} 471 472 473//! Resizes fObjectList to be large enough to contain count items. 474bool 475BList::_ResizeArray(int32 count) 476{ 477 bool result = true; 478 // calculate the new physical size 479 // by doubling the existing size 480 // until we can hold at least count items 481 int32 newSize = fPhysicalSize > 0 ? fPhysicalSize : fBlockSize; 482 int32 targetSize = count; 483 if (targetSize <= 0) 484 targetSize = fBlockSize; 485 486 if (targetSize > fPhysicalSize) { 487 while (newSize < targetSize) 488 newSize <<= 1; 489 } else if (targetSize <= fResizeThreshold) 490 newSize = fResizeThreshold; 491 492 // resize if necessary 493 if (newSize != fPhysicalSize) { 494 void** newObjectList 495 = (void**)realloc(fObjectList, newSize * sizeof(void*)); 496 if (newObjectList) { 497 fObjectList = newObjectList; 498 fPhysicalSize = newSize; 499 // set our lower bound to either 1/4 500 //of the current physical size, or 0 501 fResizeThreshold = fPhysicalSize >> 2 >= fBlockSize 502 ? fPhysicalSize >> 2 : 0; 503 } else 504 result = false; 505 } 506 507 return result; 508} 509