aboutsummaryrefslogtreecommitdiff log msg author committer range
path: root/lib/interval_tree.c
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiffstat only
author committer Michel Lespinasse 2012-10-08 16:31:25 -0700 Linus Torvalds 2012-10-09 16:22:39 +0900 6b2dbba8b6ac4df26f72eda1e5ea7bab9f950e08 (patch) 422ed8d7ac2fe45069f20cfba84a9a097bf444af /lib/interval_tree.c fff3fd8a1210a165252cd7cd01206da7a90d3a06 (diff) linux-6b2dbba8b6ac4df26f72eda1e5ea7bab9f950e08.tar.gz
mm: replace vma prio_tree with an interval tree
Implement an interval tree as a replacement for the VMA prio_tree. The algorithms are similar to lib/interval_tree.c; however that code can't be directly reused as the interval endpoints are not explicitly stored in the VMA. So instead, the common algorithm is moved into a template and the details (node type, how to get interval endpoints from the node, etc) are filled in using the C preprocessor. Once the interval tree functions are available, using them as a replacement to the VMA prio tree is a relatively simple, mechanical job. Signed-off-by: Michel Lespinasse <walken@google.com> Cc: Rik van Riel <riel@redhat.com> Cc: Hillf Danton <dhillf@gmail.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Cc: Catalin Marinas <catalin.marinas@arm.com> Cc: Andrea Arcangeli <aarcange@redhat.com> Cc: David Woodhouse <dwmw2@infradead.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Diffstat (limited to 'lib/interval_tree.c')
-rw-r--r--lib/interval_tree.c166
1 files changed, 10 insertions, 156 deletions
 diff --git a/lib/interval_tree.c b/lib/interval_tree.cindex 6fd540b1e49..77a793e0644 100644--- a/lib/interval_tree.c+++ b/lib/interval_tree.c@@ -1,159 +1,13 @@ #include #include -/* Callbacks for augmented rbtree insert and remove */--static inline unsigned long-compute_subtree_last(struct interval_tree_node *node)-{- unsigned long max = node->last, subtree_last;- if (node->rb.rb_left) {- subtree_last = rb_entry(node->rb.rb_left,- struct interval_tree_node, rb)->__subtree_last;- if (max < subtree_last)- max = subtree_last;- }- if (node->rb.rb_right) {- subtree_last = rb_entry(node->rb.rb_right,- struct interval_tree_node, rb)->__subtree_last;- if (max < subtree_last)- max = subtree_last;- }- return max;-}--RB_DECLARE_CALLBACKS(static, augment_callbacks, struct interval_tree_node, rb,- unsigned long, __subtree_last, compute_subtree_last)--/* Insert / remove interval nodes from the tree */--void interval_tree_insert(struct interval_tree_node *node,- struct rb_root *root)-{- struct rb_node **link = &root->rb_node, *rb_parent = NULL;- unsigned long start = node->start, last = node->last;- struct interval_tree_node *parent;-- while (*link) {- rb_parent = *link;- parent = rb_entry(rb_parent, struct interval_tree_node, rb);- if (parent->__subtree_last < last)- parent->__subtree_last = last;- if (start < parent->start)- link = &parent->rb.rb_left;- else- link = &parent->rb.rb_right;- }-- node->__subtree_last = last;- rb_link_node(&node->rb, rb_parent, link);- rb_insert_augmented(&node->rb, root, &augment_callbacks);-}--void interval_tree_remove(struct interval_tree_node *node,- struct rb_root *root)-{- rb_erase_augmented(&node->rb, root, &augment_callbacks);-}--/*- * Iterate over intervals intersecting [start;last]- *- * Note that a node's interval intersects [start;last] iff:- * Cond1: node->start <= last- * and- * Cond2: start <= node->last- */--static struct interval_tree_node *-subtree_search(struct interval_tree_node *node,- unsigned long start, unsigned long last)-{- while (true) {- /*- * Loop invariant: start <= node->__subtree_last- * (Cond2 is satisfied by one of the subtree nodes)- */- if (node->rb.rb_left) {- struct interval_tree_node *left =- rb_entry(node->rb.rb_left,- struct interval_tree_node, rb);- if (start <= left->__subtree_last) {- /*- * Some nodes in left subtree satisfy Cond2.- * Iterate to find the leftmost such node N.- * If it also satisfies Cond1, that's the match- * we are looking for. Otherwise, there is no- * matching interval as nodes to the right of N- * can't satisfy Cond1 either.- */- node = left;- continue;- }- }- if (node->start <= last) { /* Cond1 */- if (start <= node->last) /* Cond2 */- return node; /* node is leftmost match */- if (node->rb.rb_right) {- node = rb_entry(node->rb.rb_right,- struct interval_tree_node, rb);- if (start <= node->__subtree_last)- continue;- }- }- return NULL; /* No match */- }-}--struct interval_tree_node *-interval_tree_iter_first(struct rb_root *root,- unsigned long start, unsigned long last)-{- struct interval_tree_node *node;-- if (!root->rb_node)- return NULL;- node = rb_entry(root->rb_node, struct interval_tree_node, rb);- if (node->__subtree_last < start)- return NULL;- return subtree_search(node, start, last);-}--struct interval_tree_node *-interval_tree_iter_next(struct interval_tree_node *node,- unsigned long start, unsigned long last)-{- struct rb_node *rb = node->rb.rb_right, *prev;-- while (true) {- /*- * Loop invariants:- * Cond1: node->start <= last- * rb == node->rb.rb_right- *- * First, search right subtree if suitable- */- if (rb) {- struct interval_tree_node *right =- rb_entry(rb, struct interval_tree_node, rb);- if (start <= right->__subtree_last)- return subtree_search(right, start, last);- }-- /* Move up the tree until we come from a node's left child */- do {- rb = rb_parent(&node->rb);- if (!rb)- return NULL;- prev = &node->rb;- node = rb_entry(rb, struct interval_tree_node, rb);- rb = node->rb.rb_right;- } while (prev == rb);-- /* Check if the node intersects [start;last] */- if (last < node->start) /* !Cond1 */- return NULL;- else if (start <= node->last) /* Cond2 */- return node;- }-}+#define ITSTRUCT struct interval_tree_node+#define ITRB rb+#define ITTYPE unsigned long+#define ITSUBTREE __subtree_last+#define ITSTART(n) ((n)->start)+#define ITLAST(n) ((n)->last)+#define ITSTATIC+#define ITPREFIX interval_tree++#include
{"ft_lang_label":"__label__en","ft_lang_prob":0.5017349,"math_prob":0.78702664,"size":6176,"snap":"2021-04-2021-17","text_gpt3_token_len":1820,"char_repetition_ratio":0.21046662,"word_repetition_ratio":0.13093859,"special_character_ratio":0.3341969,"punctuation_ratio":0.18569905,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9655785,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-04-10T22:05:20Z\",\"WARC-Record-ID\":\"<urn:uuid:92b6866f-8610-43b8-b5d7-58793e35c560>\",\"Content-Length\":\"20464\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:28a9e26a-fbcc-4a04-add0-e5ac8cba2d1b>\",\"WARC-Concurrent-To\":\"<urn:uuid:c76e665f-8ed1-476b-a446-c187933e97e9>\",\"WARC-IP-Address\":\"99.81.133.34\",\"WARC-Target-URI\":\"http://git-ie.linaro.org/people/steve.capper/linux.git/commit/lib/interval_tree.c?id=6b2dbba8b6ac4df26f72eda1e5ea7bab9f950e08\",\"WARC-Payload-Digest\":\"sha1:AC5CB4EJGN7BLWENGYH5H22D4536EUIJ\",\"WARC-Block-Digest\":\"sha1:DZU6KITOXYDKSZQNEDTUICWY76FKIBXT\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-17/CC-MAIN-2021-17_segments_1618038059348.9_warc_CC-MAIN-20210410210053-20210411000053-00435.warc.gz\"}"}