xref: /illumos-gate/usr/src/cmd/cron/elm.c (revision 4870e0a7)
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 
63 extern	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	*/
70 static int	DU;		/* number of time intervals	*/
71 static time_t	LB;		/* lower bound on time	*/
72 static time_t	DT;		/* width of interval	*/
73 static 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  */
89 struct 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)	*/
98 struct 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  */
108 struct 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  */
122 struct index {	struct key *key;
123 		struct index *right; };
124 
125 /* index pts to the front of the index list */
126 static struct index *index = NULL;
127 
128 /* ******************* */
129 void
el_init(du,lb,dt,nlim)130 el_init(du, lb, dt, nlim)
131 /* ******************* */
132 int du, nlim;
133 time_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 /* ********************** */
221 int
el_add(event,time,id)222 el_add(event, time, id)
223 /* ********************** */
224 void	*event;
225 int	id;
226 time_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 /* ******************** */
307 void
el_remove(id,flag)308 el_remove(id, flag)
309 /* ******************** */
310 int	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 /* ********************* */
390 int
el_empty(void)391 el_empty(void)
392 /* ********************* */
393 {
394 	if (current == NULL)
395 		return (1);
396 	else
397 		return (0);
398 }
399 
400 
401 /* ********************* */
402 void *
el_first(void)403 el_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 /* ************** */
500 void
el_delete(void)501 el_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