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 NULL 0 /* a null pointer */
67 #define TRUE 1
68 #define FALSE 0
69
70 /* the following parameters are set in init */
71 static int DU; /* number of time intervals */
72 static time_t LB; /* lower bound on time */
73 static time_t DT; /* width of interval */
74 static int NLIM; /* max notices per sublist */
75
76 /*
77 * a notice points to an event. a notice has the following fields:
78 * time = time of the event.
79 * id = identifier for an event or class of events that may need
80 * to be removed (other than at the front of the list).
81 * event = pointer to the event.
82 * isdummy = tells whether this notice points to a real event or
83 * is just a dummy notice (one that is used to "mark off"
84 * the time intervals that the user specifies in init).
85 * key = points back to the key that points to this notice,
86 * if there is one.
87 * left = points to the notice immediately preceding this one.
88 * right = points to the notice immediately following this one.
89 */
90 struct notice { time_t time;
91 int id;
92 void *event;
93 short int isdummy;
94 struct key *key;
95 struct notice *left;
96 struct notice *right; };
97
98 /* current points to the front of the list of notices (events) */
99 struct notice *current = NULL;
100
101 /*
102 * a key points to a sublist of notices. a key has the following fields:
103 * time = max time of notices in sublist.
104 * numnote = number of notices in sublist.
105 * notice = pointer to the notice with max time.
106 * left = points to the key immediately preceding this one.
107 * right = points to the key immediately following this one.
108 */
109 struct key { time_t time;
110 int numnote;
111 struct notice *notice;
112 struct key *left;
113 struct key *right; };
114
115 /*
116 * the index list breaks the keys into time intervals as specified in init.
117 * the index is "shifted" one time interval whenever el_first returns an
118 * event with a time greater than the max time of the first interval
119 * (eg. with intervals of a day which span one week (MTWTFSS),
120 * if el_first finds the next event is on tuesday, then
121 * the intervals of the event list get shifted (TWTFSSM).
122 */
123 struct index { struct key *key;
124 struct index *right; };
125
126 /* index pts to the front of the index list */
127 static struct index *index = NULL;
128
129 /* ******************* */
130 void
el_init(du,lb,dt,nlim)131 el_init(du, lb, dt, nlim)
132 /* ******************* */
133 int du, nlim;
134 time_t lb, dt;
135 {
136 int i;
137 time_t t;
138 struct index *indprev, *ind;
139 struct key *kprev, *k;
140 struct notice *nprev, *n;
141
142 if ((du < 1) || (dt < 1) || (nlim < 1))
143 return;
144 DU = du + 1;
145 LB = lb;
146 DT = dt;
147 NLIM = nlim;
148
149 /*
150 * initialize index, keys, and notices
151 */
152
153 /* create first dummy notice */
154 n = (struct notice *)xmalloc(sizeof (struct notice));
155 n->time = LB;
156 n->isdummy = TRUE;
157 n->left = NULL;
158 nprev = n;
159 /* create first dummy key */
160 k = (struct key *)xmalloc(sizeof (struct key));
161 k->time = LB;
162 k->numnote = 1;
163 k->notice = n;
164 k->left = NULL;
165 kprev = k;
166 /* make notice point to key */
167 n->key = k;
168 /* no index element to allocate this time */
169 indprev = NULL;
170 /* create dummy notices, dummy keys, and index elements */
171 t = LB;
172 for (i = 1; i < DU; i++) {
173 t = t + DT;
174 n = (struct notice *)xmalloc(sizeof (struct notice));
175 n->time = t;
176 n->isdummy = TRUE;
177 n->left = nprev;
178 nprev->right = n;
179 nprev = n;
180 k = (struct key *)xmalloc(sizeof (struct key));
181 k->time = t;
182 k->numnote = 1;
183 k->notice = n;
184 k->left = kprev;
185 kprev->right = k;
186 kprev = k;
187 n->key = k;
188 ind = (struct index *)xmalloc(sizeof (struct index));
189 ind->key = k;
190 if (indprev == NULL)
191 index = ind;
192 else
193 indprev->right = ind;
194 indprev = ind; }
195 /* create last dummy notice */
196 n = (struct notice *)xmalloc(sizeof (struct notice));
197 n->time = INFINITY;
198 n->isdummy = TRUE;
199 n->left = nprev;
200 n->right = NULL;
201 nprev->right = n;
202 /* create last dummy key */
203 k = (struct key *)xmalloc(sizeof (struct key));
204 k->time = INFINITY;
205 k->numnote = 1;
206 k->notice = n;
207 k->left = kprev;
208 k->right = NULL;
209 kprev->right = k;
210 n->key = k;
211 /* create last index element */
212 ind = (struct index *)xmalloc(sizeof (struct index));
213 ind->key = k;
214 ind->right = NULL;
215 indprev->right = ind;
216
217 current = NULL;
218 }
219
220
221 /* ********************** */
222 int
el_add(event,time,id)223 el_add(event, time, id)
224 /* ********************** */
225 void *event;
226 int id;
227 time_t time;
228 {
229 /*
230 * add works slightly differently than in the reference. if the
231 * sublist to be inserted into is full (numnote = NLIM),
232 * the sublist is split in half. thus the size of the sublists
233 * in this implementation normally ranges from NLIM/2 to NLIM.
234 */
235
236 struct index *ind;
237 struct key *k, *k2;
238 struct notice *n, *n2;
239 int i;
240
241 /*
242 * time may be 0 when set by next_time() on error or an
243 * invalid time specification of job
244 */
245 if ((index == NULL) || (time <= 0)) {
246 return (-1);
247 }
248 if (time < LB) {
249 return (-2);
250 }
251
252 /* allocate new notice */
253 n = (struct notice *)xmalloc(sizeof (struct notice));
254 n->time = time;
255 n->id = id;
256 n->event = event;
257 n->isdummy = FALSE;
258 n->key = NULL;
259
260 /* find the right interval */
261 ind = index;
262 while ((ind->key)->time <= time) ind = ind->right;
263
264 /* find the right key */
265 k = (ind->key)->left;
266 while (k->time > time) k = k->left;
267 k = k->right;
268
269 /* (k->time>time) and ((k->left)->time<=time) */
270 if (k->numnote == NLIM) {
271 /* k's sublist is full, so split it */
272 k->numnote = NLIM / 2;
273 n2 = k->notice;
274 for (i = 1; i <= NLIM/2; i++) n2 = n2->left;
275 /* create a key which will point to notice n2 */
276 k2 = (struct key *)xmalloc(sizeof (struct key));
277 k2->time = n2->time;
278 k2->numnote = NLIM - NLIM/2;
279 k2->notice = n2;
280 k2->right = k;
281 k2->left = k->left;
282 k->left = k2;
283 (k2->left)->right = k2;
284 n2->key = k2; /* have n2 point back to k2 */
285 /* which of the new sublists will hold the new notice? */
286 if (k2->time > time) k = k2; }
287
288 /*
289 * the new notice n is ready to be inserted
290 * k points to the appropriate sublist
291 */
292 k->numnote = k->numnote + 1;
293 n2 = k->notice;
294 while (n2->time > time) n2 = n2->left;
295 n->right = n2->right;
296 n->left = n2;
297 (n2->right)->left = n;
298 n2->right = n;
299
300 if ((current == NULL) || (current->time > time))
301 current = n;
302
303 return (0);
304 }
305
306
307 /* ******************** */
308 void
el_remove(id,flag)309 el_remove(id, flag)
310 /* ******************** */
311 int id, flag;
312 {
313 /*
314 * remove finds notices n that need to be removed by traversing thru
315 * the notice list. if n is the sole element of a sublist, the
316 * sublist is deleted. if not, an adjacent sublist is merged with
317 * n's sublist, if that is possible. after these checks, n is removed.
318 */
319
320 struct notice *n, *n2;
321 struct key *k, *kl, *kr;
322
323 if ((index == NULL) || (current == NULL))
324 return;
325
326 n = current;
327 while (n != NULL) {
328 while ((n != NULL) && ((n->isdummy) || (n->id != id)))
329 n = n->right;
330 if (n != NULL) {
331 /* n should be deleted */
332 if ((n->key != NULL) && ((n->key)->numnote == 1)) {
333 /* n = sole element of a sublist */
334 k = n->key;
335 (k->left)->right = k->right;
336 (k->right)->left = k->left;
337 free(k);
338 } else { if (n->key != NULL) {
339 /* n has a key pointing to it */
340 (n->left)->key = n->key;
341 (n->key)->time = (n->left)->time;
342 (n->key)->notice = n->left; }
343 /* find the key that points to this sublist */
344 n2 = n;
345 while (n2->key == NULL) n2 = n2->right;
346 k = n2->key;
347 k->numnote = k->numnote - 1;
348 /*
349 * check if two adjacent sublists can be merged
350 * first check left, then check right
351 */
352 kl = k->left;
353 kr = k->right;
354 if ((!(kl->notice)->isdummy) &&
355 ((kl->numnote+k->numnote) <= NLIM)) {
356 /* delete the key to the left */
357 (kl->notice)->key = NULL;
358 k->numnote += kl->numnote;
359 (kl->left)->right = k;
360 k->left = kl->left;
361 free(kl);
362 } else if ((!(k->notice)->isdummy) &&
363 ((kr->numnote+k->numnote)
364 <= NLIM)) {
365 /* delete this key */
366 (k->notice)->key = NULL;
367 kr->numnote += k->numnote;
368 (k->left)->right = kr;
369 kr->left = k->left;
370 free(k); }
371 }
372 /* delete n, then advance n down the list */
373 (n->left)->right = n->right;
374 (n->right)->left = n->left;
375 n2 = n->right;
376 free(n);
377 n = n2;
378 }
379 if (flag) break;
380 }
381 /* now reset current */
382 k = (index->key)->left;
383 while (k->left != NULL) k = k->left;
384 n = (k->notice)->right;
385 while ((n != NULL) && (n->isdummy)) n = n->right;
386 current = n;
387 }
388
389
390 /* ********************* */
391 int
el_empty(void)392 el_empty(void)
393 /* ********************* */
394 {
395 if (current == NULL)
396 return (1);
397 else
398 return (0);
399 }
400
401
402 /* ********************* */
403 void *
el_first(void)404 el_first(void)
405 /* ********************* */
406 {
407 struct notice *n, *fn;
408 struct key *k, *fk;
409 struct index *ind, *fi;
410 int ctr, *val;
411 time_t next_int;
412
413 if ((index == NULL) || (current == NULL))
414 return (NULL);
415
416 while ((index->key)->time < current->time) {
417 if (DU == 2) {
418 /* only two intervals, so relabel first one */
419 k = index->key;
420 k->time += DT;
421 (k->notice)->time += DT;
422 continue; }
423 /*
424 * remove the notice, key, and index corresponding
425 * to the first time interval. Then split the
426 * overflow interval into a normal interval
427 * plus an overflow interval.
428 */
429 fi = index;
430 fk = fi->key;
431 fn = fk->notice;
432 (fn->left)->right = fn->right;
433 (fn->right)->left = fn->left;
434 (fk->left)->right = fk->right;
435 (fk->right)->left = fk->left;
436 index = index->right;
437 /* find where to split */
438 ind = index;
439 while ((ind->right)->right != NULL) ind = ind->right;
440 /* ind points to the next to last index interval */
441 k = ind->key;
442 next_int = k->time + DT; /* upper bound on new inter. */
443 while (k->time < next_int) k = k->right;
444 /* k points to the appropriate sublist of notices */
445 n = (k->notice)->left;
446 ctr = 1;
447 while (n->time >= next_int) {
448 ctr++;
449 n = n->left; }
450 n = n->right;
451 /*
452 * n points to first notice of the new overflow interval
453 * ctr tells how many notices are in the first sublist
454 * of the new overflow interval
455 * insert the new index element
456 */
457 fi->right = ind->right;
458 ind->right = fi;
459 /* insert the new dummy key */
460 fk->time = next_int;
461 fk->numnote = k->numnote - ctr + 1;
462 fk->left = k->left;
463 fk->right = k;
464 (k->left)->right = fk;
465 k->left = fk;
466 k->numnote = ctr;
467 /* insert the new dummy notice */
468 fn->time = next_int;
469 fn->left = n->left;
470 fn->right = n;
471 (n->left)->right = fn;
472 n->left = fn; }
473
474 /* remove the first element of the list */
475 (current->left)->right = current->right;
476 (current->right)->left = current->left;
477 /* now update the numnote field in the appropriate key */
478 n = current;
479 while (n->key == NULL) n = n->right;
480 k = n->key;
481 k->numnote = k->numnote - 1;
482 /* if numnote = 0 then this key must be removed */
483 if (k->numnote == 0) {
484 (k->left)->right = k->right;
485 (k->right)->left = k->left;
486 free(k); }
487
488 /* now set current to be the head of the list */
489 fn = current->right;
490 while ((fn != NULL) && (fn->isdummy))
491 fn = fn->right;
492 val = current->event;
493 free(current);
494 current = fn;
495
496 return (val);
497 }
498
499
500 /* ************** */
501 void
el_delete(void)502 el_delete(void)
503 /* ************** */
504 {
505 /* el_delete frees up all the space associated with the event list */
506
507 struct index *ind, *ind2;
508 struct key *k, *k2;
509 struct notice *n, *n2;
510
511 if (index == NULL)
512 return;
513 ind = index;
514 k = ind->key;
515 while (k->left != NULL) k = k->left;
516 n = k->notice;
517 while (n != NULL) {
518 n2 = n->right;
519 free(n);
520 n = n2; }
521 while (k != NULL) {
522 k2 = k->right;
523 free(k);
524 k = k2; }
525 while (ind != NULL) {
526 ind2 = ind->right;
527 free(ind);
528 ind = ind2; }
529
530 index = NULL;
531 current = NULL;
532 }
533