/*
 * CDE - Common Desktop Environment
 *
 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
 *
 * These libraries and programs are free software; you can
 * redistribute them and/or modify them under the terms of the GNU
 * Lesser General Public License as published by the Free Software
 * Foundation; either version 2 of the License, or (at your option)
 * any later version.
 *
 * These libraries and programs are distributed in the hope that
 * they will be useful, but WITHOUT ANY WARRANTY; without even the
 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
 * PURPOSE. See the GNU Lesser General Public License for more
 * details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with these libraries and programs; if not, write
 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
 * Floor, Boston, MA 02110-1301 USA
 */
/* $XConsortium: tree.c /main/4 1995/11/09 12:53:11 rswiston $ */
/*
 *  (c) Copyright 1993, 1994 Hewlett-Packard Company
 *  (c) Copyright 1993, 1994 International Business Machines Corp.
 *  (c) Copyright 1993, 1994 Novell, Inc.
 *  (c) Copyright 1993, 1994 Sun Microsystems, Inc.
 */

/*	2-3-4 tree, a.k.a. red-black tree, implementation  */

#include <EUSCompat.h>
#include <sys/param.h>
#include <unistd.h>
#include <stdlib.h>
#include "tree.h"

extern int debug;

typedef struct {
	int size;		/* used in insert and size */
	int count;		/* used in checktree only */
	Rb_Status status;	/* used in checktree and insert */
	caddr_t data;		/* used in lookups only */
	Tree_node *i;		/* used in insert only */
	caddr_t key;		/* used in insert only */
	Tree_node *d;		/* used in delete only */
	Tree_node *y;		/* dummy that is at both links of z */
	Tree_node *z;		/* dummy used as child of leaf nodes */
	Rb_tree *tree;		/* back link to parent tree */
	_DtCmsGetKeyProc get;
	_DtCmsEnumerateProc enumerate;
	_DtCmsCompareProc compare;
	} Private;

typedef void (*Action_proc)
	(/* Private *private; Tree_node *y, *z, *root */);


static Tree_node *
balance(Tree_node *gg, Tree_node *g, Tree_node *f, Tree_node *x)
{
	Tree_node *t;
	Color tc;
	if (gg == NULL || g == NULL) exit (-1);
	if (f == g->llink) {
	  	if (x == f->rlink) {
	    		f->rlink = x->llink;
	    		x->llink = f;
	    		t = f;
	    		f = x;
	    		x = t;
	    	}
	}
	else {
	  	if (x == f->llink) {
	    		f->llink = x->rlink;
	    		x->rlink = f;
	    		t = f;
	    		f = x;
	    		x = t;
	    	}
	}
	if (x == f->llink) {
	  	g->llink = f->rlink;
	  	f->rlink = g;
	}
	else {
	  	g->rlink = f->llink;
	  	f->llink = g;
	}
	if (g == gg->rlink) gg->rlink = f;
	else gg->llink = f;
	tc = g->color;
	g->color = f->color;
	f->color = tc;
	return(f);
}

static void 
doit(Rb_tree *tree, Action_proc proc)
{
	Private *private;
	Tree_node *root;

	if (tree==NULL) return;
	private = (Private *) tree->private;
	root = tree->root;
	if (root == NULL || root->llink != NULL) {
		private->status = rb_badtable;
		return;
	}
	proc(private, private->y, private->z, root);
}

extern Rb_tree *
rb_create (_DtCmsGetKeyProc get, _DtCmsCompareProc compare)
{
	Private *p;
	Tree_node *root, *y, *z;
	Rb_tree *tree;

	p = (Private *) calloc (1, sizeof(Private));
	p->size = 0;
	p->count = 0;
	p->status = rb_ok;
	p->data = NULL;
	p->i = NULL;
	p->key = 0;
	p->d = NULL;
	p->y = (Tree_node *) calloc (1, sizeof(Tree_node));
	p->z = (Tree_node *) calloc (1, sizeof(Tree_node));
	p->get = get;
	p->enumerate = NULL;
	p->compare = compare;

	root = (Tree_node *) calloc (1, sizeof(Tree_node));
	y = p->y;
	z = p->z;
	tree = (Rb_tree *) calloc (1, sizeof(Rb_tree));
	tree->root = root;
	tree->private = (caddr_t) p;
	p->tree = tree;   /* link back so callbacks can access */
	root->color = black;
	root->llink = NULL;
	root->rlink = z;
	y->color = red;
	y->llink = y->rlink = NULL;
	z->color = black;
	z->llink = z->rlink = y;

	return(tree);
}


