From c66ed8fdb8b64fcb8973f6b60a9696b59ba29ee6 Mon Sep 17 00:00:00 2001 From: "/C=EU/ST=EU/CN=Pablo Neira Ayuso/emailAddress=pablo@netfilter.org" Date: Tue, 29 Jan 2008 13:54:24 +0000 Subject: implement a rb-tree based alarm framework --- src/alarm.c | 156 +++++++++++++++++++++--------------------------------------- 1 file changed, 54 insertions(+), 102 deletions(-) (limited to 'src/alarm.c') diff --git a/src/alarm.c b/src/alarm.c index 4b23bd1..5013735 100644 --- a/src/alarm.c +++ b/src/alarm.c @@ -1,5 +1,5 @@ /* - * (C) 2006 by Pablo Neira Ayuso + * (C) 2006-2008 by Pablo Neira Ayuso * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -17,41 +17,45 @@ */ #include "alarm.h" -#include "jhash.h" #include #include -#define ALARM_HASH_SIZE 2048 +static struct rb_root alarm_root = RB_ROOT; +static LIST_HEAD(alarm_run_queue); -static struct list_head *alarm_hash; - -void init_alarm(struct alarm_list *t, +void init_alarm(struct alarm_block *t, void *data, - void (*fcn)(struct alarm_list *a, void *data)) + void (*fcn)(struct alarm_block *a, void *data)) { /* initialize the head to check whether a node is inserted */ - INIT_LIST_HEAD(&t->head); + RB_CLEAR_NODE(&t->node); timerclear(&t->tv); t->data = data; t->function = fcn; } -static void -__add_alarm(struct alarm_list *alarm) +static void __add_alarm(struct alarm_block *alarm) { - struct alarm_list *t; - int i = jhash(alarm, sizeof(alarm), 0) % ALARM_HASH_SIZE; + struct rb_node **new = &(alarm_root.rb_node); + struct rb_node *parent = NULL; - list_for_each_entry(t, &alarm_hash[i], head) { - if (timercmp(&alarm->tv, &t->tv, <)) { - list_add_tail(&alarm->head, &t->head); - return; - } + while (*new) { + struct alarm_block *this; + + this = container_of(*new, struct alarm_block, node); + + parent = *new; + if (timercmp(&alarm->tv, &this->tv, <)) + new = &((*new)->rb_left); + else + new = &((*new)->rb_right); } - list_add_tail(&alarm->head, &alarm_hash[i]); + + rb_link_node(&alarm->node, parent, new); + rb_insert_color(&alarm->node, &alarm_root); } -void add_alarm(struct alarm_list *alarm, unsigned long sc, unsigned long usc) +void add_alarm(struct alarm_block *alarm, unsigned long sc, unsigned long usc) { struct timeval tv; @@ -63,16 +67,18 @@ void add_alarm(struct alarm_list *alarm, unsigned long sc, unsigned long usc) __add_alarm(alarm); } -void del_alarm(struct alarm_list *alarm) +void del_alarm(struct alarm_block *alarm) { /* don't remove a non-inserted node */ - if (!list_empty(&alarm->head)) - list_del_init(&alarm->head); + if (!RB_EMPTY_NODE(&alarm->node)) { + rb_erase(&alarm->node, &alarm_root); + RB_CLEAR_NODE(&alarm->node); + } } -int alarm_pending(struct alarm_list *alarm) +int alarm_pending(struct alarm_block *alarm) { - if (list_empty(&alarm->head)) + if (RB_EMPTY_NODE(&alarm->node)) return 0; return 1; @@ -99,101 +105,47 @@ calculate_next_run(struct timeval *cand, struct timeval * get_next_alarm_run(struct timeval *next_run) { - int i; - struct alarm_list *t; + struct rb_node *node = alarm_root.rb_node; struct timeval tv; - struct timeval cand = { - .tv_sec = LONG_MAX, - .tv_usec = LONG_MAX - }; gettimeofday(&tv, NULL); - for (i=0; itv, &cand, <)) { - cand.tv_sec = t->tv.tv_sec; - cand.tv_usec = t->tv.tv_usec; - } - } + node = rb_first(&alarm_root); + if (node) { + struct alarm_block *this; + this = container_of(node, struct alarm_block, node); + return calculate_next_run(&this->tv, &tv, next_run); } - - return calculate_next_run(&cand, &tv, next_run); -} - -static inline int -tv_compare(struct alarm_list *a, struct timeval *cur, struct timeval *cand) -{ - if (timercmp(&a->tv, cur, >)) { - /* select the next alarm candidate */ - if (timercmp(&a->tv, cand, <)) { - cand->tv_sec = a->tv.tv_sec; - cand->tv_usec = a->tv.tv_usec; - } - return 1; - } - return 0; + return NULL; } struct timeval * do_alarm_run(struct timeval *next_run) { - int i; - struct alarm_list *t, *next, *prev; + struct rb_node *node = alarm_root.rb_node; + struct alarm_block *this, *tmp; struct timeval tv; - struct timeval cand = { - .tv_sec = LONG_MAX, - .tv_usec = LONG_MAX - }; gettimeofday(&tv, NULL); - for (i=0; ihead.prev, - struct alarm_list, - head); - - del_alarm(t); - t->function(t, t->data); - - /* Special case: One deleted node is inserted - * again in the same place */ - if (next->head.prev == &prev->head) { - t = list_entry(next->head.prev, - struct alarm_list, - head); - if (tv_compare(t, &tv, &cand)) - break; - } - } - } + node = rb_first(&alarm_root); + while (node) { + this = container_of(node, struct alarm_block, node); - return calculate_next_run(&cand, &tv, next_run); -} + if (timercmp(&this->tv, &tv, >)) + break; -int init_alarm_hash(void) -{ - int i; + node = rb_next(node); - alarm_hash = malloc(sizeof(struct list_head) * ALARM_HASH_SIZE); - if (alarm_hash == NULL) - return -1; - - for (i=0; ilist, &alarm_run_queue); + } - return 0; -} + list_for_each_entry_safe(this, tmp, &alarm_run_queue, list) { + list_del(&this->list); + rb_erase(&this->node, &alarm_root); + RB_CLEAR_NODE(&this->node); + this->function(this, this->data); + } -void destroy_alarm_hash(void) -{ - free(alarm_hash); + return get_next_alarm_run(next_run); } -- cgit v1.2.3