1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
#pragma once
// vm_tree.c
//
// AUTHOR NOTE:
//
// a great deal of this code is lifted and adapted straight from wikipedia at
// https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
//
// i reserve no rights under copyright law to this material, but i agree to be
// bound by the terms of the Creative Commons Share-Alike by Attribution license
//
// if any of the following is found to be in violation please contact the author
// at ada.christine.18+sophia _at_ gmail _dot_ com
//
// -Ada Christine Fontaine, 1/1/2022
//
// LICENSE NOTIFICATION
//
// THE WORK (AS DEFINED BELOW) IS PROVIDED UNDER THE TERMS OF THIS CREATIVE
// COMMONS PUBLIC LICENSE ("CCPL" OR "LICENSE"). THE WORK IS PROTECTED BY
// COPYRIGHT AND/OR OTHER APPLICABLE LAW. ANY USE OF THE WORK OTHER THAN AS
// AUTHORIZED UNDER THIS LICENSE OR COPYRIGHT LAW IS PROHIBITED.
// BY EXERCISING ANY RIGHTS TO THE WORK PROVIDED HERE, YOU ACCEPT AND AGREE TO
// BE BOUND BY THE TERMS OF THIS LICENSE. TO THE EXTENT THIS LICENSE MAY BE
// CONSIDERED TO BE A CONTRACT, THE LICENSOR GRANTS YOU THE RIGHTS CONTAINED
// HERE IN CONSIDERATION OF YOUR ACCEPTANCE OF SUCH TERMS AND CONDITIONS.
//
// The full text of the CC-BY-SA 3.0 license can be found here:
// https://en.wikipedia.org/wiki/Wikipedia:Text_of_Creative_Commons_Attribution-ShareAlike_3.0_Unported_License
#include <stdint.h>
#include <stddef.h>
enum vm_tree_direction
{
LEFT,
RIGHT
};
enum vm_tree_color
{
RED,
BLACK
};
struct vm_tree_key
{
uintptr_t address;
size_t size;
};
struct vm_object;
struct vm_tree_node
{
// red-black binary tree data
struct vm_tree_node *parent;
struct vm_tree_node *child[2];
enum vm_tree_color color;
struct vm_tree_key key;
// object that owns this node
struct vm_object *object;
};
struct vm_tree
{
struct vm_tree_node *root;
};
void vmt_insert(
struct vm_tree *,
struct vm_tree_node *,
struct vm_tree_node *,
enum vm_tree_direction);
enum vm_tree_direction vmn_child_direction(
struct vm_tree_node *n,
struct vm_tree_node *p);
void vmt_init_node(
struct vm_tree *tree,
struct vm_tree_node *node,
struct vm_object *object,
void *base,
void *head);
void vmt_delete(struct vm_tree*, struct vm_tree_node*);
struct vm_tree_node *vmt_search_key(struct vm_tree *, struct vm_tree_key *);
struct vm_tree_node *vmn_predecessor_key(
struct vm_tree_node *,
struct vm_tree_key *);
struct vm_tree_node *vmn_successor_key(
struct vm_tree_node *,
struct vm_tree_key *);
struct vm_tree_node *vmn_min(struct vm_tree_node *node);
struct vm_tree_node *vmn_max(struct vm_tree_node *node);
struct vm_object *vmt_get_object(struct vm_tree *, void *address);
|