extern void
rb_destroy(Rb_tree *tree, _DtCmsEnumerateProc destroy)
{
	Private *p = NULL;
	caddr_t data = NULL;
	Tree_node *node = NULL;
	caddr_t key;

	/* NOTE:there is a client data field
		associated with the tree struct.
		It is up to the client to destroy
		these.				*/
	if (tree==NULL) return;
	p = (Private *) tree->private;
	data = rb_lookup_smallest(tree);

	/* enumerate tree, destroying data */
	while(data != NULL) {
		key = p->get(data);
		node = rb_delete(tree, key);
		if (destroy)
			destroy(data);
		free(node);
		data = rb_lookup_next_larger(tree, key);
	}

	/* destroy the private internal struct */
	free(p->y);
	free(p->z);
	free(p);

	/* destroy the root node */
	free(tree->root);

	/* destroy the tree */
	free(tree);
}

/* ARGSUSED */
static void
size_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
{
	/* dummy proc for monitor */
}

extern int
rb_size(Rb_tree *tree)
{
	Private *p;
	if (tree==NULL) return(0);
	p = (Private *) tree->private;
	if (tree != NULL) {
		doit(tree, size_callback);
		return(p->size);
	}
	else return(0);
}

/* ARGSUSED */
static void
insert_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
{
	Tree_node *x=NULL, *gg=NULL, *g=NULL, *f=NULL;
	_DtCmsComparisonResult c = _DtCmsIsGreater;

	f = root;
	x = f->rlink;
	for (;;) {
		if (x->llink->color == red && x->rlink->color == red) {
			if (x == z) {
				if (c == _DtCmsIsEqual) {
					private->status = rb_duplicate;
					root->rlink->color = black;
					return;
				}
	      			x = private->i;
	      			x->llink = z;
	      			x->rlink = z;
	      			if (c == _DtCmsIsLess) f->llink = x; else f->rlink = x;
	      			c = _DtCmsIsEqual;
	      			private->size++;
	      		}
	    		x->llink->color = black;
	    		x->rlink->color = black;
	    		x->color = red;
	    		if (f->color == red) {
	      			g = balance (gg, g, f, x);
	      			x = g;
	      		}
		}
	  	if (c == _DtCmsIsEqual) break;
	  	gg = g; g = f; f = x;
	  	c = private->compare (private->key, x->data);
	  	if (c==_DtCmsIsEqual) {
			private->status=rb_duplicate;
			root->rlink->color=black;
			return;
		}
	  	x = (c == _DtCmsIsLess) ? x->llink : x-> rlink;
	} 
	root->rlink->color = black;
}

extern Rb_Status
rb_insert_node(Rb_tree *tree, Tree_node *node, caddr_t key)
{
	Private *private;

	if (tree==NULL) return(rb_notable);
	private = (Private *) tree->private;
	private->status = rb_ok;
	private->i = node;
	private->key = key;
	doit (tree, insert_callback);
	return (private->status);
}

extern Rb_Status
rb_insert(Rb_tree *tree, caddr_t data, caddr_t key)
{
	Tree_node *node;

	if (tree==NULL) return(rb_notable);
	node = (Tree_node *)calloc(1, sizeof(Tree_node));
	node->data = data;
	return(rb_insert_node(tree, node, key));
}

static void
delete_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
{
	Tree_node *f, *result, *parent;
	Tree_node *x, *g, *b;
	_DtCmsComparisonResult c;

	f = root;
	x = f->rlink;
	result = NULL;

	if (x == z) return;
	y->color = black;
	if (x->llink->color == black && x->rlink->color == black)
		x->color = red;
	c = private->compare(private->key, x->data);
	if (c == _DtCmsIsEqual) {
		result = x;
		parent = f;
	}
	for (;;) {
		g = f;
	  	f = x;
	  	if (c == _DtCmsIsLess) {
	    		b = x->rlink;
	    		x = x->llink;
	    	}
	  	else {
	    		b = x->llink;
	    		x = x->rlink;
	    	}
	  	if (x != z) {
	    		c = private->compare(private->key, x->data);
	    		if (c == _DtCmsIsEqual) {
	      			result = x; 
	      			parent = f;
	      		}
	    	}
		if (x->color == red || x->llink->color == red ||
	     		x->rlink->color == red) continue;
		if (b->color == red) {
	  		if (b == f->llink) {
	    			f->llink = b->rlink;
	    			b->rlink = f;
	    		}
	  		else {
	    			f->rlink = b->llink;
	    			b->llink = f;
	    		}
	  		f->color = red;
	  		b->color = black;
	  		if (f == g->llink) g->llink = b;
	  		else g->rlink = b;
	  		x = b;
	  		c = private->compare(private->key, x->data);
	  		continue;
		}
		if (x == z) break;
		x->color = red;
		if (b->llink->color == red) {
	  		b->llink->color = black;
	  		x = balance (g, f, b, b->llink);
	  		c = private->compare(private->key, x->data);
	  		continue;
	  	}
		if (b->rlink->color == red) {
	  		b->rlink->color = black;
	  		x = balance(g, f, b, b->rlink);
	  		c = private->compare(private->key, x->data);
	  		continue;
		}
		f->color = black;
		b->color = red;
	} /* end for-loop */ 
	root->rlink->color = black;
	z->color = black;
	y->color = red;
	if (result != NULL) {
		if (g->llink == f) g->llink = z;
	  	else g->rlink = z;
	  	if (f != result) {
	    		if (parent->llink == result) parent->llink = f;
	    		else parent->rlink = f;
	    		f->llink = result->llink;
	    		f->rlink = result->rlink;
	    		f->color = result->color;
	    	}
	  	private->size--;
	} 
	private->d = result;
}

