1 /* 2 * COPYRIGHT: See COPYING in the top level directory 3 * PROJECT: ReactOS system libraries 4 * FILE: lib/rtl/rangelist.c 5 * PURPOSE: Range list implementation 6 * PROGRAMMERS: No programmer listed. 7 */ 8 9 /* INCLUDES *****************************************************************/ 10 11 #include <rtl.h> 12 13 #define NDEBUG 14 #include <debug.h> 15 16 /* TYPES ********************************************************************/ 17 18 typedef struct _RTL_RANGE_ENTRY 19 { 20 LIST_ENTRY Entry; 21 RTL_RANGE Range; 22 } RTL_RANGE_ENTRY, *PRTL_RANGE_ENTRY; 23 24 /* FUNCTIONS ***************************************************************/ 25 26 /********************************************************************** 27 * NAME EXPORTED 28 * RtlAddRange 29 * 30 * DESCRIPTION 31 * Adds a range to a range list. 32 * 33 * ARGUMENTS 34 * RangeList Range list. 35 * Start 36 * End 37 * Attributes 38 * Flags 39 * UserData 40 * Owner 41 * 42 * RETURN VALUE 43 * Status 44 * 45 * TODO: 46 * - Support shared ranges. 47 * 48 * @implemented 49 */ 50 NTSTATUS 51 NTAPI 52 RtlAddRange(IN OUT PRTL_RANGE_LIST RangeList, 53 IN ULONGLONG Start, 54 IN ULONGLONG End, 55 IN UCHAR Attributes, 56 IN ULONG Flags, 57 IN PVOID UserData OPTIONAL, 58 IN PVOID Owner OPTIONAL) 59 { 60 PRTL_RANGE_ENTRY RangeEntry; 61 //PRTL_RANGE_ENTRY Previous; 62 PRTL_RANGE_ENTRY Current; 63 PLIST_ENTRY Entry; 64 65 if (Start > End) 66 return STATUS_INVALID_PARAMETER; 67 68 /* Create new range entry */ 69 RangeEntry = RtlpAllocateMemory(sizeof(RTL_RANGE_ENTRY), 'elRR'); 70 if (RangeEntry == NULL) 71 return STATUS_INSUFFICIENT_RESOURCES; 72 73 /* Initialize range entry */ 74 RangeEntry->Range.Start = Start; 75 RangeEntry->Range.End = End; 76 RangeEntry->Range.Attributes = Attributes; 77 RangeEntry->Range.UserData = UserData; 78 RangeEntry->Range.Owner = Owner; 79 80 RangeEntry->Range.Flags = 0; 81 if (Flags & RTL_RANGE_LIST_ADD_SHARED) 82 RangeEntry->Range.Flags |= RTL_RANGE_SHARED; 83 84 /* Insert range entry */ 85 if (RangeList->Count == 0) 86 { 87 InsertTailList(&RangeList->ListHead, 88 &RangeEntry->Entry); 89 RangeList->Count++; 90 RangeList->Stamp++; 91 return STATUS_SUCCESS; 92 } 93 else 94 { 95 //Previous = NULL; 96 Entry = RangeList->ListHead.Flink; 97 while (Entry != &RangeList->ListHead) 98 { 99 Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry); 100 if (Current->Range.Start > RangeEntry->Range.End) 101 { 102 /* Insert before current */ 103 DPRINT("Insert before current\n"); 104 InsertTailList(&Current->Entry, 105 &RangeEntry->Entry); 106 107 RangeList->Count++; 108 RangeList->Stamp++; 109 return STATUS_SUCCESS; 110 } 111 112 //Previous = Current; 113 Entry = Entry->Flink; 114 } 115 116 DPRINT("Insert tail\n"); 117 InsertTailList(&RangeList->ListHead, 118 &RangeEntry->Entry); 119 RangeList->Count++; 120 RangeList->Stamp++; 121 return STATUS_SUCCESS; 122 } 123 124 RtlpFreeMemory(RangeEntry, 0); 125 126 return STATUS_UNSUCCESSFUL; 127 } 128 129 130 /********************************************************************** 131 * NAME EXPORTED 132 * RtlCopyRangeList 133 * 134 * DESCRIPTION 135 * Copy a range list. 136 * 137 * ARGUMENTS 138 * CopyRangeList Pointer to the destination range list. 139 * RangeList Pointer to the source range list. 140 * 141 * RETURN VALUE 142 * Status 143 * 144 * @implemented 145 */ 146 NTSTATUS 147 NTAPI 148 RtlCopyRangeList(OUT PRTL_RANGE_LIST CopyRangeList, 149 IN PRTL_RANGE_LIST RangeList) 150 { 151 PRTL_RANGE_ENTRY Current; 152 PRTL_RANGE_ENTRY NewEntry; 153 PLIST_ENTRY Entry; 154 155 CopyRangeList->Flags = RangeList->Flags; 156 157 Entry = RangeList->ListHead.Flink; 158 while (Entry != &RangeList->ListHead) 159 { 160 Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry); 161 162 NewEntry = RtlpAllocateMemory(sizeof(RTL_RANGE_ENTRY), 'elRR'); 163 if (NewEntry == NULL) 164 return STATUS_INSUFFICIENT_RESOURCES; 165 166 RtlCopyMemory(&NewEntry->Range, 167 &Current->Range, 168 sizeof(RTL_RANGE)); 169 170 InsertTailList(&CopyRangeList->ListHead, 171 &NewEntry->Entry); 172 173 CopyRangeList->Count++; 174 175 Entry = Entry->Flink; 176 } 177 178 CopyRangeList->Stamp++; 179 180 return STATUS_SUCCESS; 181 } 182 183 184 /********************************************************************** 185 * NAME EXPORTED 186 * RtlDeleteOwnersRanges 187 * 188 * DESCRIPTION 189 * Delete all ranges that belong to the given owner. 190 * 191 * ARGUMENTS 192 * RangeList Pointer to the range list. 193 * Owner User supplied value that identifies the owner 194 * of the ranges to be deleted. 195 * 196 * RETURN VALUE 197 * Status 198 * 199 * @implemented 200 */ 201 NTSTATUS 202 NTAPI 203 RtlDeleteOwnersRanges(IN OUT PRTL_RANGE_LIST RangeList, 204 IN PVOID Owner) 205 { 206 PRTL_RANGE_ENTRY Current; 207 PLIST_ENTRY Entry; 208 209 Entry = RangeList->ListHead.Flink; 210 while (Entry != &RangeList->ListHead) 211 { 212 Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry); 213 if (Current->Range.Owner == Owner) 214 { 215 RemoveEntryList (Entry); 216 RtlpFreeMemory(Current, 0); 217 218 RangeList->Count--; 219 RangeList->Stamp++; 220 } 221 222 Entry = Entry->Flink; 223 } 224 225 return STATUS_SUCCESS; 226 } 227 228 229 /********************************************************************** 230 * NAME EXPORTED 231 * RtlDeleteRange 232 * 233 * DESCRIPTION 234 * Deletes a given range. 235 * 236 * ARGUMENTS 237 * RangeList Pointer to the range list. 238 * Start Start of the range to be deleted. 239 * End End of the range to be deleted. 240 * Owner Owner of the ranges to be deleted. 241 * 242 * RETURN VALUE 243 * Status 244 * 245 * @implemented 246 */ 247 NTSTATUS 248 NTAPI 249 RtlDeleteRange(IN OUT PRTL_RANGE_LIST RangeList, 250 IN ULONGLONG Start, 251 IN ULONGLONG End, 252 IN PVOID Owner) 253 { 254 PRTL_RANGE_ENTRY Current; 255 PLIST_ENTRY Entry; 256 257 Entry = RangeList->ListHead.Flink; 258 while (Entry != &RangeList->ListHead) 259 { 260 Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry); 261 if (Current->Range.Start == Start && 262 Current->Range.End == End && 263 Current->Range.Owner == Owner) 264 { 265 RemoveEntryList(Entry); 266 267 RtlpFreeMemory(Current, 0); 268 269 RangeList->Count--; 270 RangeList->Stamp++; 271 return STATUS_SUCCESS; 272 } 273 274 Entry = Entry->Flink; 275 } 276 277 return STATUS_RANGE_NOT_FOUND; 278 } 279 280 281 /********************************************************************** 282 * NAME EXPORTED 283 * RtlFindRange 284 * 285 * DESCRIPTION 286 * Searches for an unused range. 287 * 288 * ARGUMENTS 289 * RangeList Pointer to the range list. 290 * Minimum 291 * Maximum 292 * Length 293 * Alignment 294 * Flags 295 * AttributeAvailableMask 296 * Context 297 * Callback 298 * Start 299 * 300 * RETURN VALUE 301 * Status 302 * 303 * TODO 304 * Support shared ranges and callback. 305 * 306 * @implemented 307 */ 308 NTSTATUS 309 NTAPI 310 RtlFindRange(IN PRTL_RANGE_LIST RangeList, 311 IN ULONGLONG Minimum, 312 IN ULONGLONG Maximum, 313 IN ULONG Length, 314 IN ULONG Alignment, 315 IN ULONG Flags, 316 IN UCHAR AttributeAvailableMask, 317 IN PVOID Context OPTIONAL, 318 IN PRTL_CONFLICT_RANGE_CALLBACK Callback OPTIONAL, 319 OUT PULONGLONG Start) 320 { 321 PRTL_RANGE_ENTRY CurrentEntry; 322 PRTL_RANGE_ENTRY NextEntry; 323 PLIST_ENTRY Entry; 324 ULONGLONG RangeMin; 325 ULONGLONG RangeMax; 326 327 if (Alignment == 0 || Length == 0) 328 { 329 return STATUS_INVALID_PARAMETER; 330 } 331 332 if (IsListEmpty(&RangeList->ListHead)) 333 { 334 *Start = ROUND_DOWN(Maximum - (Length - 1), Alignment); 335 return STATUS_SUCCESS; 336 } 337 338 NextEntry = NULL; 339 Entry = RangeList->ListHead.Blink; 340 while (Entry != &RangeList->ListHead) 341 { 342 CurrentEntry = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry); 343 344 RangeMax = NextEntry ? (NextEntry->Range.Start - 1) : Maximum; 345 if (RangeMax + (Length - 1) < Minimum) 346 { 347 return STATUS_RANGE_NOT_FOUND; 348 } 349 350 RangeMin = ROUND_DOWN(RangeMax - (Length - 1), Alignment); 351 if (RangeMin < Minimum || 352 (RangeMax - RangeMin) < (Length - 1)) 353 { 354 return STATUS_RANGE_NOT_FOUND; 355 } 356 357 DPRINT("RangeMax: %I64x\n", RangeMax); 358 DPRINT("RangeMin: %I64x\n", RangeMin); 359 360 if (RangeMin > CurrentEntry->Range.End) 361 { 362 *Start = RangeMin; 363 return STATUS_SUCCESS; 364 } 365 366 NextEntry = CurrentEntry; 367 Entry = Entry->Blink; 368 } 369 370 RangeMax = NextEntry ? (NextEntry->Range.Start - 1) : Maximum; 371 if (RangeMax + (Length - 1) < Minimum) 372 { 373 return STATUS_RANGE_NOT_FOUND; 374 } 375 376 RangeMin = ROUND_DOWN(RangeMax - (Length - 1), Alignment); 377 if (RangeMin < Minimum || 378 (RangeMax - RangeMin) < (Length - 1)) 379 { 380 return STATUS_RANGE_NOT_FOUND; 381 } 382 383 DPRINT("RangeMax: %I64x\n", RangeMax); 384 DPRINT("RangeMin: %I64x\n", RangeMin); 385 386 *Start = RangeMin; 387 388 return STATUS_SUCCESS; 389 } 390 391 392 /********************************************************************** 393 * NAME EXPORTED 394 * RtlFreeRangeList 395 * 396 * DESCRIPTION 397 * Deletes all ranges in a range list. 398 * 399 * ARGUMENTS 400 * RangeList Pointer to the range list. 401 * 402 * RETURN VALUE 403 * None 404 * 405 * @implemented 406 */ 407 VOID 408 NTAPI 409 RtlFreeRangeList(IN PRTL_RANGE_LIST RangeList) 410 { 411 PLIST_ENTRY Entry; 412 PRTL_RANGE_ENTRY Current; 413 414 while (!IsListEmpty(&RangeList->ListHead)) 415 { 416 Entry = RemoveHeadList(&RangeList->ListHead); 417 Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry); 418 419 DPRINT ("Range start: %I64u\n", Current->Range.Start); 420 DPRINT ("Range end: %I64u\n", Current->Range.End); 421 422 RtlpFreeMemory(Current, 0); 423 } 424 425 RangeList->Flags = 0; 426 RangeList->Count = 0; 427 } 428 429 430 /********************************************************************** 431 * NAME EXPORTED 432 * RtlGetFirstRange 433 * 434 * DESCRIPTION 435 * Retrieves the first range of a range list. 436 * 437 * ARGUMENTS 438 * RangeList Pointer to the range list. 439 * Iterator Pointer to a user supplied list state buffer. 440 * Range Pointer to the first range. 441 * 442 * RETURN VALUE 443 * Status 444 * 445 * @implemented 446 */ 447 NTSTATUS 448 NTAPI 449 RtlGetFirstRange(IN PRTL_RANGE_LIST RangeList, 450 OUT PRTL_RANGE_LIST_ITERATOR Iterator, 451 OUT PRTL_RANGE *Range) 452 { 453 Iterator->RangeListHead = &RangeList->ListHead; 454 Iterator->MergedHead = NULL; 455 Iterator->Stamp = RangeList->Stamp; 456 457 if (IsListEmpty(&RangeList->ListHead)) 458 { 459 Iterator->Current = NULL; 460 *Range = NULL; 461 return STATUS_NO_MORE_ENTRIES; 462 } 463 464 Iterator->Current = RangeList->ListHead.Flink; 465 *Range = &((PRTL_RANGE_ENTRY)Iterator->Current)->Range; 466 467 return STATUS_SUCCESS; 468 } 469 470 471 /********************************************************************** 472 * NAME EXPORTED 473 * RtlGetNextRange 474 * 475 * DESCRIPTION 476 * Retrieves the next (or previous) range of a range list. 477 * 478 * ARGUMENTS 479 * Iterator Pointer to a user supplied list state buffer. 480 * Range Pointer to the first range. 481 * MoveForwards TRUE, get next range 482 * FALSE, get previous range 483 * 484 * RETURN VALUE 485 * Status 486 * 487 * @implemented 488 */ 489 NTSTATUS 490 NTAPI 491 RtlGetNextRange(IN OUT PRTL_RANGE_LIST_ITERATOR Iterator, 492 OUT PRTL_RANGE *Range, 493 IN BOOLEAN MoveForwards) 494 { 495 PRTL_RANGE_LIST RangeList; 496 PLIST_ENTRY Next; 497 498 RangeList = CONTAINING_RECORD(Iterator->RangeListHead, RTL_RANGE_LIST, ListHead); 499 if (Iterator->Stamp != RangeList->Stamp) 500 return STATUS_INVALID_PARAMETER; 501 502 if (MoveForwards) 503 { 504 Next = ((PRTL_RANGE_ENTRY)Iterator->Current)->Entry.Flink; 505 } 506 else 507 { 508 Next = ((PRTL_RANGE_ENTRY)Iterator->Current)->Entry.Blink; 509 } 510 511 if (Next == Iterator->RangeListHead) 512 return STATUS_NO_MORE_ENTRIES; 513 514 Iterator->Current = Next; 515 *Range = &((PRTL_RANGE_ENTRY)Next)->Range; 516 517 return STATUS_SUCCESS; 518 } 519 520 521 /********************************************************************** 522 * NAME EXPORTED 523 * RtlInitializeRangeList 524 * 525 * DESCRIPTION 526 * Initializes a range list. 527 * 528 * ARGUMENTS 529 * RangeList Pointer to a user supplied range list. 530 * 531 * RETURN VALUE 532 * None 533 * 534 * @implemented 535 */ 536 VOID 537 NTAPI 538 RtlInitializeRangeList(IN OUT PRTL_RANGE_LIST RangeList) 539 { 540 InitializeListHead(&RangeList->ListHead); 541 RangeList->Flags = 0; 542 RangeList->Count = 0; 543 RangeList->Stamp = 0; 544 } 545 546 547 /********************************************************************** 548 * NAME EXPORTED 549 * RtlInvertRangeList 550 * 551 * DESCRIPTION 552 * Inverts a range list. 553 * 554 * ARGUMENTS 555 * InvertedRangeList Inverted range list. 556 * RangeList Range list. 557 * 558 * RETURN VALUE 559 * Status 560 * 561 * @implemented 562 */ 563 NTSTATUS 564 NTAPI 565 RtlInvertRangeList(OUT PRTL_RANGE_LIST InvertedRangeList, 566 IN PRTL_RANGE_LIST RangeList) 567 { 568 PRTL_RANGE_ENTRY Previous; 569 PRTL_RANGE_ENTRY Current; 570 PLIST_ENTRY Entry; 571 NTSTATUS Status; 572 573 /* Add leading and intermediate ranges */ 574 Previous = NULL; 575 Entry = RangeList->ListHead.Flink; 576 while (Entry != &RangeList->ListHead) 577 { 578 Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry); 579 580 if (Previous == NULL) 581 { 582 if (Current->Range.Start != (ULONGLONG)0) 583 { 584 Status = RtlAddRange(InvertedRangeList, 585 (ULONGLONG)0, 586 Current->Range.Start - 1, 587 0, 588 0, 589 NULL, 590 NULL); 591 if (!NT_SUCCESS(Status)) 592 return Status; 593 } 594 } 595 else 596 { 597 if (Previous->Range.End + 1 != Current->Range.Start) 598 { 599 Status = RtlAddRange(InvertedRangeList, 600 Previous->Range.End + 1, 601 Current->Range.Start - 1, 602 0, 603 0, 604 NULL, 605 NULL); 606 if (!NT_SUCCESS(Status)) 607 return Status; 608 } 609 } 610 611 Previous = Current; 612 Entry = Entry->Flink; 613 } 614 615 /* Check if the list was empty */ 616 if (Previous == NULL) 617 { 618 /* We're done */ 619 return STATUS_SUCCESS; 620 } 621 622 /* Add trailing range */ 623 if (Previous->Range.End + 1 != (ULONGLONG)-1) 624 { 625 Status = RtlAddRange(InvertedRangeList, 626 Previous->Range.End + 1, 627 (ULONGLONG)-1, 628 0, 629 0, 630 NULL, 631 NULL); 632 if (!NT_SUCCESS(Status)) 633 return Status; 634 } 635 636 return STATUS_SUCCESS; 637 } 638 639 640 /********************************************************************** 641 * NAME EXPORTED 642 * RtlIsRangeAvailable 643 * 644 * DESCRIPTION 645 * Checks whether a range is available or not. 646 * 647 * ARGUMENTS 648 * RangeList Pointer to the range list. 649 * Start 650 * End 651 * Flags 652 * AttributeAvailableMask 653 * Context 654 * Callback 655 * Available 656 * 657 * RETURN VALUE 658 * Status 659 * 660 * TODO: 661 * - honor Flags and AttributeAvailableMask. 662 * 663 * @implemented 664 */ 665 NTSTATUS 666 NTAPI 667 RtlIsRangeAvailable(IN PRTL_RANGE_LIST RangeList, 668 IN ULONGLONG Start, 669 IN ULONGLONG End, 670 IN ULONG Flags, 671 IN UCHAR AttributeAvailableMask, 672 IN PVOID Context OPTIONAL, 673 IN PRTL_CONFLICT_RANGE_CALLBACK Callback OPTIONAL, 674 OUT PBOOLEAN Available) 675 { 676 PRTL_RANGE_ENTRY Current; 677 PLIST_ENTRY Entry; 678 679 *Available = TRUE; 680 681 Entry = RangeList->ListHead.Flink; 682 while (Entry != &RangeList->ListHead) 683 { 684 Current = CONTAINING_RECORD (Entry, RTL_RANGE_ENTRY, Entry); 685 686 if (!((Current->Range.Start >= End && Current->Range.End > End) || 687 (Current->Range.Start <= Start && Current->Range.End < Start && 688 (!(Flags & RTL_RANGE_SHARED) || 689 !(Current->Range.Flags & RTL_RANGE_SHARED))))) 690 { 691 if (Callback != NULL) 692 { 693 *Available = Callback(Context, 694 &Current->Range); 695 } 696 else 697 { 698 *Available = FALSE; 699 } 700 } 701 702 Entry = Entry->Flink; 703 } 704 705 return STATUS_SUCCESS; 706 } 707 708 709 /********************************************************************** 710 * NAME EXPORTED 711 * RtlMergeRangeList 712 * 713 * DESCRIPTION 714 * Merges two range lists. 715 * 716 * ARGUMENTS 717 * MergedRangeList Resulting range list. 718 * RangeList1 First range list. 719 * RangeList2 Second range list 720 * Flags 721 * 722 * RETURN VALUE 723 * Status 724 * 725 * @implemented 726 */ 727 NTSTATUS 728 NTAPI 729 RtlMergeRangeLists(OUT PRTL_RANGE_LIST MergedRangeList, 730 IN PRTL_RANGE_LIST RangeList1, 731 IN PRTL_RANGE_LIST RangeList2, 732 IN ULONG Flags) 733 { 734 RTL_RANGE_LIST_ITERATOR Iterator; 735 PRTL_RANGE Range; 736 NTSTATUS Status; 737 738 /* Copy range list 1 to the merged range list */ 739 Status = RtlCopyRangeList(MergedRangeList, 740 RangeList1); 741 if (!NT_SUCCESS(Status)) 742 return Status; 743 744 /* Add range list 2 entries to the merged range list */ 745 Status = RtlGetFirstRange(RangeList2, 746 &Iterator, 747 &Range); 748 if (!NT_SUCCESS(Status)) 749 return (Status == STATUS_NO_MORE_ENTRIES) ? STATUS_SUCCESS : Status; 750 751 while (TRUE) 752 { 753 Status = RtlAddRange(MergedRangeList, 754 Range->Start, 755 Range->End, 756 Range->Attributes, 757 Range->Flags | Flags, 758 Range->UserData, 759 Range->Owner); 760 if (!NT_SUCCESS(Status)) 761 break; 762 763 Status = RtlGetNextRange(&Iterator, 764 &Range, 765 TRUE); 766 if (!NT_SUCCESS(Status)) 767 break; 768 } 769 770 return (Status == STATUS_NO_MORE_ENTRIES) ? STATUS_SUCCESS : Status; 771 } 772 773 /* EOF */ 774