bdlcc_skiplist

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Template Requirements
  • Glossary
  • "R" Methods: Optimized Search From The Back Of The List
  • Referring to Elements in the Container
  • Thread Safety
  • Exception Safety
  • Usage
    • Example 1: Creating a Scheduler

Purpose

Provide a generic thread-safe Skip List.

Classes

• bdlcc::SkipList: generic thread-aware ordered map
• bdlcc::SkipListPair: type for opaque pointers
• bdlcc::SkipListPairHandle: scope mechanism for safe item references

See also

Description

This component provides a thread-safe value-semantic associative Skip List container. A Skip List stores objects of a parameterized DATA type, ordered by values of a parameterized KEY type. DATA objects can be added, looked up, and removed quickly on the basis of their KEY value. In addition, bdlcc::SkipList provides methods to change the KEY value associated with an object in the list such that it is efficiently moved to an appropriate location within the list for the new KEY value.

Associations (pairings of data objects with key values) in the list are identified by bdlcc::SkipListPairHandle objects or bdlcc::SkipListPair pointers. bdlcc::SkipListPair pointers must be used with caution: See the "`bdlcc::SkipListPair` Usage Rules" below. bdlcc::SkipListPair and bdlcc::SkipListPairHandle objects are optionally populated when new associations are added, and are also populated whenever associations are looked up (either by key or by position). Note that in addition to addPairReferenceRaw, member functions of bdlcc::SkipList such as front, back, and find also add a reference to the specified element.

Template Requirements

The bdlcc::SkipList ordered associative container is parameterized on two types, KEY and DATA. Each type must have a public copy constructor, and it is important to declare the "Uses bslma Allocator" trait if the type accepts a bslma::Allocator in its constructor (see bslalg_typetraits ). In addition, operators =, <, and == must be defined for the type KEY; for correct behavior, operator < must define a Strict Weak Ordering on KEY values.

Glossary

Some terms used frequently in this documentation:

• Back

  ‍ The last element in the list. The key value at the back is greater than or equal to every other key value in the list.

• Front

  ‍ The beginning of the list. The key value at the front is less than or equal to every other key value in the list.

• Pair

  ‍ An element of the list; a pairing (association) of a data object with a key value. Also a type name used for references to such objects (bdlcc::SkipListPair objects cannot be constructed directly).

• PairHandle

  ‍ An object (of type bdlcc::SkipListPairHandle) with scope and copy semantics that makes it easier to manage and use than a raw bdlcc::SkipListPair *.

• R

  ‍ Stands for "Reverse search" (see "R" Methods documentation below).

• Reference

  ‍ An object referring to a pair; either a bdlcc::SkipListPair * which has not yet been released, or a bdlcc::SkipListPairHandle object.

"R" Methods: Optimized Search From The Back Of The List

The regular methods (no R suffix) of bdlcc::SkipList that result in a search through the list, search from the front of the list (i.e., in ascending order).

All methods of bdlcc::SkipList that result in a search through the list have corresponding "R" versions: for example, there are add and addR methods, find and findR methods, etc. The "R" versions of these methods search from the back of the list (i.e., in descending (reverse) order). Use of an "R" method is a hint to the Skip List that the desired key is more likely to be near the back than the front. In the event of duplicate keys, find will find the first matching key, and findR will find the last matching key. Note that if there are pairs in the list with duplicate keys, the specific pair found by find may (or may not) be different from the one found by findR.

Referring to Elements in the Container

bdlcc::SkipList has two handle types for referring to elements in the container:

• bdlcc::SkipList::Pair * – raw pointer, no destructor, bdlcc::SkipList::releaseReferenceRaw must be called on these pointers before the container is destroyed.
• bdlcc::SkipList::PairHandle – class, has a destructor which will release the pair handle when it goes out of scope via RAII. If the pair handle will not be destroyed before the container is, it is necessary to call bdlcc::SkipList::PairHandle::release before the container is destroyed.

The PairHandle type has an implicit conversion to Pair *. In most cases bdlcc::SkipList provides dual functions supporting Pair * and PairHandle. Some functions, however, only support Pair * parameters; for these functions, either a Pair * or a PairHandle may be passed.

Unless the client has some reason to prefer the Pair * interface, the PairHandle interface is recommended since it provides RAII, making it harder to leak nodes.

