thttpd/timers.c

/* timers.c - simple timer routines
**
** Copyright © 1995,1998,2000 by Jef Poskanzer <jef@acme.com>.
** All rights reserved.
**
** Redistribution and use in source and binary forms, with or without
** modification, are permitted provided that the following conditions
** are met:
** 1. Redistributions of source code must retain the above copyright
**    notice, this list of conditions and the following disclaimer.
** 2. Redistributions in binary form must reproduce the above copyright
**    notice, this list of conditions and the following disclaimer in the
**    documentation and/or other materials provided with the distribution.
**
** THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
** ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
** IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
** ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
** FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
** DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
** OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
** HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
** LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
** OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
** SUCH DAMAGE.
*/

#include <sys/types.h>

#include <stdlib.h>
#include <stdio.h>
#include <syslog.h>

#include "timers.h"


#define HASH_SIZE 67
static Timer* timers[HASH_SIZE];
static Timer* free_timers;
static int alloc_count, active_count, free_count;

ClientData JunkClientData;


static unsigned int
hash( Timer* t )
    {
    /* We can hash on the trigger time, even though it can change over
    ** the life of a timer via either the periodic bit or the tmr_reset()
    ** call.  This is because both of those guys call l_resort(), which
    ** recomputes the hash and moves the timer to the appropriate list.
    */
    return (
        (unsigned int) t->time.tv_sec ^
        (unsigned int) t->time.tv_usec ) % HASH_SIZE;
    }


static void
l_add( Timer* t )
    {
    int h = t->hash;
    register Timer* t2;
    register Timer* t2prev;

    t2 = timers[h];
    if ( t2 == (Timer*) 0 )
        {
        /* The list is empty. */
        timers[h] = t;
        t->prev = t->next = (Timer*) 0;
        }
    else
        {
        if ( t->time.tv_sec < t2->time.tv_sec ||
             ( t->time.tv_sec == t2->time.tv_sec &&
               t->time.tv_usec <= t2->time.tv_usec ) )
            {
            /* The new timer goes at the head of the list. */
            timers[h] = t;
            t->prev = (Timer*) 0;
            t->next = t2;
            t2->prev = t;
            }
        else
            {
            /* Walk the list to find the insertion point. */
            for ( t2prev = t2, t2 = t2->next; t2 != (Timer*) 0;
                  t2prev = t2, t2 = t2->next )
                {
                if ( t->time.tv_sec < t2->time.tv_sec ||
                     ( t->time.tv_sec == t2->time.tv_sec &&
                       t->time.tv_usec <= t2->time.tv_usec ) )
                    {
                    /* Found it. */
                    t2prev->next = t;
                    t->prev = t2prev;
                    t->next = t2;
                    t2->prev = t;
                    return;
                    }
                }
            /* Oops, got to the end of the list.  Add to tail. */
            t2prev->next = t;
            t->prev = t2prev;
            t->next = (Timer*) 0;
            }
        }
    }


static void
l_remove( Timer* t )
    {
    int h = t->hash;

    if ( t->prev == (Timer*) 0 )
        timers[h] = t->next;
    else
        t->prev->next = t->next;
    if ( t->next != (Timer*) 0 )
        t->next->prev = t->prev;
    }


static void
l_resort( Timer* t )
    {
    /* Remove the timer from its old list. */
    l_remove( t );
    /* Recompute the hash. */
    t->hash = hash( t );
    /* And add it back in to its new list, sorted correctly. */
    l_add( t );
    }


void
tmr_init( void )
    {
    int h;

    for ( h = 0; h < HASH_SIZE; ++h )
        timers[h] = (Timer*) 0;
    free_timers = (Timer*) 0;
    alloc_count = active_count = free_count = 0;
    }


Timer*
tmr_create(
    struct timeval* nowP, TimerProc* timer_proc, ClientData client_data,
    long msecs, int periodic )
    {
    Timer* t;

    if ( free_timers != (Timer*) 0 )
        {
        t = free_timers;
        free_timers = t->next;
        --free_count;
        }
    else
        {
        t = (Timer*) malloc( sizeof(Timer) );
        if ( t == (Timer*) 0 )
            return (Timer*) 0;
        ++alloc_count;
        }

    t->timer_proc = timer_proc;
    t->client_data = client_data;
    t->msecs = msecs;
    t->periodic = periodic;
    if ( nowP != (struct timeval*) 0 )
        t->time = *nowP;
    else
        (void) gettimeofday( &t->time, (struct timezone*) 0 );
    t->time.tv_sec += msecs / 1000L;
    t->time.tv_usec += ( msecs % 1000L ) * 1000L;
    if ( t->time.tv_usec >= 1000000L )
        {
        t->time.tv_sec += t->time.tv_usec / 1000000L;
        t->time.tv_usec %= 1000000L;
        }
    t->hash = hash( t );
    /* Add the new timer to the proper active list. */
    l_add( t );
    ++active_count;

    return t;
    }


