1/*
2 * Copyright 2001-2009, Haiku Inc.
3 * Distributed under the terms of the MIT License.
4 *
5 * Authors:
6 *		Ingo Weinhold (bonefish@users.sf.net)
7 */
8
9
10#include "EventQueue.h"
11
12#include <stdio.h>
13
14#include <String.h>
15
16#include "Event.h"
17
18
19static const char *kDefaultEventQueueName = "event looper";
20
21
22/*!	\class EventQueue
23	\brief A class providing a mechanism for executing events at specified
24		   times.
25
26	The class' interface is quite small. It basically features methods to
27	add or remove an event or to modify an event's time. It is derived from
28	BLocker to inherit a locking mechanism needed to serialize the access to
29	its member variables (especially the event list).
30
31	The queue runs an own thread (in _EventLooper()), which executes the
32	events at the right times. The execution of an event consists of invoking
33	its Event::Do() method. If the event's Event::IsAutoDelete() or its Do()
34	method return \c true, the event object is deleted after execution. In
35	any case the event is removed from the list before it is executed. The
36	queue is not locked while an event is executed.
37
38	The event list (\a fEvents) is ordered ascendingly by time. The thread
39	uses a semaphore (\a fLooperControl) to wait (time out) for the next
40	event. This semaphore is released to indicate changes to the event list.
41*/
42
43/*!	\var BList EventQueue::fEvents
44	\brief List of events (Event*) in ascending order (by time).
45*/
46
47/*!	\var thread_id EventQueue::fEventLooper
48	\brief Thread ID of the queue's thread.
49*/
50
51/*!	\var sem_id EventQueue::fLooperControl
52	\brief Queue thread control semaphore.
53
54	The semaphore is initialized with count \c 0 and used by the queue's
55	thread for timing out at the time when the next event has to be executed.
56	If the event list is changed by another thread and that changed the time
57	of the next event the semaphore is released (_Reschedule()).
58*/
59
60/*!	\var volatile bigtime_t EventQueue::fNextEventTime
61	\brief Time at which the queue's thread will wake up next time.
62*/
63
64/*!	\var status_t EventQueue::fStatus
65	\brief Initialization status.
66*/
67
68/*!	\var volatile bool EventQueue::fTerminating
69	\brief Set to \c true by Die() to signal the queue's thread not to
70		   execute any more events.
71*/
72
73
74/*!	\brief Creates a new event queue.
75
76	The status of the initialization can and should be check with InitCheck().
77
78	\param name The name used for the queue's thread and semaphore. If \c NULL,
79		   a default name is used.
80*/
81EventQueue::EventQueue(const char *name)
82	:
83	fEvents(100),
84	fEventLooper(-1),
85	fLooperControl(-1),
86	fNextEventTime(0),
87	fStatus(B_ERROR),
88	fTerminating(false)
89{
90	if (!name)
91		name = kDefaultEventQueueName;
92	fLooperControl = create_sem(0, (BString(name) += " control").String());
93	if (fLooperControl >= B_OK)
94		fStatus = B_OK;
95	else
96		fStatus = fLooperControl;
97	if (fStatus == B_OK) {
98		fEventLooper = spawn_thread(_EventLooperEntry, name,
99			B_DISPLAY_PRIORITY + 1, this);
100		if (fEventLooper >= B_OK) {
101			fStatus = B_OK;
102			resume_thread(fEventLooper);
103		} else
104			fStatus = fEventLooper;
105	}
106}
107
108
109/*!	\brief Frees all resources associated by this object.
110
111	Die() is called to terminate the queue's thread and all events whose
112	IsAutoDelete() returns \c true are deleted.
113*/
114EventQueue::~EventQueue()
115{
116	Die();
117	while (Event *event = (Event*)fEvents.RemoveItem((int32)0)) {
118		if (event->IsAutoDelete())
119			delete event;
120	}
121}
122
123
124/*!	\brief Returns the initialization status of the event queue.
125	\return \c B_OK, if everything went fine, an error code otherwise.
126*/
127status_t
128EventQueue::InitCheck()
129{
130	return fStatus;
131}
132
133
134/*!	\brief Terminates the queue's thread.
135
136	If an event is currently executed, it is allowed to finish its task
137	normally, but no more events will be executed.
138
139	Afterwards events can still be added to and removed from the queue.
140*/
141void
142EventQueue::Die()
143{
144	fTerminating = true;
145	if (delete_sem(fLooperControl) == B_OK) {
146		int32 dummy;
147		wait_for_thread(fEventLooper, &dummy);
148	}
149}
150
151
152/*!	\brief Adds a new event to the queue.
153
154	The event's time must be set, before adding it. Afterwards ModifyEvent()
155	must be used to change an event's time.
156
157	If the event's time is already passed, it is executed as soon as possible.
158
159	\param event The event to be added.
160	\return \c true, if the event has been added successfully, \c false, if
161			an error occured.
162*/
163bool
164EventQueue::AddEvent(Event *event)
165{
166	Lock();
167	bool result = (event && _AddEvent(event));
168	if (result)
169		_Reschedule();
170	Unlock();
171	return result;
172}
173
174
175/*!	\brief Removes an event from the queue.
176	\param event The event to be removed.
177	\return \c true, if the event has been removed successfully, \c false, if
178			the supplied event wasn't in the queue before.
179*/
180bool
181EventQueue::RemoveEvent(Event *event)
182{
183	bool result = false;
184	Lock();
185	if (event && ((result = _RemoveEvent(event))))
186		_Reschedule();
187	Unlock();
188	return result;
189}
190
191
192/*!	\brief Modifies an event's time.
193
194	The event must be in the queue.
195
196	If the event's new time is already passed, it is executed as soon as
197	possible.
198
199	\param event The event in question.
200	\param newTime The new event time.
201*/
202void
203EventQueue::ModifyEvent(Event *event, bigtime_t newTime)
204{
205	Lock();
206	if (fEvents.RemoveItem(event)) {
207		event->SetTime(newTime);
208		_AddEvent(event);
209		_Reschedule();
210	}
211	Unlock();
212}
213
214
215/*!	\brief Adds an event to the event list.
216
217	\note The object must be locked when this method is invoked.
218
219	\param event The event to be added.
220	\return \c true, if the event has been added successfully, \c false, if
221			an error occured.
222*/
223bool
224EventQueue::_AddEvent(Event *event)
225{
226	int32 index = _FindInsertionIndex(event->Time());
227	return fEvents.AddItem(event, index);
228}
229
230
231/*!	\brief Removes an event from the event list.
232
233	\note The object must be locked when this method is invoked.
234
235	\param event The event to be removed.
236	\return \c true, if the event has been removed successfully, \c false, if
237			the supplied event wasn't in the queue before.
238*/
239bool
240EventQueue::_RemoveEvent(Event *event)
241{
242	int32 index = _IndexOfEvent(event);
243	return (index >= 0 && fEvents.RemoveItem(index));
244}
245
246
247/*!	\brief Returns an event from the event list.
248
249	\note The object must be locked when this method is invoked.
250
251	\param index The list index of the event to be returned.
252	\return The event, or \c NULL, if the index is out of range.
253*/
254Event*
255EventQueue::_EventAt(int32 index) const
256{
257	return (Event*)fEvents.ItemAt(index);
258}
259
260
261/*!	\brief Returns the event list index of the supplied event.
262
263	\note The object must be locked when this method is invoked.
264
265	\param event The event to be found.
266	\return The event list index of the supplied event or \c -1, if the event
267			is not in the event list.
268*/
269int32
270EventQueue::_IndexOfEvent(Event *event) const
271{
272	bigtime_t time = event->Time();
273	int32 index = _FindInsertionIndex(time);
274	// The found index is the index succeeding the one of the last event with
275	// the same time.
276	// search backwards for the event
277	Event *listEvent = NULL;
278	while (((listEvent = _EventAt(--index))) && listEvent->Time() == time) {
279		if (listEvent == event)
280			return index;
281	}
282	return -1;
283}
284
285
286/*!	\brief Finds the event list index at which an event with the supplied
287		   has to be added.
288
289	The returned index is the greatest possible index, that is if there are
290	events with the same time in the list, the index is the successor of the
291	index of the last of these events.
292
293	\note The object must be locked when this method is invoked.
294
295	\param time The event time.
296	\return The index at which an event with the supplied time should be added.
297*/
298int32
299EventQueue::_FindInsertionIndex(bigtime_t time) const
300{
301	// binary search
302	int32 lower = 0;
303	int32 upper = fEvents.CountItems();
304	// invariant: lower-1:time <= time < upper:time (ignoring invalid indices)
305	while (lower < upper) {
306		int32 mid = (lower + upper) / 2;
307		Event* midEvent = _EventAt(mid);
308		if (time < midEvent->Time())
309			upper = mid;		// time < mid:time  =>  time < upper:time
310		else
311			lower = mid + 1;	// mid:time <= time  =>  lower-1:time <= time
312	}
313	return lower;
314}
315
316
317/*!	\brief Entry point from the queue's thread.
318	\param data The queue's \c this pointer.
319	\return The thread's result. Of no relevance in this case.
320*/
321int32
322EventQueue::_EventLooperEntry(void *data)
323{
324	return ((EventQueue*)data)->_EventLooper();
325}
326
327
328/*!	\brief Method with the main loop of the queue's thread.
329	\return The thread's result. Of no relevance in this case.
330*/
331int32
332EventQueue::_EventLooper()
333{
334	bool running = true;
335	while (running) {
336		bigtime_t waitUntil = B_INFINITE_TIMEOUT;
337		if (Lock()) {
338			if (!fEvents.IsEmpty())
339				waitUntil = _EventAt(0)->Time();
340			fNextEventTime = waitUntil;
341			Unlock();
342		}
343		status_t err = acquire_sem_etc(fLooperControl, 1, B_ABSOLUTE_TIMEOUT,
344									   waitUntil);
345		switch (err) {
346			case B_TIMED_OUT:
347				// do events, that are supposed to go off
348				while (!fTerminating && Lock() && !fEvents.IsEmpty()
349					   && system_time() >= _EventAt(0)->Time()) {
350					Event *event = (Event*)fEvents.RemoveItem((int32)0);
351					Unlock();
352					bool autoDeleteEvent = event->IsAutoDelete();
353					bool deleteEvent = event->Do(this) || autoDeleteEvent;
354					if (deleteEvent)
355						delete event;
356				}
357				if (IsLocked())
358					Unlock();
359				break;
360			case B_BAD_SEM_ID:
361				running = false;
362				break;
363			case B_OK:
364			default:
365				break;
366		}
367	}
368	return 0;
369}
370
371
372/*!	\brief To be called, when an event has been added or removed.
373
374	Checks whether the queue's thread has to recalculate the time when it
375	needs to wake up to execute the next event, and signals the thread to
376	do so, if necessary.
377
378	\note The object must be locked when this method is invoked.
379*/
380void
381EventQueue::_Reschedule()
382{
383	if (fStatus == B_OK) {
384		if (!fEvents.IsEmpty() && _EventAt(0)->Time() < fNextEventTime)
385			release_sem(fLooperControl);
386	}
387}
388