2  * QEMU Hyper-V Dynamic Memory Protocol driver
4  * Copyright (C) 2020-2023 Oracle and/or its affiliates.
6  * This work is licensed under the terms of the GNU GPL, version 2 or later.
7  * See the COPYING file in the top-level directory.
11 #include "hv-balloon-internal.h"
12 #include "hv-balloon-page_range_tree.h"
16  * too recent Glib version until GLIB_VERSION_MAX_ALLOWED finally reaches
17  * the Glib version with this API
19 #pragma GCC diagnostic ignored "-Wdeprecated-declarations"
29         return -1;  in page_range_tree_key_compare()
45     *key = range->start = start;  in page_range_tree_insert_new()
46     range->count = count;  in page_range_tree_insert_new()
55     GTreeNode *node;  in hvb_page_range_tree_insert()  local
65     node = g_tree_upper_bound(tree.t, &start);  in hvb_page_range_tree_insert()
66     if (node) {  in hvb_page_range_tree_insert()
67         node = g_tree_node_previous(node);  in hvb_page_range_tree_insert()
69         node = g_tree_node_last(tree.t);  in hvb_page_range_tree_insert()
72     if (node) {  in hvb_page_range_tree_insert()
73         range = g_tree_node_value(node);  in hvb_page_range_tree_insert()
79     if (!node ||  in hvb_page_range_tree_insert()
82          * !node case: the tree is empty or the very first node in the tree  in hvb_page_range_tree_insert()
88         node = page_range_tree_insert_new(tree, start, count);  in hvb_page_range_tree_insert()
89         assert(node);  in hvb_page_range_tree_insert()
90         range = g_tree_node_value(node);  in hvb_page_range_tree_insert()
95          * range or ends just at its beginning - extend it  in hvb_page_range_tree_insert()
101         count += start - range->start;  in hvb_page_range_tree_insert()
102         range->count = MAX(range->count, count);  in hvb_page_range_tree_insert()
106     for (node = g_tree_node_next(node); node; ) {  in hvb_page_range_tree_insert()
109         rangecur = g_tree_node_value(node);  in hvb_page_range_tree_insert()
113                                                     range->start, range->count);  in hvb_page_range_tree_insert()
115                                             range->start, range->count);  in hvb_page_range_tree_insert()
117             /* the current node is disjoint */  in hvb_page_range_tree_insert()
125         count = rangecur->count + (rangecur->start - range->start);  in hvb_page_range_tree_insert()
126         range->count = MAX(range->count, count);  in hvb_page_range_tree_insert()
128         /* the current node was merged in, remove it */  in hvb_page_range_tree_insert()
129         start = rangecur->start;  in hvb_page_range_tree_insert()
130         node = g_tree_node_next(node);  in hvb_page_range_tree_insert()
139     GTreeNode *node;  in hvb_page_range_tree_pop()  local
142     node = g_tree_node_last(tree.t);  in hvb_page_range_tree_pop()
143     if (!node) {  in hvb_page_range_tree_pop()
147     range = g_tree_node_value(node);  in hvb_page_range_tree_pop()
150     out->start = range->start;  in hvb_page_range_tree_pop()
152     /* can't modify range->start as it is the node key */  in hvb_page_range_tree_pop()
153     if (range->count > maxcount) {  in hvb_page_range_tree_pop()
154         out->start += range->count - maxcount;  in hvb_page_range_tree_pop()
155         out->count = maxcount;  in hvb_page_range_tree_pop()
156         range->count -= maxcount;  in hvb_page_range_tree_pop()
158         out->count = range->count;  in hvb_page_range_tree_pop()
160         g_tree_remove(tree.t, &out->start);  in hvb_page_range_tree_pop()
169     GTreeNode *node;  in hvb_page_range_tree_intree_any()  local
175     /* find the first node that can possibly intersect our range */  in hvb_page_range_tree_intree_any()
176     node = g_tree_upper_bound(tree.t, &start);  in hvb_page_range_tree_intree_any()
177     if (node) {  in hvb_page_range_tree_intree_any()
179          * a NULL node below means that the very first node in the tree  in hvb_page_range_tree_intree_any()
182         node = g_tree_node_previous(node);  in hvb_page_range_tree_intree_any()
184         /* a NULL node below means that the tree is empty */  in hvb_page_range_tree_intree_any()
185         node = g_tree_node_last(tree.t);  in hvb_page_range_tree_intree_any()
187     /* node range start <= range start */  in hvb_page_range_tree_intree_any()
189     if (!node) {  in hvb_page_range_tree_intree_any()
190         /* node range start > range start */  in hvb_page_range_tree_intree_any()
191         node = g_tree_node_first(tree.t);  in hvb_page_range_tree_intree_any()
194     for ( ; node; node = g_tree_node_next(node)) {  in hvb_page_range_tree_intree_any()
195         PageRange *range = g_tree_node_value(node);  in hvb_page_range_tree_intree_any()
199          * if this node starts beyond or at the end of our range so does  in hvb_page_range_tree_intree_any()
202         if (range->start >= start + count) {  in hvb_page_range_tree_intree_any()
216     tree->t = g_tree_new_full(page_range_tree_key_compare, NULL,  in hvb_page_range_tree_init()
222     /* g_tree_destroy() is not NULL-safe */  in hvb_page_range_tree_destroy()
223     if (!tree->t) {  in hvb_page_range_tree_destroy()
227     g_tree_destroy(tree->t);  in hvb_page_range_tree_destroy()
228     tree->t = NULL;  in hvb_page_range_tree_destroy()