7.12.10

The Beauty of Qt 3: Implicit Sharing

To maximize resource usage and minimize copying, Qt uses implicit data sharing in many classes, so that the data is copied only when a function writes to it. This trick is also referred to as flyweight pattern sometimes.

Now let's take QByteArray as an example to see how it's implemented. It uses a private struct of Data to track the shared data:
struct Data {
  QBasicAtomicInt ref; // reference count, the operation on it is atomic
  int alloc; // allocated space for the data
  int size; // actual size of the data, not counting the ending '\0' added by QByteArray
  char *data; // point to the data
  char array[1]; // where the data is stored, and the data always end with '\0'
};


Here, we use both the pointer of data and array just because the data might actually be stored in another object. When an object is copied, e.g. through the assignment operator, it only copies the pointer to the shared data:
QByteArray &QByteArray::operator=(const QByteArray & other)
{
  // increase the reference count of the shared data it's supposed to be used
  other.d->ref.ref();

  // decrease the reference count of the share data currently used, and free it if no one else is using
  if (!d->ref.deref())
    qFree(d);

  // point to the shared data
  d = other.d;

  return *this;
}


On the other hand, if it's to be changed by e.g. the resize() function, it copies the data if any other object also shares it:
void QByteArray::resize(int size)
{
  if (size <= 0) {
    // if the target is no bigger than 0, points to an empty data block
    Data *x = &shared_empty;
    x->ref.ref();
    if (!d->ref.deref())
      qFree(d);
    d = x;
  } else if (d == &shared_null) {
    // if currently a null array, just create a new data block
    Data *x = static_cast<data *>(qMalloc(sizeof(Data)+size));
    Q_CHECK_PTR(x);
    x->ref = 1;
    x->alloc = x->size = size;
    x->data = x->array;
    x->array[size] = '\0';
    (void) d->ref.deref();
    d = x;
  } else {
    // if any other object uses this data block, or the current memory is too small or too big
    // reallocate space, and copy the data for it
    // note that this operation might consume some time if the data is huge
    if (d->ref != 1 || size > d->alloc || (size < d->size && size < d->alloc >> 1))
      realloc(qAllocMore(size, sizeof(Data)));
    if (d->alloc >= size) {
      d->size = size;
      if (d->data == d->array) {
        d->array[size] = '\0';
      }
    }
  }
}


With this in mind, let's see how to use QSharedData and QSharedDataPointer to implement our own implicit shared data objects.
// first implement your data object inheriting from QSharedData, which provides the reference count
class SharedData: public QSharedData
{
public:
  SharedData()
    : QSharedData()
    , var(0)
  {}

  SharedData(const SharedData &other)
    : QSharedData(other)
    , var(other.var)
  {}

  int var;
};

// then the data owner
class DataOwner
{
public:
  DataOwner()
  : d(new SharedData)
  {}

  DataOwner(int var)
  : d(new SharedData)
  {
    // for write access, the -> operator will automatically copy the shared data if needed
    d->var = var;
  }

private:
  // this template class hides all the details for implicit sharing
  // therefore, no need to provide copy constructor or assignment operator
  QSharedDataPointer<SharedData> d;
};


Quite simple, right ;) Then just proceed to implement explicit shared data objects using QExplicitlySharedDataPointer yourself.

No comments:

Post a Comment