Note that in some build modes, SkipList will attempt to detect leaked nodes, i.e., those that were referred to by Pair *s for which releaseReferenceRaw hasn't been called, and nodes referred to by PairHandles that haven't been destroyed or released at the time of the skip list's destruction.

Thread Safety

bdlcc::SkipList is thread-safe and thread-aware; that is, multiple threads may use their own Skip List objects or may concurrently use the same object.

Note that safe usage of the component depends upon correct usage of bdlcc::SkipListPair objects (see above).

bdlcc::SkipListPairHandle is only const thread-safe. It is not safe for multiple threads to invoke non-const methods on the same PairHandle object concurrently.

bdlcc::SkipListPair is a name used for opaque pointers; the concept of thread safety does not apply to it.

Exception Safety

bdlcc::SkipList is exception-neutral: no method invokes throw or catch. Insertion methods (add, addR, etc) invoke the copy constructors of the contained KEY and DATA types; if those constructors throw an exception, the list provides a full rollback guarantee (it will have the same state it had prior to the call to add). The assignment operator may also indirectly cause bad_alloc to be thrown if the system is out of memory, but in that case there is no guarantee of rollback on the left-hand list.

No method of bdlcc::SkipListPairHandle can throw.

bdlcc::SkipListPair is only a name used for opaque pointers; the concept of exception safety does not apply to it.

Usage

This section illustrates intended use of this component.

Example 1: Creating a Scheduler

The "R" methods of bdlcc::SkipList make it ideal for use in a scheduler, in which events are likely to be scheduled after existing events. In such an implementation, events are stored in the list with their scheduled execution times as KEY objects: Searching near the end of the list for the right location for new events, and removing events from the front of the list for execution, are very efficient operations. Being thread- enabled also makes bdlcc::SkipList well-suited to use in a scheduler - a "dispatcher" thread can safety use the list at the same time that events are being scheduled from other threads. The following is an implementation of a simple scheduler class using bdlcc::SkipList. Note that the mutex in the scheduler is used only in connection with the scheduler's condition variable

