qemu

1
/*
2
 * GLIB - Library of useful routines for C programming
3
 * Copyright (C) 1995-1997  Peter Mattis, Spencer Kimball and Josh MacDonald
4
 *
5
 * SPDX-License-Identifier: LGPL-2.1-or-later
6
 *
7
 * This library is free software; you can redistribute it and/or
8
 * modify it under the terms of the GNU Lesser General Public
9
 * License as published by the Free Software Foundation; either
10
 * version 2.1 of the License, or (at your option) any later version.
11
 *
12
 * This library is distributed in the hope that it will be useful,
13
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15
 * Lesser General Public License for more details.
16
 *
17
 * You should have received a copy of the GNU Lesser General Public
18
 * License along with this library; if not, see <http://www.gnu.org/licenses/>.
19
 */
20

21
/*
22
 * Modified by the GLib Team and others 1997-2000.  See the AUTHORS
23
 * file for a list of people on the GLib Team.  See the ChangeLog
24
 * files for a list of changes.  These files are distributed with
25
 * GLib at ftp://ftp.gtk.org/pub/gtk/.
26
 */
27

28
/*
29
 * MT safe
30
 */
31

32
#include "qemu/osdep.h"
33
#include "qemu/qtree.h"
34

35
/**
36
 * SECTION:trees-binary
37
 * @title: Balanced Binary Trees
38
 * @short_description: a sorted collection of key/value pairs optimized
39
 *                     for searching and traversing in order
40
 *
41
 * The #QTree structure and its associated functions provide a sorted
42
 * collection of key/value pairs optimized for searching and traversing
43
 * in order. This means that most of the operations  (access, search,
44
 * insertion, deletion, ...) on #QTree are O(log(n)) in average and O(n)
45
 * in worst case for time complexity. But, note that maintaining a
46
 * balanced sorted #QTree of n elements is done in time O(n log(n)).
47
 *
48
 * To create a new #QTree use q_tree_new().
49
 *
50
 * To insert a key/value pair into a #QTree use q_tree_insert()
51
 * (O(n log(n))).
52
 *
53
 * To remove a key/value pair use q_tree_remove() (O(n log(n))).
54
 *
55
 * To look up the value corresponding to a given key, use
56
 * q_tree_lookup() and q_tree_lookup_extended().
57
 *
58
 * To find out the number of nodes in a #QTree, use q_tree_nnodes(). To
59
 * get the height of a #QTree, use q_tree_height().
60
 *
61
 * To traverse a #QTree, calling a function for each node visited in
62
 * the traversal, use q_tree_foreach().
63
 *
64
 * To destroy a #QTree, use q_tree_destroy().
65
 **/
66

67
#define MAX_GTREE_HEIGHT 40
68

69
/**
70
 * QTree:
71
 *
72
 * The QTree struct is an opaque data structure representing a
73
 * [balanced binary tree][glib-Balanced-Binary-Trees]. It should be
74
 * accessed only by using the following functions.
75
 */
76
struct _QTree {
77
    QTreeNode        *root;
78
    GCompareDataFunc  key_compare;
79
    GDestroyNotify    key_destroy_func;
80
    GDestroyNotify    value_destroy_func;
81
    gpointer          key_compare_data;
82
    guint             nnodes;
83
    gint              ref_count;
84
};
85

86
struct _QTreeNode {
87
    gpointer   key;         /* key for this node */
88
    gpointer   value;       /* value stored at this node */
89
    QTreeNode *left;        /* left subtree */
90
    QTreeNode *right;       /* right subtree */
91
    gint8      balance;     /* height (right) - height (left) */
92
    guint8     left_child;
93
    guint8     right_child;
94
};
95

96

97
static QTreeNode *q_tree_node_new(gpointer       key,
98
                                  gpointer       value);
99
static QTreeNode *q_tree_insert_internal(QTree *tree,
100
                                         gpointer key,
101
                                         gpointer value,
102
                                         gboolean replace);
103
static gboolean   q_tree_remove_internal(QTree         *tree,
104
                                         gconstpointer  key,
105
                                         gboolean       steal);
106
static QTreeNode *q_tree_node_balance(QTreeNode     *node);
107
static QTreeNode *q_tree_find_node(QTree         *tree,
108
                                   gconstpointer  key);
109
static QTreeNode *q_tree_node_search(QTreeNode *node,
110
                                     GCompareFunc search_func,
111
                                     gconstpointer data);
112
static QTreeNode *q_tree_node_rotate_left(QTreeNode     *node);
113
static QTreeNode *q_tree_node_rotate_right(QTreeNode     *node);
114
#ifdef Q_TREE_DEBUG
115
static void       q_tree_node_check(QTreeNode     *node);
116
#endif
117

118
static QTreeNode*
119
q_tree_node_new(gpointer key,
120
                gpointer value)
121
{
122
    QTreeNode *node = g_new(QTreeNode, 1);
123

124
    node->balance = 0;
125
    node->left = NULL;
126
    node->right = NULL;
127
    node->left_child = FALSE;
128
    node->right_child = FALSE;
129
    node->key = key;
130
    node->value = value;
131

132
    return node;
133
}
134

