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