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 */
217c478bd9Sstevel@tonic-gate
22032624d5Sbasabi /*
23e2553d68SSerge Dussud * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
24032624d5Sbasabi * Use is subject to license terms.
25032624d5Sbasabi */
26032624d5Sbasabi
277c478bd9Sstevel@tonic-gate /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
28*618372bcSSebastian Wiedenroth /* All Rights Reserved */
297c478bd9Sstevel@tonic-gate
307c478bd9Sstevel@tonic-gate
317c478bd9Sstevel@tonic-gate
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 /* ********************************************************************** */
587c478bd9Sstevel@tonic-gate
597c478bd9Sstevel@tonic-gate
607c478bd9Sstevel@tonic-gate #include <sys/types.h>
617c478bd9Sstevel@tonic-gate #include <stdlib.h>
627c478bd9Sstevel@tonic-gate
637c478bd9Sstevel@tonic-gate extern void *xmalloc(size_t);
647c478bd9Sstevel@tonic-gate
657c478bd9Sstevel@tonic-gate #define INFINITY 2147483647L /* upper bound on time */
66e2553d68SSerge Dussud #define TRUE 1
67e2553d68SSerge Dussud #define FALSE 0
687c478bd9Sstevel@tonic-gate
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 */
747c478bd9Sstevel@tonic-gate
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; };
967c478bd9Sstevel@tonic-gate
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; };
1137c478bd9Sstevel@tonic-gate
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; };
1247c478bd9Sstevel@tonic-gate
125e2553d68SSerge Dussud /* index pts to the front of the index list */
126e2553d68SSerge Dussud static struct index *index = NULL;
1277c478bd9Sstevel@tonic-gate
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;
1377c478bd9Sstevel@tonic-gate
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;
1447c478bd9Sstevel@tonic-gate
1457c478bd9Sstevel@tonic-gate /*
1467c478bd9Sstevel@tonic-gate * initialize index, keys, and notices
1477c478bd9Sstevel@tonic-gate */
1487c478bd9Sstevel@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 }
2157c478bd9Sstevel@tonic-gate
2167c478bd9Sstevel@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 */
2267c478bd9Sstevel@tonic-gate
2277c478bd9Sstevel@tonic-gate struct index *ind;
228e2553d68SSerge Dussud struct key *k, *k2;
229e2553d68SSerge Dussud struct notice *n, *n2;
2307c478bd9Sstevel@tonic-gate int i;
2317c478bd9Sstevel@tonic-gate
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 }
2427c478bd9Sstevel@tonic-gate
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;
2507c478bd9Sstevel@tonic-gate
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;
2597c478bd9Sstevel@tonic-gate
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; }
2787c478bd9Sstevel@tonic-gate
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;
2907c478bd9Sstevel@tonic-gate
291e2553d68SSerge Dussud if ((current == NULL) || (current->time > time))
292e2553d68SSerge Dussud current = n;
293e2553d68SSerge Dussud
294e2553d68SSerge Dussud return (0);
2957c478bd9Sstevel@tonic-gate }
2967c478bd9Sstevel@tonic-gate
2977c478bd9Sstevel@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 */
3077c478bd9Sstevel@tonic-gate
308e2553d68SSerge Dussud struct notice *n, *n2;
309e2553d68SSerge Dussud struct key *k, *kl, *kr;
3107c478bd9Sstevel@tonic-gate
311e2553d68SSerge Dussud if ((index == NULL) || (current == NULL))
312e2553d68SSerge Dussud return;
3137c478bd9Sstevel@tonic-gate
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 }
3777c478bd9Sstevel@tonic-gate
3787c478bd9Sstevel@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 }
3877c478bd9Sstevel@tonic-gate
3887c478bd9Sstevel@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;
3977c478bd9Sstevel@tonic-gate
398e2553d68SSerge Dussud if ((index == NULL) || (current == NULL))
399e2553d68SSerge Dussud return (NULL);
4007c478bd9Sstevel@tonic-gate
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; }
4587c478bd9Sstevel@tonic-gate
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); }
4727c478bd9Sstevel@tonic-gate
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;
4807c478bd9Sstevel@tonic-gate
481e2553d68SSerge Dussud return (val);
4827c478bd9Sstevel@tonic-gate }
4837c478bd9Sstevel@tonic-gate
4847c478bd9Sstevel@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 */
4897c478bd9Sstevel@tonic-gate
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; }
5127c478bd9Sstevel@tonic-gate
5137c478bd9Sstevel@tonic-gate index = NULL;
5147c478bd9Sstevel@tonic-gate current = NULL;
5157c478bd9Sstevel@tonic-gate }
516