Changeset View
Standalone View
sys/vm/vm_map.c
Context not available. | |||||
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. */ | if (y->left != NULL) { | ||||
root->left = y->right; | /* Rotate right and put y on rlist. */ | ||||
y->right = root; | root->left = y->right; | ||||
vm_map_entry_set_max_free(root); | y->right = root; | ||||
root = y->left; | vm_map_entry_set_max_free(root); | ||||
y->left = rlist; | root = y->left; | ||||
rlist = y; | y->left = rlist; | ||||
} else { | 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… | |||||
/* Put root on rlist. */ | continue; | ||||
} | |||||
} else if (addr >= y->end) { | |||||
if (y->right == NULL) | |||||
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… | |||||
Not Done Inline ActionsChange 'b' in the last line to 'a'. dougm: Change 'b' in the last line to 'a'. | |||||
break; | |||||
/* Put root on rlist, y on llist. */ | |||||
root->left = rlist; | root->left = rlist; | ||||
rlist = root; | rlist = root; | ||||
root = y; | root = y->right; | ||||
y->right = llist; | |||||
llist = y; | |||||
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. */ | if (y->right != NULL) { | ||||
root->right = y->left; | /* Rotate left and put y on llist. */ | ||||
y->left = root; | root->right = y->left; | ||||
vm_map_entry_set_max_free(root); | y->left = root; | ||||
root = y->right; | vm_map_entry_set_max_free(root); | ||||
y->right = llist; | root = y->right; | ||||
llist = y; | y->right = llist; | ||||
} else { | llist = y; | ||||
/* Put root on llist. */ | continue; | ||||
} | |||||
} else if (addr < y->start) { | |||||
if (y->left == NULL) | |||||
break; | |||||
/* Put root on llist, y on rlist. */ | |||||
root->right = llist; | root->right = llist; | ||||
llist = root; | llist = root; | ||||
root = y; | root = y->left; | ||||
y->left = rlist; | |||||
rlist = y; | |||||
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.