modules/core/src/binary_queue.cpp

   1 /*
   2  * Copyright (c) 2011 Samsung Electronics Co., Ltd All Rights Reserved
   3  *
   4  *    Licensed under the Apache License, Version 2.0 (the "License");
   5  *    you may not use this file except in compliance with the License.
   6  *    You may obtain a copy of the License at
   7  *
   8  *        http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  *    Unless required by applicable law or agreed to in writing, software
  11  *    distributed under the License is distributed on an "AS IS" BASIS,
  12  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  *    See the License for the specific language governing permissions and
  14  *    limitations under the License.
  15  */
  16 /*
  17  * @file        binary_queue.cpp
  18  * @author      Przemyslaw Dobrowolski (p.dobrowolsk@samsung.com)
  19  * @version     1.0
  20  * @brief       This file is the implementation file of binary queue
  21  */
  22 #include <dpl/binary_queue.h>
  23 #include <dpl/assert.h>
  24 #include <dpl/scoped_free.h>
  25 #include <algorithm>
  26 #include <malloc.h>
  27 #include <cstring>
  28 #include <new>
  29
  30 namespace DPL
  31 {
  32 BinaryQueue::BinaryQueue()
  33     : m_size(0)
  34 {
  35 }
  36
  37 BinaryQueue::BinaryQueue(const BinaryQueue &other)
  38     : m_size(0)
  39 {
  40     AppendCopyFrom(other);
  41 }
  42
  43 BinaryQueue::~BinaryQueue()
  44 {
  45     // Remove all remainig buckets
  46     Clear();
  47 }
  48
  49 const BinaryQueue &BinaryQueue::operator=(const BinaryQueue &other)
  50 {
  51     if (this != &other)
  52     {
  53         Clear();
  54         AppendCopyFrom(other);
  55     }
  56
  57     return *this;
  58 }
  59
  60 void BinaryQueue::AppendCopyFrom(const BinaryQueue &other)
  61 {
  62     // To speed things up, always copy as one bucket
  63     void *bufferCopy = malloc(other.m_size);
  64
  65     if (bufferCopy == NULL)
  66         throw std::bad_alloc();
  67
  68     try
  69     {
  70         other.Flatten(bufferCopy, other.m_size);
  71         AppendUnmanaged(bufferCopy, other.m_size, &BufferDeleterFree, NULL);
  72     }
  73     catch (const std::bad_alloc &)
  74     {
  75         // Free allocated memory
  76         free(bufferCopy);
  77         throw;
  78     }
  79 }
  80
  81 void BinaryQueue::AppendMoveFrom(BinaryQueue &other)
  82 {
  83     // Copy all buckets
  84     std::copy(other.m_buckets.begin(), other.m_buckets.end(), std::back_inserter(m_buckets));
  85     m_size += other.m_size;
  86
  87     // Clear other, but do not free memory
  88     other.m_buckets.clear();
  89     other.m_size = 0;
  90 }
  91
  92 void BinaryQueue::AppendCopyTo(BinaryQueue &other) const
  93 {
  94     other.AppendCopyFrom(*this);
  95 }
  96
  97 void BinaryQueue::AppendMoveTo(BinaryQueue &other)
  98 {
  99     other.AppendMoveFrom(*this);
 100 }
 101
 102 void BinaryQueue::Clear()
 103 {
 104     std::for_each(m_buckets.begin(), m_buckets.end(), &DeleteBucket);
 105     m_buckets.clear();
 106     m_size = 0;
 107 }
 108
 109 void BinaryQueue::AppendCopy(const void* buffer, size_t bufferSize)
 110 {
 111     // Create data copy with malloc/free
 112     void *bufferCopy = malloc(bufferSize);
 113
 114     // Check if allocation succeded
 115     if (bufferCopy == NULL)
 116         throw std::bad_alloc();
 117
 118     // Copy user data
 119     memcpy(bufferCopy, buffer, bufferSize);
 120
 121     try
 122     {
 123         // Try to append new bucket
 124         AppendUnmanaged(bufferCopy, bufferSize, &BufferDeleterFree, NULL);
 125     }
 126     catch (const std::bad_alloc &)
 127     {
 128         // Free allocated memory
 129         free(bufferCopy);
 130         throw;
 131     }
 132 }
 133
 134 void BinaryQueue::AppendUnmanaged(const void* buffer, size_t bufferSize, BufferDeleter deleter, void* userParam)
 135 {
 136     // Do not attach empty buckets
 137     if (bufferSize == 0)
 138     {
 139         deleter(buffer, bufferSize, userParam);
 140         return;
 141     }
 142
 143     // Just add new bucket with selected deleter
 144     m_buckets.push_back(new Bucket(buffer, bufferSize, deleter, userParam));
 145
 146     // Increase total queue size
 147     m_size += bufferSize;
 148 }
 149
 150 size_t BinaryQueue::Size() const
 151 {
 152     return m_size;
 153 }
 154
 155 bool BinaryQueue::Empty() const
 156 {
 157     return m_size == 0;
 158 }
 159
 160 void BinaryQueue::Consume(size_t size)
 161 {
 162     // Check parameters
 163     if (size > m_size)
 164         Throw(Exception::OutOfData);
 165
 166     size_t bytesLeft = size;
 167
 168     // Consume data and/or remove buckets
 169     while (bytesLeft > 0)
 170     {
 171         // Get consume size
 172         size_t count = std::min(bytesLeft, m_buckets.front()->left);
 173
 174         m_buckets.front()->ptr = static_cast<const char *>(m_buckets.front()->ptr) + count;
 175         m_buckets.front()->left -= count;
 176         bytesLeft -= count;
 177         m_size -= count;
 178
 179         if (m_buckets.front()->left == 0)
 180         {
 181             DeleteBucket(m_buckets.front());
 182             m_buckets.pop_front();
 183         }
 184     }
 185 }
 186
 187 void BinaryQueue::Flatten(void *buffer, size_t bufferSize) const
 188 {
 189     // Check parameters
 190     if (bufferSize == 0)
 191         return;
 192
 193     if (bufferSize > m_size)
 194         Throw(Exception::OutOfData);
 195
 196     size_t bytesLeft = bufferSize;
 197     void *ptr = buffer;
 198     BucketList::const_iterator bucketIterator = m_buckets.begin();
 199     Assert(m_buckets.end() != bucketIterator);
 200
 201     // Flatten data
 202     while (bytesLeft > 0)
 203     {
 204         // Get consume size
 205         size_t count = std::min(bytesLeft, (*bucketIterator)->left);
 206
 207         // Copy data to user pointer
 208         memcpy(ptr, (*bucketIterator)->ptr, count);
 209
 210         // Update flattened bytes count
 211         bytesLeft -= count;
 212         ptr = static_cast<char *>(ptr) + count;
 213
 214         // Take next bucket
 215         ++bucketIterator;
 216     }
 217 }
 218
 219 void BinaryQueue::FlattenConsume(void *buffer, size_t bufferSize)
 220 {
 221     // FIXME: Optimize
 222     Flatten(buffer, bufferSize);
 223     Consume(bufferSize);
 224 }
 225
 226 void BinaryQueue::DeleteBucket(BinaryQueue::Bucket *bucket)
 227 {
 228     delete bucket;
 229 }
 230
 231 void BinaryQueue::BufferDeleterFree(const void* data, size_t dataSize, void* userParam)
 232 {
 233     (void)dataSize;
 234     (void)userParam;
 235
 236     // Default free deleter
 237     free(const_cast<void *>(data));
 238 }
 239
 240 BinaryQueue::Bucket::Bucket(const void* data, size_t dataSize, BufferDeleter dataDeleter, void* userParam)
 241     : buffer(data),
 242       ptr(data),
 243       size(dataSize),
 244       left(dataSize),
 245       deleter(dataDeleter),
 246       param(userParam)
 247 {
 248     Assert(data != NULL);
 249     Assert(deleter != NULL);
 250 }
 251
 252 BinaryQueue::Bucket::~Bucket()
 253 {
 254     // Invoke deleter on bucket data
 255     deleter(buffer, size, param);
 256 }
 257
 258 BinaryQueue::BucketVisitor::~BucketVisitor()
 259 {
 260 }
 261
 262 BinaryQueue::BucketVisitorCall::BucketVisitorCall(BucketVisitor *visitor)
 263     : m_visitor(visitor)
 264 {
 265 }
 266
 267 BinaryQueue::BucketVisitorCall::~BucketVisitorCall()
 268 {
 269 }
 270
 271 void BinaryQueue::BucketVisitorCall::operator()(Bucket *bucket) const
 272 {
 273     m_visitor->OnVisitBucket(bucket->ptr, bucket->left);
 274 }
 275
 276 void BinaryQueue::VisitBuckets(BucketVisitor *visitor) const
 277 {
 278     Assert(visitor != NULL);
 279
 280     // Visit all buckets
 281     std::for_each(m_buckets.begin(), m_buckets.end(), BucketVisitorCall(visitor));
 282 }
 283
 284 BinaryQueueAutoPtr BinaryQueue::Read(size_t size)
 285 {
 286     // Simulate input stream
 287     size_t available = std::min(size, m_size);
 288
 289     ScopedFree<void> bufferCopy(malloc(available));
 290
 291     if (!bufferCopy)
 292         throw std::bad_alloc();
 293
 294     BinaryQueueAutoPtr result(new BinaryQueue());
 295
 296     Flatten(bufferCopy.Get(), available);
 297     result->AppendUnmanaged(bufferCopy.Get(), available, &BufferDeleterFree, NULL);
 298     bufferCopy.Release();
 299     Consume(available);
 300
 301     return result;
 302 }
 303
 304 size_t BinaryQueue::Write(const BinaryQueue &buffer, size_t bufferSize)
 305 {
 306     // Simulate output stream
 307     AppendCopyFrom(buffer);
 308     return bufferSize;
 309 }
 310 } // namespace DPL