* Remove the specified index from the trie, and return the value stored at * that index. If the index is not present, return NULL. */
| 758 | * that index. If the index is not present, return NULL. |
| 759 | */ |
| 760 | vm_page_t |
| 761 | vm_radix_remove(struct vm_radix *rtree, vm_pindex_t index) |
| 762 | { |
| 763 | struct vm_radix_node *rnode, *parent, *tmp; |
| 764 | vm_page_t m; |
| 765 | int i, slot; |
| 766 | |
| 767 | rnode = vm_radix_root_load(rtree, LOCKED); |
| 768 | if (vm_radix_isleaf(rnode)) { |
| 769 | m = vm_radix_topage(rnode); |
| 770 | if (m->pindex != index) |
| 771 | return (NULL); |
| 772 | vm_radix_root_store(rtree, NULL, LOCKED); |
| 773 | return (m); |
| 774 | } |
| 775 | parent = NULL; |
| 776 | for (;;) { |
| 777 | if (rnode == NULL) |
| 778 | return (NULL); |
| 779 | slot = vm_radix_slot(index, rnode->rn_clev); |
| 780 | tmp = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); |
| 781 | if (vm_radix_isleaf(tmp)) { |
| 782 | m = vm_radix_topage(tmp); |
| 783 | if (m->pindex != index) |
| 784 | return (NULL); |
| 785 | vm_radix_node_store(&rnode->rn_child[slot], NULL, LOCKED); |
| 786 | rnode->rn_count--; |
| 787 | if (rnode->rn_count > 1) |
| 788 | return (m); |
| 789 | for (i = 0; i < VM_RADIX_COUNT; i++) |
| 790 | if (vm_radix_node_load(&rnode->rn_child[i], |
| 791 | LOCKED) != NULL) |
| 792 | break; |
| 793 | KASSERT(i != VM_RADIX_COUNT, |
| 794 | ("%s: invalid node configuration", __func__)); |
| 795 | tmp = vm_radix_node_load(&rnode->rn_child[i], LOCKED); |
| 796 | if (parent == NULL) |
| 797 | vm_radix_root_store(rtree, tmp, LOCKED); |
| 798 | else { |
| 799 | slot = vm_radix_slot(index, parent->rn_clev); |
| 800 | KASSERT(vm_radix_node_load( |
| 801 | &parent->rn_child[slot], LOCKED) == rnode, |
| 802 | ("%s: invalid child value", __func__)); |
| 803 | vm_radix_node_store(&parent->rn_child[slot], |
| 804 | tmp, LOCKED); |
| 805 | } |
| 806 | /* |
| 807 | * The child is still valid and we can not zero the |
| 808 | * pointer until all smr references are gone. |
| 809 | */ |
| 810 | rnode->rn_count--; |
| 811 | vm_radix_node_put(rnode, i); |
| 812 | return (m); |
| 813 | } |
| 814 | parent = rnode; |
| 815 | rnode = tmp; |
| 816 | } |
| 817 | } |
no test coverage detected