Change Details

Make the map->header sentinel a part of the initial vm_map binary search tree. Change the order of search tree comparisons so that the end field is tested before the start field, so that the map->header sentinel will always be the leftmost member of the search tree. Change the method of handling search failure in vm_map_entry_splay so that the new tree root after failure always becomes the largest map entry less than the address sought; such an entry must exist because the sentinel is less than any address sought. This makes the result of splaying more regular, and eliminates the need for several cases where the address was smaller than any map entry, or was in a range represented by the left subtree of the new root. So, several of these cases have been removed from consideration, since they can no longer happen.

Make the map->header sentinel a part of the initial vm_map binary search tree. Change the order of search tree comparisons so that the end field is tested before the start field, so that the map->header sentinel will always be the leftmost member of the search tree. Change the method of handling search failure in vm_map_entry_splay so that the new tree root after failure always becomes the largest map entry less than the address sought; such an entry must exist because the sentinel is less than any address sought. Have vm_map_entry_splay handle tree insertions and deletions. Have vm_map_entry_splay work on maps, rather than map entries. Change the splay code to eliminate duplicated comparisons.

Make the map->header sentinel a part of the initial vm_map binary search tree. Change the order of search tree comparisons so that the end field is tested before the start field, so that the map->header sentinel will always be the leftmost member of the search tree. Change the method of handling search failure in vm_map_entry_splay so that the new tree root after failure always becomes the largest map entry less than the address sought; such an entry must exist because the sentinel is less than any address sought. This makes the result of splaying more regular, and eliminates the need for several cases where the address was smaller than any map entry Have vm_map_entry_splay handle tree insertions and deletions. Have vm_map_entry_splay work on maps, or was in a range represented by the left subtree of the new rootrather than map entries. So, several of these cases have been removed from consideration, since they can no longer happen.Change the splay code to eliminate duplicated comparisons.