elm.c revision 4870e0a7381ec2ec57437062574e6ddc3dd48d7f
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2008 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
/* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
/* All Rights Reserved */
/* ********************************************************************** */
/* * General-Purpose Event List Manager * */
/* ********************************************************************** */
/*
* description: These routines maintain a time-ordered list of events.
* functions available:
* init : Creates and initializes the data structure.
* See the reference for parameters to init.
* add(&event, time, id) : Adds an event to the list.
* Returns: 0 if success,
* -2 if event time is lower
* than Lower Bound time LB
* -1 else
* remove(id) : Removes events (with appropriate id).
* empty : Returns true if the list is empty, false otherwise.
* first : Removes the element at the head of the list.
* Returns a pointer to the event.
* delete : Frees up all allocated storage associated
* with the event list.
* reference: Franta, W. R. and Maly, K.,
* "An efficient data structure for the
* simulation event set ", CACM Vol. 20(8),
* Aug 1977, pp. 596-602.
* machine dependant: the constant INFINITY
*/
/* ********************************************************************** */
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
/* the following parameters are set in init */
static int DU; /* number of time intervals */
static int NLIM; /* max notices per sublist */
/*
* a notice points to an event. a notice has the following fields:
* time = time of the event.
* id = identifier for an event or class of events that may need
* to be removed (other than at the front of the list).
* event = pointer to the event.
* isdummy = tells whether this notice points to a real event or
* is just a dummy notice (one that is used to "mark off"
* the time intervals that the user specifies in init).
* key = points back to the key that points to this notice,
* if there is one.
* left = points to the notice immediately preceding this one.
* right = points to the notice immediately following this one.
*/
int id;
void *event;
short int isdummy;
/* current points to the front of the list of notices (events) */
/*
* a key points to a sublist of notices. a key has the following fields:
* time = max time of notices in sublist.
* numnote = number of notices in sublist.
* notice = pointer to the notice with max time.
* left = points to the key immediately preceding this one.
* right = points to the key immediately following this one.
*/
int numnote;
/*
* the index list breaks the keys into time intervals as specified in init.
* the index is "shifted" one time interval whenever el_first returns an
* event with a time greater than the max time of the first interval
* (eg. with intervals of a day which span one week (MTWTFSS),
* if el_first finds the next event is on tuesday, then
* the intervals of the event list get shifted (TWTFSSM).
*/
/* index pts to the front of the index list */
/* ******************* */
void
/* ******************* */
{
int i;
time_t t;
return;
/*
* initialize index, keys, and notices
*/
/* create first dummy notice */
nprev = n;
/* create first dummy key */
k->numnote = 1;
k->notice = n;
kprev = k;
/* make notice point to key */
n->key = k;
/* no index element to allocate this time */
/* create dummy notices, dummy keys, and index elements */
t = LB;
for (i = 1; i < DU; i++) {
t = t + DT;
n->time = t;
nprev = n;
k->time = t;
k->numnote = 1;
k->notice = n;
kprev = k;
n->key = k;
else
/* create last dummy notice */
/* create last dummy key */
k->numnote = 1;
k->notice = n;
n->key = k;
/* create last index element */
}
/* ********************** */
int
/* ********************** */
void *event;
int id;
{
/*
* add works slightly differently than in the reference. if the
* sublist to be inserted into is full (numnote = NLIM),
* the sublist is split in half. thus the size of the sublists
* in this implementation normally ranges from NLIM/2 to NLIM.
*/
int i;
/*
* time may be 0 when set by next_time() on error or an
* invalid time specification of job
*/
return (-1);
}
return (-2);
}
/* allocate new notice */
/* find the right interval */
/* find the right key */
k = k->right;
/* (k->time>time) and ((k->left)->time<=time) */
/* k's sublist is full, so split it */
/* create a key which will point to notice n2 */
/* which of the new sublists will hold the new notice? */
/*
* the new notice n is ready to be inserted
* k points to the appropriate sublist
*/
current = n;
return (0);
}
/* ******************** */
void
/* ******************** */
{
/*
* remove finds notices n that need to be removed by traversing thru
* the notice list. if n is the sole element of a sublist, the
* sublist is deleted. if not, an adjacent sublist is merged with
* n's sublist, if that is possible. after these checks, n is removed.
*/
return;
n = current;
while (n != NULL) {
n = n->right;
if (n != NULL) {
/* n should be deleted */
/* n = sole element of a sublist */
k = n->key;
free(k);
/* n has a key pointing to it */
/* find the key that points to this sublist */
n2 = n;
/*
* check if two adjacent sublists can be merged
* first check left, then check right
*/
/* delete the key to the left */
<= NLIM)) {
/* delete this key */
free(k); }
}
/* delete n, then advance n down the list */
free(n);
n = n2;
}
if (flag) break;
}
/* now reset current */
current = n;
}
/* ********************* */
int
el_empty(void)
/* ********************* */
{
return (1);
else
return (0);
}
/* ********************* */
void *
el_first(void)
/* ********************* */
{
return (NULL);
if (DU == 2) {
/* only two intervals, so relabel first one */
continue; }
/*
* remove the notice, key, and index corresponding
* to the first time interval. Then split the
* overflow interval into a normal interval
* plus an overflow interval.
*/
/* find where to split */
/* ind points to the next to last index interval */
/* k points to the appropriate sublist of notices */
ctr = 1;
ctr++;
n = n->left; }
n = n->right;
/*
* n points to first notice of the new overflow interval
* ctr tells how many notices are in the first sublist
* of the new overflow interval
* insert the new index element
*/
/* insert the new dummy key */
/* insert the new dummy notice */
/* remove the first element of the list */
/* now update the numnote field in the appropriate key */
n = current;
k = n->key;
/* if numnote = 0 then this key must be removed */
if (k->numnote == 0) {
free(k); }
/* now set current to be the head of the list */
return (val);
}
/* ************** */
void
el_delete(void)
/* ************** */
{
/* el_delete frees up all the space associated with the event list */
return;
n = k->notice;
while (n != NULL) {
free(n);
n = n2; }
while (k != NULL) {
free(k);
k = k2; }
}