extern Tree_node *
rb_delete(Rb_tree *tree, caddr_t key)
{
	Private *p;
	if (tree==NULL) return((Tree_node *)NULL);
	p = (Private *) tree->private;
	p->key = key;
	p->d = NULL;	/* in case the key is not found */
	doit (tree, delete_callback);
	return(p->d);
}

/* ARGSUSED */
static void
lookup_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
{
	_DtCmsComparisonResult c;
	Tree_node *eq = root->rlink;
	for (;;) {
		if (eq == z) return;
		c = private->compare(private->key, eq->data);
	  	switch(c) {
	    	case _DtCmsIsEqual:
	      		goto bye;
	    	case _DtCmsIsLess:
	      		eq = eq->llink;
	      		break;
	    	case _DtCmsIsGreater:
	      		eq = eq->rlink;
	      		break;
	    	default:
	      		break;
	    	}
	} 
	bye: private->data = eq->data;
}

extern caddr_t
rb_lookup(Rb_tree *tree, caddr_t key)
{
	Private *private;
	if (tree==NULL) return((caddr_t)NULL);
	private = (Private *)tree->private;
	private->key = key;
	private->data = NULL; /* might have been previously used */
	doit (tree, lookup_callback);
	return (private->data);
}

/* ARGSUSED */
static void
lookup_smallest_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
{
	Tree_node *smallest = root->rlink;
	if (smallest == z) return;
	while (smallest->llink != z) {
		  smallest = smallest->llink;
	}
	private->data = smallest->data;
}

extern caddr_t
rb_lookup_smallest(Rb_tree *tree)
{
	Private *private;
	if (tree==NULL) return((caddr_t)NULL);
	private = (Private *)tree->private;
	private->data = NULL; /* might have been previously used */
	doit (tree, lookup_smallest_callback);
	return (private->data);
}

/* ARGSUSED */
static void
next_larger_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
{
	Tree_node *larger = NULL;
	Tree_node *x = root->rlink;
	while (x != z) {
		if (private->compare (private->key, x->data) == _DtCmsIsLess) {
	    		larger = x;
	    		x = x->llink;
		}
		else x= x->rlink;
	}
	if (larger != NULL) private->data = larger->data;
}

extern caddr_t
rb_lookup_next_larger(Rb_tree *tree, caddr_t key)
{
	Private *private;
	if (tree==NULL) return((caddr_t)NULL);
	private = (Private *) tree->private;
	private->key = key;
	private->data = NULL; /* might have been previously used */
	doit (tree, next_larger_callback);
	return(private->data);
}

/* ARGSUSED */
static void
lookup_largest_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
{
	Tree_node *largest = root->rlink;
	if (largest == z) return;
	while (largest->rlink != z) {
		largest = largest->rlink;
	}
	private->data = largest->data;
}

extern caddr_t
rb_lookup_largest(Rb_tree *tree)
{
	Private *private;

	if (tree==NULL) return((caddr_t)NULL);
	private = (Private *) tree->private;
	private->data = NULL; /* might have been previously used */
	doit (tree, lookup_largest_callback);
	return (private->data);
}

/* ARGSUSED */
static void
next_smaller_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
{

	Tree_node *smaller = NULL;
	Tree_node *x = root->rlink;
	while (x != z) {
		if (private->compare(private->key, x->data) == _DtCmsIsGreater) {
			smaller = x;
			x = x->rlink;
		}
		else x = x->llink;
	}
	if (smaller != NULL) private->data = smaller->data;
}