135
/**
136
 * q_tree_new:
137
 * @key_compare_func: the function used to order the nodes in the #QTree.
138
 *   It should return values similar to the standard strcmp() function -
139
 *   0 if the two arguments are equal, a negative value if the first argument
140
 *   comes before the second, or a positive value if the first argument comes
141
 *   after the second.
142
 *
143
 * Creates a new #QTree.
144
 *
145
 * Returns: a newly allocated #QTree
146
 */
147
QTree *
148
q_tree_new(GCompareFunc key_compare_func)
149
{
150
    g_return_val_if_fail(key_compare_func != NULL, NULL);
151

152
    return q_tree_new_full((GCompareDataFunc) key_compare_func, NULL,
153
                           NULL, NULL);
154
}
155

156
/**
157
 * q_tree_new_with_data:
158
 * @key_compare_func: qsort()-style comparison function
159
 * @key_compare_data: data to pass to comparison function
160
 *
161
 * Creates a new #QTree with a comparison function that accepts user data.
162
 * See q_tree_new() for more details.
163
 *
164
 * Returns: a newly allocated #QTree
165
 */
166
QTree *
167
q_tree_new_with_data(GCompareDataFunc key_compare_func,
168
                     gpointer         key_compare_data)
169
{
170
    g_return_val_if_fail(key_compare_func != NULL, NULL);
171

172
    return q_tree_new_full(key_compare_func, key_compare_data,
173
                           NULL, NULL);
174
}
175

176
/**
177
 * q_tree_new_full:
178
 * @key_compare_func: qsort()-style comparison function
179
 * @key_compare_data: data to pass to comparison function
180
 * @key_destroy_func: a function to free the memory allocated for the key
181
 *   used when removing the entry from the #QTree or %NULL if you don't
182
 *   want to supply such a function
183
 * @value_destroy_func: a function to free the memory allocated for the
184
 *   value used when removing the entry from the #QTree or %NULL if you
185
 *   don't want to supply such a function
186
 *
187
 * Creates a new #QTree like q_tree_new() and allows to specify functions
188
 * to free the memory allocated for the key and value that get called when
189
 * removing the entry from the #QTree.
190
 *
191
 * Returns: a newly allocated #QTree
192
 */
193
QTree *
194
q_tree_new_full(GCompareDataFunc key_compare_func,
195
                gpointer         key_compare_data,
196
                GDestroyNotify   key_destroy_func,
197
                GDestroyNotify   value_destroy_func)
198
{
199
    QTree *tree;
200

201
    g_return_val_if_fail(key_compare_func != NULL, NULL);
202

203
    tree = g_new(QTree, 1);
204
    tree->root               = NULL;
205
    tree->key_compare        = key_compare_func;
206
    tree->key_destroy_func   = key_destroy_func;
207
    tree->value_destroy_func = value_destroy_func;
208
    tree->key_compare_data   = key_compare_data;
209
    tree->nnodes             = 0;
210
    tree->ref_count          = 1;
211

212
    return tree;
213
}
214

215
/**
216
 * q_tree_node_first:
217
 * @tree: a #QTree
218
 *
219
 * Returns the first in-order node of the tree, or %NULL
220
 * for an empty tree.
221
 *
222
 * Returns: (nullable) (transfer none): the first node in the tree
223
 *
224
 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
225
 */
226
static QTreeNode *
227
q_tree_node_first(QTree *tree)
228
{
229
    QTreeNode *tmp;
230

231
    g_return_val_if_fail(tree != NULL, NULL);
232

233
    if (!tree->root) {
234
        return NULL;
235
    }
236

237
    tmp = tree->root;
238

239
    while (tmp->left_child) {
240
        tmp = tmp->left;
241
    }
242

243
    return tmp;
244
}
245

246
/**
247
 * q_tree_node_previous
248
 * @node: a #QTree node
249
 *
250
 * Returns the previous in-order node of the tree, or %NULL
251
 * if the passed node was already the first one.
252
 *
253
 * Returns: (nullable) (transfer none): the previous node in the tree
254
 *
255
 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
256
 */
257
static QTreeNode *
258
q_tree_node_previous(QTreeNode *node)
259
{
260
    QTreeNode *tmp;
261

262
    g_return_val_if_fail(node != NULL, NULL);
263

264
    tmp = node->left;
265

266
    if (node->left_child) {
267
        while (tmp->right_child) {
268
            tmp = tmp->right;
269
        }
270
    }
271

272
    return tmp;
273
}
274

275
/**
276
 * q_tree_node_next
277
 * @node: a #QTree node
278
 *
279
 * Returns the next in-order node of the tree, or %NULL
280
 * if the passed node was already the last one.
281
 *
282
 * Returns: (nullable) (transfer none): the next node in the tree
283
 *
284
 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
285
 */
286
static QTreeNode *
287
q_tree_node_next(QTreeNode *node)
288
{
289
    QTreeNode *tmp;
290

291
    g_return_val_if_fail(node != NULL, NULL);
292

293
    tmp = node->right;
294

295
    if (node->right_child) {
296
        while (tmp->left_child) {
297
            tmp = tmp->left;
298
        }
299
    }
300

301
    return tmp;
302
}
303

304
/**
305
 * q_tree_remove_all:
306
 * @tree: a #QTree
307
 *
308
 * Removes all nodes from a #QTree and destroys their keys and values,
309
 * then resets the #QTree’s root to %NULL.
310
 *
311
 * Since: 2.70 in GLib. Internal in Qtree, i.e. not in the public API.
312
 */
