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