extern caddr_t
rb_lookup_next_smaller(Rb_tree *tree, caddr_t key)
{
	Private *private;
	if (tree==NULL) return((caddr_t)NULL);
	private = (Private *) tree->private;
	private->key = key;
	private->data = NULL; /* might have been previously used */
	doit (tree, next_smaller_callback);
	return(private->data);
}

typedef enum {up, down} Direction;

static boolean_t
visit_subtree(Tree_node *node, Private *p, Tree_node *z, Direction dir)
{
	Tree_node *link;
	link = (dir == up) ? node->llink : node->rlink;
	if (link != z && visit_subtree(link, p, z, dir)) return(B_TRUE);
	if (p->enumerate((caddr_t)node, node->data)) return(B_TRUE);
	link = (dir == up) ? node->rlink : node->llink;
	if (link != z) return(visit_subtree(link, p, z, dir));
	else return(B_FALSE);
}

/* ARGSUSED */
static boolean_t
enumerate_up_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
{
	if (root == NULL || root->rlink == z) return (B_FALSE);
	return (visit_subtree(root->rlink, private, z, up));
}

extern Rb_Status
rb_enumerate_up(Rb_tree *tree, _DtCmsEnumerateProc proc)
{
	Private *private;
	if (tree==NULL) return (rb_badtable);
	private = (Private *) tree->private;
	private->enumerate = proc;
	if (tree->root == NULL || tree->root->llink != NULL)
		return rb_badtable;

	if (enumerate_up_callback(private, private->y, private->z, tree->root))
		return (rb_failed);
	else
		return (rb_ok);
}

/* ARGSUSED */
static void
enumerate_down_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
{
	if (root == NULL || root->rlink == z) return;
	(void) visit_subtree(root->rlink, private, z, down);
}

extern void
rb_enumerate_down(Rb_tree *tree, _DtCmsEnumerateProc proc)
{
	Private *private;
	if (tree==NULL) return;
	private = (Private *) tree->private;
	private->enumerate = proc;
	doit (tree, enumerate_down_callback);
}

/* --------------------DEBUGGING-------------------------*/

static int 
assert(int p)
{
	return(p);
}

typedef struct {caddr_t max; int i; boolean_t b;} Rec;

static void
check1(Tree_node *x, caddr_t max, Tree_node *z, Rec *rec, Private *private)
{
	int dl, dr;
	boolean_t redchild;
	Rec localrec; Rec *localp = &localrec;
	if (x == z) {
		rec->max = max;
	  	rec->i = 0;
	  	rec->b = B_FALSE;
	  	return;
	}
	check1(x->llink, max, z, localp, private);
	if (private->status == rb_badtable) return;
	max = localp->max;
	dl = localp->i;
	redchild = localp->b;
	if (!assert (!(redchild && (x->color == red)))) {
		private->status = rb_badtable;
	  	return;
	} 
	if (!assert (private->compare(max, x->data) ==
		     (private->count == 0 ? _DtCmsIsEqual : _DtCmsIsLess))) {
		private->status = rb_badtable;
	  	return;
	}
	private->count++;
	check1(x->rlink, private->get(x->data), z, localp, private);
	if (private->status == rb_badtable) return;
	max = localp->max;
	dr = localp->i;
	redchild = localp->b;
	if (!assert (!(redchild && (x->color == red)))) {
		private->status = rb_badtable;
	  	return;
	}
	if (!assert (dl == dr)) {
	  	private->status = rb_badtable;
	  	return;
	}
	rec->max = max;
	rec->i = dl + ((x->color == black) ? 1 : 0);
	rec->b = ((x->color == red) ? B_TRUE : B_FALSE);
}

static void
check_tree_callback(Private *private, Tree_node *y, Tree_node *z, Tree_node *root)
{
	if (!assert (z->llink == y)) {
		private->status = rb_badtable;
		return;
	}
	if (!assert (z->rlink == y)) {
		private->status = rb_badtable;
		return;
	}
	if (root->rlink != z) {
		Rec localrec;
		Rec *localp = &localrec;
		Tree_node *smallest = root->rlink;
		while (smallest->llink != z) {
			smallest = smallest->llink;
		}
		check1(root->rlink, private->get(smallest->data), z, localp, private);
		if (private->status == rb_badtable) return;
	}
}

extern Rb_Status
rb_check_tree(Rb_tree *tree)
{
	Private *p;
	if (tree==NULL) return(rb_notable);
	p = (Private *) tree->private;
	p->status = rb_ok;
	p->count = 0;
	doit (tree, check_tree_callback);
	return(p->status);
}