tree.c File Reference

String-indexed search tree for Commotion object system. More...

#include <stdlib.h>
#include <stddef.h>
#include <stdbool.h>
#include <stdint.h>
#include "debug.h"
#include "obj.h"
#include "list.h"
#include "tree.h"
#include "util.h"
#include "extern/halloc.h"

Macros

#define _DEFINE_TREE(L)
 

Functions

 _DEFINE_TREE (16)
 
 _DEFINE_TREE (32)
 
_treenode_tco_tree_root (const co_obj_t *tree)
 return root node of tree object More...
 
co_obj_tco_node_key (_treenode_t *node)
 return key object for given node More...
 
co_obj_tco_node_value (_treenode_t *node)
 return value object for given node More...
 
ssize_t co_tree_length (co_obj_t *tree)
 return length (number of key-value pairs) of given tree More...
 
_treenode_tco_tree_find_node (_treenode_t *root, const char *key, const size_t klen)
 find node in given tree More...
 
co_obj_tco_tree_find (const co_obj_t *root, const char *key, const size_t klen)
 return value from given tree that corresponds to key More...
 
co_obj_tco_tree_delete (co_obj_t *root, const char *key, const size_t klen)
 delete value from given tree that corresponds to key More...
 
int co_tree_insert (co_obj_t *root, const char *key, const size_t klen, co_obj_t *value)
 insert object into given tree and associate with key More...
 
int co_tree_insert_unsafe (co_obj_t *root, const char *key, const size_t klen, co_obj_t *value)
 insert object into given tree and associate with key, where value is not tied to tree More...
 
int co_tree_insert_force (co_obj_t *root, const char *key, const size_t klen, co_obj_t *value)
 insert object into given tree and associate with key (overwrite if it exists) More...
 
int co_tree_insert_unsafe_force (co_obj_t *root, const char *key, const size_t klen, co_obj_t *value)
 insert object into given tree and associate with key, where value is not tied to tree (overwrite if it exists) More...
 
int co_tree_set_str (co_obj_t *root, const char *key, const size_t klen, const char *value, const size_t vlen)
 set value contained in an object in the tree with a specified key (if a string) More...
 
int co_tree_set_int (co_obj_t *root, const char *key, const size_t klen, const signed long value)
 set value contained in an object in the tree with a specified key (if an int) More...
 
int co_tree_set_uint (co_obj_t *root, const char *key, const size_t klen, const unsigned long value)
 set value contained in an object in the tree with a specified key (if an unsigned int) More...
 
int co_tree_set_float (co_obj_t *root, const char *key, const size_t klen, const double value)
 set value contained in an object in the tree with a specified key (if a float) More...
 
int co_tree_process (co_obj_t *tree, const co_iter_t iter, void *context)
 process tree with given iterator function More...
 
void co_tree_destroy (co_obj_t *root)
 free tree structure More...
 
size_t co_tree_raw (char *output, const size_t olen, const co_obj_t *tree)
 dump raw representation of tree More...
 
size_t co_tree_import (co_obj_t **tree, const char *input, const size_t ilen)
 import raw representation of tree More...
 
void co_tree_print_indent (co_obj_t *tree, int indent)
 print tree with indent More...
 
int co_tree_print (co_obj_t *tree)
 print tree More...
 
int co_tree_print_raw (co_obj_t *tree)
 print raw dump of tree More...
 

Detailed Description

String-indexed search tree for Commotion object system.

Author
Josh King (jheretic), jking.nosp@m.@cha.nosp@m.mbana.nosp@m..net

Macro Definition Documentation

