xref: /titanic_51/usr/src/cmd/cron/elm.c (revision 4870e0a7381ec2ec57437062574e6ddc3dd48d7f)

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
/*	  All Rights Reserved  	*/



/* ********************************************************************** */
/* *		General-Purpose Event List Manager			* */
/* ********************************************************************** */
/*
 *	description:	These routines maintain a time-ordered list of events.
 *	functions available:
 *		init :	Creates and initializes the data structure.
 *			See the reference for parameters to init.
 *		add(&event, time, id) :	Adds an event to the list.
 *					Returns: 0 if success,
 *						-2 if event time is lower
 *						   than Lower Bound time LB
 *						-1 else
 *		remove(id) :	Removes events (with appropriate id).
 *		empty : Returns true if the list is empty, false otherwise.
 *		first :	Removes the element at the head of the list.
 *			Returns a pointer to the event.
 *		delete : Frees up all allocated storage associated
 *			 with the event list.
 *	reference:	Franta, W. R. and Maly, K.,
 *			"An efficient data structure for the
 *			simulation event set ", CACM Vol. 20(8),
 *			Aug 1977, pp. 596-602.
 *	machine dependant:	the constant INFINITY
 */
/* ********************************************************************** */


#include <sys/types.h>
#include <stdlib.h>

extern	void *xmalloc(size_t);

#define	INFINITY	2147483647L	/* upper bound on time	*/
#define	TRUE		1
#define	FALSE		0

/* the following parameters are set in init	*/
static int	DU;		/* number of time intervals	*/
static time_t	LB;		/* lower bound on time	*/
static time_t	DT;		/* width of interval	*/
static int	NLIM;		/* max notices per sublist	*/

/*
 * a notice points to an event.  a notice has the following fields:
 *	time = time of the event.
 *	id = identifier for an event or class of events that may need
 *		to be removed (other than at the front of the list).
 *	event = pointer to the event.
 *	isdummy = tells whether this notice points to a real event or
 *		is just a dummy notice (one that is used to "mark off"
 *		the time intervals that the user specifies in init).
 *	key = points back to the key that points to this notice,
 *		if there is one.
 *	left = points to the notice immediately preceding this one.
 *	right = points to the notice immediately following this one.
 */
struct notice {	time_t	time;
		int	id;
		void	*event;
		short int	isdummy;
		struct key	*key;
		struct notice	*left;
		struct notice	*right; };

/* current points to the front of the list of notices (events)	*/
struct notice	*current = NULL;

/*
 * a key points to a sublist of notices.  a key has the following fields:
 *	time = max time of notices in sublist.
 *	numnote = number of notices in sublist.
 *	notice = pointer to the notice with max time.
 *	left = points to the key immediately preceding this one.
 *	right = points to the key immediately following this one.
 */
struct key {	time_t	time;
		int	numnote;
		struct notice	*notice;
		struct key	*left;
		struct key	*right; };

/*
 * the index list breaks the keys into time intervals as specified in init.
 * the index is "shifted" one time interval whenever el_first returns an
 * event with a time greater than the max time of the first interval
 * (eg. with intervals of a day which span one week (MTWTFSS),
 * if el_first finds the next event is on tuesday, then
 * the intervals of the event list get shifted (TWTFSSM).
 */
struct index {	struct key *key;
		struct index *right; };

/* index pts to the front of the index list */
static struct index *index = NULL;

/* ******************* */
void
el_init(du, lb, dt, nlim)
/* ******************* */
int du, nlim;
time_t lb, dt;
{
	int	i;
	time_t	t;
	struct index *indprev, *ind;
	struct key *kprev, *k;
	struct notice *nprev, *n;

	if ((du < 1) || (dt < 1) || (nlim < 1))
		return;
	DU = du + 1;
	LB = lb;
	DT = dt;
	NLIM = nlim;

	/*
	 * initialize index, keys, and notices
	 */

	/* create first dummy notice */
	n = (struct notice *)xmalloc(sizeof (struct notice));
	n->time = LB;
	n->isdummy = TRUE;
	n->left = NULL;
	nprev = n;
	/* create first dummy key */
	k = (struct key *)xmalloc(sizeof (struct key));
	k->time = LB;
	k->numnote = 1;
	k->notice = n;
	k->left = NULL;
	kprev = k;
	/* make notice point to key */
	n->key = k;
	/* no index element to allocate this time */
	indprev = NULL;
	/* create dummy notices, dummy keys, and index elements */
	t = LB;
	for (i = 1; i < DU; i++) {
		t = t + DT;
		n = (struct notice *)xmalloc(sizeof (struct notice));
		n->time = t;
		n->isdummy = TRUE;
		n->left = nprev;
		nprev->right = n;
		nprev = n;
		k = (struct key *)xmalloc(sizeof (struct key));
		k->time = t;
		k->numnote = 1;
		k->notice = n;
		k->left = kprev;
		kprev->right = k;
		kprev = k;
		n->key = k;
		ind = (struct index *)xmalloc(sizeof (struct index));
		ind->key = k;
		if (indprev == NULL)
			index = ind;
		else
			indprev->right = ind;
		indprev = ind; }
	/* create last dummy notice */
	n = (struct notice *)xmalloc(sizeof (struct notice));
	n->time = INFINITY;
	n->isdummy = TRUE;
	n->left = nprev;
	n->right = NULL;
	nprev->right = n;
	/* create last dummy key */
	k = (struct key *)xmalloc(sizeof (struct key));
	k->time = INFINITY;
	k->numnote = 1;
	k->notice = n;
	k->left = kprev;
	k->right = NULL;
	kprev->right = k;
	n->key = k;
	/* create last index element */
	ind = (struct index *)xmalloc(sizeof (struct index));
	ind->key = k;
	ind->right = NULL;
	indprev->right = ind;

	current = NULL;
}


