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 (Iterator->Current == NULL) 503 { 504 *Range = NULL; 505 return STATUS_NO_MORE_ENTRIES; 506 } 507 508 if (MoveForwards) 509 { 510 Next = ((PRTL_RANGE_ENTRY)Iterator->Current)->Entry.Flink; 511 } 512 else 513 { 514 Next = ((PRTL_RANGE_ENTRY)Iterator->Current)->Entry.Blink; 515 } 516 517 if (Next == Iterator->RangeListHead) 518 { 519 Iterator->Current = NULL; 520 *Range = NULL; 521 return STATUS_NO_MORE_ENTRIES; 522 } 523 524 Iterator->Current = Next; 525 *Range = &((PRTL_RANGE_ENTRY)Next)->Range; 526 527 return STATUS_SUCCESS; 528 } 529 530 531 /********************************************************************** 532 * NAME EXPORTED 533 * RtlInitializeRangeList 534 * 535 * DESCRIPTION 536 * Initializes a range list. 537 * 538 * ARGUMENTS 539 * RangeList Pointer to a user supplied range list. 540 * 541 * RETURN VALUE 542 * None 543 * 544 * @implemented 545 */ 546 VOID 547 NTAPI 548 RtlInitializeRangeList(IN OUT PRTL_RANGE_LIST RangeList) 549 { 550 InitializeListHead(&RangeList->ListHead); 551 RangeList->Flags = 0; 552 RangeList->Count = 0; 553 RangeList->Stamp = 0; 554 } 555 556 557 /********************************************************************** 558 * NAME EXPORTED 559 * RtlInvertRangeList 560 * 561 * DESCRIPTION 562 * Inverts a range list. 563 * 564 * ARGUMENTS 565 * InvertedRangeList Inverted range list. 566 * RangeList Range list. 567 * 568 * RETURN VALUE 569 * Status 570 * 571 * @implemented 572 */ 573 NTSTATUS 574 NTAPI 575 RtlInvertRangeList(OUT PRTL_RANGE_LIST InvertedRangeList, 576 IN PRTL_RANGE_LIST RangeList) 577 { 578 PRTL_RANGE_ENTRY Previous; 579 PRTL_RANGE_ENTRY Current; 580 PLIST_ENTRY Entry; 581 NTSTATUS Status; 582 583 /* Add leading and intermediate ranges */ 584 Previous = NULL; 585 Entry = RangeList->ListHead.Flink; 586 while (Entry != &RangeList->ListHead) 587 { 588 Current = CONTAINING_RECORD(Entry, RTL_RANGE_ENTRY, Entry); 589 590 if (Previous == NULL) 591 { 592 if (Current->Range.Start != (ULONGLONG)0) 593 { 594 Status = RtlAddRange(InvertedRangeList, 595 (ULONGLONG)0, 596 Current->Range.Start - 1, 597 0, 598 0, 599 NULL, 600 NULL); 601 if (!NT_SUCCESS(Status)) 602 return Status; 603 } 604 } 605 else 606 { 607 if (Previous->Range.End + 1 != Current->Range.Start) 608 { 609 Status = RtlAddRange(InvertedRangeList, 610 Previous->Range.End + 1, 611 Current->Range.Start - 1, 612 0, 613 0, 614 NULL, 615 NULL); 616 if (!NT_SUCCESS(Status)) 617 return Status; 618 } 619 } 620 621 Previous = Current; 622 Entry = Entry->Flink; 623 } 624 625 /* Check if the list was empty */ 626 if (Previous == NULL) 627 { 628 /* We're done */ 629 return STATUS_SUCCESS; 630 } 631 632 /* Add trailing range */ 633 if (Previous->Range.End + 1 != (ULONGLONG)-1) 634 { 635 Status = RtlAddRange(InvertedRangeList, 636 Previous->Range.End + 1, 637 (ULONGLONG)-1, 638 0, 639 0, 640 NULL, 641 NULL); 642 if (!NT_SUCCESS(Status)) 643 return Status; 644 } 645 646 return STATUS_SUCCESS; 647 } 648 649 650 /********************************************************************** 651 * NAME EXPORTED 652 * RtlIsRangeAvailable 653 * 654 * DESCRIPTION 655 * Checks whether a range is available or not. 656 * 657 * ARGUMENTS 658 * RangeList Pointer to the range list. 659 * Start 660 * End 661 * Flags 662 * AttributeAvailableMask 663 * Context 664 * Callback 665 * Available 666 * 667 * RETURN VALUE 668 * Status 669 * 670 * TODO: 671 * - honor Flags and AttributeAvailableMask. 672 * 673 * @implemented 674 */ 675 NTSTATUS 676 NTAPI 677 RtlIsRangeAvailable(IN PRTL_RANGE_LIST RangeList, 678 IN ULONGLONG Start, 679 IN ULONGLONG End, 680 IN ULONG Flags, 681 IN UCHAR AttributeAvailableMask, 682 IN PVOID Context OPTIONAL, 683 IN PRTL_CONFLICT_RANGE_CALLBACK Callback OPTIONAL, 684 OUT PBOOLEAN Available) 685 { 686 PRTL_RANGE_ENTRY Current; 687 PLIST_ENTRY Entry; 688 689 *Available = TRUE; 690 691 Entry = RangeList->ListHead.Flink; 692 while (Entry != &RangeList->ListHead) 693 { 694 Current = CONTAINING_RECORD (Entry, RTL_RANGE_ENTRY, Entry); 695 696 if (!((Current->Range.Start >= End && Current->Range.End > End) || 697 (Current->Range.Start <= Start && Current->Range.End < Start && 698 (!(Flags & RTL_RANGE_SHARED) || 699 !(Current->Range.Flags & RTL_RANGE_SHARED))))) 700 { 701 if (Callback != NULL) 702 { 703 *Available = Callback(Context, 704 &Current->Range); 705 } 706 else 707 { 708 *Available = FALSE; 709 } 710 } 711 712 Entry = Entry->Flink; 713 } 714 715 return STATUS_SUCCESS; 716 } 717 718 719 /********************************************************************** 720 * NAME EXPORTED 721 * RtlMergeRangeList 722 * 723 * DESCRIPTION 724 * Merges two range lists. 725 * 726 * ARGUMENTS 727 * MergedRangeList Resulting range list. 728 * RangeList1 First range list. 729 * RangeList2 Second range list 730 * Flags 731 * 732 * RETURN VALUE 733 * Status 734 * 735 * @implemented 736 */ 737 NTSTATUS 738 NTAPI 739 RtlMergeRangeLists(OUT PRTL_RANGE_LIST MergedRangeList, 740 IN PRTL_RANGE_LIST RangeList1, 741 IN PRTL_RANGE_LIST RangeList2, 742 IN ULONG Flags) 743 { 744 RTL_RANGE_LIST_ITERATOR Iterator; 745 PRTL_RANGE Range; 746 NTSTATUS Status; 747 748 /* Copy range list 1 to the merged range list */ 749 Status = RtlCopyRangeList(MergedRangeList, 750 RangeList1); 751 if (!NT_SUCCESS(Status)) 752 return Status; 753 754 /* Add range list 2 entries to the merged range list */ 755 Status = RtlGetFirstRange(RangeList2, 756 &Iterator, 757 &Range); 758 if (!NT_SUCCESS(Status)) 759 return (Status == STATUS_NO_MORE_ENTRIES) ? STATUS_SUCCESS : Status; 760 761 while (TRUE) 762 { 763 Status = RtlAddRange(MergedRangeList, 764 Range->Start, 765 Range->End, 766 Range->Attributes, 767 Range->Flags | Flags, 768 Range->UserData, 769 Range->Owner); 770 if (!NT_SUCCESS(Status)) 771 break; 772 773 Status = RtlGetNextRange(&Iterator, 774 &Range, 775 TRUE); 776 if (!NT_SUCCESS(Status)) 777 break; 778 } 779 780 return (Status == STATUS_NO_MORE_ENTRIES) ? STATUS_SUCCESS : Status; 781 } 782 783 /* EOF */ 784