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 if (_ResizeArray(list.fItemCount)) { 87 fItemCount = list.fItemCount; 88 memcpy(fObjectList, list.fObjectList, fItemCount * sizeof(void*)); 89 } 90 91 return *this; 92 } 93 94 95 // AddItem 96 bool 97 BList::AddItem(void *item, int32 index) 98 { 99 if (index < 0 || index > fItemCount) 100 return false; 101 102 bool result = true; 103 104 if (fItemCount + 1 > fPhysicalSize) 105 result = _ResizeArray(fItemCount + 1); 106 if (result) { 107 ++fItemCount; 108 move_items(fObjectList + index, 1, fItemCount - index - 1); 109 fObjectList[index] = item; 110 } 111 return result; 112 } 113 114 115 // AddItem 116 bool 117 BList::AddItem(void *item) 118 { 119 bool result = true; 120 if (fPhysicalSize > fItemCount) { 121 fObjectList[fItemCount] = item; 122 ++fItemCount; 123 } else { 124 if ((result = _ResizeArray(fItemCount + 1))) { 125 fObjectList[fItemCount] = item; 126 ++fItemCount; 127 } 128 } 129 return result; 130 } 131 132 133 // AddList 134 bool 135 BList::AddList(const BList *list, int32 index) 136 { 137 bool result = (list && index >= 0 && index <= fItemCount); 138 if (result && list->fItemCount > 0) { 139 int32 count = list->fItemCount; 140 if (fItemCount + count > fPhysicalSize) 141 result = _ResizeArray(fItemCount + count); 142 if (result) { 143 fItemCount += count; 144 move_items(fObjectList + index, count, fItemCount - index - count); 145 memcpy(fObjectList + index, list->fObjectList, 146 list->fItemCount * sizeof(void *)); 147 } 148 } 149 return result; 150 } 151 152 153 // AddList 154 bool 155 BList::AddList(const BList *list) 156 { 157 bool result = (list != NULL); 158 if (result && list->fItemCount > 0) { 159 int32 index = fItemCount; 160 int32 count = list->fItemCount; 161 if (fItemCount + count > fPhysicalSize) 162 result = _ResizeArray(fItemCount + count); 163 if (result) { 164 fItemCount += count; 165 memcpy(fObjectList + index, list->fObjectList, 166 list->fItemCount * sizeof(void *)); 167 } 168 } 169 return result; 170 } 171 172 173 // RemoveItem 174 bool 175 BList::RemoveItem(void *item) 176 { 177 int32 index = IndexOf(item); 178 bool result = (index >= 0); 179 if (result) 180 RemoveItem(index); 181 return result; 182 } 183 184 185 // RemoveItem 186 void * 187 BList::RemoveItem(int32 index) 188 { 189 void *item = NULL; 190 if (index >= 0 && index < fItemCount) { 191 item = fObjectList[index]; 192 move_items(fObjectList + index + 1, -1, fItemCount - index - 1); 193 --fItemCount; 194 if (fItemCount <= fResizeThreshold) 195 _ResizeArray(fItemCount); 196 } 197 return item; 198 } 199 200 201 // RemoveItems 202 bool 203 BList::RemoveItems(int32 index, int32 count) 204 { 205 bool result = (index >= 0 && index <= fItemCount); 206 if (result) { 207 if (index + count > fItemCount) 208 count = fItemCount - index; 209 if (count > 0) { 210 move_items(fObjectList + index + count, -count, 211 fItemCount - index - count); 212 fItemCount -= count; 213 if (fItemCount <= fResizeThreshold) 214 _ResizeArray(fItemCount); 215 } else 216 result = false; 217 } 218 return result; 219 } 220 221 222 //ReplaceItem 223 bool 224 BList::ReplaceItem(int32 index, void *newItem) 225 { 226 bool result = false; 227 228 if (index >= 0 && index < fItemCount) { 229 fObjectList[index] = newItem; 230 result = true; 231 } 232 return result; 233 } 234 235 236 // MakeEmpty 237 void 238 BList::MakeEmpty() 239 { 240 fItemCount = 0; 241 _ResizeArray(0); 242 } 243 244 245 /* Reordering items. */ 246 // SortItems 247 void 248 BList::SortItems(int (*compareFunc)(const void *, const void *)) 249 { 250 if (compareFunc) 251 qsort(fObjectList, fItemCount, sizeof(void *), compareFunc); 252 } 253 254 255 //SwapItems 256 bool 257 BList::SwapItems(int32 indexA, int32 indexB) 258 { 259 bool result = false; 260 261 if (indexA >= 0 && indexA < fItemCount 262 && indexB >= 0 && indexB < fItemCount) { 263 264 void *tmpItem = fObjectList[indexA]; 265 fObjectList[indexA] = fObjectList[indexB]; 266 fObjectList[indexB] = tmpItem; 267 268 result = true; 269 } 270 271 return result; 272 } 273 274 275 // MoveItem 276 // This moves a list item from posititon a to position b, moving the appropriate 277 // block of list elements to make up for the move. For example, in the array: 278 // A B C D E F G H I J 279 // Moveing 1(B)->6(G) would result in this: 280 // A C D E F G B H I J 281 bool 282 BList::MoveItem(int32 fromIndex, int32 toIndex) 283 { 284 if ((fromIndex >= fItemCount) || (toIndex >= fItemCount) || (fromIndex < 0) 285 || (toIndex < 0)) 286 return false; 287 288 void * tmpMover = fObjectList[fromIndex]; 289 if (fromIndex < toIndex) { 290 memmove(fObjectList + fromIndex, fObjectList + fromIndex + 1, 291 (toIndex - fromIndex) * sizeof(void *)); 292 } else if (fromIndex > toIndex) { 293 memmove(fObjectList + toIndex + 1, fObjectList + toIndex, 294 (fromIndex - toIndex) * sizeof(void *)); 295 }; 296 fObjectList[toIndex] = tmpMover; 297 298 return true; 299 } 300 301 302 /* Retrieving items. */ 303 // ItemAt 304 void * 305 BList::ItemAt(int32 index) const 306 { 307 void *item = NULL; 308 if (index >= 0 && index < fItemCount) 309 item = fObjectList[index]; 310 return item; 311 } 312 313 314 // FirstItem 315 void * 316 BList::FirstItem() const 317 { 318 void *item = NULL; 319 if (fItemCount > 0) 320 item = fObjectList[0]; 321 return item; 322 } 323 324 325 // ItemAtFast 326 void * 327 BList::ItemAtFast(int32 index) const 328 { 329 return fObjectList[index]; 330 } 331 332 333 // Items 334 void * 335 BList::Items() const 336 { 337 return fObjectList; 338 } 339 340 341 // LastItem 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 /* Querying the list. */ 353 // HasItem 354 bool 355 BList::HasItem(void *item) const 356 { 357 return (IndexOf(item) >= 0); 358 } 359 360 361 // IndexOf 362 int32 363 BList::IndexOf(void *item) const 364 { 365 for (int32 i = 0; i < fItemCount; i++) { 366 if (fObjectList[i] == item) 367 return i; 368 } 369 return -1; 370 } 371 372 373 // CountItems 374 int32 375 BList::CountItems() const 376 { 377 return fItemCount; 378 } 379 380 381 // IsEmpty 382 bool 383 BList::IsEmpty() const 384 { 385 return (fItemCount == 0); 386 } 387 388 389 /* Iterating over the list. */ 390 //iterate a function over the whole list. If the function outputs a true 391 //value, then the process is terminated. 392 393 void 394 BList::DoForEach(bool (*func)(void *)) 395 { 396 bool terminate = false; int32 index = 0; //set terminate condition variables to go. 397 if (func != NULL) 398 { 399 while ((!terminate) && (index < fItemCount)) //check terminate condition. 400 { 401 terminate = func(fObjectList[index]); //reset immediate terminator 402 index++; //advance along the list. 403 }; 404 } 405 406 } 407 408 409 //same as above, except this function takes an argument. 410 void 411 BList::DoForEach(bool (*func)(void *, void*), void * arg) 412 { 413 bool terminate = false; int32 index = 0; 414 if (func != NULL) 415 { 416 while ((!terminate) && (index < fItemCount)) 417 { 418 terminate = func(fObjectList[index], arg); 419 index++; 420 }; 421 } 422 } 423 424 #if (__GNUC__ == 2) 425 426 // This is somewhat of a hack for backwards compatibility - 427 // the reason these functions are defined this way rather than simply 428 // being made private members is that if they are included, then whenever 429 // gcc encounters someone calling AddList() with a non-const BList pointer, 430 // it will try to use the private version and fail with a compiler error. 431 432 // obsolete AddList(BList* list, int32 index) and AddList(BList* list) 433 // AddList 434 extern "C" bool 435 AddList__5BListP5BListl(BList* self, BList* list, int32 index) 436 { 437 return self->AddList((const BList*)list, index); 438 } 439 440 // AddList 441 extern "C" bool 442 AddList__5BListP5BList(BList* self, BList* list) 443 { 444 return self->AddList((const BList *)list); 445 } 446 #endif 447 448 // FBC 449 void BList::_ReservedList1() {} 450 void BList::_ReservedList2() {} 451 452 // Resize 453 // 454 // Resizes fObjectList to be large enough to contain count items. 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