Component bslstl_function [Package bslstl]

Provide a polymorphic function object with a specific prototype. More...

Outline

• Purpose
• Classes
• Description
  • Invocation
  • Allocator Usage
  • Small-object Optimization
  • Usage
    • Example 1: Polymorphic Invocation
    • Example 2: Use in Generic a Algorithm
    • Example 3: A Parallel Work queue

Purpose:

Provide a polymorphic function object with a specific prototype.

Classes:

bsl::function

polymorphic function object with a specific prototype.

Canonical Header:

bsl_functional.h

Description:

This component provides a single class template, bsl::function, implementing the standard template std::function, a runtime-polymorphic wrapper that encapsulates an arbitrary callable object (the target) and allows the wrapped object to be invoked. bsl::function extends std::function by adding allocator support in a manner consistent with standards proposal P0987 (http://wg21.link/P0987).

Objects of type bsl::function generalize the notion of function pointers and are generally used to pass callbacks to a non-template function or class. For example, bsl::function<RET (ARG1, ARG2, ...)> can be used similarly to RET (*)(ARG1, ARG2, ...) but, unlike the function pointer, the bsl::function can hold a non-function callable type such as pointer to member function, pointer to member data, lambda expression, or functor (class type having an operator()). A bsl::function can also be "empty", i.e., having no target object. In a bool context, a bsl::function object will evaluate to false if it is empty, and true otherwise. The target type is determined at runtime using type erasure in the constructors and can be changed by means of assignment, but the function prototype (argument types and return type) is specified as a template parameter at compile time.

An instantiation of bsl::function is an in-core value-semantic type whose salient attributes are the type and value of its target, if any. The bsl::function owns the target object and manages its lifetime; copying or moving the bsl::function object copies or moves the target and destroying the bsl::function destroys the target. Somewhat counter-intuitively, the target is always mutable within the bsl::function; when wrapping a class type, calling a bsl::function can modify its target object, even if the bsl::function itself is const-qualified.

Although, as a value-semantic type, bsl::function does have an abstract notion of "value", there is no general equality operator comparing between two bsl::function objects. This limitation is a consequence of the target type not being required to provide equality comparison operators. The operator== overloads that are provided compare a bsl::function against the null pointer and do not satisfy the requirements we typically expect for value-semantic equality operators.

Invocation:

Calling an empty bsl::function object will cause it to throw a bsl::bad_function_call exception. Given a non-empty object of type bsl::function<RET(ARG0, ARG1, ...)> invoked with arguments arg0, arg1, ..., invocation of the target follows the definition of INVOKE in section [func.require] of the C++ standard. These rules are summarized in the following table:

  +----------------------------+-----------------------+
  | Type of target object, 'f' | Invocation expression |
  +============================+=======================+
  | Functor, function, or      | f(arg0, arg1, ...)    |
  | pointer to function        |                       |
  +----------------------------+-----------------------+
  | Pointer to member function | (arg0X.*f)(arg1, ...) |
  +----------------------------+-----------------------+
  | Pointer to member data     | arg0X.*f              |
  +----------------------------+-----------------------+

The arguments to f must be implicitly convertible from the corresponding argument types ARG0, ARG1, ... and the return value of the call expression must be implicitly convertible to RET, unless RET is void.

In the case of a pointer to member function, R (T::*f)(...), or pointer to data member R T::*f, arg0X is one of the following:

• arg0 if ARG0 is T or derived from T
• arg0.get() if ARG0 is a specialization of reference_wrapper
• (*arg0) if ARG0 is a pointer type or pointer-like type (e.g., a smart pointer).

Note that, consistent with the C++ Standard definition of INVOKE, we consider pointer-to-member-function and pointer-to-member-data types to be "callable" even though, strictly speaking, they cannot be called directly due to the lack of an operator().

Allocator Usage:

The C++11 standard specified a type erasure scheme for allocator support in std::function. This specification was never implemented by any vendor or popular open-source standard library and allocator support was removed from the 2017 standard version of std::function. A new design for allocator support using std::pmr::polymorphic_allocator instead of type erasure is currently part of version 3 of the Library Fundamentals Technical Specification (LFTS 3), after acceptance of paper P0987 (http://wg21.link/P0987). This component follows the P0987 specification, substituting bsl::allocator for std::pmr::polymorphic_allocator.

bsl::function meets the requirements for an allocator-aware type. Specifically:

• The type allocator_type is an alias for bsl::allocator<char>,
• Every constructor can be invoked with an allocator argument, using the bsl::allocator_arg_t leading-allocator argument convention.
• get_allocator() returns the allocator specified at construction.

There are two uses for the allocator in bsl::function:

1. To allocate storage for holding the target object.
2. To pass to the constructor of the wrapped object if the wrapped object is allocator aware.

Small-object Optimization:

A bsl::function class has a buffer capable of holding a small callable object without allocating dynamic memory. The buffer is guaranteed to be large enough to hold a pointer to function, pointer to member function, pointer to member data, a bsl::reference_wrapper, or a stateless functor. In practice, it is large enough to hold many stateful functors up to six times the size of a void *. Note that, even if the target object is stored in the small object buffer, memory might still be allocated by the target object itself.

There are only two circumstances under which bsl::function will store the target object in allocated memory:

1. If the object is too large to fit into the small object buffer
2. If the object has a move constructor that might throw an exception

The second restriction allows the move constructor and swap operation on bsl::function to be noexcept, as required by the C++ Standard.

Usage:

In this section we show intended use of this component.

Example 1: Polymorphic Invocation:

In this example, we create a single bsl::function object, then assign it to callable objects of different types at run time.

First, we define a simple function that returns the XOR of its two integer arguments:

  int intXor(int a, int b) { return a ^ b; }

Next, we create a bsl::function that takes two integers and returns an integer. Because we have not initialized the object with a target, it starts out as empty and evaluates to false in a Boolean context:

  void main()
  {
      bsl::function<int(int, int)> funcObject;
      assert(! funcObject);

Next, we use assignment to give it the value of (a pointer to) intXor and test that we can invoke it to get the expected result:

      funcObject = intXor;
      assert(funcObject);
      assert(5 == funcObject(6, 3));

Next, we assign an instance of std::plus<int> functor to funcObject, which then holds a copy of it, and again test that we get the expected result when we invoke funcObject.

      funcObject = std::plus<int>();
      assert(funcObject);
      assert(9 == funcObject(6, 3));

Then, if we are using C++11 or later, we assign it to a lambda expression that multiplies its arguments:

    #if BSLS_COMPILERFEATURES_CPLUSPLUS >= 201103L
      funcObject = [](int a, int b) { return a * b; };
      assert(funcObject);
      assert(18 == funcObject(6, 3));
    #endif

Finally, we assign funcObject to nullptr, which makes it empty again:

      funcObject = bsl::nullptr_t();
      assert(! funcObject);
  }

Example 2: Use in Generic a Algorithm:

Suppose we want to define an algorithm that performs a mutating operation on every element of an array of integers. The inputs are pointers to the first and last element to transform, a pointer to the first element into which the to write the output, and an operation that takes an integer in and produces an integer return value. Although the pointer arguments have known type (int *), the type of the transformation operation can be anything that can be called with an integral argument and produces an integral return value. We do not want to accept this operation as a template argument, however (perhaps because our algorithm is sufficiently complex and/or proprietary that we want to keep it out of header files). We solve these disparate requirements by passing the operation as a bsl::function object, whose type is known at compile time but which can be set to an arbitrary operation at run time:

  void myAlgorithm(const int                      *begin,
                   const int                      *end,
                   int                            *output,
                   const bsl::function<int(int)>&  op);
      // Apply my special algorithm to the elements in the contiguous address
      // range from the specified 'begin' pointer up to but not including the
      // specified 'end' pointer, writing the result to the contiguous range
      // starting at the specified 'output' pointer.  The specified 'op'
      // function is applied to each element before it is fed into the
      // algorithm.

For the purpose of illustration, myAlgorithm is a simple loop that invokes the specified op on each element in the input range and writes it directly to the output:

  void myAlgorithm(const int                      *begin,
                   const int                      *end,
                   int                            *output,
                   const bsl::function<int(int)>&  op)
  {
      for (; begin != end; ++begin) {
          *output++ = op(*begin);
      }
  }

Next, we define input and output arrays to be used throughout the rest of this example:

  static const std::size_t DATA_SIZE = 5;
  static const int         testInput[DATA_SIZE] = { 4, 3, -2, 9, -7 };
  static int               testOutput[DATA_SIZE];

Next, we define a function that simply negates its argument:

  long negate(long v) { return -v; }
      // Return the arithmetic negation of the specified 'v' integer.

Then, we test our algorithm using our negation function:

  bool testNegation()
      // Test the use of the 'negation' function with 'myAlgorithm'.
  {
      myAlgorithm(testInput, testInput + DATA_SIZE, testOutput, negate);

      for (std::size_t i = 0; i < DATA_SIZE; ++i) {
          if (-testInput[i] != testOutput[i]) {
              return false;                                         // RETURN
          }
      }
      return true;
  }

Note that the prototype for negate is not identical to the prototype used to instantiate the op argument in myAlgorithm. All that is required is that each argument to op be convertible to the corresponding argument in the function and that the return type of the function be convertible to the return type of op.

Next, we get a bit more sophisticated and define an operation that produces a running sum over its inputs. A running sum requires holding on to state, so we define a functor class for this purpose:

  class RunningSum {
      // Keep a running total of all of the inputs provided to 'operator()'.

      // DATA
      int d_sum;

    public:
      // CREATORS
      explicit RunningSum(int initial = 0) : d_sum(initial) { }
          // Create a 'RunningSum' with initial value set to the specified
          // 'initial' argument.

      // MANIPULATORS
      int operator()(int v)
          // Add the specified 'v' to the running sum and return the running
          // sum.
          { return d_sum += v; }
  };

Then, we test myAlgorithm with RunningSum:

  bool testRunningSum()
      // Test the user of 'RunningSum' with 'myAlgorithm'.
  {
      myAlgorithm(testInput, testInput+DATA_SIZE, testOutput, RunningSum());

      int sum = 0;
      for (std::size_t i = 0; i < DATA_SIZE; ++i) {
          sum += testInput[i];
          if (sum != testOutput[i]) {
              return false;                                         // RETURN
          }
      }
      return true;
  }

Note that RunningSum::operator() is a mutating operation and that, within myAlgorithm, op is const. Even though bsl::function owns a copy of its target, logical constness does not apply, as per the standard.

Finally, we run our tests and validate the results:

  void main()
  {
      assert(testNegation());
      assert(testRunningSum());
  }

Example 3: A Parallel Work queue:

In this example, we'll simulate a simple library whereby worker threads take work items from a queue and execute them asynchronously. This simulation is single-threaded, but keeps metrics on how much work each worker accomplished so that we can get a rough idea of how much parallelism was expressed by the program.

We start by defining a work item type to be stored in our work queue. This type is simply a bsl::function taking a WorkQueue pointer argument and returning void.

  class WorkQueue;  // Forward declaration

  typedef bsl::function<void(WorkQueue *)> WorkItem;

Next, we define a work queue class. For simplicity, we'll implement our queue as a fixed-sized circular buffer and (because this is a single-threaded simulation), ignore synchronization concerns.

  class WorkQueue {
      // A FIFO queue of tasks to be executed.

      // PRIVATE CONSTANTS
      static const int k_MAX_ITEMS = 16;

      // DATA
      int      d_numItems;
      int      d_head;
      WorkItem d_items[k_MAX_ITEMS];

    public:
      // CREATORS
      WorkQueue()
          // Create an empty work queue.
          : d_numItems(0), d_head(0) { }

      // MANIPULATORS
      void dequeue(WorkItem *result)
          // Move the work item at the head of the queue into the specified
          // 'result' and remove it from the queue.  The behavior is
          // undefined if this queue is empty.
      {
          assert(d_numItems > 0);
          *result = bslmf::MovableRefUtil::move(d_items[d_head]);
          d_head = (d_head + 1) % k_MAX_ITEMS;  // circular
          --d_numItems;
      }

      void enqueue(bslmf::MovableRef<WorkItem> item)
          // Enqueue the specified 'item' work item onto the tail of the
          // queue.  The work is moved from 'item'.
      {
          int tail = (d_head + d_numItems++) % k_MAX_ITEMS; // circular
          assert(d_numItems <= k_MAX_ITEMS);
          d_items[tail] = bslmf::MovableRefUtil::move(item);
      }

      // ACCESSORS
      bool isEmpty() const
          // Return true if there are no items in the queue; otherwise return
          // false.
          { return 0 == d_numItems; }

      int size() const
          // Return the number of items currently in the queue.
          { return d_numItems; }
  };

Next, we'll create a worker class that represents the state of a worker thread:

  class Worker {
      // A simulated worker thread.

      // DATA
      bool d_isIdle;             // True if the worker is idle

    public:
      // CREATORS
      Worker()
          // Create an idle worker.
          : d_isIdle(true) { }

      // MANIPULATORS
      void run(WorkQueue *queue);
          // Dequeue a task from the specified 'queue' and execute it
          // (asynchronously, in theory).  The behavior is undefined unless
          // this worker is idle before the call to 'run'.

      // ACCESSORS
      bool isIdle() const
          // Return whether this worker is idle.  An idle worker is one that
          // can except work.
          { return d_isIdle; }
  };

Next, we implement the run function, which removes a bsl::function object from the work queue and then executes it, passing the work queue as the sole argument:

  void Worker::run(WorkQueue *queue)
  {
      if (queue->isEmpty()) {
          // No work to do
          return;                                                   // RETURN
      }

      WorkItem task;
      queue->dequeue(&task);

      d_isIdle = false;  // We're about to do work.
      task(queue);       // Do the work.
      d_isIdle = true;   // We're idle again.
  }

Now, we implement a simple scheduler containing a work queue and an array of four workers, which are run in a round-robin fashion:

  class Scheduler {
      // Parallel work scheduler.

      // PRIVATE CONSTANTS
      static const int k_NUM_WORKERS = 4;

      // DATA
      WorkQueue d_workQueue;
      Worker    d_workers[k_NUM_WORKERS];

    public:
      // CREATORS
      explicit Scheduler(bslmf::MovableRef<WorkItem> initialTask)
          // Create a scheduler and enqueue the specified 'initialTask'.
      {
          d_workQueue.enqueue(bslmf::MovableRefUtil::move(initialTask));
      }

      // MANIPULATORS
      void run();
          // Execute the tasks in the work queue (theoretically in parallel)
          // until the queue is empty.
  };

Next, we implement the scheduler's run method: which does a round-robin scheduling of the workers, allowing each to pull work off of the queue and run it. As tasks are run, they may enqueue more work. The scheduler returns when there are no more tasks in the queue.

  void Scheduler::run()
  {
      while (! d_workQueue.isEmpty()) {
          for (int i = 0; i < k_NUM_WORKERS; ++i) {
              if (d_workers[i].isIdle()) {
                  d_workers[i].run(&d_workQueue);
              }
          }
      }
  }

Next, we create a job for the parallel system to execute. A popular illustration of parallel execution is the quicksort algorithm, which is a recursive algorithm whereby the input array is partitioned into a low and high half and quicksort is recursively applied, in parallel, to the two halves. We define a class that encapsulates an invocation of quicksort on an input range:

  template <class TYPE>
  class QuickSortTask {
      // A functor class to execute parallel quicksort on a contiguous range
      // of elements of specified 'TYPE' supplied at construction.

      // DATA
      TYPE *d_begin_p;
      TYPE *d_end_p;

      // PRIVATE CLASS METHODS
      static TYPE* partition(TYPE *begin, TYPE *end);
          // Partition the contiguous range specified by '[begin, end)' and
          // return an iterator, 'mid', such that every element in the range
          // '[begin, mid)' is less than '*mid' and every element in the
          // range '[mid + 1, end)' is not less than '*mid'.  The behavior is
          // undefined unless 'begin < end'.

    public:
      // CREATORS
      QuickSortTask(TYPE *begin, TYPE *end)
          // Create a task to sort the contiguous range from the item at the
          // specified 'begin' location up to but not included the item at
          // the specified 'end' location.
          : d_begin_p(begin), d_end_p(end) { }

      // MANIPULATORS
      void operator()(WorkQueue *queue);
          // Preform the sort in parallel using the specified 'queue' to
          // enqueue parallel work.
  };

Next we implement the partition method, using a variation of the Lomuto partition scheme:

  template <class TYPE>
  TYPE* QuickSortTask<TYPE>::partition(TYPE *begin, TYPE *end)
  {
      using std::swap;

      swap(begin[(end - begin) / 2], end[-1]); // Put pivot at end
      TYPE& pivot = *--end;
      TYPE *divider = begin;
      for (; begin != end; ++begin) {
          if (*begin < pivot) {
              swap(*divider, *begin);
              ++divider;
          }
      }
      swap(*divider, pivot);  // Put pivot in the middle
      return divider;
  }

Then we define the call operator for our task type, which performs the quicksort:

  template <class TYPE>
  void QuickSortTask<TYPE>::operator()(WorkQueue *queue)
  {
      if (d_end_p - d_begin_p < 2) {
          // Zero or one element. End recursion.
          return;                                                   // RETURN
      }

      // Partition returns end iterator for low partition == begin iterator
      // for high partition.
      TYPE *mid = partition(d_begin_p, d_end_p);

      // Asynchronously sort the two partitions
      WorkItem sortLoPart(QuickSortTask(d_begin_p, mid));
      WorkItem sortHiPart(QuickSortTask(mid + 1, d_end_p));
      queue->enqueue(bslmf::MovableRefUtil::move(sortLoPart));
      queue->enqueue(bslmf::MovableRefUtil::move(sortHiPart));
  }

Finally, we use our scheduler and our QuickSortTask to sort an array initially containing the integers between 1 and 31 in random order:

  void main()
  {
      short data[] = {
          23, 12, 2, 28, 1, 10, 5, 13, 15, 8, 19, 14, 31, 29, 9, 11, 24, 3,
          30, 7, 17, 27, 20, 21, 18, 4, 22, 25, 16, 6, 26
      };

      static const int DATA_SIZE = sizeof(data) / sizeof(data[0]);

      WorkItem  initialTask(QuickSortTask<short>(data, data + DATA_SIZE));
      Scheduler sched(bslmf::MovableRefUtil::move(initialTask));
      sched.run();

      // Validate results
      for (int i = 0; i < DATA_SIZE; ++i) {
          assert(i + 1 == data[i]);
      }
  }