313
static void QEMU_DISABLE_CFI
314
q_tree_remove_all(QTree *tree)
315
{
316
    QTreeNode *node;
317
    QTreeNode *next;
318

319
    g_return_if_fail(tree != NULL);
320

321
    node = q_tree_node_first(tree);
322

323
    while (node) {
324
        next = q_tree_node_next(node);
325

326
        if (tree->key_destroy_func) {
327
            tree->key_destroy_func(node->key);
328
        }
329
        if (tree->value_destroy_func) {
330
            tree->value_destroy_func(node->value);
331
        }
332
        g_free(node);
333

334
#ifdef Q_TREE_DEBUG
335
        g_assert(tree->nnodes > 0);
336
        tree->nnodes--;
337
#endif
338

339
        node = next;
340
    }
341

342
#ifdef Q_TREE_DEBUG
343
    g_assert(tree->nnodes == 0);
344
#endif
345

346
    tree->root = NULL;
347
#ifndef Q_TREE_DEBUG
348
    tree->nnodes = 0;
349
#endif
350
}
351

352
/**
353
 * q_tree_ref:
354
 * @tree: a #QTree
355
 *
356
 * Increments the reference count of @tree by one.
357
 *
358
 * It is safe to call this function from any thread.
359
 *
360
 * Returns: the passed in #QTree
361
 *
362
 * Since: 2.22
363
 */
364
QTree *
365
q_tree_ref(QTree *tree)
366
{
367
    g_return_val_if_fail(tree != NULL, NULL);
368

369
    g_atomic_int_inc(&tree->ref_count);
370

371
    return tree;
372
}
373

374
/**
375
 * q_tree_unref:
376
 * @tree: a #QTree
377
 *
378
 * Decrements the reference count of @tree by one.
379
 * If the reference count drops to 0, all keys and values will
380
 * be destroyed (if destroy functions were specified) and all
381
 * memory allocated by @tree will be released.
382
 *
383
 * It is safe to call this function from any thread.
384
 *
385
 * Since: 2.22
386
 */
387
void
388
q_tree_unref(QTree *tree)
389
{
390
    g_return_if_fail(tree != NULL);
391

392
    if (g_atomic_int_dec_and_test(&tree->ref_count)) {
393
        q_tree_remove_all(tree);
394
        g_free(tree);
395
    }
396
}
397

398
/**
399
 * q_tree_destroy:
400
 * @tree: a #QTree
401
 *
402
 * Removes all keys and values from the #QTree and decreases its
403
 * reference count by one. If keys and/or values are dynamically
404
 * allocated, you should either free them first or create the #QTree
405
 * using q_tree_new_full(). In the latter case the destroy functions
406
 * you supplied will be called on all keys and values before destroying
407
 * the #QTree.
408
 */
409
void
410
q_tree_destroy(QTree *tree)
411
{
412
    g_return_if_fail(tree != NULL);
413

414
    q_tree_remove_all(tree);
415
    q_tree_unref(tree);
416
}
417

418
/**
419
 * q_tree_insert_node:
420
 * @tree: a #QTree
421
 * @key: the key to insert
422
 * @value: the value corresponding to the key
423
 *
424
 * Inserts a key/value pair into a #QTree.
425
 *
426
 * If the given key already exists in the #QTree its corresponding value
427
 * is set to the new value. If you supplied a @value_destroy_func when
428
 * creating the #QTree, the old value is freed using that function. If
429
 * you supplied a @key_destroy_func when creating the #QTree, the passed
430
 * key is freed using that function.
431
 *
432
 * The tree is automatically 'balanced' as new key/value pairs are added,
433
 * so that the distance from the root to every leaf is as small as possible.
434
 * The cost of maintaining a balanced tree while inserting new key/value
435
 * result in a O(n log(n)) operation where most of the other operations
436
 * are O(log(n)).
437
 *
438
 * Returns: (transfer none): the inserted (or set) node.
439
 *
440
 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
441
 */
442
static QTreeNode *
443
q_tree_insert_node(QTree    *tree,
444
                   gpointer  key,
445
                   gpointer  value)
446
{
447
    QTreeNode *node;
448

449
    g_return_val_if_fail(tree != NULL, NULL);
450

451
    node = q_tree_insert_internal(tree, key, value, FALSE);
452

453
#ifdef Q_TREE_DEBUG
454
    q_tree_node_check(tree->root);
455
#endif
456

457
    return node;
458
}
459

460
/**
461
 * q_tree_insert:
462
 * @tree: a #QTree
463
 * @key: the key to insert
464
 * @value: the value corresponding to the key
465
 *
466
 * Inserts a key/value pair into a #QTree.
467
 *
468
 * Inserts a new key and value into a #QTree as q_tree_insert_node() does,
469
 * only this function does not return the inserted or set node.
470
 */
471
void
472
q_tree_insert(QTree    *tree,
473
              gpointer  key,
474
              gpointer  value)
475
{
476
    q_tree_insert_node(tree, key, value);
477
}
478

