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