Changeset View
Standalone View
sys/vm/vm_map.c
Context not available. | |||||
{ | { | ||||
vm_map_entry_t llist, rlist; | vm_map_entry_t llist, rlist; | ||||
vm_map_entry_t ltree, rtree; | vm_map_entry_t ltree, rtree; | ||||
vm_map_entry_t y; | vm_map_entry_t y, z; | ||||
/* Special case of empty tree. */ | /* Special case of empty tree. */ | ||||
if (root == NULL) | if (root == NULL) | ||||
Context not available. | |||||
*/ | */ | ||||
llist = NULL; | llist = NULL; | ||||
rlist = NULL; | rlist = NULL; | ||||
for (;;) { | for (;; root = z) { | ||||
/* root is never NULL in here. */ | /* root is never NULL in here. */ | ||||
if (addr < root->start) { | if (addr < root->start) { | ||||
y = root->left; | y = root->left; | ||||
if (y == NULL) | if (y == NULL) | ||||
break; | break; | ||||
if (addr < y->start && y->left != NULL) { | if (addr < y->start) { | ||||
/* Rotate right and put y on rlist. */ | z = y->left; | ||||
root->left = y->right; | if (z != NULL) { | ||||
y->right = root; | /* Put y on rlist. */ | ||||
vm_map_entry_set_max_free(root); | y->left = rlist; | ||||
root = y->left; | rlist = y; | ||||
alc: This can also be a redundant comparison if addr < y->start but y->left == NULL. | |||||
Not Done Inline ActionsThis would get rid of your redundant comparison. Do you prefer it? if (addr < y->start) { if (y->left != NULL) { /* Rotate right and put y on rlist. */ root->left = y->right; y->right = root; vm_map_entry_set_max_free(root); root = y->left; y->left = rlist; rlist = y; continue; } } else if (addr >= y->end) { if (y->right == NULL) break; /* Put root on rlist, y on llist. */ root->left = rlist; rlist = root; root = y->right; y->right = llist; llist = y; continue; } /* Put root on rlist. */ root->left = rlist; rlist = root; root = y; break; dougm: This would get rid of your redundant comparison. Do you prefer it?
```
if (addr < y… | |||||
y->left = rlist; | /* Rotate right. */ | ||||
rlist = y; | root->left = y->right; | ||||
} else { | y->right = root; | ||||
/* Put root on rlist. */ | vm_map_entry_set_max_free(root); | ||||
dougmAuthorUnsubmitted Not Done Inline ActionsThis case, and the symmetric 'rotate left' case below, are the only cases in this splay code in which a node is modified, but not put on either rlist or llist. We know that max_free is calculated for those nodes in the second pass up the tree. Do we need to recompute max_free for this case, for 'root'? Yes. Suppose that at the top of the loop 'd' was root in a tree like this: We know that no changes are happening to the subtrees C and E the rest of the splay, as the next root value is b and further changes happen in only that subtree. dougm: This case, and the symmetric 'rotate left' case below, are the only cases in this splay code in… | |||||
dougmAuthorUnsubmitted Not Done Inline ActionsChange 'b' in the last line to 'a'. dougm: Change 'b' in the last line to 'a'. | |||||
root->left = rlist; | continue; | ||||
rlist = root; | } | ||||
root = y; | } else if (addr >= y->end) { | ||||
z = y->right; | |||||
if (z != NULL) { | |||||
/* Put y on llist. */ | |||||
y->right = llist; | |||||
llist = y; | |||||
/* Put root on rlist. */ | |||||
root->left = rlist; | |||||
rlist = root; | |||||
continue; | |||||
} | |||||
} | } | ||||
/* Put root on rlist. */ | |||||
root->left = rlist; | |||||
rlist = root; | |||||
root = y; | |||||
} else if (addr >= root->end) { | } else if (addr >= root->end) { | ||||
y = root->right; | y = root->right; | ||||
if (y == NULL) | if (y == NULL) | ||||
break; | break; | ||||
if (addr >= y->end && y->right != NULL) { | if (addr >= y->end) { | ||||
/* Rotate left and put y on llist. */ | z = y->right; | ||||
root->right = y->left; | if (z != NULL) { | ||||
y->left = root; | /* Put y on llist. */ | ||||
vm_map_entry_set_max_free(root); | y->right = llist; | ||||
root = y->right; | llist = y; | ||||
y->right = llist; | /* Rotate left. */ | ||||
llist = y; | root->right = y->left; | ||||
} else { | y->left = root; | ||||
/* Put root on llist. */ | vm_map_entry_set_max_free(root); | ||||
root->right = llist; | continue; | ||||
llist = root; | } | ||||
root = y; | } else if (addr < y->start) { | ||||
z = y->left; | |||||
if (z != NULL) { | |||||
/* Put y on rlist */ | |||||
y->left = rlist; | |||||
rlist = y; | |||||
/* Put root on llist. */ | |||||
root->right = llist; | |||||
llist = root; | |||||
continue; | |||||
} | |||||
} | } | ||||
} else | /* Put root on llist. */ | ||||
break; | root->right = llist; | ||||
llist = root; | |||||
root = y; | |||||
} | |||||
break; | |||||
} | } | ||||
/* | /* | ||||
Context not available. |
This can also be a redundant comparison if addr < y->start but y->left == NULL.