#pragma ident "%Z%%M% %I% %E% SMI"

#include <sys/types.h>

#include <stdlib.h>

extern void *xmalloc(size_t);

#define INFINITY 2147483647L /* upper bound on time */

#define NULL 0 /* a null pointer */

#define TRUE 1

#define FALSE 0

static int DU; /* number of time intervals */

static time_t LB; /* lower bound on time */

static time_t DT; /* width of interval */

static int NLIM; /* max notices per sublist */

struct notice { time_t time;

int id;

void *event;

short int isdummy;

struct key *key;

struct notice *left;

struct notice *right; };

struct notice *current=NULL;

struct key { time_t time;

int numnote;

struct notice *notice;

struct key *left;

struct key *right; };

struct index { struct key *key;

struct index *right; };

static struct index *index=NULL; /* index pts to the front of the index list */

el_init(du,lb,dt,nlim)

int du, nlim;

time_t lb, dt;

{

int i;

time_t t;

struct index *indprev,*ind;

struct key *kprev, *k;

struct notice *nprev, *n;

if ((du<1) || (dt<1) || (nlim<1)) return;

DU = du + 1;

LB = lb;

DT = dt;

NLIM = nlim;

/*

/* create first dummy notice */

n= (struct notice *) xmalloc(sizeof(struct notice));

n->time = LB;

n->isdummy = TRUE;

n->left = NULL;

nprev = n;

/* create first dummy key */

k= (struct key *) xmalloc(sizeof(struct key));

k->time = LB;

k->numnote = 1;

k->notice = n;

k->left = NULL;

kprev = k;

/* make notice point to key */

n->key = k;

/* no index element to allocate this time */

indprev = NULL;

/* create dummy notices, dummy keys, and index elements */

t = LB;

for (i=1; i<DU; i++) {

t = t + DT;

n = (struct notice *) xmalloc(sizeof(struct notice));

n->time = t;

n->isdummy = TRUE;

n->left = nprev;

nprev->right = n;

nprev = n;

k = (struct key *) xmalloc(sizeof(struct key));

k->time = t;

k->numnote = 1;

k->notice = n;

k->left = kprev;

kprev->right = k;

kprev = k;

n->key = k;

ind = (struct index *) xmalloc(sizeof(struct index));

ind->key = k;

if (indprev == NULL) index = ind;

else indprev->right = ind;

indprev = ind; }

/* create last dummy notice */

n = (struct notice *) xmalloc(sizeof(struct notice));

n->time = INFINITY;

n->isdummy = TRUE;

n->left = nprev;

n->right = NULL;

nprev->right = n;

/* create last dummy key */

k = (struct key *) xmalloc(sizeof(struct key));

k->time = INFINITY;

k->numnote = 1;

k->notice = n;

k->left = kprev;

k->right = NULL;

kprev->right = k;

n->key = k;

/* create last index element */

ind = (struct index *) xmalloc(sizeof(struct index));

ind->key = k;

ind->right = NULL;

indprev->right = ind;

current = NULL;

}

el_add(event,time,id)

void *event;

int id;

time_t time;

{

struct index *ind;

struct key *k,*k2;

struct notice *n,*n2;

int i;

if ((index==NULL) || (time<LB)) return;

/* allocate new notice */

n = (struct notice *) xmalloc(sizeof(struct notice));

n->time = time;

n->id = id;

n->event = event;

n->isdummy = FALSE;

n->key = NULL;

/* find the right interval */

ind = index;

while ((ind->key)->time <= time) ind = ind->right;

/* find the right key */

k = (ind->key)->left;

while (k->time > time) k = k->left;

k = k->right;

/* (k->time>time) and ((k->left)->time<=time) */

if (k->numnote == NLIM) {

/* k's sublist is full, so split it */

k->numnote = NLIM / 2;

n2 = k->notice;

for (i=1; i<=NLIM/2; i++) n2 = n2->left;

/* create a key which will point to notice n2 */

k2 = (struct key *) xmalloc(sizeof(struct key));

k2->time = n2->time;

k2->numnote = NLIM - NLIM/2;

k2->notice = n2;

k2->right = k;

k2->left = k->left;

k->left = k2;

(k2->left)->right = k2;

n2->key = k2; /* have n2 point back to k2 */

/* which of the new sublists will hold the new notice? */

if (k2->time > time) k = k2; }

/* the new notice n is ready to be inserted

k->numnote = k->numnote + 1;

n2 = k->notice;

while (n2->time > time) n2 = n2->left;

n->right = n2->right;

n->left = n2;

(n2->right)->left = n;

n2->right = n;

if ( (current == NULL) || (current->time > time) ) current = n;

}

el_remove(id,flag)

int id,flag;

{

struct notice *n,*n2;

struct key *k,*kl,*kr;

if ((index==NULL) || (current==NULL)) return;

n = current;

while ( n != NULL) {

while ( (n!=NULL) && ((n->isdummy)||(n->id!=id)) ) n = n->right;

if (n != NULL) {

/* n should be deleted */

if ( (n->key!=NULL) && ((n->key)->numnote==1) ) {

/* n = sole element of a sublist */

k = n->key;

(k->left)->right = k->right;

(k->right)->left = k->left;

free(k); }

else { if (n->key != NULL) {

/* n has a key pointing to it */

(n->left)->key = n->key;

(n->key)->time = (n->left)->time;

(n->key)->notice = n->left; }

/* find the key that points to this sublist */

n2 = n;

while (n2->key == NULL) n2 = n2->right;

k = n2->key;

k->numnote = k->numnote - 1;

/* check if two adjacent sublists can be merged

kl = k->left;

kr = k->right;

if ( (!(kl->notice)->isdummy) &&

((kl->numnote+k->numnote)<=NLIM) ) {

/* delete the key to the left */

(kl->notice)->key = NULL;

k->numnote += kl->numnote;

(kl->left)->right = k;

k->left = kl->left;

free(kl); }

else if ( (!(k->notice)->isdummy) &&

((kr->numnote+k->numnote)<=NLIM) ) {

/* delete this key */

(k->notice)->key = NULL;

kr->numnote += k->numnote;

(k->left)->right = kr;

kr->left = k->left;

free(k); }

}