479
/**
480
 * q_tree_replace_node:
481
 * @tree: a #QTree
482
 * @key: the key to insert
483
 * @value: the value corresponding to the key
484
 *
485
 * Inserts a new key and value into a #QTree similar to q_tree_insert_node().
486
 * The difference is that if the key already exists in the #QTree, it gets
487
 * replaced by the new key. If you supplied a @value_destroy_func when
488
 * creating the #QTree, the old value is freed using that function. If you
489
 * supplied a @key_destroy_func when creating the #QTree, the old key is
490
 * freed using that function.
491
 *
492
 * The tree is automatically 'balanced' as new key/value pairs are added,
493
 * so that the distance from the root to every leaf is as small as possible.
494
 *
495
 * Returns: (transfer none): the inserted (or set) node.
496
 *
497
 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
498
 */
499
static QTreeNode *
500
q_tree_replace_node(QTree    *tree,
501
                    gpointer  key,
502
                    gpointer  value)
503
{
504
    QTreeNode *node;
505

506
    g_return_val_if_fail(tree != NULL, NULL);
507

508
    node = q_tree_insert_internal(tree, key, value, TRUE);
509

510
#ifdef Q_TREE_DEBUG
511
    q_tree_node_check(tree->root);
512
#endif
513

514
    return node;
515
}
516

517
/**
518
 * q_tree_replace:
519
 * @tree: a #QTree
520
 * @key: the key to insert
521
 * @value: the value corresponding to the key
522
 *
523
 * Inserts a new key and value into a #QTree as q_tree_replace_node() does,
524
 * only this function does not return the inserted or set node.
525
 */
526
void
527
q_tree_replace(QTree    *tree,
528
               gpointer  key,
529
               gpointer  value)
530
{
531
    q_tree_replace_node(tree, key, value);
532
}
533

534
/* internal insert routine */
535
static QTreeNode * QEMU_DISABLE_CFI
536
q_tree_insert_internal(QTree    *tree,
537
                       gpointer  key,
538
                       gpointer  value,
539
                       gboolean  replace)
540
{
541
    QTreeNode *node, *retnode;
542
    QTreeNode *path[MAX_GTREE_HEIGHT];
543
    int idx;
544

545
    g_return_val_if_fail(tree != NULL, NULL);
546

547
    if (!tree->root) {
548
        tree->root = q_tree_node_new(key, value);
549
        tree->nnodes++;
550
        return tree->root;
551
    }
552

553
    idx = 0;
554
    path[idx++] = NULL;
555
    node = tree->root;
556

557
    while (1) {
558
        int cmp = tree->key_compare(key, node->key, tree->key_compare_data);
559

560
        if (cmp == 0) {
561
            if (tree->value_destroy_func) {
562
                tree->value_destroy_func(node->value);
563
            }
564

565
            node->value = value;
566

567
            if (replace) {
568
                if (tree->key_destroy_func) {
569
                    tree->key_destroy_func(node->key);
570
                }
571

572
                node->key = key;
573
            } else {
574
                /* free the passed key */
575
                if (tree->key_destroy_func) {
576
                    tree->key_destroy_func(key);
577
                }
578
            }
579

580
            return node;
581
        } else if (cmp < 0) {
582
            if (node->left_child) {
583
                path[idx++] = node;
584
                node = node->left;
585
            } else {
586
                QTreeNode *child = q_tree_node_new(key, value);
587

588
                child->left = node->left;
589
                child->right = node;
590
                node->left = child;
591
                node->left_child = TRUE;
592
                node->balance -= 1;
593

594
                tree->nnodes++;
595

596
                retnode = child;
597
                break;
598
            }
599
        } else {
600
            if (node->right_child) {
601
                path[idx++] = node;
602
                node = node->right;
603
            } else {
604
                QTreeNode *child = q_tree_node_new(key, value);
605

606
                child->right = node->right;
607
                child->left = node;
608
                node->right = child;
609
                node->right_child = TRUE;
610
                node->balance += 1;
611

612
                tree->nnodes++;
613

614
                retnode = child;
615
                break;
616
            }
617
        }
618
    }
619

620
    /*
621
     * Restore balance. This is the goodness of a non-recursive
622
     * implementation, when we are done with balancing we 'break'
623
     * the loop and we are done.
624
     */
625
    while (1) {
626
        QTreeNode *bparent = path[--idx];
627
        gboolean left_node = (bparent && node == bparent->left);
628
        g_assert(!bparent || bparent->left == node || bparent->right == node);
629

630
        if (node->balance < -1 || node->balance > 1) {
631
            node = q_tree_node_balance(node);
632
            if (bparent == NULL) {
633
                tree->root = node;
634
            } else if (left_node) {
635
                bparent->left = node;
636
            } else {
637
                bparent->right = node;
638
            }
639
        }
640

641
        if (node->balance == 0 || bparent == NULL) {
642
            break;
643
        }
644

645
        if (left_node) {
646
            bparent->balance -= 1;
647
        } else {
648
            bparent->balance += 1;
649
        }
650

651
        node = bparent;
652
    }
653

654
    return retnode;
655
}
656

657
/**
658
 * q_tree_remove:
659
 * @tree: a #QTree
660
 * @key: the key to remove
661
 *
662
 * Removes a key/value pair from a #QTree.
663
 *
664
 * If the #QTree was created using q_tree_new_full(), the key and value
665
 * are freed using the supplied destroy functions, otherwise you have to
666
 * make sure that any dynamically allocated values are freed yourself.
667
 * If the key does not exist in the #QTree, the function does nothing.
668
 *
669
 * The cost of maintaining a balanced tree while removing a key/value
670
 * result in a O(n log(n)) operation where most of the other operations
671
 * are O(log(n)).
672
 *
673
 * Returns: %TRUE if the key was found (prior to 2.8, this function
674
 *     returned nothing)
675
 */
