Component bdlc_indexclerk [Package bdlc]

Provide a manager of reusable, non-negative integer indices. More...

Namespaces
namespace	bdlc

---

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Performance
  • Usage

Purpose:

Provide a manager of reusable, non-negative integer indices.

Classes:

bdlc::IndexClerkIter	sequential accessor to decommissioned indices
bdlc::IndexClerk	manager of reusable, non-negative integer indices

Description:

This component implements an efficient, value-semantic manager class for reusable, non-negative integer indices. Each new instance of a bdlc::IndexClerk will issue consecutive integers on request, beginning with 0, 1, 2, .... Indices that are no longer needed may be returned for reuse. Existing decommissioned indices are reissued before any new ones are created. Value-semantic operations such as copy construction and assignment, equality comparison, and streaming are also provided. Finally, a bdlc::IndexClerkIter is provided to enable sequential, read-only access to the currently decommissioned indices. Note that the order of iteration is not defined.

Performance:

The following characterizes the performance of representative operations using "big-oh" notation, O[f(N,M)], where the names N and M also refer to the number of respective elements in the sequence of decommissioned indices.

     Operation                     Worst Case
     ---------                     ----------
     DEFAULT CTOR                  O[1]
     COPY CTOR(N)                  O[N]
     N.DTOR()                      O[1]
     N.OP=(M)                      O[M]
     OP==(N,M)                     O[min(N,M)]

     N.getIndex()                  O[1]
     N.putIndex(index)             O[1]
     N.removeAll()                 O[1]
     N.numCommissionedIndices()    O[1]
     N.numDecommissionedIndices()  O[1]
     N.nextNewIndex()              O[1]
     N.isInUse(index)              O[N]

Usage:

A bdlc::IndexClerk is commonly used in conjunction with an array to enable machine-address-independent referencing. Rather than dynamically allocating an object and holding its address, the object is stored in the array at the next position dispensed by its associated bdlc::IndexClerk, and that index becomes an identifier (Id) for the new object. Instead of destroying an unneeded object, its Id is merely returned to the clerk.

Care must be taken to ensure that objects "created" at reused indices (i.e., indices below the current length of the array) replace (the value of) an existing object in the array while objects created at new indices (i.e., indices at the current length) are appended to the array.

For example, suppose we have a security class object. To add and remove security values from a security array/clerk pair, you might write the following two functions:

  int addSecurity(bsl::vector<Security> *securityArray,
                  bdlc::IndexClerk      *securityClerk,
                  const Security&        newSecurity)
      // Add a copy of the specified 'newSecurity' to the specified
      // 'securityArray' at the index dispensed by the specified
      // 'securityClerk'.  Also update the 'securityClerk', and return the id
      // (in 'securityArray') for the newly added security.
  {
      BSLS_ASSERT(securityArray);
      BSLS_ASSERT(securityClerk);

      int id = securityClerk->getIndex();

      if (id < securityArray->size()) {
          (*securityArray)[id] = newSecurity;
      }
      else {
          securityArray->push_back(newSecurity);
      }

      return id;
  }

  void removeSecurity(bsl::vector<Security> *securityArray,
                      bdlc::IndexClerk      *securityClerk,
                      int                    securityId)
      // Remove the security object identified by the specified 'securityId'
      // from the specified 'securityArray', and update the specified
      // 'securityClerk' (making 'securityId' available for reuse).  The
      // behavior is undefined unless 'securityId' refers to an active
      // security in 'securityArray' dispensed by 'securityClerk'.
  {
      BSLS_ASSERT(securityArray);
      BSLS_ASSERT(securityClerk);

      BSLS_ASSERT(0                             <= securityId);
      BSLS_ASSERT(securityClerk->nextNewIndex() >  securityId);
      BSLS_ASSERT(securityArray->size()         >  securityId);

      // Note that the 'isInUse' function (below) runs in linear time.

      BSLS_ASSERT_SAFE(securityClerk->isInUse(securityId));

      (*securityArray)[securityId] = Security();  // optional
      securityClerk->putIndex(securityId);
  }