/* ********************** */
int
el_add(event, time, id)
/* ********************** */
void	*event;
int	id;
time_t	time;
{
	/*
	 * add works slightly differently than in the reference.  if the
	 * sublist to be inserted into is full (numnote = NLIM),
	 * the sublist is split in half.  thus the size of the sublists
	 * in this implementation normally ranges from NLIM/2 to NLIM.
	 */

	struct index *ind;
	struct key *k, *k2;
	struct notice *n, *n2;
	int i;

	/*
	 * time may be 0 when set by next_time() on error or an
	 * invalid time specification of job
	 */
	if ((index == NULL) || (time <= 0)) {
		return (-1);
	}
	if (time < LB) {
		return (-2);
	}

	/* allocate new notice */
	n = (struct notice *)xmalloc(sizeof (struct notice));
	n->time = time;
	n->id = id;
	n->event = event;
	n->isdummy = FALSE;
	n->key = NULL;

	/* find the right interval */
	ind = index;
	while ((ind->key)->time <= time) ind = ind->right;

	/* find the right key */
	k = (ind->key)->left;
	while (k->time > time) k = k->left;
	k = k->right;

	/* (k->time>time) and ((k->left)->time<=time) */
	if (k->numnote == NLIM) {
		/* k's sublist is full, so split it */
		k->numnote = NLIM / 2;
		n2 = k->notice;
		for (i = 1; i <= NLIM/2; i++) n2 = n2->left;
		/* create a key which will point to notice n2 */
		k2 = (struct key *)xmalloc(sizeof (struct key));
		k2->time = n2->time;
		k2->numnote = NLIM - NLIM/2;
		k2->notice = n2;
		k2->right = k;
		k2->left = k->left;
		k->left = k2;
		(k2->left)->right = k2;
		n2->key = k2;	/* have n2 point back to k2 */
		/* which of the new sublists will hold the new notice? */
		if (k2->time > time) k = k2; }

	/*
	 * the new notice n is ready to be inserted
	 * k points to the appropriate sublist
	 */
	k->numnote = k->numnote + 1;
	n2 = k->notice;
	while (n2->time > time) n2 = n2->left;
	n->right = n2->right;
	n->left = n2;
	(n2->right)->left = n;
	n2->right = n;

	if ((current == NULL) || (current->time > time))
		current = n;

	return (0);
}


/* ******************** */
void
el_remove(id, flag)
/* ******************** */
int	id, flag;
{
	/*
	 * remove finds notices n that need to be removed by traversing thru
	 * the notice list.  if n is the sole element of a sublist, the
	 * sublist is deleted.  if not, an adjacent sublist is merged with
	 * n's sublist, if that is possible.  after these checks, n is removed.
	 */

	struct notice *n, *n2;
	struct key *k, *kl, *kr;

	if ((index == NULL) || (current == NULL))
		return;

	n = current;
	while (n != NULL) {
		while ((n != NULL) && ((n->isdummy) || (n->id != id)))
			n = n->right;
		if (n != NULL) {
			/* n should be deleted */
			if ((n->key != NULL) && ((n->key)->numnote == 1)) {
				/* n = sole element of a sublist */
				k = n->key;
				(k->left)->right = k->right;
				(k->right)->left = k->left;
				free(k);
			} else { if (n->key != NULL) {
					/* n has a key pointing to it */
					(n->left)->key = n->key;
					(n->key)->time = (n->left)->time;
					(n->key)->notice = n->left; }
				/* find the key that points to this sublist */
				n2 = n;
				while (n2->key == NULL) n2 = n2->right;
				k = n2->key;
				k->numnote = k->numnote - 1;
				/*
				 * check if two adjacent sublists can be merged
				 * first check left, then check right
				 */
				kl = k->left;
				kr = k->right;
				if ((!(kl->notice)->isdummy) &&
				    ((kl->numnote+k->numnote) <= NLIM)) {
					/* delete the key to the left */
					(kl->notice)->key = NULL;
					k->numnote += kl->numnote;
					(kl->left)->right = k;
					k->left = kl->left;
					free(kl);
				} else if ((!(k->notice)->isdummy) &&
					    ((kr->numnote+k->numnote)
					    <= NLIM)) {
					/* delete this key */
					(k->notice)->key = NULL;
					kr->numnote += k->numnote;
					(k->left)->right = kr;
					kr->left = k->left;
					free(k); }
				}
			/* delete n, then advance n down the list */
			(n->left)->right = n->right;
			(n->right)->left = n->left;
			n2 = n->right;
			free(n);
			n = n2;
			}
		if (flag) break;
		}
	/* now reset current */
	k = (index->key)->left;
	while (k->left != NULL) k = k->left;
	n = (k->notice)->right;
	while ((n != NULL) && (n->isdummy)) n = n->right;
	current = n;
}


