1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21
22/*
23 * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
24 * Use is subject to license terms.
25 */
26
27/*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
28/*	  All Rights Reserved  	*/
29
30
31
32/* ********************************************************************** */
33/* *		General-Purpose Event List Manager			* */
34/* ********************************************************************** */
35/*
36 *	description:	These routines maintain a time-ordered list of events.
37 *	functions available:
38 *		init :	Creates and initializes the data structure.
39 *			See the reference for parameters to init.
40 *		add(&event, time, id) :	Adds an event to the list.
41 *					Returns: 0 if success,
42 *						-2 if event time is lower
43 *						   than Lower Bound time LB
44 *						-1 else
45 *		remove(id) :	Removes events (with appropriate id).
46 *		empty : Returns true if the list is empty, false otherwise.
47 *		first :	Removes the element at the head of the list.
48 *			Returns a pointer to the event.
49 *		delete : Frees up all allocated storage associated
50 *			 with the event list.
51 *	reference:	Franta, W. R. and Maly, K.,
52 *			"An efficient data structure for the
53 *			simulation event set ", CACM Vol. 20(8),
54 *			Aug 1977, pp. 596-602.
55 *	machine dependant:	the constant INFINITY
56 */
57/* ********************************************************************** */
58
59
60#include <sys/types.h>
61#include <stdlib.h>
62
63extern	void *xmalloc(size_t);
64
65#define	INFINITY	2147483647L	/* upper bound on time	*/
66#define	TRUE		1
67#define	FALSE		0
68
69/* the following parameters are set in init	*/
70static int	DU;		/* number of time intervals	*/
71static time_t	LB;		/* lower bound on time	*/
72static time_t	DT;		/* width of interval	*/
73static int	NLIM;		/* max notices per sublist	*/
74
75/*
76 * a notice points to an event.  a notice has the following fields:
77 *	time = time of the event.
78 *	id = identifier for an event or class of events that may need
79 *		to be removed (other than at the front of the list).
80 *	event = pointer to the event.
81 *	isdummy = tells whether this notice points to a real event or
82 *		is just a dummy notice (one that is used to "mark off"
83 *		the time intervals that the user specifies in init).
84 *	key = points back to the key that points to this notice,
85 *		if there is one.
86 *	left = points to the notice immediately preceding this one.
87 *	right = points to the notice immediately following this one.
88 */
89struct notice {	time_t	time;
90		int	id;
91		void	*event;
92		short int	isdummy;
93		struct key	*key;
94		struct notice	*left;
95		struct notice	*right; };
96
97/* current points to the front of the list of notices (events)	*/
98struct notice	*current = NULL;
99
100/*
101 * a key points to a sublist of notices.  a key has the following fields:
102 *	time = max time of notices in sublist.
103 *	numnote = number of notices in sublist.
104 *	notice = pointer to the notice with max time.
105 *	left = points to the key immediately preceding this one.
106 *	right = points to the key immediately following this one.
107 */
108struct key {	time_t	time;
109		int	numnote;
110		struct notice	*notice;
111		struct key	*left;
112		struct key	*right; };
113
114/*
115 * the index list breaks the keys into time intervals as specified in init.
116 * the index is "shifted" one time interval whenever el_first returns an
117 * event with a time greater than the max time of the first interval
118 * (eg. with intervals of a day which span one week (MTWTFSS),
119 * if el_first finds the next event is on tuesday, then
120 * the intervals of the event list get shifted (TWTFSSM).
121 */
122struct index {	struct key *key;
123		struct index *right; };
124
125/* index pts to the front of the index list */
126static struct index *index = NULL;
127
128/* ******************* */
129void
130el_init(du, lb, dt, nlim)
131/* ******************* */
132int du, nlim;
133time_t lb, dt;
134{
135	int	i;
136	time_t	t;
137	struct index *indprev, *ind;
138	struct key *kprev, *k;
139	struct notice *nprev, *n;
140
141	if ((du < 1) || (dt < 1) || (nlim < 1))
142		return;
143	DU = du + 1;
144	LB = lb;
145	DT = dt;
146	NLIM = nlim;
147
148	/*
149	 * initialize index, keys, and notices
150	 */
151
152	/* create first dummy notice */
153	n = (struct notice *)xmalloc(sizeof (struct notice));
154	n->time = LB;
155	n->isdummy = TRUE;
156	n->left = NULL;
157	nprev = n;
158	/* create first dummy key */
159	k = (struct key *)xmalloc(sizeof (struct key));
160	k->time = LB;
161	k->numnote = 1;
162	k->notice = n;
163	k->left = NULL;
164	kprev = k;
165	/* make notice point to key */
166	n->key = k;
167	/* no index element to allocate this time */
168	indprev = NULL;
169	/* create dummy notices, dummy keys, and index elements */
170	t = LB;
171	for (i = 1; i < DU; i++) {
172		t = t + DT;
173		n = (struct notice *)xmalloc(sizeof (struct notice));
174		n->time = t;
175		n->isdummy = TRUE;
176		n->left = nprev;
177		nprev->right = n;
178		nprev = n;
179		k = (struct key *)xmalloc(sizeof (struct key));
180		k->time = t;
181		k->numnote = 1;
182		k->notice = n;
183		k->left = kprev;
184		kprev->right = k;
185		kprev = k;
186		n->key = k;
187		ind = (struct index *)xmalloc(sizeof (struct index));
188		ind->key = k;
189		if (indprev == NULL)
190			index = ind;
191		else
192			indprev->right = ind;
193		indprev = ind; }
194	/* create last dummy notice */
195	n = (struct notice *)xmalloc(sizeof (struct notice));
196	n->time = INFINITY;
197	n->isdummy = TRUE;
198	n->left = nprev;
199	n->right = NULL;
200	nprev->right = n;
201	/* create last dummy key */
202	k = (struct key *)xmalloc(sizeof (struct key));
203	k->time = INFINITY;
204	k->numnote = 1;
205	k->notice = n;
206	k->left = kprev;
207	k->right = NULL;
208	kprev->right = k;
209	n->key = k;
210	/* create last index element */
211	ind = (struct index *)xmalloc(sizeof (struct index));
212	ind->key = k;
213	ind->right = NULL;
214	indprev->right = ind;
215
216	current = NULL;
217}
218
219
220/* ********************** */
221int
222el_add(event, time, id)
223/* ********************** */
224void	*event;
225int	id;
226time_t	time;
227{
228	/*
229	 * add works slightly differently than in the reference.  if the
230	 * sublist to be inserted into is full (numnote = NLIM),
231	 * the sublist is split in half.  thus the size of the sublists
232	 * in this implementation normally ranges from NLIM/2 to NLIM.
233	 */
234
235	struct index *ind;
236	struct key *k, *k2;
237	struct notice *n, *n2;
238	int i;
239
240	/*
241	 * time may be 0 when set by next_time() on error or an
242	 * invalid time specification of job
243	 */
244	if ((index == NULL) || (time <= 0)) {
245		return (-1);
246	}
247	if (time < LB) {
248		return (-2);
249	}
250
251	/* allocate new notice */
252	n = (struct notice *)xmalloc(sizeof (struct notice));
253	n->time = time;
254	n->id = id;
255	n->event = event;
256	n->isdummy = FALSE;
257	n->key = NULL;
258
259	/* find the right interval */
260	ind = index;
261	while ((ind->key)->time <= time) ind = ind->right;
262
263	/* find the right key */
264	k = (ind->key)->left;
265	while (k->time > time) k = k->left;
266	k = k->right;
267
268	/* (k->time>time) and ((k->left)->time<=time) */
269	if (k->numnote == NLIM) {
270		/* k's sublist is full, so split it */
271		k->numnote = NLIM / 2;
272		n2 = k->notice;
273		for (i = 1; i <= NLIM/2; i++) n2 = n2->left;
274		/* create a key which will point to notice n2 */
275		k2 = (struct key *)xmalloc(sizeof (struct key));
276		k2->time = n2->time;
277		k2->numnote = NLIM - NLIM/2;
278		k2->notice = n2;
279		k2->right = k;
280		k2->left = k->left;
281		k->left = k2;
282		(k2->left)->right = k2;
283		n2->key = k2;	/* have n2 point back to k2 */
284		/* which of the new sublists will hold the new notice? */
285		if (k2->time > time) k = k2; }
286
287	/*
288	 * the new notice n is ready to be inserted
289	 * k points to the appropriate sublist
290	 */
291	k->numnote = k->numnote + 1;
292	n2 = k->notice;
293	while (n2->time > time) n2 = n2->left;
294	n->right = n2->right;
295	n->left = n2;
296	(n2->right)->left = n;
297	n2->right = n;
298
299	if ((current == NULL) || (current->time > time))
300		current = n;
301
302	return (0);
303}
304
305
306/* ******************** */
307void
308el_remove(id, flag)
309/* ******************** */
310int	id, flag;
311{
312	/*
313	 * remove finds notices n that need to be removed by traversing thru
314	 * the notice list.  if n is the sole element of a sublist, the
315	 * sublist is deleted.  if not, an adjacent sublist is merged with
316	 * n's sublist, if that is possible.  after these checks, n is removed.
317	 */
318
319	struct notice *n, *n2;
320	struct key *k, *kl, *kr;
321
322	if ((index == NULL) || (current == NULL))
323		return;
324
325	n = current;
326	while (n != NULL) {
327		while ((n != NULL) && ((n->isdummy) || (n->id != id)))
328			n = n->right;
329		if (n != NULL) {
330			/* n should be deleted */
331			if ((n->key != NULL) && ((n->key)->numnote == 1)) {
332				/* n = sole element of a sublist */
333				k = n->key;
334				(k->left)->right = k->right;
335				(k->right)->left = k->left;
336				free(k);
337			} else { if (n->key != NULL) {
338					/* n has a key pointing to it */
339					(n->left)->key = n->key;
340					(n->key)->time = (n->left)->time;
341					(n->key)->notice = n->left; }
342				/* find the key that points to this sublist */
343				n2 = n;
344				while (n2->key == NULL) n2 = n2->right;
345				k = n2->key;
346				k->numnote = k->numnote - 1;
347				/*
348				 * check if two adjacent sublists can be merged
349				 * first check left, then check right
350				 */
351				kl = k->left;
352				kr = k->right;
353				if ((!(kl->notice)->isdummy) &&
354				    ((kl->numnote+k->numnote) <= NLIM)) {
355					/* delete the key to the left */
356					(kl->notice)->key = NULL;
357					k->numnote += kl->numnote;
358					(kl->left)->right = k;
359					k->left = kl->left;
360					free(kl);
361				} else if ((!(k->notice)->isdummy) &&
362					    ((kr->numnote+k->numnote)
363					    <= NLIM)) {
364					/* delete this key */
365					(k->notice)->key = NULL;
366					kr->numnote += k->numnote;
367					(k->left)->right = kr;
368					kr->left = k->left;
369					free(k); }
370				}
371			/* delete n, then advance n down the list */
372			(n->left)->right = n->right;
373			(n->right)->left = n->left;
374			n2 = n->right;
375			free(n);
376			n = n2;
377			}
378		if (flag) break;
379		}
380	/* now reset current */
381	k = (index->key)->left;
382	while (k->left != NULL) k = k->left;
383	n = (k->notice)->right;
384	while ((n != NULL) && (n->isdummy)) n = n->right;
385	current = n;
386}
387
388
389/* ********************* */
390int
391el_empty(void)
392/* ********************* */
393{
394	if (current == NULL)
395		return (1);
396	else
397		return (0);
398}
399
400
401/* ********************* */
402void *
403el_first(void)
404/* ********************* */
405{
406	struct notice *n, *fn;
407	struct key *k, *fk;
408	struct index *ind, *fi;
409	int ctr, *val;
410	time_t next_int;
411
412	if ((index == NULL) || (current == NULL))
413		return (NULL);
414
415	while ((index->key)->time < current->time) {
416		if (DU == 2) {
417			/* only two intervals, so relabel first one */
418			k = index->key;
419			k->time += DT;
420			(k->notice)->time += DT;
421			continue; }
422		/*
423		 * remove the notice, key, and index corresponding
424		 * to the first time interval.  Then split the
425		 * overflow interval into a normal interval
426		 * plus an overflow interval.
427		 */
428		fi = index;
429		fk = fi->key;
430		fn = fk->notice;
431		(fn->left)->right = fn->right;
432		(fn->right)->left = fn->left;
433		(fk->left)->right = fk->right;
434		(fk->right)->left = fk->left;
435		index = index->right;
436		/* find where to split	*/
437		ind = index;
438		while ((ind->right)->right != NULL) ind = ind->right;
439		/* ind points to the next to last index interval	*/
440		k = ind->key;
441		next_int = k->time + DT;	/* upper bound on new inter.  */
442		while (k->time < next_int) k = k->right;
443		/* k points to the appropriate sublist of notices	*/
444		n = (k->notice)->left;
445		ctr = 1;
446		while (n->time >= next_int) {
447			ctr++;
448			n = n->left; }
449		n = n->right;
450		/*
451		 * n points to first notice of the new overflow interval
452		 * ctr tells how many notices are in the first sublist
453		 *	of the new overflow interval
454		 * insert the new index element
455		 */
456		fi->right = ind->right;
457		ind->right = fi;
458		/* insert the new dummy key	*/
459		fk->time = next_int;
460		fk->numnote = k->numnote - ctr + 1;
461		fk->left = k->left;
462		fk->right = k;
463		(k->left)->right = fk;
464		k->left = fk;
465		k->numnote = ctr;
466		/* insert the new dummy notice	*/
467		fn->time = next_int;
468		fn->left = n->left;
469		fn->right = n;
470		(n->left)->right = fn;
471		n->left = fn; }
472
473	/* remove the first element of the list */
474	(current->left)->right = current->right;
475	(current->right)->left = current->left;
476	/* now update the numnote field in the appropriate key */
477	n = current;
478	while (n->key == NULL) n = n->right;
479	k = n->key;
480	k->numnote = k->numnote - 1;
481	/* if numnote = 0 then this key must be removed */
482	if (k->numnote == 0) {
483		(k->left)->right = k->right;
484		(k->right)->left = k->left;
485		free(k); }
486
487	/* now set current to be the head of the list */
488	fn = current->right;
489	while ((fn != NULL) && (fn->isdummy))
490		fn = fn->right;
491	val = current->event;
492	free(current);
493	current = fn;
494
495	return (val);
496}
497
498
499/* ************** */
500void
501el_delete(void)
502/* ************** */
503{
504	/* el_delete frees up all the space associated with the event list */
505
506	struct index *ind, *ind2;
507	struct key *k, *k2;
508	struct notice *n, *n2;
509
510	if (index == NULL)
511		return;
512	ind = index;
513	k = ind->key;
514	while (k->left != NULL) k = k->left;
515	n = k->notice;
516	while (n != NULL) {
517		n2 = n->right;
518		free(n);
519		n = n2; }
520	while (k != NULL) {
521		k2 = k->right;
522		free(k);
523		k = k2; }
524	while (ind != NULL) {
525		ind2 = ind->right;
526		free(ind);
527		ind = ind2; }
528
529	index = NULL;
530	current = NULL;
531}
532