class Patricia

Public Class Methods

new(p1 = v1) click to toggle source

static VALUE
p_init(int argc, VALUE *argv, VALUE self)
{
  VALUE family;
  int maxbits;

  rb_scan_args(argc, argv, "01", &family);

  if (NIL_P(family) || family == sym_AF_INET)
    maxbits = 32;
  else if (family == sym_AF_INET6)
    maxbits = 128;
  else
    rb_raise(rb_eArgError, "unknown family (must be :AF_INET6 or :AF_INET)");

  DATA_PTR(self) = New_Patricia(maxbits);
  return self;
}

Public Instance Methods

add(*args) click to toggle source

static VALUE
p_add (int argc, VALUE *argv, VALUE self)
{
  VALUE user_data;
  patricia_tree_t *tree;
  patricia_node_t *node;
  prefix_t prefix;

  if (argc > 2 || argc < 1) 
    return Qnil;

  Data_Get_Struct(self, patricia_tree_t, tree);
  my_ascii2prefix(tree, argv[0], &prefix);
  node = patricia_lookup(tree, &prefix);

  if (argc == 2) {
    user_data = argv[1];

    /* for backwards compatibility, we always dup and return new strings */
    if (TYPE(user_data) == T_STRING)
      user_data = rb_str_dup(user_data);
  } else {
    user_data = rb_str_new(NULL, 0);
  }
  PATRICIA_DATA_SET(node, user_data);

  /* node will be freed when parent is freed */
  return wrap_node(node);
}

Also aliased as: add_node

add_node(*args)

Alias for: add

clear()

Alias for: destroy

destroy() click to toggle source

static VALUE
p_destroy (VALUE self)
{
  patricia_tree_t *tree;

  Data_Get_Struct(self, patricia_tree_t, tree);
  Clear_Patricia(tree, dummy);
  tree->head = NULL; /* Clear_Patricia() should do this, actually */

  return Qtrue;
}

Also aliased as: clear

family() click to toggle source

static VALUE
p_family(VALUE self)
{
  patricia_tree_t *tree;

  Data_Get_Struct(self, patricia_tree_t, tree);

  switch (tree->maxbits) {
  case 32: return sym_AF_INET;
  case 128: return sym_AF_INET6;
  }
  assert(0 && "unknown maxbits, corrupt tree");
  return Qnil;
}

include?(p1) click to toggle source

static VALUE
p_include (VALUE self, VALUE r_key)
{
  patricia_tree_t *tree;
  patricia_node_t *node;
  prefix_t prefix;

  Data_Get_Struct(self, patricia_tree_t, tree);
  my_ascii2prefix(tree, r_key, &prefix);
  node = patricia_search_best(tree, &prefix);

  return node ? Qtrue : Qfalse;
}

initialize_copy(p1) click to toggle source

static VALUE
p_init_copy(VALUE self, VALUE orig)
{
  patricia_tree_t *orig_tree;

  Data_Get_Struct(orig, patricia_tree_t, orig_tree);
  if (orig_tree->head) {
    patricia_tree_t *tree;
    patricia_node_t *orig_node, *node;
    VALUE user_data;

    DATA_PTR(self) = tree = New_Patricia(orig_tree->maxbits);

    PATRICIA_WALK(orig_tree->head, orig_node) {
      node = patricia_lookup(tree, orig_node->prefix);
      assert(node->prefix == orig_node->prefix);

      user_data = (VALUE)(orig_node->data);
      if (T_STRING == TYPE(user_data))
        user_data = rb_str_dup(user_data);
      PATRICIA_DATA_SET(node, user_data);
    } PATRICIA_WALK_END;
  }

  return self;
}

match_best(p1) click to toggle source

static VALUE
p_match (VALUE self, VALUE r_key)
{
  patricia_tree_t *tree;
  patricia_node_t *node;
  prefix_t prefix;
  
  Data_Get_Struct(self, patricia_tree_t, tree);
  my_ascii2prefix(tree, r_key, &prefix);
  node = patricia_search_best(tree, &prefix);

  return node ? wrap_node(node) : Qnil;
}

Also aliased as: search_best

match_exact(p1) click to toggle source

static VALUE
p_match_exact (VALUE self, VALUE r_key)
{
  patricia_tree_t *tree;
  patricia_node_t *node;
  prefix_t prefix;

  Data_Get_Struct(self, patricia_tree_t, tree);
  my_ascii2prefix(tree, r_key, &prefix);
  node = patricia_search_exact(tree, &prefix);

  return node ? wrap_node(node) : Qnil;
}

Also aliased as: search_exact

nodes() click to toggle source

static VALUE
p_nodes (VALUE self)
{
  VALUE buf = rb_str_new(0, 0);
  char *cbuf;
  patricia_tree_t *tree;
  patricia_node_t *node;
  VALUE hash;

  Data_Get_Struct(self, patricia_tree_t, tree);

  hash = rb_hash_new();
  if (tree->head) {
    PATRICIA_WALK(tree->head, node) {
      rb_str_resize(buf, PATRICIA_MAXSTRLEN);
      cbuf = RSTRING_PTR(buf);
      prefix_toa2x(node->prefix, cbuf, 1);
      rb_str_set_len(buf, strlen(cbuf));
      rb_hash_aset(hash, buf, (VALUE)node->data);
    } PATRICIA_WALK_END;
  }
  return hash;
}

num_nodes() click to toggle source

static VALUE
p_num_nodes (VALUE self)
{
  int n;
  patricia_tree_t *tree;

  Data_Get_Struct(self, patricia_tree_t, tree);
  n = tree->head ? patricia_walk_inorder(tree->head, dummy) : 0;

  return INT2NUM(n);
}

remove(p1) click to toggle source

static VALUE
p_remove (VALUE self, VALUE r_key)
{
  patricia_tree_t *tree;
  patricia_node_t *node;
  prefix_t prefix;

  Data_Get_Struct(self, patricia_tree_t, tree);
  my_ascii2prefix(tree, r_key, &prefix);
  node = patricia_search_exact(tree, &prefix);

  if (node) {
    patricia_remove (tree, node);
    return Qtrue;
  } else {
    return Qfalse;
  }
}

Also aliased as: remove_node

remove_node(p1)

Alias for: remove

search_best(p1)

Alias for: match_best

search_exact(p1)

Alias for: match_exact

show_nodes(p1 = v1) click to toggle source

static VALUE
p_print_nodes (int argc, VALUE *argv, VALUE self)
{
  ID id_printf = rb_intern("printf");
  VALUE fmt = rb_str_new2("node: %s\n");
  VALUE buf = rb_str_new(0, 0);
  char *cbuf;
  patricia_tree_t *tree;
  patricia_node_t *node;
  VALUE out;
  Data_Get_Struct(self, patricia_tree_t, tree);

  rb_scan_args(argc, argv, "01", &out);
  if (NIL_P(out))
    out = rb_stdout;

  if (tree->head) {
    PATRICIA_WALK(tree->head, node) {
      rb_str_resize(buf, PATRICIA_MAXSTRLEN);
      cbuf = RSTRING_PTR(buf);
      prefix_toa2x(node->prefix, cbuf, 1);
      rb_str_set_len(buf, strlen(cbuf));
      rb_funcall(out, id_printf, 2, fmt, buf);
    } PATRICIA_WALK_END;
  }
  return Qtrue;
}