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