return index_bits_to_maxindex[bits - 1];
}
+static void prio_tree_remove(struct prio_tree_root *, struct prio_tree_node *);
+
/*
* Extend a priority search tree so that it can store a node with heap_index
* max_heap_index. In the worst case, this algorithm takes O((log n)^2).
static struct prio_tree_node *prio_tree_expand(struct prio_tree_root *root,
struct prio_tree_node *node, unsigned long max_heap_index)
{
- static void prio_tree_remove(struct prio_tree_root *,
- struct prio_tree_node *);
struct prio_tree_node *first = NULL, *prev, *last = NULL;
if (max_heap_index > prio_tree_maxindex(root->index_bits))
* 'm' is the number of prio_tree_nodes that overlap the interval X.
*/
-static struct prio_tree_node *prio_tree_left(
- struct prio_tree_root *root, struct prio_tree_iter *iter,
- unsigned long radix_index, unsigned long heap_index,
+static struct prio_tree_node *prio_tree_left(struct prio_tree_iter *iter,
unsigned long *r_index, unsigned long *h_index)
{
if (prio_tree_left_empty(iter->cur))
GET_INDEX(iter->cur->left, *r_index, *h_index);
- if (radix_index <= *h_index) {
+ if (iter->r_index <= *h_index) {
iter->cur = iter->cur->left;
iter->mask >>= 1;
if (iter->mask) {
iter->mask = ULONG_MAX;
} else {
iter->size_level = 1;
- iter->mask = 1UL << (root->index_bits - 1);
+ iter->mask = 1UL << (iter->root->index_bits - 1);
}
}
return iter->cur;
return NULL;
}
-static struct prio_tree_node *prio_tree_right(
- struct prio_tree_root *root, struct prio_tree_iter *iter,
- unsigned long radix_index, unsigned long heap_index,
+static struct prio_tree_node *prio_tree_right(struct prio_tree_iter *iter,
unsigned long *r_index, unsigned long *h_index)
{
unsigned long value;
else
value = iter->value | iter->mask;
- if (heap_index < value)
+ if (iter->h_index < value)
return NULL;
GET_INDEX(iter->cur->right, *r_index, *h_index);
- if (radix_index <= *h_index) {
+ if (iter->r_index <= *h_index) {
iter->cur = iter->cur->right;
iter->mask >>= 1;
iter->value = value;
iter->mask = ULONG_MAX;
} else {
iter->size_level = 1;
- iter->mask = 1UL << (root->index_bits - 1);
+ iter->mask = 1UL << (iter->root->index_bits - 1);
}
}
return iter->cur;
return iter->cur;
}
-static inline int overlap(unsigned long radix_index, unsigned long heap_index,
+static inline int overlap(struct prio_tree_iter *iter,
unsigned long r_index, unsigned long h_index)
{
- return heap_index >= r_index && radix_index <= h_index;
+ return iter->h_index >= r_index && iter->r_index <= h_index;
}
/*
* heap_index]. Note that always radix_index <= heap_index. We do a pre-order
* traversal of the tree.
*/
-static struct prio_tree_node *prio_tree_first(struct prio_tree_root *root,
- struct prio_tree_iter *iter, unsigned long radix_index,
- unsigned long heap_index)
+static struct prio_tree_node *prio_tree_first(struct prio_tree_iter *iter)
{
+ struct prio_tree_root *root;
unsigned long r_index, h_index;
INIT_PRIO_TREE_ITER(iter);
+ root = iter->root;
if (prio_tree_empty(root))
return NULL;
GET_INDEX(root->prio_tree_node, r_index, h_index);
- if (radix_index > h_index)
+ if (iter->r_index > h_index)
return NULL;
iter->mask = 1UL << (root->index_bits - 1);
iter->cur = root->prio_tree_node;
while (1) {
- if (overlap(radix_index, heap_index, r_index, h_index))
+ if (overlap(iter, r_index, h_index))
return iter->cur;
- if (prio_tree_left(root, iter, radix_index, heap_index,
- &r_index, &h_index))
+ if (prio_tree_left(iter, &r_index, &h_index))
continue;
- if (prio_tree_right(root, iter, radix_index, heap_index,
- &r_index, &h_index))
+ if (prio_tree_right(iter, &r_index, &h_index))
continue;
break;
*
* Get the next prio_tree_node that overlaps with the input interval in iter
*/
-static struct prio_tree_node *prio_tree_next(struct prio_tree_root *root,
- struct prio_tree_iter *iter, unsigned long radix_index,
- unsigned long heap_index)
+static struct prio_tree_node *prio_tree_next(struct prio_tree_iter *iter)
{
unsigned long r_index, h_index;
repeat:
- while (prio_tree_left(root, iter, radix_index,
- heap_index, &r_index, &h_index)) {
- if (overlap(radix_index, heap_index, r_index, h_index))
+ while (prio_tree_left(iter, &r_index, &h_index))
+ if (overlap(iter, r_index, h_index))
return iter->cur;
- }
- while (!prio_tree_right(root, iter, radix_index,
- heap_index, &r_index, &h_index)) {
+ while (!prio_tree_right(iter, &r_index, &h_index)) {
while (!prio_tree_root(iter->cur) &&
iter->cur->parent->right == iter->cur)
prio_tree_parent(iter);
prio_tree_parent(iter);
}
- if (overlap(radix_index, heap_index, r_index, h_index))
+ if (overlap(iter, r_index, h_index))
return iter->cur;
goto repeat;
BUG_ON(RADIX_INDEX(vma) != RADIX_INDEX(old));
BUG_ON(HEAP_INDEX(vma) != HEAP_INDEX(old));
+ vma->shared.vm_set.head = NULL;
+ vma->shared.vm_set.parent = NULL;
+
if (!old->shared.vm_set.parent)
list_add(&vma->shared.vm_set.list,
&old->shared.vm_set.list);
struct prio_tree_node *ptr;
struct vm_area_struct *old;
+ vma->shared.vm_set.head = NULL;
+
ptr = prio_tree_insert(root, &vma->shared.prio_tree_node);
if (ptr != &vma->shared.prio_tree_node) {
old = prio_tree_entry(ptr, struct vm_area_struct,
* page in the given range of contiguous file pages.
*/
struct vm_area_struct *vma_prio_tree_next(struct vm_area_struct *vma,
- struct prio_tree_root *root, struct prio_tree_iter *iter,
- pgoff_t begin, pgoff_t end)
+ struct prio_tree_iter *iter)
{
struct prio_tree_node *ptr;
struct vm_area_struct *next;
/*
* First call is with NULL vma
*/
- ptr = prio_tree_first(root, iter, begin, end);
+ ptr = prio_tree_first(iter);
if (ptr) {
next = prio_tree_entry(ptr, struct vm_area_struct,
shared.prio_tree_node);
}
}
- ptr = prio_tree_next(root, iter, begin, end);
+ ptr = prio_tree_next(iter);
if (ptr) {
next = prio_tree_entry(ptr, struct vm_area_struct,
shared.prio_tree_node);