traverse_with_key.h

Go to the documentation of this file.

 
#ifdef ONLY_FOR_DOXYGEN
#include "node.h"
#endif //ONLY_FOR_DOXYGEN
 
#ifndef RBT_TRAVERSE_H_PREFIX_
#define RBT_TRAVERSE_H_PREFIX_ RBT_NODE_H_PREFIX_
#endif
 
#undef RBT_NODE_TRAVERSE_WITH_KEY
#define RBT_NODE_TRAVERSE_WITH_KEY RBT_TOKEN_2_W(RBT_TRAVERSE_H_PREFIX_, node_traverse_with_key)
 
#undef RBT_NODE_FILTER_WITH_KEY
#define RBT_NODE_FILTER_WITH_KEY RBT_TOKEN_2_W(RBT_TRAVERSE_H_PREFIX_, node_filter_with_key)
 
#ifndef RBT_RESIZE_TO_FIT_KEY
#define RBT_RESIZE_TO_FIT_KEY(current_size, required_size, fail) \
do \
{ \
  current_size = required_size * 2; \
  if (current_size < required_size) \
  { \
    current_size = -1; \
    if (current_size < required_size) \
    { \
      fail; \
    } \
  } \
} \
while(0)
#endif // RBT_RESIZE_TO_FIT_KEY
 
 
 
 
 
 
/*
  Use a linked list to track right nodes while descending into left nodes. The
  linked list is constructed in such a way that the bit order (as determined by
  the endianess of RBT_PIN_T) is respected when traversing the tree. The order
  may vary across systems and should not be relied on for e.g. sorting.
 
  stack_unused is used to track allocated list elements to avoid unnecessary
  reallocation of memory (i.e. free -> malloc).
 
*/
void
RBT_NODE_TRAVERSE_WITH_KEY(
  RBT_NODE_T * node,
  RBT_NODE_TRAVERSE_WITH_KEY_FUNCTION_T func_v,
  ...
)
{
  int rc;
  _RBT_NODE_TRAVERSE_WITH_KEY_STACK_T * stack, * stack_tmp, * stack_unused;
  RBT_KEY_SIZE_T size, pins, bytes, tmp, height;
  RBT_KEY_DATA_T key_data;
 
  va_list func_args;
 
  errno = 0;
 
  if (node == NULL)
  {
    return;
  }
 
  key_data.bytes = 0;
  height = 0;
  stack = NULL;
  stack_unused = NULL;
  rc = 0;
 
  /*
    If the key size is fixed then we can use an array and avoid dynamic
    allocation.
  */
#ifdef RBT_KEY_SIZE_FIXED
    RBT_PIN_T key[RBT_KEY_SIZE_FIXED/RBT_PIN_SIZE];
    key_data.key = (RBT_PIN_T *) key;
    size = RBT_KEY_SIZE_FIXED;
#else
    key_data.key = NULL;
    size = 0;
#endif //RBT_KEY_SIZE_FIXED
 
  while (1)
  {
    key_data.node = node;
    RBT_DIVMOD(node->bits, RBT_PIN_SIZE_BITS, pins, key_data.bits);
    bytes = pins * RBT_PIN_SIZE;
    if (key_data.bits)
    {
      bytes += RBT_PIN_SIZE;
    }
    tmp = key_data.bytes + bytes;
#ifndef RBT_KEY_SIZE_FIXED
    if (tmp > size)
    {
      RBT_RESIZE_TO_FIT_KEY(size, tmp, errno = EOVERFLOW; break);
      key_data.key = realloc(key_data.key, size);
      if (key_data.key == NULL)
      {
        rc = errno;
        break;
      }
    }
#endif //RBT_KEY_SIZE_FIXED
    memcpy(((uint8_t *) key_data.key) + key_data.bytes, node->key, bytes);
    key_data.bytes += bytes;
    if (key_data.bits)
    {
      key_data.bytes -= RBT_PIN_SIZE;
    }
    key_data.bits += (key_data.bytes * RBT_PIN_SIZE_BITS);
 
    va_start(func_args, func_v);
    if (func_v(&key_data, height, func_args) || errno)
    {
      rc = errno;
      break;
    }
    va_end(func_args);
 
    if (node->right == NULL)
    {
      if (node->left == NULL)
      {
        if (stack == NULL)
        {
          break;
        }
        else
        {
          node = stack->node;
          key_data.bytes = stack->bytes_in_key_prefix;
          height = stack->height;
          _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
          continue;
        }
      }
      else
      {
        node = node->left;
        height ++;
      }
    }
    else if (node->left == NULL)
    {
      node = node->right;
      height ++;
    }
    else
    {
      _RBT_NODE_STACK_ALLOCATE(stack, stack_tmp, stack_unused, _RBT_NODE_TRAVERSE_WITH_KEY_STACK_T);
      height ++;
      stack->node = node->right;
      stack->height = height;
      stack->bytes_in_key_prefix = key_data.bytes;
      node = node->left;
    }
  }
#ifndef RBT_KEY_SIZE_FIXED
//   if (! (RBT_KEY_SIZE_FIXED || key == NULL))
  if (key_data.key != NULL)
  {
    free(key_data.key);
  }
#endif
  _RBT_NODE_STACK_FREE(stack, stack_tmp, stack_unused);
  errno = rc;
}
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
void
RBT_NODE_FILTER_WITH_KEY(
  RBT_NODE_T * node,
  RBT_NODE_FILTER_WITH_KEY_FUNCTION_T func_v,
  int include_empty,
  ...
)
{
  int rc, unwanted, is_left, placeholder;
  RBT_NODE_T * tmp_node, * sibling_node;
  RBT_NODE_STACK_T * parent_stack, * parent_stack_tmp, * parent_stack_unused;
  RBT_KEY_SIZE_T size, pins, bytes, tmp;
  _RBT_NODE_FILTER_WITH_KEY_STACK_T * stack, * stack_tmp, * stack_unused;
  RBT_KEY_DATA_T key_data;
  va_list func_args;
 
  errno = 0;
 
  if (node == NULL)
  {
    return;
  }
 
  key_data.bytes = 0;
  stack = NULL;
  stack_unused = NULL;
  parent_stack = NULL;
  parent_stack_unused = NULL;
  rc = 0;
 
  /*
    If the key size is fixed then we can use an array and avoid dynamic
    allocation.
  */
#ifdef RBT_KEY_SIZE_FIXED
    RBT_PIN_T key[RBT_KEY_SIZE_FIXED/RBT_PIN_SIZE];
    key_data.key = (RBT_PIN_T *) key;
    size = RBT_KEY_SIZE_FIXED;
#else
    key_data.key = NULL;
    size = 0;
#endif //RBT_KEY_SIZE_FIXED
 
  while (1)
  {
    key_data.node = node;
    RBT_DIVMOD(node->bits, RBT_PIN_SIZE_BITS, pins, key_data.bits);
    bytes = pins * RBT_PIN_SIZE;
    if (key_data.bits)
    {
      bytes += RBT_PIN_SIZE;
    }
    tmp = key_data.bytes + bytes;
#ifndef RBT_KEY_SIZE_FIXED
    if (tmp > size)
    {
      RBT_RESIZE_TO_FIT_KEY(size, tmp, errno = EOVERFLOW; break);
      key_data.key = realloc(key_data.key, size);
      if (key_data.key == NULL)
      {
        rc = errno;
        break;
      }
    }
#endif //RBT_KEY_SIZE_FIXED
    memcpy(((uint8_t *) key_data.key) + key_data.bytes, node->key, bytes);
    key_data.bytes += bytes;
    if (key_data.bits)
    {
      key_data.bytes -= RBT_PIN_SIZE;
    }
    key_data.bits += (key_data.bytes * RBT_PIN_SIZE_BITS);
 
    if (node != NULL)
    {
      if (parent_stack != NULL)
      {
        debug_printf("filtering node: %p (parent: %p)\n", node, parent_stack->node);
      }
      else
      {
        debug_printf("filtering node: %p (no parent)\n", node);
      }
      if (include_empty || !RBT_VALUE_IS_NULL(node->value))
      {
        va_start(func_args, include_empty);
        /*
          This would purge superfluous nodes:
        */
//         unwanted = func_v(node->value, func_args) || RBT_VALUE_IS_NULL(node->value);
        unwanted = func_v(&key_data, func_args);
        va_end(func_args);
        if (errno)
        {
          rc = errno;
          break;
        }
        if (unwanted)
        {
          if (parent_stack != NULL)
          {
            is_left = parent_stack->node->left == node;
            /*
              The node will not be removed if it has any children. If it has
              two then it will be left as a placeholder node. If it has only
              one then it will be merged and we will need to continue the loop.
            */
            placeholder = (node->left != NULL) && (node->right != NULL);
            if (is_left)
            {
              sibling_node = parent_stack->node->right;
            }
            else
            {
              sibling_node = parent_stack->node->left;
            }
            tmp_node = RBT_NODE_REMOVE(node, parent_stack->node);
            if (errno)
            {
              rc = errno;
              break;
            }
            /*
              If the node has been completely removed then the sibling may have
              been merged into the parent. Go back to the parent in that case.
            */
            if (tmp_node != node)
            {
              if (is_left)
              {
                /*
                  Jump directly to the sibling node if it has not changed.
                */
                if (parent_stack->node->right == sibling_node)
                {
                  node = sibling_node;
                  key_data.bytes -= bytes;
                }
                /*
                  Otherwise jump to the parent.
                */
                else
                {
                  node = parent_stack->node;
                  _RBT_NODE_STACK_POP(parent_stack, parent_stack_tmp, parent_stack_unused);
                  if (stack != NULL && stack->parent_stack->node == node)
                  {
                    _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
                  }
                  if (stack != NULL)
                  {
                    key_data.bytes = stack->bytes_in_key_prefix;
                  }
                  else
                  {
                    // TODO: break instead?
                    key_data.bytes = 0;
                  }
                }
              }
              /*
                If the node was the right child, then jump back to the last
                right child.
              */
              else
              {
                if (stack != NULL)
                {
                  node = stack->node;
                  key_data.bytes = stack->bytes_in_key_prefix;
                  while (parent_stack != NULL && parent_stack != stack->parent_stack)
                  {
                    _RBT_NODE_STACK_POP(parent_stack, parent_stack_tmp, parent_stack_unused);
                  }
                  _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
                }
                else
                {
                  break;
                }
              }
              continue;
            }
            /*
              If the node remains, it is either a placeholder or it has been
              merged with a child. In the latter case, continue to filter the
              new value of the node.
            */
            if (! placeholder)
            {
              continue;
            }
          }
          else
          {
            RBT_NODE_REMOVE(node, NULL);
            if (errno)
            {
              rc = errno;
              break;
            }
          }
        }
      }
      if (node->left != NULL)
      {
        _RBT_NODE_STACK_ALLOCATE(parent_stack, parent_stack_tmp, parent_stack_unused, RBT_NODE_STACK_T);
        parent_stack->node = node;
        if (node->right != NULL)
        {
          _RBT_NODE_STACK_ALLOCATE(stack, stack_tmp, stack_unused, _RBT_NODE_FILTER_WITH_KEY_STACK_T);
          stack->node = node->right;
          stack->bytes_in_key_prefix = key_data.bytes;
          stack->parent_stack = parent_stack;
        }
        node = node->left;
        continue;
      }
      else if (node->right != NULL)
      {
        _RBT_NODE_STACK_ALLOCATE(parent_stack, parent_stack_tmp, parent_stack_unused, RBT_NODE_STACK_T);
        parent_stack->node = node;
        node = node->right;
        continue;
      }
    }
    if (stack != NULL)
    {
      node = stack->node;
      key_data.bytes = stack->bytes_in_key_prefix;
      while (parent_stack != NULL && parent_stack != stack->parent_stack)
      {
        _RBT_NODE_STACK_POP(parent_stack, parent_stack_tmp, parent_stack_unused);
      }
      _RBT_NODE_STACK_POP(stack, stack_tmp, stack_unused);
    }
    else
    {
      break;
    }
  }
#ifndef RBT_KEY_SIZE_FIXED
//   if (! (RBT_KEY_SIZE_FIXED || key == NULL))
  if (key_data.key != NULL)
  {
    free(key_data.key);
  }
#endif
  _RBT_NODE_STACK_FREE(parent_stack, parent_stack_tmp, parent_stack_unused);
  _RBT_NODE_STACK_FREE(stack, stack_tmp, stack_unused);
  errno = rc;
}