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 19 static 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 */ 81 EventQueue::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 */ 114 EventQueue::~EventQueue() 115 { 116 Die(); 117 while (Event *event = (Event*)fEvents.RemoveItem(0L)) { 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 */ 127 status_t 128 EventQueue::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 */ 141 void 142 EventQueue::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 */ 163 bool 164 EventQueue::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 */ 180 bool 181 EventQueue::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 */ 202 void 203 EventQueue::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 */ 223 bool 224 EventQueue::_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 */ 239 bool 240 EventQueue::_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 */ 254 Event* 255 EventQueue::_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 */ 269 int32 270 EventQueue::_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 */ 298 int32 299 EventQueue::_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 */ 321 int32 322 EventQueue::_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 */ 331 int32 332 EventQueue::_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(0L); 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 */ 380 void 381 EventQueue::_Reschedule() 382 { 383 if (fStatus == B_OK) { 384 if (!fEvents.IsEmpty() && _EventAt(0)->Time() < fNextEventTime) 385 release_sem(fLooperControl); 386 } 387 } 388