• thread-safe access to the bdlcc::SkipList object does not require any synchronization.

  class SimpleScheduler
  {
      // TYPES
      typedef bdlcc::SkipList<bdlt::Datetime, bsl::function<void()> > List;
   
      // DATA
      List                       d_list;
      bslmt::ThreadUtil::Handle  d_dispatcher;
      bslmt::Condition           d_notEmptyCond;
      bslmt::Condition           d_emptyCond;
      bslmt::Barrier             d_startBarrier;
      bslmt::Mutex               d_condMutex;
      bsls::AtomicInt            d_doneFlag;
   
    private:
      // NOT IMPLEMENTED
      SimpleScheduler(const SimpleScheduler&);
   
    private:
      // PRIVATE MANIPULATORS
   
      /// Run a thread that executes functions off `d_list`.
      void dispatcherThread()
      {
          d_startBarrier.wait();
   
          while (!d_doneFlag) {
              List::PairHandle firstItem;
              if (0 == d_list.front(&firstItem)) {
                  // The list is not empty.
   
                  bsls::TimeInterval when =
                      bdlt::IntervalConversionUtil::convertToTimeInterval(
                                 firstItem.key() - bdlt::CurrentTime::utc());
                  if (when.totalSecondsAsDouble() <= 0) {
                      // Execute now and remove from schedule, then iterate.
   
                      d_list.remove(firstItem);
                      firstItem.data()();
   
                      List::PairHandle tmpItem;
   
                      bslmt::LockGuard<bslmt::Mutex> guard(&d_condMutex);
   
                      if (0 == d_list.length()) {
                          d_emptyCond.broadcast();
                      }
                  }
                  else {
                      // Wait until the first scheduled item is due.
   
                      bslmt::LockGuard<bslmt::Mutex> guard(&d_condMutex);
                      List::PairHandle newFirst;
                      if (!d_doneFlag && (0 != d_list.front(&newFirst) ||
                                        newFirst.key() == firstItem.key())) {
                          d_notEmptyCond.timedWait(&d_condMutex,
                                            bdlt::CurrentTime::now() + when);
                      }
                  }
              }
              else {
                  // The list is empty; wait on the condition variable.
   
                  bslmt::LockGuard<bslmt::Mutex> guard(&d_condMutex);
                  if (d_list.isEmpty() && !d_doneFlag) {
                      d_notEmptyCond.wait(&d_condMutex);
                  }
              }
          }
      }
   
    public:
      // CREATORS
      explicit
      SimpleScheduler(bslma::Allocator *basicAllocator = 0)
      : d_list(basicAllocator)
      , d_startBarrier(2)
      , d_doneFlag(false)
          // Creator.
      {
          int rc = bslmt::ThreadUtil::create(
                  &d_dispatcher,
                  bdlf::BindUtil::bind(&SimpleScheduler::dispatcherThread,
                                          this));
          BSLS_ASSERT(0 == rc);  (void)rc;
          d_startBarrier.wait();
      }
   
      ~SimpleScheduler()
          // d'tor
      {
          stop();
      }
   
      // MANIPULATORS
   
      /// Block until the scheduler has no jobs.
      void drain()
      {
          bslmt::LockGuard<bslmt::Mutex> guard(&d_condMutex);
   
          while (!d_doneFlag && 0 != d_list.length()) {
              d_emptyCond.wait(&d_condMutex);
          }
      }
   
      /// Schedule the specified `event` to occur at the specified `when`.
      void scheduleEvent(const bsl::function<void()>& event,
                         const bdlt::Datetime&        when)
      {
          // Use `addR` since this event will probably be placed near the end
          // of the list.
   
          bool newFrontFlag;
          d_list.addR(when, event, &newFrontFlag);
          if (newFrontFlag) {
              // This event is scheduled before all other events.  Wake up
              // the dispatcher thread.
   
              d_notEmptyCond.signal();
          }
      }
   
      /// Stop the scheduler.
      void stop()
      {
          bslmt::LockGuard<bslmt::Mutex> guard(&d_condMutex);
   
          d_list.removeAll();
   
          d_doneFlag = true;
          d_notEmptyCond.signal();
          d_emptyCond.broadcast();
   
          if (bslmt::ThreadUtil::invalidHandle() != d_dispatcher) {
              bslmt::ThreadUtil::Handle dispatcher = d_dispatcher;
              {
                  bslmt::LockGuardUnlock<bslmt::Mutex> g(&d_condMutex);
                  bslmt::ThreadUtil::join(dispatcher);
              }
              d_dispatcher = bslmt::ThreadUtil::invalidHandle();
          }
      }
  };

  We can verify the correct behavior of SimpleScheduler. First, we need a wrapper around vector<int>::push_back, since this function is overloaded and cannot be bound directly:

  /// Push the specified `item` onto the specified `vector`.
  void pushBackWrapper(bsl::vector<int> *vector, int item)
  {
      vector->push_back(item);
  }

  Now, in main, verify that the scheduler executes events when expected:

  SimpleScheduler      scheduler;
   
  bsl::vector<int>     values;
   
  const bdlt::Datetime start = bdlt::CurrentTime::utc();
  bdlt::Datetime       scheduleTime;

  Add events out of sequence and ensure they are executed in the proper order.

  scheduleTime = start;
  scheduleTime.addMilliseconds(2250);
  scheduler.scheduleEvent(bdlf::BindUtil::bind(&pushBackWrapper, &values, 2),
                          scheduleTime);
   
  scheduleTime = start;
  scheduleTime.addMilliseconds(750);
  scheduler.scheduleEvent(bdlf::BindUtil::bind(&pushBackWrapper, &values, 0),
                          scheduleTime);
   
  scheduleTime = start;
  scheduleTime.addMilliseconds(1500);
  scheduler.scheduleEvent(bdlf::BindUtil::bind(&pushBackWrapper, &values, 1),
                          scheduleTime);
   
  assert(values.empty());
   
  scheduler.drain();
   
  bdlt::Datetime finish = bdlt::CurrentTime::utc();
   
  assert(3 == values.size());
  assert(0 == values[0]);
  assert(1 == values[1]);
  assert(2 == values[2]);
   
  const double elapsed = bdlt::IntervalConversionUtil::convertToTimeInterval(
                                      finish - start).totalSecondsAsDouble();
   
  assert(2.25 <= elapsed);
  assert(elapsed < 2.75);

  Note that the destructor of scheduler will call stop().