/* delete n, then advance n down the list */

(n->left)->right = n->right;

(n->right)->left = n->left;

n2 = n->right;

free(n);

n = n2;

}

if (flag) break;

}

/* now reset current */

k = (index->key)->left;

while (k->left != NULL) k = k->left;

n = (k->notice)->right;

while ((n!=NULL) && (n->isdummy)) n = n->right;

current = n;

}

el_empty(void)

{

if (current == NULL) return(1);

else return(0);

}

void *

el_first(void)

{

struct notice *n,*fn;

struct key *k,*fk;

struct index *ind,*fi;

int ctr,*val;

time_t next_int;

if ((index==NULL) || (current==NULL)) return(NULL);

while ((index->key)->time < current->time) {

if (DU == 2) {

/* only two intervals, so relabel first one */

k = index->key;

k->time += DT;

(k->notice)->time += DT;

continue; }

/* remove the notice, key, and index corresponding

fi = index;

fk = fi->key;

fn = fk->notice;

(fn->left)->right = fn->right;

(fn->right)->left = fn->left;

(fk->left)->right = fk->right;

(fk->right)->left = fk->left;

index = index->right;

/* find where to split */

ind = index;

while ((ind->right)->right != NULL) ind = ind->right;

/* ind points to the next to last index interval */

k = ind->key;

next_int = k->time + DT; /* upper bound on new inter. */

while (k->time < next_int) k = k->right;

/* k points to the appropriate sublist of notices */

n = (k->notice)->left;

ctr = 1;

while (n->time >= next_int) {

ctr++;

n = n->left; }

n = n->right;

/* n points to first notice of the new overflow interval

fi->right = ind->right;

ind->right = fi;

/* insert the new dummy key */

fk->time = next_int;

fk->numnote = k->numnote - ctr + 1;

fk->left = k->left;

fk->right = k;

(k->left)->right = fk;

k->left = fk;

k->numnote = ctr;

/* insert the new dummy notice */

fn->time = next_int;

fn->left = n->left;

fn->right = n;

(n->left)->right = fn;

n->left = fn; }

/* remove the first element of the list */

(current->left)->right = current->right;

(current->right)->left = current->left;

/* now update the numnote field in the appropriate key */

n = current;

while ( n->key == NULL ) n = n->right;

k = n->key;

k->numnote = k->numnote - 1;

/* if numnote = 0 then this key must be removed */

if (k->numnote == 0) {

(k->left)->right = k->right;

(k->right)->left = k->left;

free(k); }

/* now set current to be the head of the list */

fn = current->right;

while ( (fn != NULL) && (fn->isdummy) )

fn = fn->right;

val = current->event;

free(current);

current = fn;

return(val);

}

el_delete(void)

{

/* el_delete frees up all the space associated with the event list */

struct index *ind,*ind2;

struct key *k,*k2;

struct notice *n,*n2;

if (index==NULL) return;

ind = index;

k = ind->key;

while (k->left != NULL) k = k->left;

n = k->notice;

while (n!=NULL) {

n2 = n->right;

free(n);

n = n2; }

while (k!=NULL) {

k2 = k->right;

free(k);

k = k2; }

while (ind!=NULL) {

ind2 = ind->right;

free(ind);

ind = ind2; }

index = NULL;

current = NULL;

}