struct timeval*
tmr_timeout( struct timeval* nowP )
    {
    long msecs;
    static struct timeval timeout;

    msecs = tmr_mstimeout( nowP );
    if ( msecs == INFTIM )
        return (struct timeval*) 0;
    timeout.tv_sec = msecs / 1000L;
    timeout.tv_usec = ( msecs % 1000L ) * 1000L;
    return &timeout;
    }


long
tmr_mstimeout( struct timeval* nowP )
    {
    int h;
    int gotone;
    long msecs, m;
    register Timer* t;

    gotone = 0;
    msecs = 0;          /* make lint happy */
    /* Since the lists are sorted, we only need to look at the
    ** first timer on each one.
    */
    for ( h = 0; h < HASH_SIZE; ++h )
        {
        t = timers[h];
        if ( t != (Timer*) 0 )
            {
            m = ( t->time.tv_sec - nowP->tv_sec ) * 1000L +
                ( t->time.tv_usec - nowP->tv_usec ) / 1000L;
            if ( ! gotone )
                {
                msecs = m;
                gotone = 1;
                }
            else if ( m < msecs )
                msecs = m;
            }
        }
    if ( ! gotone )
        return INFTIM;
    if ( msecs <= 0 )
        msecs = 0;
    return msecs;
    }


void
tmr_run( struct timeval* nowP )
    {
    int h;
    Timer* t;
    Timer* next;

    for ( h = 0; h < HASH_SIZE; ++h )
        for ( t = timers[h]; t != (Timer*) 0; t = next )
            {
            next = t->next;
            /* Since the lists are sorted, as soon as we find a timer
            ** that isn't ready yet, we can go on to the next list.
            */
            if ( t->time.tv_sec > nowP->tv_sec ||
                 ( t->time.tv_sec == nowP->tv_sec &&
                   t->time.tv_usec > nowP->tv_usec ) )
                break;
            (t->timer_proc)( t->client_data, nowP );
            if ( t->periodic )
                {
                /* Reschedule. */
                t->time.tv_sec += t->msecs / 1000L;
                t->time.tv_usec += ( t->msecs % 1000L ) * 1000L;
                if ( t->time.tv_usec >= 1000000L )
                    {
                    t->time.tv_sec += t->time.tv_usec / 1000000L;
                    t->time.tv_usec %= 1000000L;
                    }
                l_resort( t );
                }
            else
                tmr_cancel( t );
            }
    }


void
tmr_reset( struct timeval* nowP, Timer* t )
    {
    t->time = *nowP;
    t->time.tv_sec += t->msecs / 1000L;
    t->time.tv_usec += ( t->msecs % 1000L ) * 1000L;
    if ( t->time.tv_usec >= 1000000L )
        {
        t->time.tv_sec += t->time.tv_usec / 1000000L;
        t->time.tv_usec %= 1000000L;
        }
    l_resort( t );
    }


void
tmr_cancel( Timer* t )
    {
    /* Remove it from its active list. */
    l_remove( t );
    --active_count;
    /* And put it on the free list. */
    t->next = free_timers;
    free_timers = t;
    ++free_count;
    t->prev = (Timer*) 0;
    }


void
tmr_cleanup( void )
    {
    Timer* t;

    while ( free_timers != (Timer*) 0 )
        {
        t = free_timers;
        free_timers = t->next;
        --free_count;
        free( (void*) t );
        --alloc_count;
        }
    }


void
tmr_destroy( void )
    {
    int h;

    for ( h = 0; h < HASH_SIZE; ++h )
        while ( timers[h] != (Timer*) 0 )
            tmr_cancel( timers[h] );
    tmr_cleanup();
    }


/* Generate debugging statistics syslog message. */
void
tmr_logstats( long secs )
    {
    syslog(
        LOG_NOTICE, "  timers - %d allocated, %d active, %d free",
        alloc_count, active_count, free_count );
    if ( active_count + free_count != alloc_count )
        syslog( LOG_ERR, "timer counts don't add up!" );
    }