676
gboolean
677
q_tree_remove(QTree         *tree,
678
              gconstpointer  key)
679
{
680
    gboolean removed;
681

682
    g_return_val_if_fail(tree != NULL, FALSE);
683

684
    removed = q_tree_remove_internal(tree, key, FALSE);
685

686
#ifdef Q_TREE_DEBUG
687
    q_tree_node_check(tree->root);
688
#endif
689

690
    return removed;
691
}
692

693
/**
694
 * q_tree_steal:
695
 * @tree: a #QTree
696
 * @key: the key to remove
697
 *
698
 * Removes a key and its associated value from a #QTree without calling
699
 * the key and value destroy functions.
700
 *
701
 * If the key does not exist in the #QTree, the function does nothing.
702
 *
703
 * Returns: %TRUE if the key was found (prior to 2.8, this function
704
 *     returned nothing)
705
 */
706
gboolean
707
q_tree_steal(QTree         *tree,
708
             gconstpointer  key)
709
{
710
    gboolean removed;
711

712
    g_return_val_if_fail(tree != NULL, FALSE);
713

714
    removed = q_tree_remove_internal(tree, key, TRUE);
715

716
#ifdef Q_TREE_DEBUG
717
    q_tree_node_check(tree->root);
718
#endif
719

720
    return removed;
721
}
722

723
/* internal remove routine */
724
static gboolean QEMU_DISABLE_CFI
725
q_tree_remove_internal(QTree         *tree,
726
                       gconstpointer  key,
727
                       gboolean       steal)
728
{
729
    QTreeNode *node, *parent, *balance;
730
    QTreeNode *path[MAX_GTREE_HEIGHT];
731
    int idx;
732
    gboolean left_node;
733

734
    g_return_val_if_fail(tree != NULL, FALSE);
735

736
    if (!tree->root) {
737
        return FALSE;
738
    }
739

740
    idx = 0;
741
    path[idx++] = NULL;
742
    node = tree->root;
743

744
    while (1) {
745
        int cmp = tree->key_compare(key, node->key, tree->key_compare_data);
746

747
        if (cmp == 0) {
748
            break;
749
        } else if (cmp < 0) {
750
            if (!node->left_child) {
751
                return FALSE;
752
            }
753

754
            path[idx++] = node;
755
            node = node->left;
756
        } else {
757
            if (!node->right_child) {
758
                return FALSE;
759
            }
760

761
            path[idx++] = node;
762
            node = node->right;
763
        }
764
    }
765

766
    /*
767
     * The following code is almost equal to q_tree_remove_node,
768
     * except that we do not have to call q_tree_node_parent.
769
     */
770
    balance = parent = path[--idx];
771
    g_assert(!parent || parent->left == node || parent->right == node);
772
    left_node = (parent && node == parent->left);
773

774
    if (!node->left_child) {
775
        if (!node->right_child) {
776
            if (!parent) {
777
                tree->root = NULL;
778
            } else if (left_node) {
779
                parent->left_child = FALSE;
780
                parent->left = node->left;
781
                parent->balance += 1;
782
            } else {
783
                parent->right_child = FALSE;
784
                parent->right = node->right;
785
                parent->balance -= 1;
786
            }
787
        } else {
788
            /* node has a right child */
789
            QTreeNode *tmp = q_tree_node_next(node);
790
            tmp->left = node->left;
791

792
            if (!parent) {
793
                tree->root = node->right;
794
            } else if (left_node) {
795
                parent->left = node->right;
796
                parent->balance += 1;
797
            } else {
798
                parent->right = node->right;
799
                parent->balance -= 1;
800
            }
801
        }
802
    } else {
803
        /* node has a left child */
804
        if (!node->right_child) {
805
            QTreeNode *tmp = q_tree_node_previous(node);
806
            tmp->right = node->right;
807

808
            if (parent == NULL) {
809
                tree->root = node->left;
810
            } else if (left_node) {
811
                parent->left = node->left;
812
                parent->balance += 1;
813
            } else {
814
                parent->right = node->left;
815
                parent->balance -= 1;
816
            }
817
        } else {
818
            /* node has a both children (pant, pant!) */
819
            QTreeNode *prev = node->left;
820
            QTreeNode *next = node->right;
821
            QTreeNode *nextp = node;
822
            int old_idx = idx + 1;
823
            idx++;
824

825
            /* path[idx] == parent */
826
            /* find the immediately next node (and its parent) */
827
            while (next->left_child) {
828
                path[++idx] = nextp = next;
829
                next = next->left;
830
            }
831

832
            path[old_idx] = next;
833
            balance = path[idx];
834

835
            /* remove 'next' from the tree */
836
            if (nextp != node) {
837
                if (next->right_child) {
838
                    nextp->left = next->right;
839
                } else {
840
                    nextp->left_child = FALSE;
841
                }
842
                nextp->balance += 1;
843

844
                next->right_child = TRUE;
845
                next->right = node->right;
846
            } else {
847
                node->balance -= 1;
848
            }
849

850
            /* set the prev to point to the right place */
851
            while (prev->right_child) {
852
                prev = prev->right;
853
            }
854
            prev->right = next;
855

856
            /* prepare 'next' to replace 'node' */
857
            next->left_child = TRUE;
858
            next->left = node->left;
859
            next->balance = node->balance;
860

861
            if (!parent) {
862
                tree->root = next;
863
            } else if (left_node) {
864
                parent->left = next;
865
            } else {
866
                parent->right = next;
867
            }
868
        }
869
    }
870

871
    /* restore balance */
872
    if (balance) {
873
        while (1) {
874
            QTreeNode *bparent = path[--idx];
875
            g_assert(!bparent ||
876
                     bparent->left == balance ||
877
                     bparent->right == balance);
878
            left_node = (bparent && balance == bparent->left);
879

880
            if (balance->balance < -1 || balance->balance > 1) {
881
                balance = q_tree_node_balance(balance);
882
                if (!bparent) {
883
                    tree->root = balance;
884
                } else if (left_node) {
885
                    bparent->left = balance;
886
                } else {
887
                    bparent->right = balance;
888
                }
889
            }
890

891
            if (balance->balance != 0 || !bparent) {
892
                break;
893
            }
894

895
            if (left_node) {
896
                bparent->balance += 1;
897
            } else {
898
                bparent->balance -= 1;
899
            }
900

901
            balance = bparent;
902
        }
903
    }
904

905
    if (!steal) {
906
        if (tree->key_destroy_func) {
907
            tree->key_destroy_func(node->key);
908
        }
909
        if (tree->value_destroy_func) {
910
            tree->value_destroy_func(node->value);
911
        }
912
    }
913

914
    g_free(node);
915

916
    tree->nnodes--;
917

918
    return TRUE;
919
}
920

