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