Revision:	1.1
Committed:	Mon Jun 18 21:11:57 2001 UTC (25 years, 3 months ago) by root
Content type:	text/plain
Branch:	MAIN
CVS Tags:	mp_j, dp_j, cp_j, HEAD
Branch point for:	connpatch, dirpatch, mmapppatch
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	/* timers.c - simple timer routines
2			**
3			** Copyright © 1995,1998,2000 by Jef Poskanzer <jef@acme.com>.
4			** All rights reserved.
5			**
6			** Redistribution and use in source and binary forms, with or without
7			** modification, are permitted provided that the following conditions
8			** are met:
9			** 1. Redistributions of source code must retain the above copyright
10			** notice, this list of conditions and the following disclaimer.
11			** 2. Redistributions in binary form must reproduce the above copyright
12			** notice, this list of conditions and the following disclaimer in the
13			** documentation and/or other materials provided with the distribution.
14			**
15			** THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16			** ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17			** IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18			** ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19			** FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20			** DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21			** OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22			** HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23			** LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24			** OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
25			** SUCH DAMAGE.
26			*/
27
28			#include <sys/types.h>
29
30			#include <stdlib.h>
31			#include <stdio.h>
32			#include <syslog.h>
33
34			#include "timers.h"
35
36
37			#define HASH_SIZE 67
38			static Timer* timers[HASH_SIZE];
39			static Timer* free_timers;
40			static int alloc_count, active_count, free_count;
41
42			ClientData JunkClientData;
43
44
45
46			static unsigned int
47			hash( Timer* t )
48			{
49			/* We can hash on the trigger time, even though it can change over
50			** the life of a timer via either the periodic bit or the tmr_reset()
51			** call. This is because both of those guys call l_resort(), which
52			** recomputes the hash and moves the timer to the appropriate list.
53			*/
54			return (
55			(unsigned int) t->time.tv_sec ^
56			(unsigned int) t->time.tv_usec ) % HASH_SIZE;
57			}
58
59
60			static void
61			l_add( Timer* t )
62			{
63			int h = t->hash;
64			register Timer* t2;
65			register Timer* t2prev;
66
67			t2 = timers[h];
68			if ( t2 == (Timer*) 0 )
69			{
70			/* The list is empty. */
71			timers[h] = t;
72			t->prev = t->next = (Timer*) 0;
73			}
74			else
75			{
76			if ( t->time.tv_sec < t2->time.tv_sec \|\|
77			( t->time.tv_sec == t2->time.tv_sec &&
78			t->time.tv_usec <= t2->time.tv_usec ) )
79			{
80			/* The new timer goes at the head of the list. */
81			timers[h] = t;
82			t->prev = (Timer*) 0;
83			t->next = t2;
84			t2->prev = t;
85			}
86			else
87			{
88			/* Walk the list to find the insertion point. */
89			for ( t2prev = t2, t2 = t2->next; t2 != (Timer*) 0;
90			t2prev = t2, t2 = t2->next )
91			{
92			if ( t->time.tv_sec < t2->time.tv_sec \|\|
93			( t->time.tv_sec == t2->time.tv_sec &&
94			t->time.tv_usec <= t2->time.tv_usec ) )
95			{
96			/* Found it. */
97			t2prev->next = t;
98			t->prev = t2prev;
99			t->next = t2;
100			t2->prev = t;
101			return;
102			}
103			}
104			/* Oops, got to the end of the list. Add to tail. */
105			t2prev->next = t;
106			t->prev = t2prev;
107			t->next = (Timer*) 0;
108			}
109			}
110			}
111
112
113			static void
114			l_remove( Timer* t )
115			{
116			int h = t->hash;
117
118			if ( t->prev == (Timer*) 0 )
119			timers[h] = t->next;
120			else
121			t->prev->next = t->next;
122			if ( t->next != (Timer*) 0 )
123			t->next->prev = t->prev;
124			}
125
126
127			static void
128			l_resort( Timer* t )
129			{
130			/* Remove the timer from its old list. */
131			l_remove( t );
132			/* Recompute the hash. */
133			t->hash = hash( t );
134			/* And add it back in to its new list, sorted correctly. */
135			l_add( t );
136			}
137
138
139			void
140			tmr_init( void )
141			{
142			int h;
143
144			for ( h = 0; h < HASH_SIZE; ++h )
145			timers[h] = (Timer*) 0;
146			free_timers = (Timer*) 0;
147			alloc_count = active_count = free_count = 0;
148			}
149
150
151			Timer*
152			tmr_create(
153			struct timeval* nowP, TimerProc* timer_proc, ClientData client_data,
154			long msecs, int periodic )
155			{
156			Timer* t;
157
158			if ( free_timers != (Timer*) 0 )
159			{
160			t = free_timers;
161			free_timers = t->next;
162			--free_count;
163			}
164			else
165			{
166			t = (Timer*) malloc( sizeof(Timer) );
167			if ( t == (Timer*) 0 )
168			return (Timer*) 0;
169			++alloc_count;
170			}
171
172			t->timer_proc = timer_proc;
173			t->client_data = client_data;
174			t->msecs = msecs;
175			t->periodic = periodic;
176			if ( nowP != (struct timeval*) 0 )
177			t->time = *nowP;
178			else
179			(void) gettimeofday( &t->time, (struct timezone*) 0 );
180			t->time.tv_sec += msecs / 1000L;
181			t->time.tv_usec += ( msecs % 1000L ) * 1000L;
182			if ( t->time.tv_usec >= 1000000L )
183			{
184			t->time.tv_sec += t->time.tv_usec / 1000000L;
185			t->time.tv_usec %= 1000000L;
186			}
187			t->hash = hash( t );
188			/* Add the new timer to the proper active list. */
189			l_add( t );
190			++active_count;
191
192			return t;
193			}
194
195
196			struct timeval*
197			tmr_timeout( struct timeval* nowP )
198			{
199			long msecs;
200			static struct timeval timeout;
201
202			msecs = tmr_mstimeout( nowP );
203			if ( msecs == INFTIM )
204			return (struct timeval*) 0;
205			timeout.tv_sec = msecs / 1000L;
206			timeout.tv_usec = ( msecs % 1000L ) * 1000L;
207			return &timeout;
208			}
209
210
211			long
212			tmr_mstimeout( struct timeval* nowP )
213			{
214			int h;
215			int gotone;
216			long msecs, m;
217			register Timer* t;
218
219			gotone = 0;
220			msecs = 0; /* make lint happy */
221			/* Since the lists are sorted, we only need to look at the
222			** first timer on each one.
223			*/
224			for ( h = 0; h < HASH_SIZE; ++h )
225			{
226			t = timers[h];
227			if ( t != (Timer*) 0 )
228			{
229			m = ( t->time.tv_sec - nowP->tv_sec ) * 1000L +
230			( t->time.tv_usec - nowP->tv_usec ) / 1000L;
231			if ( ! gotone )
232			{
233			msecs = m;
234			gotone = 1;
235			}
236			else if ( m < msecs )
237			msecs = m;
238			}
239			}
240			if ( ! gotone )
241			return INFTIM;
242			if ( msecs <= 0 )
243			msecs = 0;
244			return msecs;
245			}
246
247
248			void
249			tmr_run( struct timeval* nowP )
250			{
251			int h;
252			Timer* t;
253			Timer* next;
254
255			for ( h = 0; h < HASH_SIZE; ++h )
256			for ( t = timers[h]; t != (Timer*) 0; t = next )
257			{
258			next = t->next;
259			/* Since the lists are sorted, as soon as we find a timer
260			** that isn't ready yet, we can go on to the next list.
261			*/
262			if ( t->time.tv_sec > nowP->tv_sec \|\|
263			( t->time.tv_sec == nowP->tv_sec &&
264			t->time.tv_usec > nowP->tv_usec ) )
265			break;
266			(t->timer_proc)( t->client_data, nowP );
267			if ( t->periodic )
268			{
269			/* Reschedule. */
270			t->time.tv_sec += t->msecs / 1000L;
271			t->time.tv_usec += ( t->msecs % 1000L ) * 1000L;
272			if ( t->time.tv_usec >= 1000000L )
273			{
274			t->time.tv_sec += t->time.tv_usec / 1000000L;
275			t->time.tv_usec %= 1000000L;
276			}
277			l_resort( t );
278			}
279			else
280			tmr_cancel( t );
281			}
282			}
283
284
285			void
286			tmr_reset( struct timeval* nowP, Timer* t )
287			{
288			t->time = *nowP;
289			t->time.tv_sec += t->msecs / 1000L;
290			t->time.tv_usec += ( t->msecs % 1000L ) * 1000L;
291			if ( t->time.tv_usec >= 1000000L )
292			{
293			t->time.tv_sec += t->time.tv_usec / 1000000L;
294			t->time.tv_usec %= 1000000L;
295			}
296			l_resort( t );
297			}
298
299
300			void
301			tmr_cancel( Timer* t )
302			{
303			/* Remove it from its active list. */
304			l_remove( t );
305			--active_count;
306			/* And put it on the free list. */
307			t->next = free_timers;
308			free_timers = t;
309			++free_count;
310			t->prev = (Timer*) 0;
311			}
312
313
314			void
315			tmr_cleanup( void )
316			{
317			Timer* t;
318
319			while ( free_timers != (Timer*) 0 )
320			{
321			t = free_timers;
322			free_timers = t->next;
323			--free_count;
324			free( (void*) t );
325			--alloc_count;
326			}
327			}
328
329
330			void
331			tmr_destroy( void )
332			{
333			int h;
334
335			for ( h = 0; h < HASH_SIZE; ++h )
336			while ( timers[h] != (Timer*) 0 )
337			tmr_cancel( timers[h] );
338			tmr_cleanup();
339			}
340
341
342			/* Generate debugging statistics syslog message. */
343			void
344			tmr_logstats( long secs )
345			{
346			syslog(
347			LOG_NOTICE, " timers - %d allocated, %d active, %d free",
348			alloc_count, active_count, free_count );
349			if ( active_count + free_count != alloc_count )
350			syslog( LOG_ERR, "timer counts don't add up!" );
351			}