921
/**
922
 * q_tree_lookup_node:
923
 * @tree: a #QTree
924
 * @key: the key to look up
925
 *
926
 * Gets the tree node corresponding to the given key. Since a #QTree is
927
 * automatically balanced as key/value pairs are added, key lookup
928
 * is O(log n) (where n is the number of key/value pairs in the tree).
929
 *
930
 * Returns: (nullable) (transfer none): the tree node corresponding to
931
 *          the key, or %NULL if the key was not found
932
 *
933
 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
934
 */
935
static QTreeNode *
936
q_tree_lookup_node(QTree         *tree,
937
                   gconstpointer  key)
938
{
939
    g_return_val_if_fail(tree != NULL, NULL);
940

941
    return q_tree_find_node(tree, key);
942
}
943

944
/**
945
 * q_tree_lookup:
946
 * @tree: a #QTree
947
 * @key: the key to look up
948
 *
949
 * Gets the value corresponding to the given key. Since a #QTree is
950
 * automatically balanced as key/value pairs are added, key lookup
951
 * is O(log n) (where n is the number of key/value pairs in the tree).
952
 *
953
 * Returns: the value corresponding to the key, or %NULL
954
 *     if the key was not found
955
 */
956
gpointer
957
q_tree_lookup(QTree         *tree,
958
              gconstpointer  key)
959
{
960
    QTreeNode *node;
961

962
    node = q_tree_lookup_node(tree, key);
963

964
    return node ? node->value : NULL;
965
}
966

967
/**
968
 * q_tree_lookup_extended:
969
 * @tree: a #QTree
970
 * @lookup_key: the key to look up
971
 * @orig_key: (out) (optional) (nullable): returns the original key
972
 * @value: (out) (optional) (nullable): returns the value associated with
973
 *         the key
974
 *
975
 * Looks up a key in the #QTree, returning the original key and the
976
 * associated value. This is useful if you need to free the memory
977
 * allocated for the original key, for example before calling
978
 * q_tree_remove().
979
 *
980
 * Returns: %TRUE if the key was found in the #QTree
981
 */
982
gboolean
983
q_tree_lookup_extended(QTree         *tree,
984
                       gconstpointer  lookup_key,
985
                       gpointer      *orig_key,
986
                       gpointer      *value)
987
{
988
    QTreeNode *node;
989

990
    g_return_val_if_fail(tree != NULL, FALSE);
991

992
    node = q_tree_find_node(tree, lookup_key);
993

994
    if (node) {
995
        if (orig_key) {
996
            *orig_key = node->key;
997
        }
998
        if (value) {
999
            *value = node->value;
1000
        }
1001
        return TRUE;
1002
    } else {
1003
        return FALSE;
1004
    }
1005
}
1006

1007
/**
1008
 * q_tree_foreach:
1009
 * @tree: a #QTree
1010
 * @func: the function to call for each node visited.
1011
 *     If this function returns %TRUE, the traversal is stopped.
1012
 * @user_data: user data to pass to the function
1013
 *
1014
 * Calls the given function for each of the key/value pairs in the #QTree.
1015
 * The function is passed the key and value of each pair, and the given
1016
 * @data parameter. The tree is traversed in sorted order.
1017
 *
1018
 * The tree may not be modified while iterating over it (you can't
1019
 * add/remove items). To remove all items matching a predicate, you need
1020
 * to add each item to a list in your #GTraverseFunc as you walk over
1021
 * the tree, then walk the list and remove each item.
1022
 */
1023
void
1024
q_tree_foreach(QTree         *tree,
1025
               GTraverseFunc  func,
1026
               gpointer       user_data)