/* ********************* */
int
el_empty(void)
/* ********************* */
{
	if (current == NULL)
		return (1);
	else
		return (0);
}


/* ********************* */
void *
el_first(void)
/* ********************* */
{
	struct notice *n, *fn;
	struct key *k, *fk;
	struct index *ind, *fi;
	int ctr, *val;
	time_t next_int;

	if ((index == NULL) || (current == NULL))
		return (NULL);

	while ((index->key)->time < current->time) {
		if (DU == 2) {
			/* only two intervals, so relabel first one */
			k = index->key;
			k->time += DT;
			(k->notice)->time += DT;
			continue; }
		/*
		 * remove the notice, key, and index corresponding
		 * to the first time interval.  Then split the
		 * overflow interval into a normal interval
		 * plus an overflow interval.
		 */
		fi = index;
		fk = fi->key;
		fn = fk->notice;
		(fn->left)->right = fn->right;
		(fn->right)->left = fn->left;
		(fk->left)->right = fk->right;
		(fk->right)->left = fk->left;
		index = index->right;
		/* find where to split	*/
		ind = index;
		while ((ind->right)->right != NULL) ind = ind->right;
		/* ind points to the next to last index interval	*/
		k = ind->key;
		next_int = k->time + DT;	/* upper bound on new inter.  */
		while (k->time < next_int) k = k->right;
		/* k points to the appropriate sublist of notices	*/
		n = (k->notice)->left;
		ctr = 1;
		while (n->time >= next_int) {
			ctr++;
			n = n->left; }
		n = n->right;
		/*
		 * n points to first notice of the new overflow interval
		 * ctr tells how many notices are in the first sublist
		 *	of the new overflow interval
		 * insert the new index element
		 */
		fi->right = ind->right;
		ind->right = fi;
		/* insert the new dummy key	*/
		fk->time = next_int;
		fk->numnote = k->numnote - ctr + 1;
		fk->left = k->left;
		fk->right = k;
		(k->left)->right = fk;
		k->left = fk;
		k->numnote = ctr;
		/* insert the new dummy notice	*/
		fn->time = next_int;
		fn->left = n->left;
		fn->right = n;
		(n->left)->right = fn;
		n->left = fn; }

	/* remove the first element of the list */
	(current->left)->right = current->right;
	(current->right)->left = current->left;
	/* now update the numnote field in the appropriate key */
	n = current;
	while (n->key == NULL) n = n->right;
	k = n->key;
	k->numnote = k->numnote - 1;
	/* if numnote = 0 then this key must be removed */
	if (k->numnote == 0) {
		(k->left)->right = k->right;
		(k->right)->left = k->left;
		free(k); }

	/* now set current to be the head of the list */
	fn = current->right;
	while ((fn != NULL) && (fn->isdummy))
		fn = fn->right;
	val = current->event;
	free(current);
	current = fn;

	return (val);
}


/* ************** */
void
el_delete(void)
/* ************** */
{
	/* el_delete frees up all the space associated with the event list */

	struct index *ind, *ind2;
	struct key *k, *k2;
	struct notice *n, *n2;

	if (index == NULL)
		return;
	ind = index;
	k = ind->key;
	while (k->left != NULL) k = k->left;
	n = k->notice;
	while (n != NULL) {
		n2 = n->right;
		free(n);
		n = n2; }
	while (k != NULL) {
		k2 = k->right;
		free(k);
		k = k2; }
	while (ind != NULL) {
		ind2 = ind->right;
		free(ind);
		ind = ind2; }

	index = NULL;
	current = NULL;
}