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 24 static inline void 25 move_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 32 BList::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 46 BList::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 57 BList::~BList() 58 { 59 free(fObjectList); 60 } 61 62 63 BList& 64 BList::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 78 bool 79 BList::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 96 bool 97 BList::operator!=(const BList& other) const 98 { 99 return !(*this == other); 100 } 101 102 103 bool 104 BList::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 122 bool 123 BList::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 139 bool 140 BList::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 160 bool 161 BList::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 181 bool 182 BList::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 192 void* 193 BList::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 207 bool 208 BList::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 227 bool 228 BList::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 240 void 241 BList::MakeEmpty() 242 { 243 fItemCount = 0; 244 _ResizeArray(0); 245 } 246 247 248 // #pragma mark - Reordering items. 249 250 251 void 252 BList::SortItems(int (*compareFunc)(const void*, const void*)) 253 { 254 if (compareFunc) 255 qsort(fObjectList, fItemCount, sizeof(void*), compareFunc); 256 } 257 258 259 bool 260 BList::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 */ 285 bool 286 BList::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 308 void* 309 BList::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 318 void* 319 BList::FirstItem() const 320 { 321 void* item = NULL; 322 if (fItemCount > 0) 323 item = fObjectList[0]; 324 return item; 325 } 326 327 328 void* 329 BList::ItemAtFast(int32 index) const 330 { 331 return fObjectList[index]; 332 } 333 334 335 void* 336 BList::Items() const 337 { 338 return fObjectList; 339 } 340 341 342 void* 343 BList::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 355 bool 356 BList::HasItem(void* item) const 357 { 358 return (IndexOf(item) >= 0); 359 } 360 361 362 bool 363 BList::HasItem(const void* item) const 364 { 365 return (IndexOf(item) >= 0); 366 } 367 368 369 int32 370 BList::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 380 int32 381 BList::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 391 int32 392 BList::CountItems() const 393 { 394 return fItemCount; 395 } 396 397 398 bool 399 BList::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 */ 410 void 411 BList::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 */ 430 void 431 BList::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 454 extern "C" bool 455 AddList__5BListP5BListl(BList* self, BList* list, int32 index) 456 { 457 return self->AddList((const BList*)list, index); 458 } 459 460 // AddList 461 extern "C" bool 462 AddList__5BListP5BList(BList* self, BList* list) 463 { 464 return self->AddList((const BList*)list); 465 } 466 #endif 467 468 // FBC 469 void BList::_ReservedList1() {} 470 void BList::_ReservedList2() {} 471 472 473 //! Resizes fObjectList to be large enough to contain count items. 474 bool 475 BList::_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