1027
{
1028
    QTreeNode *node;
1029

1030
    g_return_if_fail(tree != NULL);
1031

1032
    if (!tree->root) {
1033
        return;
1034
    }
1035

1036
    node = q_tree_node_first(tree);
1037

1038
    while (node) {
1039
        if ((*func)(node->key, node->value, user_data)) {
1040
            break;
1041
        }
1042

1043
        node = q_tree_node_next(node);
1044
    }
1045
}
1046

1047
/**
1048
 * q_tree_search_node:
1049
 * @tree: a #QTree
1050
 * @search_func: a function used to search the #QTree
1051
 * @user_data: the data passed as the second argument to @search_func
1052
 *
1053
 * Searches a #QTree using @search_func.
1054
 *
1055
 * The @search_func is called with a pointer to the key of a key/value
1056
 * pair in the tree, and the passed in @user_data. If @search_func returns
1057
 * 0 for a key/value pair, then the corresponding node is returned as
1058
 * the result of q_tree_search(). If @search_func returns -1, searching
1059
 * will proceed among the key/value pairs that have a smaller key; if
1060
 * @search_func returns 1, searching will proceed among the key/value
1061
 * pairs that have a larger key.
1062
 *
1063
 * Returns: (nullable) (transfer none): the node corresponding to the
1064
 *          found key, or %NULL if the key was not found
1065
 *
1066
 * Since: 2.68 in GLib. Internal in Qtree, i.e. not in the public API.
1067
 */
1068
static QTreeNode *
1069
q_tree_search_node(QTree         *tree,
1070
                   GCompareFunc   search_func,
1071
                   gconstpointer  user_data)
1072
{
1073
    g_return_val_if_fail(tree != NULL, NULL);
1074

1075
    if (!tree->root) {
1076
        return NULL;
1077
    }
1078

1079
    return q_tree_node_search(tree->root, search_func, user_data);
1080
}
1081

1082
/**
1083
 * q_tree_search:
1084
 * @tree: a #QTree
1085
 * @search_func: a function used to search the #QTree
1086
 * @user_data: the data passed as the second argument to @search_func
1087
 *
1088
 * Searches a #QTree using @search_func.
1089
 *
1090
 * The @search_func is called with a pointer to the key of a key/value
1091
 * pair in the tree, and the passed in @user_data. If @search_func returns
1092
 * 0 for a key/value pair, then the corresponding value is returned as
1093
 * the result of q_tree_search(). If @search_func returns -1, searching
1094
 * will proceed among the key/value pairs that have a smaller key; if
1095
 * @search_func returns 1, searching will proceed among the key/value
1096
 * pairs that have a larger key.
1097
 *
1098
 * Returns: the value corresponding to the found key, or %NULL
1099
 *     if the key was not found
1100
 */
1101
gpointer
1102
q_tree_search(QTree         *tree,
1103
              GCompareFunc   search_func,
1104
              gconstpointer  user_data)
1105
{
1106
    QTreeNode *node;
1107

1108
    node = q_tree_search_node(tree, search_func, user_data);
1109

1110
    return node ? node->value : NULL;
1111
}
1112

1113
/**
1114
 * q_tree_height:
1115
 * @tree: a #QTree
1116
 *
1117
 * Gets the height of a #QTree.
1118
 *
1119
 * If the #QTree contains no nodes, the height is 0.
1120
 * If the #QTree contains only one root node the height is 1.
1121
 * If the root node has children the height is 2, etc.
1122
 *
1123
 * Returns: the height of @tree
1124
 */
1125
gint
1126
q_tree_height(QTree *tree)
1127
{
1128
    QTreeNode *node;
1129
    gint height;
1130

1131
    g_return_val_if_fail(tree != NULL, 0);
1132

1133
    if (!tree->root) {
1134
        return 0;
1135
    }
1136

1137
    height = 0;
1138
    node = tree->root;
1139

1140
    while (1) {
1141
        height += 1 + MAX(node->balance, 0);
1142

1143
        if (!node->left_child) {
1144
            return height;
1145
        }
1146

1147
        node = node->left;
1148
    }
1149
}
1150

1151
/**
1152
 * q_tree_nnodes:
1153
 * @tree: a #QTree
1154
 *
1155
 * Gets the number of nodes in a #QTree.
1156
 *
1157
 * Returns: the number of nodes in @tree
1158
 */
1159
gint
1160
q_tree_nnodes(QTree *tree)
1161
{
1162
    g_return_val_if_fail(tree != NULL, 0);
1163

1164
    return tree->nnodes;
1165
}
1166

1167
static QTreeNode *
1168
q_tree_node_balance(QTreeNode *node)
1169
{
1170
    if (node->balance < -1) {
1171
        if (node->left->balance > 0) {
1172
            node->left = q_tree_node_rotate_left(node->left);
1173
        }
1174
        node = q_tree_node_rotate_right(node);
1175
    } else if (node->balance > 1) {
1176
        if (node->right->balance < 0) {
1177
            node->right = q_tree_node_rotate_right(node->right);
1178
        }
1179
        node = q_tree_node_rotate_left(node);
1180
    }
1181

1182
    return node;
1183
}
1184

1185
static QTreeNode * QEMU_DISABLE_CFI
1186
q_tree_find_node(QTree        *tree,
1187
                 gconstpointer key)
