uspace/lib/bithenge/src/tree.c

   1 /*
   2  * Copyright (c) 2012 Sean Bartell
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  * - Redistributions in binary form must reproduce the above copyright
  12  *   notice, this list of conditions and the following disclaimer in the
  13  *   documentation and/or other materials provided with the distribution.
  14  * - The name of the author may not be used to endorse or promote products
  15  *   derived from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /** @addtogroup bithenge
  30  * @{
  31  */
  32 /**
  33  * @file
  34  * Trees and nodes.
  35  */
  36
  37 #include <errno.h>
  38 #include <stdlib.h>
  39 #include <bithenge/blob.h>
  40 #include <bithenge/os.h>
  41 #include <bithenge/tree.h>
  42
  43 static void blob_destroy(bithenge_node_t *base)
  44 {
  45         bithenge_blob_t *self = bithenge_node_as_blob(base);
  46         assert(self->base.blob_ops);
  47         self->base.blob_ops->destroy(self);
  48 }
  49
  50 static void node_destroy(bithenge_node_t *self)
  51 {
  52         switch (bithenge_node_type(self)) {
  53         case BITHENGE_NODE_BLOB:
  54                 blob_destroy(self);
  55                 return;
  56         case BITHENGE_NODE_STRING:
  57                 if (self->string_value.needs_free)
  58                         free((void *)self->string_value.ptr);
  59                 break;
  60         case BITHENGE_NODE_INTERNAL:
  61                 self->internal_ops->destroy(self);
  62                 return;
  63         case BITHENGE_NODE_BOOLEAN:
  64                 return; /* The boolean nodes are allocated statically below. */
  65         case BITHENGE_NODE_INTEGER: /* pass-through */
  66                 break;
  67         }
  68         free(self);
  69 }
  70
  71 /** Decrement a node's reference count and free it if appropriate.
  72  * @memberof bithenge_node_t
  73  * @param node The node to dereference, or NULL. */
  74 void bithenge_node_dec_ref(bithenge_node_t *node)
  75 {
  76         if (!node)
  77                 return;
  78         assert (node->refs > 0);
  79         if (--node->refs == 0)
  80                 node_destroy(node);
  81 }
  82
  83 typedef struct {
  84         bithenge_node_t *key;
  85         bithenge_node_t **out;
  86 } get_for_each_data_t;
  87
  88 static int get_for_each_func(bithenge_node_t *key, bithenge_node_t *value,
  89     void *raw_data)
  90 {
  91         get_for_each_data_t *data = (get_for_each_data_t *)raw_data;
  92         bool equal;
  93         int rc = bithenge_node_equal(&equal, key, data->key);
  94         bithenge_node_dec_ref(key);
  95         if (rc != EOK)
  96                 return rc;
  97         if (equal) {
  98                 *data->out = value;
  99                 return EEXIST;
 100         }
 101         bithenge_node_dec_ref(value);
 102         return EOK;
 103 }
 104
 105 /** Get a child of a node. Takes ownership of the key. If the node does not
 106  * provide this function, for_each will be used as an alternative, which may be
 107  * very slow. Also works for blob nodes to find the byte value at a given
 108  * index.
 109  * @memberof bithenge_node_t
 110  * @param self The internal/blob node to find a child of.
 111  * @param key The key to search for.
 112  * @param[out] out Holds the found node.
 113  * @return EOK on success, ENOENT if not found, or another error code from
 114  * errno.h. */
 115 int bithenge_node_get(bithenge_node_t *self, bithenge_node_t *key,
 116     bithenge_node_t **out)
 117 {
 118         if (self->type == BITHENGE_NODE_BLOB) {
 119                 if (bithenge_node_type(key) != BITHENGE_NODE_INTEGER) {
 120                         bithenge_node_dec_ref(key);
 121                         return ENOENT;
 122                 }
 123                 bithenge_int_t offset = bithenge_integer_node_value(key);
 124                 bithenge_node_dec_ref(key);
 125                 uint8_t byte;
 126                 aoff64_t size = 1;
 127                 int rc = bithenge_blob_read(bithenge_node_as_blob(self),
 128                     offset, (char *)&byte, &size);
 129                 if (rc != EOK)
 130                         return rc;
 131                 if (size != 1)
 132                         return ENOENT;
 133
 134                 return bithenge_new_integer_node(out, byte);
 135         }
 136
 137         assert(self->type == BITHENGE_NODE_INTERNAL);
 138         if (self->internal_ops->get)
 139                 return self->internal_ops->get(self, key, out);
 140         *out = NULL;
 141         get_for_each_data_t data = {key, out};
 142         int rc = bithenge_node_for_each(self, get_for_each_func, &data);
 143         bithenge_node_dec_ref(key);
 144         if (rc == EEXIST && *out)
 145                 return EOK;
 146         if (rc == EOK)
 147                 rc = ENOENT;
 148         bithenge_node_dec_ref(*out);
 149         return rc;
 150 }
 151
 152 /** Initialize an internal node.
 153  * @memberof bithenge_node_t
 154  * @param[out] self The node.
 155  * @param[in] ops The operations provided.
 156  * @return EOK on success or an error code from errno.h. */
 157 int bithenge_init_internal_node(bithenge_node_t *self,
 158     const bithenge_internal_node_ops_t *ops)
 159 {
 160         self->type = BITHENGE_NODE_INTERNAL;
 161         self->refs = 1;
 162         self->internal_ops = ops;
 163         return EOK;
 164 }
 165
 166 static void internal_node_indestructible(bithenge_node_t *self)
 167 {
 168         assert(false);
 169 }
 170
 171 static int empty_internal_node_for_each(bithenge_node_t *base,
 172     bithenge_for_each_func_t func, void *data)
 173 {
 174         return EOK;
 175 }
 176
 177 static int empty_internal_node_get(bithenge_node_t *self, bithenge_node_t *key,
 178     bithenge_node_t **out)
 179 {
 180         return ENOENT;
 181 }
 182
 183 static const bithenge_internal_node_ops_t empty_internal_node_ops = {
 184         .for_each = empty_internal_node_for_each,
 185         .get = empty_internal_node_get,
 186         .destroy = internal_node_indestructible,
 187 };
 188
 189 static bithenge_node_t empty_internal_node = {
 190         BITHENGE_NODE_INTERNAL,
 191         1,
 192         { .internal_ops = &empty_internal_node_ops },
 193 };
 194
 195 /** Create an empty internal node.
 196  * @param[out] out Holds the created node.
 197  * @return EOK on success or an error code from errno.h. */
 198 int bithenge_new_empty_internal_node(bithenge_node_t **out)
 199 {
 200         if (bithenge_should_fail())
 201                 return ENOMEM;
 202         bithenge_node_inc_ref(&empty_internal_node);
 203         *out = &empty_internal_node;
 204         return EOK;
 205 }
 206
 207 typedef struct
 208 {
 209         bithenge_node_t base;
 210         bithenge_node_t **nodes;
 211         bithenge_int_t len;
 212         bool needs_free;
 213 } simple_internal_node_t;
 214
 215 static simple_internal_node_t *node_as_simple(bithenge_node_t *node)
 216 {
 217         return (simple_internal_node_t *)node;
 218 }
 219
 220 static bithenge_node_t *simple_as_node(simple_internal_node_t *node)
 221 {
 222         return &node->base;
 223 }
 224
 225 static int simple_internal_node_for_each(bithenge_node_t *base,
 226     bithenge_for_each_func_t func, void *data)
 227 {
 228         int rc;
 229         simple_internal_node_t *self = node_as_simple(base);
 230         for (bithenge_int_t i = 0; i < self->len; i++) {
 231                 bithenge_node_inc_ref(self->nodes[2*i+0]);
 232                 bithenge_node_inc_ref(self->nodes[2*i+1]);
 233                 rc = func(self->nodes[2*i+0], self->nodes[2*i+1], data);
 234                 if (rc != EOK)
 235                         return rc;
 236         }
 237         return EOK;
 238 }
 239
 240 static void simple_internal_node_destroy(bithenge_node_t *base)
 241 {
 242         simple_internal_node_t *self = node_as_simple(base);
 243         for (bithenge_int_t i = 0; i < 2 * self->len; i++)
 244                 bithenge_node_dec_ref(self->nodes[i]);
 245         if (self->needs_free)
 246                 free(self->nodes);
 247         free(self);
 248 }
 249
 250 static bithenge_internal_node_ops_t simple_internal_node_ops = {
 251         .for_each = simple_internal_node_for_each,
 252         .destroy = simple_internal_node_destroy,
 253 };
 254
 255 /** Create an internal node from a set of keys and values. This function takes
 256  * ownership of a reference to the key and value nodes, and optionally the
 257  * array @a nodes.
 258  * @memberof bithenge_node_t
 259  * @param[out] out Stores the created internal node.
 260  * @param nodes The array of key-value pairs. Keys are stored at even indices
 261  * and values are stored at odd indices.
 262  * @param len The number of key-value pairs in the node array.
 263  * @param needs_free If true, when the internal node is destroyed it will free
 264  * the nodes array rather than just dereferencing each node inside it.
 265  * @return EOK on success or an error code from errno.h. */
 266 int bithenge_new_simple_internal_node(bithenge_node_t **out,
 267     bithenge_node_t **nodes, bithenge_int_t len, bool needs_free)
 268 {
 269         int rc;
 270         assert(out);
 271         simple_internal_node_t *self = malloc(sizeof(*self));
 272         if (!self) {
 273                 rc = ENOMEM;
 274                 goto error;
 275         }
 276         rc = bithenge_init_internal_node(simple_as_node(self),
 277             &simple_internal_node_ops);
 278         if (rc != EOK)
 279                 goto error;
 280         self->nodes = nodes;
 281         self->len = len;
 282         self->needs_free = needs_free;
 283         *out = simple_as_node(self);
 284         return EOK;
 285 error:
 286         for (bithenge_int_t i = 0; i < 2 * len; i++)
 287                 bithenge_node_dec_ref(nodes[i]);
 288         if (needs_free)
 289                 free(nodes);
 290         free(self);
 291         return rc;
 292 }
 293
 294 static bithenge_node_t false_node = { BITHENGE_NODE_BOOLEAN, 1, .boolean_value = false };
 295 static bithenge_node_t true_node = { BITHENGE_NODE_BOOLEAN, 1, .boolean_value = true };
 296
 297 /** Create a boolean node.
 298  * @memberof bithenge_node_t
 299  * @param[out] out Stores the created boolean node.
 300  * @param value The value for the node to hold.
 301  * @return EOK on success or an error code from errno.h. */
 302 int bithenge_new_boolean_node(bithenge_node_t **out, bool value)
 303 {
 304         assert(out);
 305         if (bithenge_should_fail())
 306                 return ENOMEM;
 307         *out = value ? &true_node : &false_node;
 308         (*out)->refs++;
 309         return EOK;
 310 }
 311
 312 /** Create an integer node.
 313  * @memberof bithenge_node_t
 314  * @param[out] out Stores the created integer node.
 315  * @param value The value for the node to hold.
 316  * @return EOK on success or an error code from errno.h. */
 317 int bithenge_new_integer_node(bithenge_node_t **out, bithenge_int_t value)
 318 {
 319         assert(out);
 320         bithenge_node_t *self = malloc(sizeof(*self));
 321         if (!self)
 322                 return ENOMEM;
 323         self->type = BITHENGE_NODE_INTEGER;
 324         self->refs = 1;
 325         self->integer_value = value;
 326         *out = self;
 327         return EOK;
 328 }
 329
 330 /** Create a string node.
 331  * @memberof bithenge_node_t
 332  * @param[out] out Stores the created string node. On error, this is unchanged.
 333  * @param value The value for the node to hold.
 334  * @param needs_free Whether the string should be freed when the node is
 335  * destroyed.
 336  * @return EOK on success or an error code from errno.h. */
 337 int bithenge_new_string_node(bithenge_node_t **out, const char *value, bool needs_free)
 338 {
 339         assert(out);
 340         bithenge_node_t *self = malloc(sizeof(*self));
 341         if (!self) {
 342                 if (needs_free)
 343                         free((void *)value);
 344                 return ENOMEM;
 345         }
 346         self->type = BITHENGE_NODE_STRING;
 347         self->refs = 1;
 348         self->string_value.ptr = value;
 349         self->string_value.needs_free = needs_free;
 350         *out = self;
 351         return EOK;
 352 }
 353
 354 /** Check whether the contents of two nodes are equal. Does not yet work for
 355  * internal nodes. Takes ownership of nothing.
 356  * @memberof bithenge_node_t
 357  * @param[out] out Holds whether the nodes are equal.
 358  * @param a, b Nodes to compare.
 359  * @return EOK on success or an error code from errno.h.
 360  * @todo Add support for internal nodes. */
 361 int bithenge_node_equal(bool *out, bithenge_node_t *a, bithenge_node_t *b)
 362 {
 363         if (a->type != b->type) {
 364                 *out = false;
 365                 return EOK;
 366         }
 367         switch (a->type) {
 368         case BITHENGE_NODE_INTERNAL:
 369                 *out = false;
 370                 return EOK;
 371         case BITHENGE_NODE_BOOLEAN:
 372                 *out = a->boolean_value == b->boolean_value;
 373                 return EOK;
 374         case BITHENGE_NODE_INTEGER:
 375                 *out = a->integer_value == b->integer_value;
 376                 return EOK;
 377         case BITHENGE_NODE_STRING:
 378                 *out = !str_cmp(a->string_value.ptr, b->string_value.ptr);
 379                 return EOK;
 380         case BITHENGE_NODE_BLOB:
 381                 return bithenge_blob_equal(out, bithenge_node_as_blob(a),
 382                     bithenge_node_as_blob(b));
 383         }
 384         return EINVAL;
 385 }
 386
 387 /** @}
 388  */