Module Information
ADT.Tree
Viewing contents of ADT_Tree-1.2/splay.c
/*
* Time-stamp: <05/11/21 08:34:24 riffraff>
*
* $Id: splay.c,v 1.1 2005/11/21 15:34:18 riffraff Exp riffraff $
*/
#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)
extern struct anode sentinel;
static void double_right(struct anode *child,
struct anode *parent,
struct anode *g) {
tree_rotate_right(parent,g);
tree_rotate_right(child,parent);
}
static void double_left(struct anode *child,
struct anode *parent,
struct anode *g) {
tree_rotate_left(parent,g);
tree_rotate_left(child,parent);
}
static void right_left(struct anode *child,
struct anode *parent,
struct anode *g) {
tree_rotate_right(child,parent);
tree_rotate_left(child,g);
}
static void left_right(struct anode *child,
struct anode *parent,
struct anode *g) {
tree_rotate_left(child,parent);
tree_rotate_right(child,g);
}
static void splay_node(struct anode *node) {
struct anode *root,*parent;
root=THIS->root->left;
parent=node->parent;
if (parent->left==node) {
if (parent==root) {
tree_rotate_right(node,parent);
} else {
struct anode *g=parent->parent;
if (g->left==parent) {
double_right(node,parent,g);
} else {
if (g->right!=parent) {
fputs("splay_node: g->right!=parent\n",stderr);
}
right_left(node,parent,g);
}
}
} else {
if (parent->right!=node) {
fputs("splay_node: parent->right!=node\n",stderr);
}
if (parent==root) {
tree_rotate_left(node,parent);
} else {
struct anode *g=parent->parent;
if (g->right==parent) {
double_left(node,parent,g);
} else {
if (g->left!=parent) {
fputs("splay_node: g->left!=parent\n",stderr);
}
left_right(node,parent,g);
}
}
}
}
static void real_low_splay_insert(struct anode *node) {
while (node!=THIS->root->left)
splay_node(node);
}
static struct anode *low_splay_insert(struct svalue *key,
struct svalue *val) {
struct anode *n;
n=low_tree_insert(key,val);
if (n==NULL)
return NULL;
real_low_splay_insert(n);
return n;
}
void splay_insert(INT32 args) {
struct svalue *key,*val;
struct anode *n;
get_all_args("insert",args,"%*.%*",&key,&val);
if (key==NULL) {
pop_n_elems(args);
RETURN_THIS();
return;
}
n=low_splay_insert(key,val);
pop_n_elems(args);
if (n==NULL && THIS->abend)
Pike_error("Key already exists.\n");
RETURN_THIS();
}
static void real_low_splay_remove(struct anode *n) {
struct anode *dummy;
low_tree_delete(n,&dummy,&dummy);
}
static struct anode *low_splay_remove(struct svalue *key) {
struct anode *n;
n=low_tree_find(key);
if (n==NULL)
return NULL;
real_low_splay_remove(n);
return n;
}
void splay_remove(INT32 args) {
struct svalue *key;
struct anode *n;
get_all_args("remove",args,"%*",&key);
if (key==NULL) {
pop_n_elems(args);
push_undefined();
return;
}
n=low_splay_remove(key);
pop_n_elems(args);
if (n) {
push_svalue(n->key);
push_svalue(n->val);
f_aggregate(2);
} else
push_undefined();
}
void splay_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);
if (n==NULL) {
push_undefined();
return;
}
push_svalue(n->key);
push_svalue(n->val);
f_aggregate(2);
while (n!=THIS->root->left)
splay_node(n);
}
void splay_create(INT32 args) {
struct svalue *cb=NULL;
get_all_args("create",args,".%*",&cb);
low_tree_create(cb);
THIS->type=TREE_SPLAY;
pop_n_elems(args);
}
extern struct program *tree_program;
struct program *create_splay_program() {
start_new_program();
low_inherit(tree_program,0,0,0,0,0);
ADD_FUNCTION("create",splay_create,tFunc(tOr(tVoid,tFunc(tMixed tMixed,tInt)),tVoid),ID_STATIC);
ADD_FUNCTION("insert",splay_insert,tFunc(tMixed tOr(tMixed,tVoid),tOr(tObj,tInt)),0);
ADD_FUNCTION("remove",splay_remove,tFunc(tMixed,tArray),0);
ADD_FUNCTION("find",splay_find,tFunc(tMixed,tArray),0);
return end_program();
}
|
|