2 * This file is part of the Palacios Virtual Machine Monitor developed
3 * by the V3VEE Project with funding from the United States National
4 * Science Foundation and the Department of Energy.
6 * The V3VEE Project is a joint project between Northwestern University
7 * and the University of New Mexico. You can find out more at
10 * Copyright (c) 2008, Jack Lange <jarusl@cs.northwestern.edu>
11 * Copyright (c) 2008, The V3VEE Project <http://www.v3vee.org>
12 * All rights reserved.
14 * Author: Jack Lange <jarusl@cs.northwestern.edu>
16 * This is free software. You are permitted to use,
17 * redistribute, and modify it as specified in the file "V3VEE_LICENSE".
21 #include <palacios/vmm_multitree.h>
22 #include <palacios/vmm_string.h>
24 #include <palacios/vmm_rbtree.h>
27 struct v3_mtree * __insert_mtree_node(struct v3_mtree * root, struct v3_mtree * node) {
28 struct rb_node ** p = &(root->child.rb_node);
29 struct rb_node * parent = NULL;
30 struct v3_mtree * tmp_node;
35 tmp_node = rb_entry(parent, struct v3_mtree, tree_node);
37 ret = strcmp(node->name, tmp_node->name);
48 rb_link_node(&(node->tree_node), parent, p);
55 struct v3_mtree * v3_mtree_create_node(struct v3_mtree * root, char * name) {
56 struct v3_mtree * node = (struct v3_mtree *)V3_Malloc(sizeof(struct v3_mtree));
57 struct v3_mtree * ret = NULL;
60 PrintDebug(VM_NONE, VCORE_NONE, "Creating Node %s\n", name);
64 PrintError(VM_NONE, VCORE_NONE, "Cannot allocate multitree node\n");
68 memset(node, 0, sizeof(struct v3_mtree));
69 strncpy(node->name, name, V3_MTREE_NAME_LEN);
70 node->name[V3_MTREE_NAME_LEN-1] = 0;
72 if ((ret = __insert_mtree_node(root, node))) {
73 PrintError(VM_NONE, VCORE_NONE, "Insertion failure\n");
78 PrintDebug(VM_NONE, VCORE_NONE, "Node (%s)=%p, root=%p, root->child=%p\n", node->name, node, root, root->child.rb_node);
80 v3_rb_insert_color(&(node->tree_node), &(root->child));
82 PrintDebug(VM_NONE, VCORE_NONE, "balanced\n");
88 struct v3_mtree * v3_mtree_create_subtree(struct v3_mtree * root, char * name) {
89 struct v3_mtree * node = NULL;
91 PrintDebug(VM_NONE, VCORE_NONE, "Creating Subtree %s\n", name);
92 node = v3_mtree_create_node(root, name);
104 struct v3_mtree * v3_mtree_create_value(struct v3_mtree * root, char * name,
105 uint64_t size, void * value) {
106 struct v3_mtree * node = NULL;
108 PrintDebug(VM_NONE, VCORE_NONE, "Creating value %s\n", name);
109 node = v3_mtree_create_node(root, name);
123 struct v3_mtree * v3_mtree_find_node(struct v3_mtree * root, char * name) {
124 struct rb_node * n = root->child.rb_node;
125 struct v3_mtree * tmp_node = NULL;
127 if (root->subtree == 0) {
128 PrintError(VM_NONE, VCORE_NONE, "Searching for node on a non-root mtree (search=%s), root=%s\n", name, root->name);
134 tmp_node = rb_entry(n, struct v3_mtree, tree_node);
135 ret = strcmp(tmp_node->name, name);
139 } else if (ret > 0) {
150 struct v3_mtree * v3_mtree_find_subtree(struct v3_mtree * root, char * name) {
151 struct v3_mtree * node = v3_mtree_find_node(root, name);
153 if (node->subtree == 0) {
161 struct v3_mtree * v3_mtree_find_value(struct v3_mtree * root, char * name) {
162 struct v3_mtree * node= v3_mtree_find_node(root, name);
164 if (node->subtree == 1) {
172 struct v3_mtree * v3_mtree_first_child(struct v3_mtree * root) {
173 struct rb_node * node = v3_rb_first(&(root->child));
179 return rb_entry(node, struct v3_mtree, tree_node);
183 struct v3_mtree * v3_mtree_next_node(struct v3_mtree * node) {
184 struct rb_node * next_node = v3_rb_next(&(node->tree_node));
186 if (next_node == NULL) {
189 return rb_entry(next_node, struct v3_mtree, tree_node);