Modules
ADT Database GTK2 GUI IP PiJAX Public Sql Stdio Subversion System Tools Xosd lua v4l2 wx
Recent Changes
Public.Parser.XML2 1.50
Public.ZeroMQ 1.1
Public.Template.Mustache 1.0
Public.Protocols.XMPP 1.4
Sql.Provider.jdbc 1.0
Popular Downloads
Public.Parser.JSON2 1.0
Public.Parser.JSON 0.2
GTK2 2.23
Public.Web.FCGI 1.8
Public.Parser.XML2 1.48
|
Module Information
ADT.Tree
Viewing contents of ADT_Tree-1.2/tree.c
/*
* Time-stamp: <05/11/21 09:32:53 riffraff>
*
* $Id: tree.c,v 1.4 2005/11/21 15:34:03 riffraff Exp $
*/
#include "global.h"
#include "module.h"
#include "interpret.h"
#include "svalue.h"
#include "stralloc.h"
#include "array.h"
#include "pike_macros.h"
#include "program.h"
#include "object.h"
#include "pike_types.h"
#include "pike_error.h"
#include "builtin_functions.h"
#include "opcodes.h"
#include "module_support.h"
#include "operators.h"
#include "mapping.h"
#include "tree.h"
#undef THIS
#define THIS ((struct atable *)(Pike_fp->current_storage))
#define THIS_PROGRAM (Pike_fp->context.prog)
#define RETURN_THIS() do{ ref_push_object(Pike_fp->current_object); }while(0)
struct anode sentinel;
void tree_sizeof(INT32 args) {
pop_n_elems(args);
push_int(THIS->count);
}
/****************************************/
struct anode *low_tree_insert(struct svalue *key, struct svalue *val) {
struct anode *where,*parent,*node;
int res=-1;
where=THIS->root->left;
parent=where->parent;
node=create_node();
assign_svalue_no_free(node->key,key);
assign_svalue_no_free(node->val,val?val:key);
while (where!=&sentinel) {
parent=where;
res=compare_svalue(key,where->key);
if (res==0) { /* duplicate */
destroy_node(node);
return NULL;
}
if (res<0)
where=where->left;
else
where=where->right;
}
/* where==&sentinel */
if (res<0)
parent->left=node;
else
parent->right=node;
node->parent=parent;
node->left=&sentinel;
node->right=&sentinel;
THIS->count++;
THIS->gen++;
return node;
}
void low_tree_remove(struct anode *node) {
struct anode *s,*c;
low_tree_delete(node,&s,&c);
}
void low_tree_delete(struct anode *node,
struct anode **pswap,
struct anode **pchild) {
struct anode *child,*delparent,*next,*nextparent;
delparent=node->parent;
next=node;
if (node->left!=&sentinel && node->right!=&sentinel) {
next=find_next(node);
nextparent=next->parent;
if (next==&sentinel) {
fputs("low_tree_delete: next==NULL\n",stderr);
return;
}
if (next->parent==&sentinel) {
fputs("low_tree_delete: next->parent==NULL\n",stderr);
return;
}
if (next->left!=&sentinel) {
fputs("low_tree_delete: next->left!=NULL\n",stderr);
return;
}
/* next!=NULL && next->parent!=NULL && next->left==NULL */
child=next->right;
child->parent=nextparent;
if (nextparent->left==next) {
nextparent->left=child;
} else {
if (nextparent->right!=next) {
fputs("low_tree_delete: nextparent->right!=next\n",stderr);
return;
}
/* nextparent->right==next */
nextparent->right=child;
}
next->parent=delparent;
next->left=node->left;
next->right=node->right;
next->left->parent=next;
next->right->parent=next;
if (delparent->left==node) {
delparent->left=next;
} else {
if (delparent->right!=node) {
fputs("low_tree_delete: delparent->right!=node\n",stderr);
return;
}
/* delparent->right==node */
delparent->right=next;
}
} else {
if (node==&sentinel) {
fputs("low_tree_delete: node==NULL\n",stderr);
return;
}
if (!(node->left==&sentinel || node->right==&sentinel)) {
fputs("low_tree_delete: !(node->left==NULL || node->right==NULL)\n",stderr);
return;
}
/* node!=NULL */
/* node->left==NULL && node->right==NULL */
child=(node->left!=&sentinel)?node->left:node->right;
child->parent=delparent=node->parent;
if (node==delparent->left) {
delparent->left=child;
} else {
if (node!=delparent->right) {
fputs("low_tree_delete: node!=delparent->right\n",stderr);
return;
}
/* node==delparent->right */
delparent->right=child;
}
}
node->parent=node->left=node->right=NULL;
THIS->count--;
THIS->gen--;
*pswap=next;
*pchild=child;
}
struct anode *low_tree_find(struct svalue *key) {
struct anode *root,*saved;
int res;
root=THIS->root->left;
while (root!=&sentinel) {
res=compare_svalue(key,root->key);
if (res<0)
root=root->left;
else if (res>0)
root=root->right;
else {
if (!THIS->dup) /* no dupes, return match */
return root;
else { /* could be dupes, find leftmost one */
do {
saved=root;
root=root->left;
while (root!=&sentinel && compare_svalue(key,root->key))
root=root->right;
} while (root!=&sentinel);
return saved;
}
}
}
return NULL;
}
struct anode *low_tree_lower_bound(struct svalue *key) {
struct anode *root,*tent;
root=THIS->root->left;
tent=NULL;
while (root!=&sentinel) {
int res=compare_svalue(key,root->key);
if (res>0) {
root=root->right;
} else if (res<0) {
tent=root;
root=root->left;
} else {
if (!THIS->dup) {
return root;
} else {
tent=root;
root=root->left;
}
}
}
return tent;
}
struct anode *low_tree_upper_bound(struct svalue *key) {
struct anode *root,*tent;
root=THIS->root->left;
tent=NULL;
while (root!=&sentinel) {
int res=compare_svalue(key,root->key);
if (res<0) {
root=root->left;
} else if (res>0) {
tent=root;
root=root->right;
} else {
if (!THIS->dup) {
return root;
} else {
tent=root;
root=root->right;
}
}
}
return tent;
}
void tree_rotate_left(struct anode *child, struct anode *parent) {
struct anode *leftgc,*g;
if (parent->right!=child) {
fputs("tree_rotate_left: parent->right!=child\n",stderr);
return;
}
parent->right=leftgc=child->left;
leftgc->parent=parent;
child->parent=g=parent->parent;
if (parent==g->left) {
g->left=child;
} else {
if (parent!=g->right) {
fputs("tree_rotate_left: parent!=g->right\n",stderr);
return;
}
g->right=child;
}
child->left=parent;
parent->parent=child;
}
void tree_rotate_right(struct anode *child, struct anode *parent) {
struct anode *rgc,*g;
if (parent->left!=child) {
fputs("tree_rotate_right: parent->left!=child\n",stderr);
return;
}
parent->left=rgc=child->right;
rgc->parent=parent;
child->parent=g=parent->parent;
if (parent==g->right) {
g->right=child;
} else {
if (parent!=g->left) {
fputs("tree_rotate_right: parent!=g->left\n",stderr);
}
/* parent==g->left */
g->left=child;
}
child->right=parent;
parent->parent=child;
}
/************************************/
void tree_clear(INT32 args) {
pop_n_elems(args);
while (THIS->count) {
struct anode *n;
n=find_first(THIS->root->left);
low_tree_remove(n);
destroy_node(n);
}
}
void tree_destroy(INT32 args) {
tree_clear(args);
free_svalue(&THIS->comp_func);
/* free(THIS->root->left); */
}
void tree_create(INT32 args) {
struct svalue *cb=NULL;
get_all_args("create",args,".%*",&cb);
low_tree_create(cb);
THIS->type=TREE_BIN;
pop_n_elems(args);
}
void low_describe_tree(struct anode *a, int type) {
if (a==&sentinel)
return;
#define DESCRIBE() if (a->key) { \
struct pike_string *s; \
s=tree_describe_type(a->key); \
push_string(s); \
s=tree_describe_type(a->val); \
push_string(s); \
f_aggregate(2); \
}
#define push_stuff() { \
push_svalue(a->key); \
push_svalue(a->val); \
f_aggregate(2); \
}
if (type==TREE_PREORDER)
push_stuff();
low_describe_tree(a->left,type);
if (type==TREE_INORDER)
push_stuff();
low_describe_tree(a->right,type);
if (type==TREE_POSTORDER)
push_stuff();
}
void tree_cast(INT32 args) {
char *type;
get_all_args("cast",args,"%s",&type);
if (!strcmp(type,"array")) {
pop_n_elems(args);
low_describe_tree(THIS->root->left,0);
f_aggregate(THIS->count);
} else {
push_undefined();
}
}
void tree_insert(INT32 args) {
struct svalue *key,*val;
struct anode *n;
struct anode *res;
val=NULL;
get_all_args("insert",args,"%*.%*",&key,&val);
if (key==NULL) {
pop_n_elems(args);
RETURN_THIS();
return;
}
res=low_tree_insert(key,val);
pop_n_elems(args);
if (res==NULL && THIS->abend)
Pike_error("Key already exists.\n");
RETURN_THIS();
}
void tree_find(INT32 args) {
struct svalue *key;
struct anode *n;
get_all_args("find",args,"%*",&key);
if (key==NULL) {
pop_n_elems(args);
push_undefined();
return;
}
n=low_tree_find(key);
pop_n_elems(args);
if (n)
push_svalue(n->val);
else
push_undefined();
}
void tree_remove(INT32 args) {
struct svalue *key=NULL;
struct anode *n;
get_all_args("remove",args,"%*",&key);
if (key==NULL) {
push_undefined();
return;
}
n=low_tree_find(key);
if (n==NULL) {
push_undefined();
return;
}
low_tree_remove(n);
pop_n_elems(args);
push_svalue(n->key);
push_svalue(n->val);
f_aggregate(2);
}
void tree_first(INT32 args) {
struct anode *n;
pop_n_elems(args);
n=find_first(THIS->root->left);
if (n) {
push_svalue(n->key);
push_svalue(n->val);
f_aggregate(2);
} else
push_undefined();
}
void tree_next(INT32 args) {
struct anode *n;
struct svalue *key;
get_all_args("next",args,"%*",&key);
if (key==NULL) {
push_undefined();
return;
}
n=low_tree_find(key);
pop_n_elems(args);
if (n==NULL) {
push_undefined();
return;
}
n=find_next(n);
if (n) {
push_svalue(n->key);
push_svalue(n->val);
f_aggregate(2);
} else
push_undefined();
}
void tree_last(INT32 args) {
struct anode *n;
pop_n_elems(args);
n=find_last(THIS->root->left);
if (n) {
push_svalue(n->key);
push_svalue(n->val);
f_aggregate(2);
} else
push_undefined();
}
void tree_prev(INT32 args) {
struct anode *n;
struct svalue *key;
get_all_args("prev",args,"%*",&key);
if (key==NULL) {
push_undefined();
return;
}
n=low_tree_find(key);
pop_n_elems(args);
if (n==NULL) {
push_undefined();
return;
}
n=find_prev(n);
if (n) {
push_svalue(n->key);
push_svalue(n->val);
f_aggregate(2);
} else
push_undefined();
}
void tree_init() {
sentinel.key=sentinel.val=NULL;
}
struct program *tree_program;
struct program *rbtree_program;
struct program *avltree_program;
struct program *splay_program;
PIKE_MODULE_INIT
{
start_new_program();
ADD_STORAGE(struct atable);
ADD_FUNCTION("create",tree_create,tFunc(tOr(tVoid,tFunc(tMixed tMixed,tInt)),tVoid),ID_STATIC);
ADD_FUNCTION("_sizeof",tree_sizeof,tFunc(tVoid,tInt),0);
ADD_FUNCTION("cast",tree_cast,tFunc(tString,tMixed),0);
ADD_FUNCTION("insert",tree_insert,tFunc(tMixed tOr(tMixed,tVoid),tOr(tObj,tInt)),0);
ADD_FUNCTION("find",tree_find,tFunc(tMixed,tOr(tMixed,tVoid)),0);
ADD_FUNCTION("remove",tree_remove,tFunc(tMixed,tArray),0);
ADD_FUNCTION("first",tree_first,tFunc(tVoid,tArray),0);
ADD_FUNCTION("last",tree_last,tFunc(tVoid,tArray),0);
ADD_FUNCTION("next",tree_next,tFunc(tMixed,tArray),0);
ADD_FUNCTION("prev",tree_prev,tFunc(tMixed,tArray),0);
ADD_FUNCTION("clear",tree_clear,tFunc(tVoid,tObj),0);
ADD_FUNCTION("destroy",tree_destroy,tFunc(tVoid,tVoid),ID_STATIC);
tree_program=end_program();
add_integer_constant("INORDER",TREE_INORDER,0);
add_integer_constant("PREORDER",TREE_PREORDER,0);
add_integer_constant("POSTORDER",TREE_POSTORDER,0);
rbtree_program=create_rbtree_program();
splay_program=create_splay_program();
add_program_constant("Tree",tree_program,0);
add_program_constant("RedBlack",rbtree_program,0);
add_program_constant("Splay",splay_program,0);
/* set_init_callback(tree_init); */
}
PIKE_MODULE_EXIT
{
free_program(splay_program);
free_program(rbtree_program);
free_program(tree_program);
}
|
|
|