1188
{
1189
    QTreeNode *node;
1190
    gint cmp;
1191

1192
    node = tree->root;
1193
    if (!node) {
1194
        return NULL;
1195
    }
1196

1197
    while (1) {
1198
        cmp = tree->key_compare(key, node->key, tree->key_compare_data);
1199
        if (cmp == 0) {
1200
            return node;
1201
        } else if (cmp < 0) {
1202
            if (!node->left_child) {
1203
                return NULL;
1204
            }
1205

1206
            node = node->left;
1207
        } else {
1208
            if (!node->right_child) {
1209
                return NULL;
1210
            }
1211

1212
            node = node->right;
1213
        }
1214
    }
1215
}
1216

1217
static QTreeNode *
1218
q_tree_node_search(QTreeNode     *node,
1219
                   GCompareFunc   search_func,
1220
                   gconstpointer  data)
1221
{
1222
    gint dir;
1223

1224
    if (!node) {
1225
        return NULL;
1226
    }
1227

1228
    while (1) {
1229
        dir = (*search_func)(node->key, data);
1230
        if (dir == 0) {
1231
            return node;
1232
        } else if (dir < 0) {
1233
            if (!node->left_child) {
1234
                return NULL;
1235
            }
1236

1237
            node = node->left;
1238
        } else {
1239
            if (!node->right_child) {
1240
                return NULL;
1241
            }
1242

1243
            node = node->right;
1244
        }
1245
    }
1246
}
1247

1248
static QTreeNode *
1249
q_tree_node_rotate_left(QTreeNode *node)
1250
{
1251
    QTreeNode *right;
1252
    gint a_bal;
1253
    gint b_bal;
1254

1255
    right = node->right;
1256

1257
    if (right->left_child) {
1258
        node->right = right->left;
1259
    } else {
1260
        node->right_child = FALSE;
1261
        right->left_child = TRUE;
1262
    }
1263
    right->left = node;
1264

1265
    a_bal = node->balance;
1266
    b_bal = right->balance;
1267

1268
    if (b_bal <= 0) {
1269
        if (a_bal >= 1) {
1270
            right->balance = b_bal - 1;
1271
        } else {
1272
            right->balance = a_bal + b_bal - 2;
1273
        }
1274
        node->balance = a_bal - 1;
1275
    } else {
1276
        if (a_bal <= b_bal) {
1277
            right->balance = a_bal - 2;
1278
        } else {
1279
            right->balance = b_bal - 1;
1280
        }
1281
        node->balance = a_bal - b_bal - 1;
1282
    }
1283

1284
    return right;
1285
}
1286

1287
static QTreeNode *
1288
q_tree_node_rotate_right(QTreeNode *node)
1289
{
1290
    QTreeNode *left;
1291
    gint a_bal;
1292
    gint b_bal;
1293

1294
    left = node->left;
1295

1296
    if (left->right_child) {
1297
        node->left = left->right;
1298
    } else {
1299
        node->left_child = FALSE;
1300
        left->right_child = TRUE;
1301
    }
1302
    left->right = node;
1303

1304
    a_bal = node->balance;
1305
    b_bal = left->balance;
1306

1307
    if (b_bal <= 0) {
1308
        if (b_bal > a_bal) {
1309
            left->balance = b_bal + 1;
1310
        } else {
1311
            left->balance = a_bal + 2;
1312
        }
1313
        node->balance = a_bal - b_bal + 1;
1314
    } else {
1315
        if (a_bal <= -1) {
1316
            left->balance = b_bal + 1;
1317
        } else {
1318
            left->balance = a_bal + b_bal + 2;
1319
        }
1320
        node->balance = a_bal + 1;
1321
    }
1322

1323
    return left;
1324
}
1325

1326
#ifdef Q_TREE_DEBUG
1327
static gint
1328
q_tree_node_height(QTreeNode *node)
1329
{
1330
    gint left_height;
1331
    gint right_height;
1332

1333
    if (node) {
1334
        left_height = 0;
1335
        right_height = 0;
1336

1337
        if (node->left_child) {
1338
            left_height = q_tree_node_height(node->left);
1339
        }
1340

1341
        if (node->right_child) {
1342
            right_height = q_tree_node_height(node->right);
1343
        }
1344

1345
        return MAX(left_height, right_height) + 1;
1346
    }
1347

1348
    return 0;
1349
}
1350

1351
static void q_tree_node_check(QTreeNode *node)
1352
{
1353
    gint left_height;
1354
    gint right_height;
1355
    gint balance;
1356
    QTreeNode *tmp;
1357

1358
    if (node) {
1359
        if (node->left_child) {
1360
            tmp = q_tree_node_previous(node);
1361
            g_assert(tmp->right == node);
1362
        }
1363

1364
        if (node->right_child) {
1365
            tmp = q_tree_node_next(node);
1366
            g_assert(tmp->left == node);
1367
        }
1368

1369
        left_height = 0;
1370
        right_height = 0;
1371

1372
        if (node->left_child) {
1373
            left_height = q_tree_node_height(node->left);
1374
        }
1375
        if (node->right_child) {
1376
            right_height = q_tree_node_height(node->right);
1377
        }
1378

1379
        balance = right_height - left_height;
1380
        g_assert(balance == node->balance);
1381

1382
        if (node->left_child) {
1383
            q_tree_node_check(node->left);
1384
        }
1385
        if (node->right_child) {
1386
            q_tree_node_check(node->right);
1387
        }
1388
    }
1389
}
1390
#endif
1391