src/servers/registrar/EventQueue.cpp

   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((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 */
 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((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 */
 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 }