xref: /illumos-gate/usr/src/cmd/cron/elm.c (revision 618372bc)
17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate  * CDDL HEADER START
37c478bd9Sstevel@tonic-gate  *
47c478bd9Sstevel@tonic-gate  * The contents of this file are subject to the terms of the
5e2553d68SSerge Dussud  * Common Development and Distribution License (the "License").
6e2553d68SSerge Dussud  * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate  *
87c478bd9Sstevel@tonic-gate  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate  * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate  * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate  * and limitations under the License.
127c478bd9Sstevel@tonic-gate  *
137c478bd9Sstevel@tonic-gate  * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate  * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate  * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate  * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate  *
197c478bd9Sstevel@tonic-gate  * CDDL HEADER END
207c478bd9Sstevel@tonic-gate  */
22032624d5Sbasabi /*
23e2553d68SSerge Dussud  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
24032624d5Sbasabi  * Use is subject to license terms.
25032624d5Sbasabi  */
277c478bd9Sstevel@tonic-gate /*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
28*618372bcSSebastian Wiedenroth /*	  All Rights Reserved  */
32e2553d68SSerge Dussud /* ********************************************************************** */
33e2553d68SSerge Dussud /* *		General-Purpose Event List Manager			* */
34e2553d68SSerge Dussud /* ********************************************************************** */
35e2553d68SSerge Dussud /*
36e2553d68SSerge Dussud  *	description:	These routines maintain a time-ordered list of events.
37e2553d68SSerge Dussud  *	functions available:
38e2553d68SSerge Dussud  *		init :	Creates and initializes the data structure.
39e2553d68SSerge Dussud  *			See the reference for parameters to init.
40e2553d68SSerge Dussud  *		add(&event, time, id) :	Adds an event to the list.
41e2553d68SSerge Dussud  *					Returns: 0 if success,
42e2553d68SSerge Dussud  *						-2 if event time is lower
43e2553d68SSerge Dussud  *						   than Lower Bound time LB
44e2553d68SSerge Dussud  *						-1 else
45e2553d68SSerge Dussud  *		remove(id) :	Removes events (with appropriate id).
46e2553d68SSerge Dussud  *		empty : Returns true if the list is empty, false otherwise.
47e2553d68SSerge Dussud  *		first :	Removes the element at the head of the list.
48e2553d68SSerge Dussud  *			Returns a pointer to the event.
49e2553d68SSerge Dussud  *		delete : Frees up all allocated storage associated
50e2553d68SSerge Dussud  *			 with the event list.
51e2553d68SSerge Dussud  *	reference:	Franta, W. R. and Maly, K.,
52e2553d68SSerge Dussud  *			"An efficient data structure for the
53e2553d68SSerge Dussud  *			simulation event set ", CACM Vol. 20(8),
54e2553d68SSerge Dussud  *			Aug 1977, pp. 596-602.
55e2553d68SSerge Dussud  *	machine dependant:	the constant INFINITY
56e2553d68SSerge Dussud  */
57e2553d68SSerge Dussud /* ********************************************************************** */
607c478bd9Sstevel@tonic-gate #include <sys/types.h>
617c478bd9Sstevel@tonic-gate #include <stdlib.h>
637c478bd9Sstevel@tonic-gate extern	void *xmalloc(size_t);
657c478bd9Sstevel@tonic-gate #define	INFINITY	2147483647L	/* upper bound on time	*/
66e2553d68SSerge Dussud #define	TRUE		1
67e2553d68SSerge Dussud #define	FALSE		0
697c478bd9Sstevel@tonic-gate /* the following parameters are set in init	*/
707c478bd9Sstevel@tonic-gate static int	DU;		/* number of time intervals	*/
717c478bd9Sstevel@tonic-gate static time_t	LB;		/* lower bound on time	*/
727c478bd9Sstevel@tonic-gate static time_t	DT;		/* width of interval	*/
737c478bd9Sstevel@tonic-gate static int	NLIM;		/* max notices per sublist	*/
75e2553d68SSerge Dussud /*
76e2553d68SSerge Dussud  * a notice points to an event.  a notice has the following fields:
77e2553d68SSerge Dussud  *	time = time of the event.
78e2553d68SSerge Dussud  *	id = identifier for an event or class of events that may need
79e2553d68SSerge Dussud  *		to be removed (other than at the front of the list).
80e2553d68SSerge Dussud  *	event = pointer to the event.
81e2553d68SSerge Dussud  *	isdummy = tells whether this notice points to a real event or
82e2553d68SSerge Dussud  *		is just a dummy notice (one that is used to "mark off"
83e2553d68SSerge Dussud  *		the time intervals that the user specifies in init).
84e2553d68SSerge Dussud  *	key = points back to the key that points to this notice,
85e2553d68SSerge Dussud  *		if there is one.
86e2553d68SSerge Dussud  *	left = points to the notice immediately preceding this one.
87e2553d68SSerge Dussud  *	right = points to the notice immediately following this one.
88e2553d68SSerge Dussud  */
897c478bd9Sstevel@tonic-gate struct notice {	time_t	time;
907c478bd9Sstevel@tonic-gate 		int	id;
917c478bd9Sstevel@tonic-gate 		void	*event;
927c478bd9Sstevel@tonic-gate 		short int	isdummy;
937c478bd9Sstevel@tonic-gate 		struct key	*key;
947c478bd9Sstevel@tonic-gate 		struct notice	*left;
957c478bd9Sstevel@tonic-gate 		struct notice	*right; };
977c478bd9Sstevel@tonic-gate /* current points to the front of the list of notices (events)	*/
98e2553d68SSerge Dussud struct notice	*current = NULL;
99e2553d68SSerge Dussud 
100e2553d68SSerge Dussud /*
101e2553d68SSerge Dussud  * a key points to a sublist of notices.  a key has the following fields:
102e2553d68SSerge Dussud  *	time = max time of notices in sublist.
103e2553d68SSerge Dussud  *	numnote = number of notices in sublist.
104e2553d68SSerge Dussud  *	notice = pointer to the notice with max time.
105e2553d68SSerge Dussud  *	left = points to the key immediately preceding this one.
106e2553d68SSerge Dussud  *	right = points to the key immediately following this one.
107e2553d68SSerge Dussud  */
1087c478bd9Sstevel@tonic-gate struct key {	time_t	time;
1097c478bd9Sstevel@tonic-gate 		int	numnote;
1107c478bd9Sstevel@tonic-gate 		struct notice	*notice;
1117c478bd9Sstevel@tonic-gate 		struct key	*left;
1127c478bd9Sstevel@tonic-gate 		struct key	*right; };
114e2553d68SSerge Dussud /*
115e2553d68SSerge Dussud  * the index list breaks the keys into time intervals as specified in init.
116e2553d68SSerge Dussud  * the index is "shifted" one time interval whenever el_first returns an
117e2553d68SSerge Dussud  * event with a time greater than the max time of the first interval
118e2553d68SSerge Dussud  * (eg. with intervals of a day which span one week (MTWTFSS),
119e2553d68SSerge Dussud  * if el_first finds the next event is on tuesday, then
120e2553d68SSerge Dussud  * the intervals of the event list get shifted (TWTFSSM).
121e2553d68SSerge Dussud  */
1227c478bd9Sstevel@tonic-gate struct index {	struct key *key;
1237c478bd9Sstevel@tonic-gate 		struct index *right; };
125e2553d68SSerge Dussud /* index pts to the front of the index list */
126e2553d68SSerge Dussud static struct index *index = NULL;
128*618372bcSSebastian Wiedenroth 
1297c478bd9Sstevel@tonic-gate void
el_init(int du,time_t lb,time_t dt,int nlim)130*618372bcSSebastian Wiedenroth el_init(int du, time_t lb, time_t dt, int nlim)
1317c478bd9Sstevel@tonic-gate {
1327c478bd9Sstevel@tonic-gate 	int	i;
1337c478bd9Sstevel@tonic-gate 	time_t	t;
134e2553d68SSerge Dussud 	struct index *indprev, *ind;
1357c478bd9Sstevel@tonic-gate 	struct key *kprev, *k;
1367c478bd9Sstevel@tonic-gate 	struct notice *nprev, *n;
138e2553d68SSerge Dussud 	if ((du < 1) || (dt < 1) || (nlim < 1))
139e2553d68SSerge Dussud 		return;
1407c478bd9Sstevel@tonic-gate 	DU = du + 1;
1417c478bd9Sstevel@tonic-gate 	LB = lb;
1427c478bd9Sstevel@tonic-gate 	DT = dt;
1437c478bd9Sstevel@tonic-gate 	NLIM = nlim;
1457c478bd9Sstevel@tonic-gate 	/*
1467c478bd9Sstevel@tonic-gate 	 * initialize index, keys, and notices
1477c478bd9Sstevel@tonic-gate 	 */
1497c478bd9Sstevel@tonic-gate 	/* create first dummy notice */
150e2553d68SSerge Dussud 	n = (struct notice *)xmalloc(sizeof (struct notice));
1517c478bd9Sstevel@tonic-gate 	n->time = LB;
1527c478bd9Sstevel@tonic-gate 	n->isdummy = TRUE;
1537c478bd9Sstevel@tonic-gate 	n->left = NULL;
1547c478bd9Sstevel@tonic-gate 	nprev = n;
1557c478bd9Sstevel@tonic-gate 	/* create first dummy key */
156e2553d68SSerge Dussud 	k = (struct key *)xmalloc(sizeof (struct key));
1577c478bd9Sstevel@tonic-gate 	k->time = LB;
1587c478bd9Sstevel@tonic-gate 	k->numnote = 1;
1597c478bd9Sstevel@tonic-gate 	k->notice = n;
1607c478bd9Sstevel@tonic-gate 	k->left = NULL;
1617c478bd9Sstevel@tonic-gate 	kprev = k;
1627c478bd9Sstevel@tonic-gate 	/* make notice point to key */
1637c478bd9Sstevel@tonic-gate 	n->key = k;
1647c478bd9Sstevel@tonic-gate 	/* no index element to allocate this time */
1657c478bd9Sstevel@tonic-gate 	indprev = NULL;
1667c478bd9Sstevel@tonic-gate 	/* create dummy notices, dummy keys, and index elements */
1677c478bd9Sstevel@tonic-gate 	t = LB;
168e2553d68SSerge Dussud 	for (i = 1; i < DU; i++) {
1697c478bd9Sstevel@tonic-gate 		t = t + DT;
170e2553d68SSerge Dussud 		n = (struct notice *)xmalloc(sizeof (struct notice));
1717c478bd9Sstevel@tonic-gate 		n->time = t;
1727c478bd9Sstevel@tonic-gate 		n->isdummy = TRUE;
1737c478bd9Sstevel@tonic-gate 		n->left = nprev;
1747c478bd9Sstevel@tonic-gate 		nprev->right = n;
1757c478bd9Sstevel@tonic-gate 		nprev = n;
176e2553d68SSerge Dussud 		k = (struct key *)xmalloc(sizeof (struct key));
1777c478bd9Sstevel@tonic-gate 		k->time = t;
1787c478bd9Sstevel@tonic-gate 		k->numnote = 1;
1797c478bd9Sstevel@tonic-gate 		k->notice = n;
1807c478bd9Sstevel@tonic-gate 		k->left = kprev;
1817c478bd9Sstevel@tonic-gate 		kprev->right = k;
1827c478bd9Sstevel@tonic-gate 		kprev = k;
1837c478bd9Sstevel@tonic-gate 		n->key = k;
184e2553d68SSerge Dussud 		ind = (struct index *)xmalloc(sizeof (struct index));
1857c478bd9Sstevel@tonic-gate 		ind->key = k;
186e2553d68SSerge Dussud 		if (indprev == NULL)
187e2553d68SSerge Dussud 			index = ind;
188e2553d68SSerge Dussud 		else
189e2553d68SSerge Dussud 			indprev->right = ind;
1907c478bd9Sstevel@tonic-gate 		indprev = ind; }
1917c478bd9Sstevel@tonic-gate 	/* create last dummy notice */
192e2553d68SSerge Dussud 	n = (struct notice *)xmalloc(sizeof (struct notice));
1937c478bd9Sstevel@tonic-gate 	n->time = INFINITY;
1947c478bd9Sstevel@tonic-gate 	n->isdummy = TRUE;
1957c478bd9Sstevel@tonic-gate 	n->left = nprev;
1967c478bd9Sstevel@tonic-gate 	n->right = NULL;
1977c478bd9Sstevel@tonic-gate 	nprev->right = n;
1987c478bd9Sstevel@tonic-gate 	/* create last dummy key */
199e2553d68SSerge Dussud 	k = (struct key *)xmalloc(sizeof (struct key));
2007c478bd9Sstevel@tonic-gate 	k->time = INFINITY;
2017c478bd9Sstevel@tonic-gate 	k->numnote = 1;
2027c478bd9Sstevel@tonic-gate 	k->notice = n;
2037c478bd9Sstevel@tonic-gate 	k->left = kprev;
2047c478bd9Sstevel@tonic-gate 	k->right = NULL;
2057c478bd9Sstevel@tonic-gate 	kprev->right = k;
2067c478bd9Sstevel@tonic-gate 	n->key = k;
2077c478bd9Sstevel@tonic-gate 	/* create last index element */
208e2553d68SSerge Dussud 	ind = (struct index *)xmalloc(sizeof (struct index));
2097c478bd9Sstevel@tonic-gate 	ind->key = k;
2107c478bd9Sstevel@tonic-gate 	ind->right = NULL;
2117c478bd9Sstevel@tonic-gate 	indprev->right = ind;
212e2553d68SSerge Dussud 
2137c478bd9Sstevel@tonic-gate 	current = NULL;
2147c478bd9Sstevel@tonic-gate }
217e2553d68SSerge Dussud int
el_add(void * event,time_t time,int id)218*618372bcSSebastian Wiedenroth el_add(void *event, time_t time, int id)
2197c478bd9Sstevel@tonic-gate {
220e2553d68SSerge Dussud 	/*
221e2553d68SSerge Dussud 	 * add works slightly differently than in the reference.  if the
222e2553d68SSerge Dussud 	 * sublist to be inserted into is full (numnote = NLIM),
223e2553d68SSerge Dussud 	 * the sublist is split in half.  thus the size of the sublists
224e2553d68SSerge Dussud 	 * in this implementation normally ranges from NLIM/2 to NLIM.
225e2553d68SSerge Dussud 	 */
2277c478bd9Sstevel@tonic-gate 	struct index *ind;
228e2553d68SSerge Dussud 	struct key *k, *k2;
229e2553d68SSerge Dussud 	struct notice *n, *n2;
2307c478bd9Sstevel@tonic-gate 	int i;
232e2553d68SSerge Dussud 	/*
233e2553d68SSerge Dussud 	 * time may be 0 when set by next_time() on error or an
234e2553d68SSerge Dussud 	 * invalid time specification of job
235e2553d68SSerge Dussud 	 */
236e2553d68SSerge Dussud 	if ((index == NULL) || (time <= 0)) {
237e2553d68SSerge Dussud 		return (-1);
238e2553d68SSerge Dussud 	}
239e2553d68SSerge Dussud 	if (time < LB) {
240e2553d68SSerge Dussud 		return (-2);
241e2553d68SSerge Dussud 	}
2437c478bd9Sstevel@tonic-gate 	/* allocate new notice */
244e2553d68SSerge Dussud 	n = (struct notice *)xmalloc(sizeof (struct notice));
2457c478bd9Sstevel@tonic-gate 	n->time = time;
2467c478bd9Sstevel@tonic-gate 	n->id = id;
2477c478bd9Sstevel@tonic-gate 	n->event = event;
2487c478bd9Sstevel@tonic-gate 	n->isdummy = FALSE;
2497c478bd9Sstevel@tonic-gate 	n->key = NULL;
2517c478bd9Sstevel@tonic-gate 	/* find the right interval */
2527c478bd9Sstevel@tonic-gate 	ind = index;
2537c478bd9Sstevel@tonic-gate 	while ((ind->key)->time <= time) ind = ind->right;
254e2553d68SSerge Dussud 
2557c478bd9Sstevel@tonic-gate 	/* find the right key */
2567c478bd9Sstevel@tonic-gate 	k = (ind->key)->left;
2577c478bd9Sstevel@tonic-gate 	while (k->time > time) k = k->left;
2587c478bd9Sstevel@tonic-gate 	k = k->right;
2607c478bd9Sstevel@tonic-gate 	/* (k->time>time) and ((k->left)->time<=time) */
2617c478bd9Sstevel@tonic-gate 	if (k->numnote == NLIM) {
2627c478bd9Sstevel@tonic-gate 		/* k's sublist is full, so split it */
2637c478bd9Sstevel@tonic-gate 		k->numnote = NLIM / 2;
2647c478bd9Sstevel@tonic-gate 		n2 = k->notice;
265e2553d68SSerge Dussud 		for (i = 1; i <= NLIM/2; i++) n2 = n2->left;
2667c478bd9Sstevel@tonic-gate 		/* create a key which will point to notice n2 */
267e2553d68SSerge Dussud 		k2 = (struct key *)xmalloc(sizeof (struct key));
2687c478bd9Sstevel@tonic-gate 		k2->time = n2->time;
2697c478bd9Sstevel@tonic-gate 		k2->numnote = NLIM - NLIM/2;
2707c478bd9Sstevel@tonic-gate 		k2->notice = n2;
2717c478bd9Sstevel@tonic-gate 		k2->right = k;
2727c478bd9Sstevel@tonic-gate 		k2->left = k->left;
2737c478bd9Sstevel@tonic-gate 		k->left = k2;
2747c478bd9Sstevel@tonic-gate 		(k2->left)->right = k2;
2757c478bd9Sstevel@tonic-gate 		n2->key = k2;	/* have n2 point back to k2 */
2767c478bd9Sstevel@tonic-gate 		/* which of the new sublists will hold the new notice? */
2777c478bd9Sstevel@tonic-gate 		if (k2->time > time) k = k2; }
279e2553d68SSerge Dussud 	/*
280e2553d68SSerge Dussud 	 * the new notice n is ready to be inserted
281e2553d68SSerge Dussud 	 * k points to the appropriate sublist
282e2553d68SSerge Dussud 	 */
2837c478bd9Sstevel@tonic-gate 	k->numnote = k->numnote + 1;
2847c478bd9Sstevel@tonic-gate 	n2 = k->notice;
2857c478bd9Sstevel@tonic-gate 	while (n2->time > time) n2 = n2->left;
2867c478bd9Sstevel@tonic-gate 	n->right = n2->right;
2877c478bd9Sstevel@tonic-gate 	n->left = n2;
2887c478bd9Sstevel@tonic-gate 	(n2->right)->left = n;
2897c478bd9Sstevel@tonic-gate 	n2->right = n;
291e2553d68SSerge Dussud 	if ((current == NULL) || (current->time > time))
292e2553d68SSerge Dussud 		current = n;
293e2553d68SSerge Dussud 
294e2553d68SSerge Dussud 	return (0);
2957c478bd9Sstevel@tonic-gate }
2987c478bd9Sstevel@tonic-gate void
el_remove(int id,int flag)299*618372bcSSebastian Wiedenroth el_remove(int id, int flag)
3007c478bd9Sstevel@tonic-gate {
301e2553d68SSerge Dussud 	/*
302e2553d68SSerge Dussud 	 * remove finds notices n that need to be removed by traversing thru
303e2553d68SSerge Dussud 	 * the notice list.  if n is the sole element of a sublist, the
304e2553d68SSerge Dussud 	 * sublist is deleted.  if not, an adjacent sublist is merged with
305e2553d68SSerge Dussud 	 * n's sublist, if that is possible.  after these checks, n is removed.
306e2553d68SSerge Dussud 	 */
308e2553d68SSerge Dussud 	struct notice *n, *n2;
309e2553d68SSerge Dussud 	struct key *k, *kl, *kr;
311e2553d68SSerge Dussud 	if ((index == NULL) || (current == NULL))
312e2553d68SSerge Dussud 		return;
3147c478bd9Sstevel@tonic-gate 	n = current;
315e2553d68SSerge Dussud 	while (n != NULL) {
316e2553d68SSerge Dussud 		while ((n != NULL) && ((n->isdummy) || (n->id != id)))
317e2553d68SSerge Dussud 			n = n->right;
3187c478bd9Sstevel@tonic-gate 		if (n != NULL) {
3197c478bd9Sstevel@tonic-gate 			/* n should be deleted */
320e2553d68SSerge Dussud 			if ((n->key != NULL) && ((n->key)->numnote == 1)) {
3217c478bd9Sstevel@tonic-gate 				/* n = sole element of a sublist */
3227c478bd9Sstevel@tonic-gate 				k = n->key;
3237c478bd9Sstevel@tonic-gate 				(k->left)->right = k->right;
3247c478bd9Sstevel@tonic-gate 				(k->right)->left = k->left;
325e2553d68SSerge Dussud 				free(k);
326*618372bcSSebastian Wiedenroth 			} else {
327*618372bcSSebastian Wiedenroth 				if (n->key != NULL) {
3287c478bd9Sstevel@tonic-gate 					/* n has a key pointing to it */
3297c478bd9Sstevel@tonic-gate 					(n->left)->key = n->key;
3307c478bd9Sstevel@tonic-gate 					(n->key)->time = (n->left)->time;
331*618372bcSSebastian Wiedenroth 					(n->key)->notice = n->left;
332*618372bcSSebastian Wiedenroth 				}
3337c478bd9Sstevel@tonic-gate 				/* find the key that points to this sublist */
3347c478bd9Sstevel@tonic-gate 				n2 = n;
3357c478bd9Sstevel@tonic-gate 				while (n2->key == NULL) n2 = n2->right;
3367c478bd9Sstevel@tonic-gate 				k = n2->key;
3377c478bd9Sstevel@tonic-gate 				k->numnote = k->numnote - 1;
338e2553d68SSerge Dussud 				/*
339e2553d68SSerge Dussud 				 * check if two adjacent sublists can be merged
340e2553d68SSerge Dussud 				 * first check left, then check right
341e2553d68SSerge Dussud 				 */
3427c478bd9Sstevel@tonic-gate 				kl = k->left;
3437c478bd9Sstevel@tonic-gate 				kr = k->right;
344e2553d68SSerge Dussud 				if ((!(kl->notice)->isdummy) &&
345e2553d68SSerge Dussud 				    ((kl->numnote+k->numnote) <= NLIM)) {
3467c478bd9Sstevel@tonic-gate 					/* delete the key to the left */
3477c478bd9Sstevel@tonic-gate 					(kl->notice)->key = NULL;
3487c478bd9Sstevel@tonic-gate 					k->numnote += kl->numnote;
3497c478bd9Sstevel@tonic-gate 					(kl->left)->right = k;
3507c478bd9Sstevel@tonic-gate 					k->left = kl->left;
351e2553d68SSerge Dussud 					free(kl);
352e2553d68SSerge Dussud 				} else if ((!(k->notice)->isdummy) &&
353*618372bcSSebastian Wiedenroth 				    ((kr->numnote+k->numnote) <= NLIM)) {
3547c478bd9Sstevel@tonic-gate 					/* delete this key */
3557c478bd9Sstevel@tonic-gate 					(k->notice)->key = NULL;
3567c478bd9Sstevel@tonic-gate 					kr->numnote += k->numnote;
3577c478bd9Sstevel@tonic-gate 					(k->left)->right = kr;
3587c478bd9Sstevel@tonic-gate 					kr->left = k->left;
3597c478bd9Sstevel@tonic-gate 					free(k); }
3607c478bd9Sstevel@tonic-gate 				}
3617c478bd9Sstevel@tonic-gate 			/* delete n, then advance n down the list */
3627c478bd9Sstevel@tonic-gate 			(n->left)->right = n->right;
3637c478bd9Sstevel@tonic-gate 			(n->right)->left = n->left;
3647c478bd9Sstevel@tonic-gate 			n2 = n->right;
3657c478bd9Sstevel@tonic-gate 			free(n);
3667c478bd9Sstevel@tonic-gate 			n = n2;
3677c478bd9Sstevel@tonic-gate 			}
3687c478bd9Sstevel@tonic-gate 		if (flag) break;
3697c478bd9Sstevel@tonic-gate 		}
3707c478bd9Sstevel@tonic-gate 	/* now reset current */
3717c478bd9Sstevel@tonic-gate 	k = (index->key)->left;
3727c478bd9Sstevel@tonic-gate 	while (k->left != NULL) k = k->left;
3737c478bd9Sstevel@tonic-gate 	n = (k->notice)->right;
374e2553d68SSerge Dussud 	while ((n != NULL) && (n->isdummy)) n = n->right;
3757c478bd9Sstevel@tonic-gate 	current = n;
3767c478bd9Sstevel@tonic-gate }
379032624d5Sbasabi int
el_empty(void)380032624d5Sbasabi el_empty(void)
3817c478bd9Sstevel@tonic-gate {
382e2553d68SSerge Dussud 	if (current == NULL)
383e2553d68SSerge Dussud 		return (1);
384e2553d68SSerge Dussud 	else
385e2553d68SSerge Dussud 		return (0);
3867c478bd9Sstevel@tonic-gate }
3897c478bd9Sstevel@tonic-gate void *
el_first(void)390032624d5Sbasabi el_first(void)
3917c478bd9Sstevel@tonic-gate {
392e2553d68SSerge Dussud 	struct notice *n, *fn;
393e2553d68SSerge Dussud 	struct key *k, *fk;
394e2553d68SSerge Dussud 	struct index *ind, *fi;
395e2553d68SSerge Dussud 	int ctr, *val;
3967c478bd9Sstevel@tonic-gate 	time_t next_int;
398e2553d68SSerge Dussud 	if ((index == NULL) || (current == NULL))
399e2553d68SSerge Dussud 		return (NULL);
4017c478bd9Sstevel@tonic-gate 	while ((index->key)->time < current->time) {
4027c478bd9Sstevel@tonic-gate 		if (DU == 2) {
4037c478bd9Sstevel@tonic-gate 			/* only two intervals, so relabel first one */
4047c478bd9Sstevel@tonic-gate 			k = index->key;
4057c478bd9Sstevel@tonic-gate 			k->time += DT;
4067c478bd9Sstevel@tonic-gate 			(k->notice)->time += DT;
4077c478bd9Sstevel@tonic-gate 			continue; }
408e2553d68SSerge Dussud 		/*
409e2553d68SSerge Dussud 		 * remove the notice, key, and index corresponding
410e2553d68SSerge Dussud 		 * to the first time interval.  Then split the
411e2553d68SSerge Dussud 		 * overflow interval into a normal interval
412e2553d68SSerge Dussud 		 * plus an overflow interval.
413e2553d68SSerge Dussud 		 */
4147c478bd9Sstevel@tonic-gate 		fi = index;
4157c478bd9Sstevel@tonic-gate 		fk = fi->key;
4167c478bd9Sstevel@tonic-gate 		fn = fk->notice;
4177c478bd9Sstevel@tonic-gate 		(fn->left)->right = fn->right;
4187c478bd9Sstevel@tonic-gate 		(fn->right)->left = fn->left;
4197c478bd9Sstevel@tonic-gate 		(fk->left)->right = fk->right;
4207c478bd9Sstevel@tonic-gate 		(fk->right)->left = fk->left;
4217c478bd9Sstevel@tonic-gate 		index = index->right;
4227c478bd9Sstevel@tonic-gate 		/* find where to split	*/
4237c478bd9Sstevel@tonic-gate 		ind = index;
4247c478bd9Sstevel@tonic-gate 		while ((ind->right)->right != NULL) ind = ind->right;
4257c478bd9Sstevel@tonic-gate 		/* ind points to the next to last index interval	*/
4267c478bd9Sstevel@tonic-gate 		k = ind->key;
4277c478bd9Sstevel@tonic-gate 		next_int = k->time + DT;	/* upper bound on new inter.  */
4287c478bd9Sstevel@tonic-gate 		while (k->time < next_int) k = k->right;
4297c478bd9Sstevel@tonic-gate 		/* k points to the appropriate sublist of notices	*/
4307c478bd9Sstevel@tonic-gate 		n = (k->notice)->left;
4317c478bd9Sstevel@tonic-gate 		ctr = 1;
4327c478bd9Sstevel@tonic-gate 		while (n->time >= next_int) {
4337c478bd9Sstevel@tonic-gate 			ctr++;
4347c478bd9Sstevel@tonic-gate 			n = n->left; }
4357c478bd9Sstevel@tonic-gate 		n = n->right;
436e2553d68SSerge Dussud 		/*
437e2553d68SSerge Dussud 		 * n points to first notice of the new overflow interval
438e2553d68SSerge Dussud 		 * ctr tells how many notices are in the first sublist
439e2553d68SSerge Dussud 		 *	of the new overflow interval
440e2553d68SSerge Dussud 		 * insert the new index element
441e2553d68SSerge Dussud 		 */
4427c478bd9Sstevel@tonic-gate 		fi->right = ind->right;
4437c478bd9Sstevel@tonic-gate 		ind->right = fi;
4447c478bd9Sstevel@tonic-gate 		/* insert the new dummy key	*/
4457c478bd9Sstevel@tonic-gate 		fk->time = next_int;
4467c478bd9Sstevel@tonic-gate 		fk->numnote = k->numnote - ctr + 1;
4477c478bd9Sstevel@tonic-gate 		fk->left = k->left;
4487c478bd9Sstevel@tonic-gate 		fk->right = k;
4497c478bd9Sstevel@tonic-gate 		(k->left)->right = fk;
4507c478bd9Sstevel@tonic-gate 		k->left = fk;
4517c478bd9Sstevel@tonic-gate 		k->numnote = ctr;
4527c478bd9Sstevel@tonic-gate 		/* insert the new dummy notice	*/
4537c478bd9Sstevel@tonic-gate 		fn->time = next_int;
4547c478bd9Sstevel@tonic-gate 		fn->left = n->left;
4557c478bd9Sstevel@tonic-gate 		fn->right = n;
4567c478bd9Sstevel@tonic-gate 		(n->left)->right = fn;
4577c478bd9Sstevel@tonic-gate 		n->left = fn; }
4597c478bd9Sstevel@tonic-gate 	/* remove the first element of the list */
4607c478bd9Sstevel@tonic-gate 	(current->left)->right = current->right;
4617c478bd9Sstevel@tonic-gate 	(current->right)->left = current->left;
4627c478bd9Sstevel@tonic-gate 	/* now update the numnote field in the appropriate key */
4637c478bd9Sstevel@tonic-gate 	n = current;
464e2553d68SSerge Dussud 	while (n->key == NULL) n = n->right;
4657c478bd9Sstevel@tonic-gate 	k = n->key;
4667c478bd9Sstevel@tonic-gate 	k->numnote = k->numnote - 1;
4677c478bd9Sstevel@tonic-gate 	/* if numnote = 0 then this key must be removed */
4687c478bd9Sstevel@tonic-gate 	if (k->numnote == 0) {
4697c478bd9Sstevel@tonic-gate 		(k->left)->right = k->right;
470e2553d68SSerge Dussud 		(k->right)->left = k->left;
4717c478bd9Sstevel@tonic-gate 		free(k); }
4737c478bd9Sstevel@tonic-gate 	/* now set current to be the head of the list */
4747c478bd9Sstevel@tonic-gate 	fn = current->right;
475e2553d68SSerge Dussud 	while ((fn != NULL) && (fn->isdummy))
4767c478bd9Sstevel@tonic-gate 		fn = fn->right;
4777c478bd9Sstevel@tonic-gate 	val = current->event;
4787c478bd9Sstevel@tonic-gate 	free(current);
4797c478bd9Sstevel@tonic-gate 	current = fn;
481e2553d68SSerge Dussud 	return (val);
4827c478bd9Sstevel@tonic-gate }
4857c478bd9Sstevel@tonic-gate void
el_delete(void)486032624d5Sbasabi el_delete(void)
4877c478bd9Sstevel@tonic-gate {
4887c478bd9Sstevel@tonic-gate 	/* el_delete frees up all the space associated with the event list */
490e2553d68SSerge Dussud 	struct index *ind, *ind2;
491e2553d68SSerge Dussud 	struct key *k, *k2;
492e2553d68SSerge Dussud 	struct notice *n, *n2;
493e2553d68SSerge Dussud 
494e2553d68SSerge Dussud 	if (index == NULL)
495e2553d68SSerge Dussud 		return;
4967c478bd9Sstevel@tonic-gate 	ind = index;
4977c478bd9Sstevel@tonic-gate 	k = ind->key;
4987c478bd9Sstevel@tonic-gate 	while (k->left != NULL) k = k->left;
4997c478bd9Sstevel@tonic-gate 	n = k->notice;
500e2553d68SSerge Dussud 	while (n != NULL) {
5017c478bd9Sstevel@tonic-gate 		n2 = n->right;
5027c478bd9Sstevel@tonic-gate 		free(n);
5037c478bd9Sstevel@tonic-gate 		n = n2; }
504e2553d68SSerge Dussud 	while (k != NULL) {
5057c478bd9Sstevel@tonic-gate 		k2 = k->right;
5067c478bd9Sstevel@tonic-gate 		free(k);
5077c478bd9Sstevel@tonic-gate 		k = k2; }
508e2553d68SSerge Dussud 	while (ind != NULL) {
5097c478bd9Sstevel@tonic-gate 		ind2 = ind->right;
5107c478bd9Sstevel@tonic-gate 		free(ind);
5117c478bd9Sstevel@tonic-gate 		ind = ind2; }
5137c478bd9Sstevel@tonic-gate 	index = NULL;
5147c478bd9Sstevel@tonic-gate 	current = NULL;
5157c478bd9Sstevel@tonic-gate }