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