[icinga-checkins] icinga.org: icinga-core/test/core: core: fix event removal from queues with O(1) removal from doubly linked lists ( Andreas Ericsson) #2183

git at icinga.org git at icinga.org
Fri Jan 27 19:57:51 CET 2012


Module: icinga-core
Branch: test/core
Commit: d4cab08a7bf1eedd65891f362fca3d9d2989143a
URL:    https://git.icinga.org/?p=icinga-core.git;a=commit;h=d4cab08a7bf1eedd65891f362fca3d9d2989143a

Author: Michael Friedrich <michael.friedrich at univie.ac.at>
Date:   Fri Jan 27 14:27:47 2012 +0100

core: fix event removal from queues with O(1) removal from doubly linked lists (Andreas Ericsson) #2183

given the fact that the algorithm before was violating the purpose
of a double linked list, looping over the event list if the on top
event was not found in the first place, this is now revamped.

since the event itsself provides next and prev pointers already,
we can work with the "next" and the "previous" events in the list.

if there is a previous event before the current one, we modify its
next pointer to target the events' next event, leaving out the event
to remove.
same goes for the next event, if there, its previous pointer leaves
out the event to remove, but targetting the event before.

in case there is no previous event, the head of the list is modified
to point to the next event after the removed one.
same matches for the tail of the list, assigning the previous and now
last event of the list.

if there was only one element in the list, the last 2 condition would
match, setting the head and tail pointers to NULL, meaning to say -
1 list, removed 1 element, now empty list.

this algorithm allows to remove an event just by reordering next and
previous pointers within a doubly linked list, and preventing us to loop.

so to say, Andreas is a genius ...

refs #2183

---

 Changelog     |    1 +
 base/events.c |   54 ++++++++++++++++++++++++++++++++----------------------
 2 files changed, 33 insertions(+), 22 deletions(-)

diff --git a/Changelog b/Changelog
index c71c18f..287ecf1 100644
--- a/Changelog
+++ b/Changelog
@@ -8,6 +8,7 @@ Thanks to all contributers, testers and developers. Please read AUTHORS and THAN
 
 ENHANCEMENTS
 * core: notifications: Create contact list after eventbroker callbacks (Andreas Ericsson) #2110
+* core: fix event removal from queues with O(1) removal from doubly linked lists (Andreas Ericsson) #2183
 
 FIXES
 * core: Plug some macro leaks triggered when sending notifications (Andreas Ericsson) #2109
diff --git a/base/events.c b/base/events.c
index d567a89..7c4084f 100644
--- a/base/events.c
+++ b/base/events.c
@@ -1031,10 +1031,13 @@ void add_event(timed_event *event, timed_event **event_list, timed_event **event
 
 /* remove an event from the queue */
 void remove_event(timed_event *event, timed_event **event_list, timed_event **event_list_tail) {
-	timed_event *temp_event = NULL;
+	timed_event *prev_event, *next_event;
 
 	log_debug_info(DEBUGL_FUNCTIONS, 0, "remove_event()\n");
 
+	if (!event)
+		return;
+
 #ifdef USE_EVENT_BROKER
 	/* send event data to broker */
 	broker_timed_event(NEBTYPE_TIMEDEVENT_REMOVE, NEBFLAG_NONE, NEBATTR_NONE, event, NULL);
@@ -1043,31 +1046,38 @@ void remove_event(timed_event *event, timed_event **event_list, timed_event **ev
 	if (*event_list == NULL)
 		return;
 
-	if (*event_list == event) {
-		event->prev = NULL;
-		*event_list = event->next;
-		if (*event_list == NULL)
-			*event_list_tail = NULL;
+	/*
+	 * the event struct already holds next+prev ptrs
+	 * for the doubly linked list, so fetch them
+	 * and reassign previous with next, and reverse
+	 * check #2183 for a detailed description
+	 */
+	prev_event = event->prev;
+	next_event = event->next;
+
+	if (prev_event) {
+		prev_event->next = next_event;
 	}
-
-	else {
-
-		for (temp_event = *event_list; temp_event != NULL; temp_event = temp_event->next) {
-			if (temp_event->next == event) {
-				temp_event->next = temp_event->next->next;
-				if (temp_event->next == NULL)
-					*event_list_tail = temp_event;
-				else
-					temp_event->next->prev = temp_event;
-				event->next = NULL;
-				event->prev = NULL;
-				break;
-			}
-		}
+	if (next_event) {
+		next_event->prev = prev_event;
 	}
 
+	/* re-assign head and tail */
+	if (!prev_event) {
+		/* no previous event, so "next" is now first in list */
+		*event_list = next_event;
+	}
+	if (!next_event) {
+		/* no following event, so "prev" is now last in list */
+		*event_list_tail = prev_event;
+	}
 
-	return;
+	/*
+	 * If there was only one event in the list,
+	 * it's done just as if there were events before
+	 * and after the deleted event.
+	 * head and tail pointers are now NULL in this case
+	 */
 }
 
 





More information about the icinga-checkins mailing list