1 /********************************************************************
2 * *
3 * Voice Terminal (VT) *
4 * June, 1991 *
5 * *
6 * Written at USC/Information Sciences Institute from an earlier *
7 * version developed by Bolt Beranek and Newman Inc. *
8 * *
9 * Copyright (c) 1991 University of Southern California. *
10 * All rights reserved. *
11 * *
12 * Redistribution and use in source and binary forms are permitted *
13 * provided that the above copyright notice and this paragraph are *
14 * duplicated in all such forms and that any documentation, *
15 * advertising materials, and other materials related to such *
16 * distribution and use acknowledge that the software was *
17 * developed by the University of Southern California, Information *
18 * Sciences Institute. The name of the University may not be used *
19 * to endorse or promote products derived from this software *
20 * without specific prior written permission. *
21 * THIS SOFTWARE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR *
22 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED *
23 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR *
24 * PURPOSE. *
25 * *
26 *******************************************************************/
27
28 /****************************************************************************/
29 /****** ******/
30 /****** Multiple Timer Package ******/
31 /****** ******/
32 /****************************************************************************/
33 /* */
34 /* These routines manage an ordered queue of interval timers so */
35 /* that a single process may have multiple, independent timers */
36 /* pending. Each timer is identified by an opaque client handle. */
37 /* These routines are intended to multiplex the timers onto the */
38 /* timeout mechanism of the select() call, or onto the single */
39 /* interval timer provided by setitimer(). */
40 /* */
41 /****************************************************************************/
42
43 #include "notify.h" /* Notify_func */
44 #include <stdio.h>
45 #include <stdlib.h> /* */
46 #include <sys/types.h>
47 #include <sys/time.h> /* timeval, gettimeofday() */
48 #include <assert.h>
49 #include "sysdep.h" /* system-dependent */
50
51 typedef struct TQE {
52 struct TQE *link; /* link to next timer */
53 struct timeval time; /* expiration time */
54 struct timeval interval; /* next interval */
55 Notify_func func; /* function to be invoked */
56 Notify_client client;
57 int which; /* type; currently always ITIMER_REAL */
58 } TQE;
59
60 /* active timer queue, in time order */
61 static TQE *timerQ = (TQE *)0;
62
63 /* queue of free Timer Queue Elements */
64 static TQE *freeTQEQ = (TQE *)0;
65
66 #ifndef timeradd
timeradd(struct timeval * a,struct timeval * b,struct timeval * sum)67 void timeradd(struct timeval *a, struct timeval *b,
68 struct timeval *sum)
69 {
70 sum->tv_usec = a->tv_usec + b->tv_usec;
71 if (sum->tv_usec >= 1000000L) { /* > to >= by Akira 12/29/01 */
72 sum->tv_sec = a->tv_sec + b->tv_sec + 1;
73 sum->tv_usec -= 1000000L;
74 }
75 else {
76 sum->tv_sec = a->tv_sec + b->tv_sec;
77 }
78 } /* timeradd */
79 #endif
80
81 /*
82 * Return 1 if a < b, 0 otherwise.
83 */
timerless(struct timeval * a,struct timeval * b)84 static int timerless(struct timeval *a, struct timeval *b)
85 {
86 if (a->tv_sec < b->tv_sec ||
87 (a->tv_sec == b->tv_sec && a->tv_usec < b->tv_usec)) return 1;
88 return 0;
89 } /* timerless */
90
timer_check(void)91 void timer_check(void)
92 {
93 register struct TQE *np;
94
95 for (np = timerQ; np; np = np->link) {
96 assert(np->time.tv_usec < 1000000);
97 assert(np->interval.tv_usec < 1000000);
98 }
99 } /* timer_check */
100
101
102 /*
103 * This routine sets a timer event for the specified client. The client
104 * pointer is opaque to this routine but must be unique among all clients.
105 * Each client may have only one timer pending. If the interval specified
106 * is zero, the pending timer, if any, for this client will be cancelled.
107 * Otherwise, a timer event will be created for the requested amount of
108 * time in the future, and will be inserted in chronological order
109 * into the queue of all clients' timers.
110 * interval: in: time interval
111 * func: in: function to be called when time expires
112 * client: in: first argument for the handler function
113 * relative: in: flag; set relative to current time
114 */
timer_set(struct timeval * interval,Notify_func func,Notify_client client,int relative)115 struct timeval *timer_set(struct timeval *interval,
116 Notify_func func, Notify_client client, int relative)
117 {
118 register struct TQE *np, *op, *tp; /* To scan the timer queue */
119
120 /* scan the timer queue to see if client has pending timer */
121 op = (struct TQE *)&timerQ; /* Fudge OK since link is first */
122 for (np = timerQ; np; op = np, np = np->link)
123 if (np->client == client) {
124 op->link = np->link; /* Yes, remove the timer from Q */
125 break; /* and stop the search */
126 }
127
128 /* if the requested interval is zero, just free the timer */
129 if (interval == 0) {
130 if (np) { /* If we found a timer, */
131 np->link = freeTQEQ; /* link TQE at head of free Q */
132 freeTQEQ = np;
133 }
134 return 0; /* return, no timer set */
135 }
136
137 /* nonzero interval, calculate new expiration time */
138 if (!(tp = np)) { /* If no previous timer, get a TQE */
139 /* allocate timer */
140 if (!freeTQEQ) {
141 freeTQEQ = (TQE *)malloc(sizeof(TQE));
142 freeTQEQ->link = (TQE *)0;
143 freeTQEQ->interval.tv_usec = 0;
144 freeTQEQ->interval.tv_sec = 0;
145 }
146 tp = freeTQEQ;
147 freeTQEQ = tp->link;
148 }
149
150 /* calculate expiration time */
151 if (relative) {
152 (void) gettimeofday(&(tp->time), (struct timezone *)0);
153 timeradd(&(tp->time), interval, &(tp->time));
154 assert(tp->time.tv_usec < 1000000);
155 }
156 else tp->time = *interval;
157 #ifdef DEBUG
158 printf("timer_set(): %d.%06d\n", tp->time.tv_sec, tp->time.tv_usec);
159 #endif
160 tp->func = func;
161 tp->client = client;
162 tp->which = ITIMER_REAL;
163
164 /* insert new timer into timer queue */
165 op = (struct TQE *)&timerQ; /* fudge OK since link is first */
166 for (np = timerQ; np; op = np, np=np->link) {
167 if (timerless(&tp->time, &np->time)) break;
168 }
169 op->link = tp; /* point prev TQE to new one */
170 tp->link = np; /* point new TQE to next one */
171
172 timer_check(); /*DEBUG*/
173 return &(tp->interval);
174 } /* timer_set */
175
176 /*
177 * This routine returns a timeout value suitable for use in a select() call.
178 * Before returning, all timer events that have expired are removed from the
179 * queue and processed. If no timer events remain, a NULL pointer is returned
180 * so the select() will just block. Otherwise, the supplied timeval struct is
181 * filled with the timeout interval until the next timer expires.
182
183 * Note: This routine may be called recursively if the timer event handling
184 * routine leads to another select() call! Therefore, we just take one timer
185 * at a time, and don't use static variables.
186 */
timer_get(struct timeval * timeout)187 struct timeval *timer_get(struct timeval *timeout)
188 {
189 register struct TQE *tp; /* to scan the timer queue */
190 struct timeval now; /* current time */
191
192 timer_check(); /*DEBUG*/
193 for (;;) {
194 /* return null pointer if there is no timer pending. */
195 if (!timerQ) return (struct timeval *)0;
196
197 /* check head of timer queue to see if timer has expired */
198 (void) gettimeofday(&now, (struct timezone *)0);
199 if (timerless(&now, &timerQ->time)) { /* unexpired, calc timeout */
200 timeout->tv_sec = timerQ->time.tv_sec - now.tv_sec;
201 timeout->tv_usec = timerQ->time.tv_usec - now.tv_usec;
202 if (timeout->tv_usec < 0) {
203 timeout->tv_usec += 1000000L;
204 --timeout->tv_sec;
205 }
206 assert(timeout->tv_usec < 1000000);
207 return timeout; /* timeout until timer expires */
208 } else { /* head timer has expired, */
209 tp = timerQ; /* so remove it from the */
210 timerQ = tp->link; /* timer queue, */
211 tp->link = freeTQEQ;
212 freeTQEQ = tp;
213 /* restart timer (absolute) */
214 if (tp->interval.tv_sec || tp->interval.tv_usec) {
215 timeradd(&tp->interval, &tp->time, &tp->time);
216 timer_set(&tp->time, tp->func, tp->client, 0);
217 }
218 (*(tp->func))(tp->client); /* call the event handler */
219 }
220 } /* loop to see if another timer expired */
221 } /* timer_get */
222
223
224 /*
225 * Return 1 if the timer queue is not empty.
226 */
timer_pending(void)227 int timer_pending(void)
228 {
229 return timerQ != 0;
230 } /* timer_pending */
231