palacios/src/palacios/vmm_multitree.c

   1 /*
   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.
   5  *
   6  * The V3VEE Project is a joint project between Northwestern University
   7  * and the University of New Mexico.  You can find out more at
   8  * http://www.v3vee.org
   9  *
  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.
  13  *
  14  * Author: Jack Lange <jarusl@cs.northwestern.edu>
  15  *
  16  * This is free software.  You are permitted to use,
  17  * redistribute, and modify it as specified in the file "V3VEE_LICENSE".
  18  */
  19
  20
  21 #include <palacios/vmm_multitree.h>
  22 #include <palacios/vmm_string.h>
  23
  24 #include <palacios/vmm_rbtree.h>
  25
  26 static inline
  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;
  31
  32     while (*p) {
  33         int ret = 0;
  34         parent = *p;
  35         tmp_node = rb_entry(parent, struct v3_mtree, tree_node);
  36
  37         ret = strcmp(node->name, tmp_node->name);
  38
  39         if (ret < 0) {
  40             p = &(*p)->rb_left;
  41         } else if (ret > 0) {
  42             p = &(*p)->rb_right;
  43         } else {
  44             return tmp_node;
  45         }
  46     }
  47
  48     rb_link_node(&(node->tree_node), parent, p);
  49
  50     return NULL;
  51 }
  52
  53
  54
  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;
  58
  59
  60     PrintDebug(VM_NONE, VCORE_NONE, "Creating Node %s\n", name);
  61
  62
  63     if (!node) {
  64         PrintError(VM_NONE, VCORE_NONE, "Cannot allocate multitree node\n");
  65         return NULL;
  66     }
  67
  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;
  71
  72     if ((ret = __insert_mtree_node(root, node))) {
  73         PrintError(VM_NONE, VCORE_NONE, "Insertion failure\n");
  74         V3_Free(node);
  75         return NULL;
  76     }
  77
  78     PrintDebug(VM_NONE, VCORE_NONE, "Node (%s)=%p, root=%p, root->child=%p\n", node->name, node, root, root->child.rb_node);
  79
  80     v3_rb_insert_color(&(node->tree_node), &(root->child));
  81
  82     PrintDebug(VM_NONE, VCORE_NONE, "balanced\n");
  83
  84     return node;
  85 }
  86
  87
  88 struct v3_mtree * v3_mtree_create_subtree(struct v3_mtree * root, char * name) {
  89     struct v3_mtree * node = NULL;
  90
  91     PrintDebug(VM_NONE, VCORE_NONE, "Creating Subtree %s\n", name);
  92     node = v3_mtree_create_node(root, name);
  93
  94     if (node == NULL) {
  95         return NULL;
  96     }
  97
  98     node->subtree = 1;
  99
 100     return node;
 101 }
 102
 103
 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;
 107
 108     PrintDebug(VM_NONE, VCORE_NONE, "Creating value %s\n", name);
 109     node = v3_mtree_create_node(root, name);
 110
 111     if (node == NULL) {
 112         return NULL;
 113     }
 114
 115     node->size = size;
 116     node->value = value;
 117
 118     return node;
 119 }
 120
 121
 122
 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;
 126
 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);
 129         return NULL;
 130     }
 131
 132     while (n) {
 133         int ret = 0;
 134         tmp_node = rb_entry(n, struct v3_mtree, tree_node);
 135         ret = strcmp(tmp_node->name, name);
 136
 137         if (ret < 0) {
 138             n = n->rb_left;
 139         } else if (ret > 0) {
 140             n = n->rb_right;
 141         } else {
 142             return tmp_node;
 143         }
 144     }
 145
 146     return NULL;
 147 }
 148
 149
 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);
 152
 153     if (node->subtree == 0) {
 154         return NULL;
 155     }
 156
 157     return node;
 158 }
 159
 160
 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);
 163
 164     if (node->subtree == 1) {
 165         return NULL;
 166     }
 167
 168     return node;
 169 }
 170
 171
 172 struct v3_mtree * v3_mtree_first_child(struct v3_mtree * root) {
 173     struct rb_node * node = v3_rb_first(&(root->child));
 174
 175     if (node == NULL) {
 176         return NULL;
 177     }
 178
 179     return rb_entry(node, struct v3_mtree, tree_node);
 180 }
 181
 182
 183 struct v3_mtree * v3_mtree_next_node(struct v3_mtree * node) {
 184     struct rb_node * next_node = v3_rb_next(&(node->tree_node));
 185
 186     if (next_node == NULL) {
 187         return NULL;
 188     }
 189     return rb_entry(next_node, struct v3_mtree, tree_node);
 190 }