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