#define _DEFINE_TREE (   L)
Value:
int co_tree##L##_alloc(co_obj_t *output) \
{ \
output->_type = _tree##L; \
output->_next = NULL; \
output->_prev = NULL; \
output->_ref = 0; \
output->_flags = 0; \
((co_tree##L##_t *)output)->_len = 0; \
((co_tree##L##_t *)output)->root = NULL; \
return 1; \
} \
co_obj_t *co_tree##L##_create(void) \
{ \
co_obj_t *output = h_calloc(1, sizeof(co_tree##L##_t)); \
CHECK_MEM(output); \
CHECK(co_tree##L##_alloc(output), \
"Failed to allocate object."); \
return output; \
error: \
return NULL; \
}
Definition: obj.h:131

Function Documentation

co_obj_t* co_node_key ( _treenode_t node)

return key object for given node

Parameters
nodenode to return object for
90 {
91  if(node != NULL)
92  return node->key;
93  else
94  return NULL;
95 }
co_obj_t* co_node_value ( _treenode_t node)

return value object for given node

Parameters
nodenode to return object for
99 {
100  if(node != NULL)
101  return node->value;
102  else
103  return NULL;
104 }
co_obj_t* co_tree_delete ( co_obj_t root,
const char *  key,
const size_t  klen 
)

delete value from given tree that corresponds to key

Parameters
roottree object
keykey to search for
klenlength of key
228 {
229  co_obj_t *value = NULL;
230  if(CO_TYPE(root) == _tree16)
231  {
232  ((co_tree16_t *)root)->root = _co_tree_delete_r(((co_tree16_t *)root)->root, \
233  ((co_tree16_t *)root)->root, key, klen, &value);
234  }
235  else if(CO_TYPE(root) == _tree32)
236  {
237  ((co_tree32_t *)root)->root = _co_tree_delete_r(((co_tree32_t *)root)->root, \
238  ((co_tree32_t *)root)->root, key, klen, &value);
239  }
240 
241  CHECK(value != NULL, "Failed to delete value.");
242  CHECK(_co_tree_decrement(root) >= 0, "Failed to decrement value.");
243  return value;
244 error:
245  return NULL;
246 }
Definition: obj.h:131
void co_tree_destroy ( co_obj_t root)

free tree structure

Parameters
roottree object to free
576 {
577  if(root) {
578  h_free(root);
579  }
580 }
co_obj_t* co_tree_find ( const co_obj_t root,
const char *  key,
const size_t  klen 
)

return value from given tree that corresponds to key

Parameters
roottree object
keykey to search for
klenlength of key

References co_tree_find_node(), and co_tree_root().

Referenced by co_cmd_desc(), co_cmd_exec(), co_cmd_hook(), co_cmd_hook_str(), co_cmd_usage(), co_profile_get(), co_profile_get_float(), co_profile_get_int(), co_profile_get_str(), co_profile_get_uint(), and co_response_get().

174 {
175  DEBUG("Get from tree: %s", key);
176  _treenode_t *n = NULL;
177  CHECK((n = co_tree_root(root)) != NULL, "Specified object is not a tree.");
178  n = co_tree_find_node(n, key, klen);
179 
180  CHECK(n != NULL, "Unable to find value.");
181  return n->value;
182 error:
183  return NULL;
184 }
_treenode_t * co_tree_find_node(_treenode_t *root, const char *key, const size_t klen)
find node in given tree
Definition: tree.c:140
Definition: tree.h:44
_treenode_t * co_tree_root(const co_obj_t *tree)
return root node of tree object
Definition: tree.c:69
_treenode_t* co_tree_find_node ( _treenode_t root,
const char *  key,
const size_t  klen 
)

find node in given tree

Parameters
roottree in which to search
keykey to search for
klenlength of key

Referenced by co_tree_find(), co_tree_insert(), co_tree_insert_unsafe(), co_tree_set_float(), co_tree_set_int(), co_tree_set_str(), and co_tree_set_uint().

141 {
142  _treenode_t *n = root;
143  size_t i = 0;
144 
145  while(i < klen && n)
146  {
147  if (key[i] < n->splitchar)
148  {
149  n = n->low;
150  }
151  else if (key[i] == n->splitchar)
152  {
153  i++;
154  if(i < klen) n = n->equal;
155  }
156  else
157  {
158  n = n->high;
159  }
160  }
161 
162  if(n)
163  {
164  return n;
165  }
166  else
167  {
168  return NULL;
169  }
170 }
Definition: tree.h:44
size_t co_tree_import ( co_obj_t **  tree,
const char *  input,
const size_t  ilen 
)

import raw representation of tree

Parameters
treetarget pointer of new, imported tree object
inputinput buffer
ilenlength of input buffer

References co_list_import(), co_tree_import(), and co_tree_insert().

Referenced by co_list_import(), and co_tree_import().

660 {
661  size_t length = 0, olen = 0, read = 0, klen = 0;
662  char *kstr = NULL;
663  int i = 0;
664  co_obj_t *obj = NULL;
665  const char *cursor = input;
666  switch((uint8_t)input[0])
667  {
668  case _tree16:
669  length = *((uint16_t *)(input + 1));
670  *tree = co_tree16_create();
671  cursor += sizeof(uint16_t) + 1;
672  read = sizeof(uint16_t) + 1;
673  break;
674  case _tree32:
675  length = (uint32_t)(*(uint32_t*)(input + 1));
676  *tree = co_tree32_create();
677  cursor += sizeof(uint32_t) + 1;
678  read = sizeof(uint32_t) + 1;
679  break;
680  default:
681  SENTINEL("Not a tree.");
682  break;
683  }
684  while(i < length && read <= ilen)
685  {
686  DEBUG("Importing tuple:");
687  if((uint8_t)cursor[0] == _str8)
688  {
689  DEBUG("Reading key...");
690  cursor += 1;
691  read += 1;
692  klen = (uint8_t)cursor[0];
693  kstr = (char *)&cursor[1];
694  cursor += klen + 1;
695  read += klen + 1;
696 
697  DEBUG("Reading value...");
698  switch((uint8_t)cursor[0])
699  {
700  case _list16:
701  case _list32:
702  olen = co_list_import(&obj, cursor, ilen - read);
703  break;
704  case _tree16:
705  case _tree32:
706  olen = co_tree_import(&obj, cursor, ilen - read);
707  break;
708  default:
709  olen = co_obj_import(&obj, cursor, ilen - read, 0);
710  break;
711  }
712  CHECK(olen > 0, "Failed to import object.");
713  cursor +=olen;
714  read += olen;
715 
716  DEBUG("Inserting value into tree with key.");
717  CHECK(co_tree_insert(*tree, kstr, klen, obj), "Failed to insert object.");
718  i++;
719  }
720  }
721  return read;
722 error:
723  if(obj != NULL) co_obj_free(obj);
724  return -1;
725 }
Definition: obj.h:131
size_t co_list_import(co_obj_t **list, const char *input, const size_t ilen)
import list from raw representation
Definition: list.c:562
int co_tree_insert(co_obj_t *root, const char *key, const size_t klen, co_obj_t *value)
insert object into given tree and associate with key
Definition: tree.c:332
size_t co_tree_import(co_obj_t **tree, const char *input, const size_t ilen)
import raw representation of tree
Definition: tree.c:659
int co_tree_insert ( co_obj_t root,
const char *  key,
const size_t  klen,
co_obj_t value 
)

insert object into given tree and associate with key

Parameters
roottree object
keykey to search for
klenlength of key
valuevalue object to insert

References co_tree_find_node(), and co_tree_root().

Referenced by co_tree_import(), and dispatcher_cb().

333 {
334  _treenode_t *n = co_tree_find_node(co_tree_root(root), key, klen);
335  CHECK(n == NULL, "Key exists.");
336  return _co_tree_insert(root, key, klen, value, true);
337 error:
338  return 0;
339 }
_treenode_t * co_tree_find_node(_treenode_t *root, const char *key, const size_t klen)
find node in given tree
Definition: tree.c:140
Definition: tree.h:44
_treenode_t * co_tree_root(const co_obj_t *tree)
return root node of tree object
Definition: tree.c:69
int co_tree_insert_force ( co_obj_t root,
const char *  key,
const size_t  klen,
co_obj_t value 
)

insert object into given tree and associate with key (overwrite if it exists)

Parameters
roottree object
keykey to search for
klenlength of key
valuevalue object to insert
353 {
354  return _co_tree_insert(root, key, klen, value, true);
355 }
int co_tree_insert_unsafe ( co_obj_t root,
const char *  key,
const size_t  klen,
co_obj_t value 
)

insert object into given tree and associate with key, where value is not tied to tree

Parameters
roottree object
keykey to search for
klenlength of key
valuevalue object to insert

References co_tree_find_node(), and co_tree_root().

343 {
344  _treenode_t *n = co_tree_find_node(co_tree_root(root), key, klen);
345  CHECK(n == NULL, "Key exists.");
346  return _co_tree_insert(root, key, klen, value, false);
347 error:
348  return 0;
349 }
_treenode_t * co_tree_find_node(_treenode_t *root, const char *key, const size_t klen)
find node in given tree
Definition: tree.c:140
Definition: tree.h:44
_treenode_t * co_tree_root(const co_obj_t *tree)
return root node of tree object
Definition: tree.c:69
int co_tree_insert_unsafe_force ( co_obj_t root,
const char *  key,
const size_t  klen,
co_obj_t value 
)

insert object into given tree and associate with key, where value is not tied to tree (overwrite if it exists)

Parameters
roottree object
keykey to search for
klenlength of key
valuevalue object to insert
359 {
360  return _co_tree_insert(root, key, klen, value, false);
361 }
ssize_t co_tree_length ( co_obj_t tree)

return length (number of key-value pairs) of given tree

Parameters
treetree object
123 {
124  return _co_tree_change_length(tree, 0);
125 }
int co_tree_print ( co_obj_t tree)

print tree

Parameters
treetree object to print

References co_tree_print_indent().

Referenced by co_response_print().

823 {
824  CHECK_MEM(tree);
825 
826  co_tree_print_indent(tree,0);
827 
828  return 1;
829 error:
830  return 0;
831 }
void co_tree_print_indent(co_obj_t *tree, int indent)
print tree with indent
Definition: tree.c:809
void co_tree_print_indent ( co_obj_t tree,
int  indent 
)

print tree with indent

Parameters
treetree object to print
indentlevel of indent

References co_tree_root().

Referenced by co_tree_print().

810 {
811  int count = 0;
812 
813  for (int i = 0; i < indent; i++) printf(" ");
814  printf("{\n");
815  _co_tree_print_r(tree, co_tree_root(tree), &count, indent+1);
816  for (int i = 0; i < indent; i++) printf(" ");
817  printf("}");
818  if (!indent) printf("\n");
819 }
_treenode_t * co_tree_root(const co_obj_t *tree)
return root node of tree object
Definition: tree.c:69
int co_tree_print_raw ( co_obj_t tree)

print raw dump of tree

Parameters
treetree object to print

References co_tree_root().

859 {
860  CHECK_MEM(tree);
861  _co_tree_print_raw_r(tree, co_tree_root(tree));
862  return 1;
863 error:
864  return 0;
865 }
_treenode_t * co_tree_root(const co_obj_t *tree)
return root node of tree object
Definition: tree.c:69
int co_tree_process ( co_obj_t tree,
const co_iter_t  iter,
void *  context 
)

process tree with given iterator function

Parameters
treetree object to process
iteriterator function
contextadditional arguments to iterator

Referenced by co_cmd_process().

556 {
557  switch(CO_TYPE(tree))
558  {
559  case _tree16:
560  _co_tree_process_r(tree, ((co_tree16_t *)tree)->root, iter, context);
561  break;
562  case _tree32:
563  _co_tree_process_r(tree, ((co_tree32_t *)tree)->root, iter, context);
564  break;
565  default:
566  SENTINEL("Object is not a tree.");
567  break;
568  }
569  return 1;
570 error:
571  return 0;
572 }
size_t co_tree_raw ( char *  output,
const size_t  olen,
const co_obj_t tree 
)

dump raw representation of tree

Parameters
outputoutput buffer
olenlength of output buffer
treetree to dump

References co_tree_root().

Referenced by co_list_raw(), and co_response_alloc().

624 {
625  char *out = output;
626  size_t written = 0;
627  switch(CO_TYPE(tree))
628  {
629  case _tree16:
630  memmove(out, &(tree->_type), sizeof(tree->_type));
631  out += sizeof(tree->_type);
632  written += sizeof(tree->_type);
633  memmove(out, &(((co_tree16_t *)tree)->_len), sizeof(((co_tree16_t *)tree)->_len));
634  out += sizeof(((co_tree16_t *)tree)->_len);
635  written += sizeof(((co_tree16_t *)tree)->_len);
636  break;
637  case _tree32:
638  memmove(out, &(tree->_type), sizeof(tree->_type));
639  out += sizeof(tree->_type);
640  written += sizeof(tree->_type);
641  memmove(out, &(((co_tree32_t *)tree)->_len), sizeof(((co_tree32_t *)tree)->_len));
642  out += sizeof(((co_tree32_t *)tree)->_len);
643  written += sizeof(((co_tree32_t *)tree)->_len);
644  break;
645  default:
646  SENTINEL("Not a tree object.");
647  break;
648  }
649 
650  _co_tree_raw_r(&out, &olen, &written, co_tree_root(tree));
651  DEBUG("Tree bytes written: %d", (int)written);
652  return written;
653 error:
654  return -1;
655 }
_treenode_t * co_tree_root(const co_obj_t *tree)
return root node of tree object
Definition: tree.c:69
_treenode_t* co_tree_root ( const co_obj_t tree)

return root node of tree object

Parameters
treetree object that contains root

Referenced by co_profile_export_file(), co_tree_find(), co_tree_insert(), co_tree_insert_unsafe(), co_tree_print_indent(), co_tree_print_raw(), co_tree_raw(), co_tree_set_float(), co_tree_set_int(), co_tree_set_str(), and co_tree_set_uint().

70 {
71  CHECK_MEM(tree);
72  _treenode_t *n = NULL;
73  if(CO_TYPE(tree) == _tree16)
74  {
75  n = ((co_tree16_t *)tree)->root;
76  }
77  else if(CO_TYPE(tree) == _tree32)
78  {
79  n = ((co_tree32_t *)tree)->root;
80  }
81  else SENTINEL("Specified object is not a tree.");
82 
83  return n;
84 error:
85  return NULL;
86 }
Definition: tree.h:44
int co_tree_set_float ( co_obj_t root,
const char *  key,
const size_t  klen,
const double  value 
)

set value contained in an object in the tree with a specified key (if a float)

Parameters
roottree object
keykey to search for
klenlength of key
valuevalue to insert

References co_tree_find_node(), and co_tree_root().

Referenced by co_profile_set_float().

525 {
526  DEBUG("Get from tree: %s", key);
527  _treenode_t *n = NULL;
528  CHECK((n = co_tree_root(root)) != NULL, "Specified object is not a tree.");
529  n = co_tree_find_node(n, key, klen);
530  CHECK(n != NULL, "Failed to find key in tree.");
531  CHECK(_co_node_set_float(n, value), "Unable to set float for node.");
532 
533  return 1;
534 error:
535  return 0;
536 }
_treenode_t * co_tree_find_node(_treenode_t *root, const char *key, const size_t klen)
find node in given tree
Definition: tree.c:140
Definition: tree.h:44
_treenode_t * co_tree_root(const co_obj_t *tree)
return root node of tree object
Definition: tree.c:69
int co_tree_set_int ( co_obj_t root,
const char *  key,
const size_t  klen,
const signed long  value 
)

set value contained in an object in the tree with a specified key (if an int)

Parameters
roottree object
keykey to search for
klenlength of key
valuevalue to insert

References co_tree_find_node(), and co_tree_root().

Referenced by co_profile_set_int().

450 {
451  DEBUG("Get from tree: %s", key);
452  _treenode_t *n = NULL;
453  CHECK((n = co_tree_root(root)) != NULL, "Specified object is not a tree.");
454  n = co_tree_find_node(n, key, klen);
455  CHECK(n != NULL, "Failed to find key in tree.");
456  CHECK(_co_node_set_int(n, value), "Unable to set integer for node.");
457  return 1;
458 error:
459  return 0;
460 }
_treenode_t * co_tree_find_node(_treenode_t *root, const char *key, const size_t klen)
find node in given tree
Definition: tree.c:140
Definition: tree.h:44
_treenode_t * co_tree_root(const co_obj_t *tree)
return root node of tree object
Definition: tree.c:69
int co_tree_set_str ( co_obj_t root,
const char *  key,
const size_t  klen,
const char *  value,
const size_t  vlen 
)

set value contained in an object in the tree with a specified key (if a string)

Parameters
roottree object
keykey to search for
klenlength of key
valuevalue to insert
vlenlength of value

References co_tree_find_node(), and co_tree_root().

Referenced by co_profile_set_str().

409 {
410  DEBUG("Get from tree: %s", key);
411  _treenode_t *n = NULL;
412  CHECK((n = co_tree_root(root)) != NULL, "Specified object is not a tree.");
413  n = co_tree_find_node(n, key, klen);
414  CHECK(n != NULL, "Failed to find key in tree.");
415  CHECK(_co_node_set_str(n, value, vlen), "Unable to set string for node.");
416  return 1;
417 error:
418  return 0;
419 }
_treenode_t * co_tree_find_node(_treenode_t *root, const char *key, const size_t klen)
find node in given tree
Definition: tree.c:140
Definition: tree.h:44
_treenode_t * co_tree_root(const co_obj_t *tree)
return root node of tree object
Definition: tree.c:69
int co_tree_set_uint ( co_obj_t root,
const char *  key,
const size_t  klen,
const unsigned long  value 
)

set value contained in an object in the tree with a specified key (if an unsigned int)

Parameters
roottree object
keykey to search for
klenlength of key
valuevalue to insert

References co_tree_find_node(), and co_tree_root().

Referenced by co_profile_set_uint().

491 {
492  DEBUG("Get from tree: %s", key);
493  _treenode_t *n = NULL;
494  CHECK((n = co_tree_root(root)) != NULL, "Specified object is not a tree.");
495  n = co_tree_find_node(n, key, klen);
496  CHECK(n != NULL, "Failed to find key in tree.");
497  CHECK(_co_node_set_uint(n, value), "Unable to set unsigned integer for node.");
498 
499  return 1;
500 error:
501  return 0;
502 }
_treenode_t * co_tree_find_node(_treenode_t *root, const char *key, const size_t klen)
find node in given tree
Definition: tree.c:140
Definition: tree.h:44
_treenode_t * co_tree_root(const co_obj_t *tree)
return root node of tree object
Definition: tree.c:69