/*
- * Copyright (c) 2011 Samsung Electronics Co., Ltd All Rights Reserved
+ * Copyright (c) 2011 - 2020 Samsung Electronics Co., Ltd All Rights Reserved
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
#ifndef CENT_KEY_BINARY_QUEUE_H
#define CENT_KEY_BINARY_QUEUE_H
-//#include <dpl/abstract_input_output.h>
#include <dpl/exception.h>
-#include <memory>
#include <list>
+#include <vector>
#include <symbol-visibility.h>
-#include <noncopyable.h>
namespace CKM {
-/**
- * Binary queue auto pointer
- */
-class BinaryQueue;
-using BinaryQueueUniquePtr = std::unique_ptr<BinaryQueue>;
/**
* Binary stream implemented as constant size bucket list
- *
- * @todo Add optimized implementation for FlattenConsume
*/
-class COMMON_API BinaryQueue {
- // : public AbstractInputOutput
+class COMMON_API BinaryQueue final {
public:
class Exception {
public:
DECLARE_EXCEPTION_TYPE(Base, OutOfData)
};
- typedef void (*BufferDeleter)(const void *buffer, size_t bufferSize,
- void *userParam);
- static void BufferDeleterFree(const void *buffer,
- size_t bufferSize,
- void *userParam);
-
- class BucketVisitor {
- public:
- /**
- * Destructor
- */
- virtual ~BucketVisitor();
-
- /**
- * Visit bucket
- *
- * @return none
- * @param[in] buffer Constant pointer to bucket data buffer
- * @param[in] bufferSize Number of bytes in bucket
- */
- virtual void OnVisitBucket(const void *buffer, size_t bufferSize) = 0;
- };
-
private:
- struct Bucket {
- NONCOPYABLE(Bucket);
-
- const void *buffer;
- const void *ptr;
- size_t size;
- size_t left;
-
- BufferDeleter deleter;
- void *param;
+ typedef std::vector<unsigned char> Bucket;
- Bucket(const void *buffer,
- size_t bufferSize,
- BufferDeleter deleter,
- void *userParam);
- virtual ~Bucket();
- };
-
- typedef std::list<Bucket *> BucketList;
+ typedef std::list<Bucket> BucketList;
BucketList m_buckets;
size_t m_size;
- static void DeleteBucket(Bucket *bucket);
-
- class BucketVisitorCall {
- private:
- BucketVisitor *m_visitor;
-
- public:
- BucketVisitorCall(BucketVisitor *visitor);
- virtual ~BucketVisitorCall();
-
- void operator()(Bucket *bucket) const;
- };
-
public:
/**
* Construct empty binary queue
*/
BinaryQueue();
- /**
- * Construct binary queue via bare copy of other binary queue
- *
- * @param[in] other Other binary queue to copy from
- * @warning One cannot assume that bucket structure is preserved during copy
- */
- BinaryQueue(const BinaryQueue &other);
+ BinaryQueue(const BinaryQueue &other) = delete;
/**
* Construct binary queue by moving data from other binary queue
BinaryQueue(BinaryQueue &&) = default;
/**
- * Destructor
- */
- virtual ~BinaryQueue();
-
- /**
- * Construct binary queue via bare copy of other binary queue
- *
- * @param[in] other Other binary queue to copy from
- * @warning One cannot assume that bucket structure is preserved during copy
- */
- const BinaryQueue &operator=(const BinaryQueue &other);
-
- /**
- * Assign data from other binary queue using move semantics
- *
- * @param[in] other Other binary queue to move from
- */
- BinaryQueue &operator=(BinaryQueue &&) = default;
-
- /**
* Append copy of @a bufferSize bytes from memory pointed by @a buffer
* to the end of binary queue. Uses default deleter based on free.
*
* @param[in] buffer Pointer to buffer to copy data from
* @param[in] bufferSize Number of bytes to copy
* @exception std::bad_alloc Cannot allocate memory to hold additional data
- * @see BinaryQueue::BufferDeleterFree
*/
void AppendCopy(const void *buffer, size_t bufferSize);
/**
- * Append @a bufferSize bytes from memory pointed by @a buffer
- * to the end of binary queue. Uses custom provided deleter.
- * Responsibility for deleting provided buffer is transfered to BinaryQueue.
- *
- * @return none
- * @param[in] buffer Pointer to data buffer
- * @param[in] bufferSize Number of bytes available in buffer
- * @param[in] deleter Pointer to deleter procedure used to free provided
- * buffer
- * @param[in] userParam User parameter passed to deleter routine
- * @exception std::bad_alloc Cannot allocate memory to hold additional data
- */
- void AppendUnmanaged(
- const void *buffer,
- size_t bufferSize,
- BufferDeleter deleter =
- &BinaryQueue::BufferDeleterFree,
- void *userParam = NULL);
-
- /**
- * Append copy of other binary queue to the end of this binary queue
- *
- * @return none
- * @param[in] other Constant reference to other binary queue to copy data
- * from
- * @exception std::bad_alloc Cannot allocate memory to hold additional data
- * @warning One cannot assume that bucket structure is preserved during copy
- */
- void AppendCopyFrom(const BinaryQueue &other);
-
- /**
- * Move bytes from other binary queue to the end of this binary queue.
- * This also removes all bytes from other binary queue.
- * This method is designed to be as fast as possible (only pointer swaps)
- * and is suggested over making copies of binary queues.
- * Bucket structure is preserved after operation.
- *
- * @return none
- * @param[in] other Reference to other binary queue to move data from
- * @exception std::bad_alloc Cannot allocate memory to hold additional data
- */
- void AppendMoveFrom(BinaryQueue &other);
-
- /**
- * Append copy of binary queue to the end of other binary queue
- *
- * @return none
- * @param[in] other Constant reference to other binary queue to copy data to
- * @exception std::bad_alloc Cannot allocate memory to hold additional data
- * @warning One cannot assume that bucket structure is preserved during copy
- */
- void AppendCopyTo(BinaryQueue &other) const;
-
- /**
- * Move bytes from binary queue to the end of other binary queue.
- * This also removes all bytes from binary queue.
- * This method is designed to be as fast as possible (only pointer swaps)
- * and is suggested over making copies of binary queues.
- * Bucket structure is preserved after operation.
- *
- * @return none
- * @param[in] other Reference to other binary queue to move data to
- * @exception std::bad_alloc Cannot allocate memory to hold additional data
- */
- void AppendMoveTo(BinaryQueue &other);
-
- /**
* Retrieve total size of all data contained in binary queue
*
* @return Number of bytes in binary queue
size_t Size() const;
/**
- * Remove all data from binary queue
- *
- * @return none
- */
- void Clear();
-
- /**
- * Check if binary queue is empty
- *
- * @return true if binary queue is empty, false otherwise
- */
- bool Empty() const;
-
- /**
- * Remove @a size bytes from beginning of binary queue
- *
- * @return none
- * @param[in] size Number of bytes to remove
- * @exception BinaryQueue::Exception::OutOfData Number of bytes is larger
- * than available bytes in binary queue
- */
- void Consume(size_t size);
-
- /**
- * Retrieve @a bufferSize bytes from beginning of binary queue and copy them
- * to user supplied buffer
- *
- * @return none
- * @param[in] buffer Pointer to user buffer to receive bytes
- * @param[in] bufferSize Size of user buffer pointed by @a buffer
- * @exception BinaryQueue::Exception::OutOfData Number of bytes to flatten
- * is larger than available bytes in binary queue
- */
- void Flatten(void *buffer, size_t bufferSize) const;
-
- /**
* Retrieve @a bufferSize bytes from beginning of binary queue, copy them
* to user supplied buffer, and remove from binary queue
*
* is larger than available bytes in binary queue
*/
void FlattenConsume(void *buffer, size_t bufferSize);
-
- /**
- * Visit each buffer with data using visitor object
- *
- * @return none
- * @param[in] visitor Pointer to bucket visitor
- * @see BinaryQueue::BucketVisitor
- */
- void VisitBuckets(BucketVisitor *visitor) const;
-
- /**
- * IAbstractInput interface
- */
- virtual BinaryQueueUniquePtr Read(size_t size);
-
- /**
- * IAbstractOutput interface
- */
- virtual size_t Write(const BinaryQueue &buffer, size_t bufferSize);
};
} // namespace CKM
* @version 1.0
* @brief This file is the implementation file of binary queue
*/
-#include <stddef.h>
#include <dpl/binary_queue.h>
#include <cassert>
#include <algorithm>
-#include <functional>
-#include <malloc.h>
#include <cstring>
-#include <new>
namespace CKM {
BinaryQueue::BinaryQueue() :
m_size(0)
{}
-BinaryQueue::BinaryQueue(const BinaryQueue &other) :
- m_size(0)
-{
- AppendCopyFrom(other);
-}
-
-BinaryQueue::~BinaryQueue()
-{
- // Remove all remainig buckets
- Clear();
-}
-
-const BinaryQueue &BinaryQueue::operator=(const BinaryQueue &other)
-{
- if (this != &other) {
- Clear();
- AppendCopyFrom(other);
- }
-
- return *this;
-}
-
-void BinaryQueue::AppendCopyFrom(const BinaryQueue &other)
-{
- // To speed things up, always copy as one bucket
- void *bufferCopy = malloc(other.m_size);
-
- if (bufferCopy == NULL)
- throw std::bad_alloc();
-
- try {
- other.Flatten(bufferCopy, other.m_size);
- AppendUnmanaged(bufferCopy, other.m_size, &BufferDeleterFree, NULL);
- } catch (const std::bad_alloc &) {
- // Free allocated memory
- free(bufferCopy);
- throw;
- }
-}
-
-void BinaryQueue::AppendMoveFrom(BinaryQueue &other)
-{
- // Copy all buckets
- std::copy(other.m_buckets.begin(),
- other.m_buckets.end(), std::back_inserter(m_buckets));
- m_size += other.m_size;
-
- // Clear other, but do not free memory
- other.m_buckets.clear();
- other.m_size = 0;
-}
-
-void BinaryQueue::AppendCopyTo(BinaryQueue &other) const
-{
- other.AppendCopyFrom(*this);
-}
-
-void BinaryQueue::AppendMoveTo(BinaryQueue &other)
-{
- other.AppendMoveFrom(*this);
-}
-
-void BinaryQueue::Clear()
-{
- std::for_each(m_buckets.begin(), m_buckets.end(), &DeleteBucket);
- m_buckets.clear();
- m_size = 0;
-}
-
void BinaryQueue::AppendCopy(const void *buffer, size_t bufferSize)
{
- // Create data copy with malloc/free
- void *bufferCopy = malloc(bufferSize);
-
- // Check if allocation succeded
- if (bufferCopy == NULL)
- throw std::bad_alloc();
-
- // Copy user data
- memcpy(bufferCopy, buffer, bufferSize);
-
- try {
- // Try to append new bucket
- AppendUnmanaged(bufferCopy, bufferSize, &BufferDeleterFree, NULL);
- } catch (const std::bad_alloc &) {
- // Free allocated memory
- free(bufferCopy);
- throw;
- }
-}
-
-void BinaryQueue::AppendUnmanaged(const void *buffer,
- size_t bufferSize,
- BufferDeleter deleter,
- void *userParam)
-{
- // Do not attach empty buckets
- if (bufferSize == 0) {
- deleter(buffer, bufferSize, userParam);
+ if (bufferSize == 0)
return;
- }
- // Just add new bucket with selected deleter
- Bucket *bucket = new Bucket(buffer, bufferSize, deleter, userParam);
+ assert(buffer != NULL);
- try {
- m_buckets.push_back(bucket);
- } catch (const std::bad_alloc &) {
- delete bucket;
- throw;
- }
-
- // Increase total queue size
+ m_buckets.emplace_back(bufferSize);
+ memcpy(m_buckets.back().data(), buffer, bufferSize);
m_size += bufferSize;
}
return m_size;
}
-bool BinaryQueue::Empty() const
-{
- return m_size == 0;
-}
-
-void BinaryQueue::Consume(size_t size)
-{
- // Check parameters
- if (size > m_size)
- Throw(Exception::OutOfData);
-
- size_t bytesLeft = size;
-
- // Consume data and/or remove buckets
- while (bytesLeft > 0) {
- // Get consume size
- size_t count = std::min(bytesLeft, m_buckets.front()->left);
-
- m_buckets.front()->ptr =
- static_cast<const char *>(m_buckets.front()->ptr) + count;
- m_buckets.front()->left -= count;
- bytesLeft -= count;
- m_size -= count;
-
- if (m_buckets.front()->left == 0) {
- DeleteBucket(m_buckets.front());
- m_buckets.pop_front();
- }
- }
-}
-
-void BinaryQueue::Flatten(void *buffer, size_t bufferSize) const
+void BinaryQueue::FlattenConsume(void *buffer, size_t bufferSize)
{
// Check parameters
if (bufferSize == 0)
return;
+ assert(buffer != NULL);
+
if (bufferSize > m_size)
Throw(Exception::OutOfData);
size_t bytesLeft = bufferSize;
void *ptr = buffer;
- BucketList::const_iterator bucketIterator = m_buckets.begin();
- assert(m_buckets.end() != bucketIterator);
+ assert(!m_buckets.empty());
// Flatten data
- while (bytesLeft > 0) {
+ do {
+ auto& bucket = m_buckets.front();
+
// Get consume size
- size_t count = std::min(bytesLeft, (*bucketIterator)->left);
+ size_t bucketSize = bucket.size();
+ size_t count = std::min(bytesLeft, bucketSize);
// Copy data to user pointer
- memcpy(ptr, (*bucketIterator)->ptr, count);
+ memcpy(ptr, bucket.data(), count);
+
+ // consume
+ if (count == bucketSize) {
+ m_buckets.pop_front();
+ } else {
+ bucket.erase(bucket.begin(), bucket.begin() + count);
+ assert(count == bytesLeft);
+ break;
+ }
- // Update flattened bytes count
bytesLeft -= count;
ptr = static_cast<char *>(ptr) + count;
-
- // Take next bucket
- ++bucketIterator;
- }
-}
-
-void BinaryQueue::FlattenConsume(void *buffer, size_t bufferSize)
-{
- // FIXME: Optimize
- Flatten(buffer, bufferSize);
- Consume(bufferSize);
-}
-
-void BinaryQueue::DeleteBucket(BinaryQueue::Bucket *bucket)
-{
- delete bucket;
+ } while (bytesLeft);
+ m_size -= bufferSize;
}
-void BinaryQueue::BufferDeleterFree(const void *data,
- size_t dataSize,
- void *userParam)
-{
- (void)dataSize;
- (void)userParam;
-
- // Default free deleter
- free(const_cast<void *>(data));
-}
-
-BinaryQueue::Bucket::Bucket(const void *data,
- size_t dataSize,
- BufferDeleter dataDeleter,
- void *userParam) :
- buffer(data),
- ptr(data),
- size(dataSize),
- left(dataSize),
- deleter(dataDeleter),
- param(userParam)
-{
- assert(data != NULL);
- assert(deleter != NULL);
-}
-
-BinaryQueue::Bucket::~Bucket()
-{
- // Invoke deleter on bucket data
- deleter(buffer, size, param);
-}
-
-BinaryQueue::BucketVisitor::~BucketVisitor()
-{
-}
-
-BinaryQueue::BucketVisitorCall::BucketVisitorCall(BucketVisitor *visitor) :
- m_visitor(visitor)
-{
-}
-
-BinaryQueue::BucketVisitorCall::~BucketVisitorCall()
-{
-}
-
-void BinaryQueue::BucketVisitorCall::operator()(Bucket *bucket) const
-{
- m_visitor->OnVisitBucket(bucket->ptr, bucket->left);
-}
-
-void BinaryQueue::VisitBuckets(BucketVisitor *visitor) const
-{
- assert(visitor != NULL);
-
- // Visit all buckets
- std::for_each(m_buckets.begin(), m_buckets.end(), BucketVisitorCall(visitor));
-}
-
-BinaryQueueUniquePtr BinaryQueue::Read(size_t size)
-{
- // Simulate input stream
- size_t available = std::min(size, m_size);
-
- std::unique_ptr<void, std::function<void(void *)>>
- bufferCopy(malloc(available), free);
-
- if (!bufferCopy.get())
- throw std::bad_alloc();
-
- BinaryQueueUniquePtr result(new BinaryQueue());
-
- Flatten(bufferCopy.get(), available);
- result->AppendUnmanaged(
- bufferCopy.release(), available, &BufferDeleterFree, NULL);
- Consume(available);
-
- return result;
-}
-
-size_t BinaryQueue::Write(const BinaryQueue &buffer, size_t bufferSize)
-{
- // Simulate output stream
- AppendCopyFrom(buffer);
- return bufferSize;
-}
} // namespace CKM
namespace {
-RawBuffer buf({0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07});
+constexpr unsigned char buf[] = {0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07};
+constexpr size_t bufSize = sizeof(buf);
} // namespace anonymous
BOOST_AUTO_TEST_SUITE(BINARY_QUEUE_TEST)
-POSITIVE_TEST_CASE(copy_assignment)
+POSITIVE_TEST_CASE(append_copy)
{
- BinaryQueue bq1;
- bq1.AppendCopy(buf.data(), buf.size());
-
- BinaryQueue bq2;
- bq2 = bq1;
-
- BOOST_REQUIRE(bq1.Size() == bq2.Size() && bq1.Size() == buf.size());
-
- RawBuffer buf1(bq1.Size(), 0x00);
- RawBuffer buf2(bq2.Size(), 0x00);
-
- bq1.Flatten(buf1.data(), buf1.size());
- bq2.Flatten(buf2.data(), buf2.size());
-
- BOOST_REQUIRE(buf1 == buf2);
-}
-
-POSITIVE_TEST_CASE(append_copy_to)
-{
- BinaryQueue bq1;
- bq1.AppendCopy(buf.data(), buf.size());
-
- BinaryQueue bq2;
- bq1.AppendCopyTo(bq2);
+ BinaryQueue bq;
+ BOOST_REQUIRE(bq.Size() == 0);
- BOOST_REQUIRE(bq1.Size() == bq2.Size() && bq1.Size() == buf.size());
+ bq.AppendCopy(buf, bufSize);
- RawBuffer buf1(bq1.Size(), 0x00);
- RawBuffer buf2(bq2.Size(), 0x00);
+ BOOST_REQUIRE(bq.Size() == bufSize);
- bq1.Flatten(buf1.data(), buf1.size());
- bq2.Flatten(buf2.data(), buf2.size());
+ bq.AppendCopy(buf, bufSize);
- BOOST_REQUIRE(buf1 == buf2);
+ BOOST_REQUIRE(bq.Size() == 2 * bufSize);
}
-POSITIVE_TEST_CASE(append_move_to)
+NEGATIVE_TEST_CASE(append_copy)
{
- BinaryQueue bq1;
- bq1.AppendCopy(buf.data(), buf.size());
-
- BinaryQueue bq2;
- bq1.AppendMoveTo(bq2);
+ BinaryQueue bq;
- BOOST_REQUIRE(bq2.Size() == buf.size() && bq1.Empty());
+ bq.AppendCopy(buf, 0);
- RawBuffer buf2(bq2.Size(), 0x00);
- bq2.Flatten(buf2.data(), buf2.size());
- BOOST_REQUIRE(buf == buf2);
+ BOOST_REQUIRE(bq.Size() == 0);
}
-POSITIVE_TEST_CASE(read)
+POSITIVE_TEST_CASE(flatten_consume)
{
- BinaryQueue bq1;
- bq1.AppendCopy(buf.data(), buf.size());
+ BinaryQueue bq;
- auto bq2 = bq1.Read(buf.size());
- BOOST_REQUIRE(bq1.Empty());
+ constexpr size_t part1Size = bufSize / 2;
- RawBuffer buf2(bq2->Size(), 0x00);
- bq2->Flatten(buf2.data(), buf2.size());
- BOOST_REQUIRE(buf == buf2);
-}
+ bq.AppendCopy(buf, part1Size);
+ bq.AppendCopy(buf + part1Size, bufSize - part1Size);
-POSITIVE_TEST_CASE(write)
-{
- BinaryQueue bq1;
- bq1.AppendCopy(buf.data(), buf.size());
+ char out[3 * bufSize / 4];
+ bq.FlattenConsume(out, sizeof(out));
+ BOOST_REQUIRE(memcmp(buf, out, sizeof(out)) == 0);
- BinaryQueue bq2;
- bq2.Write(bq1, bq1.Size());
+ constexpr size_t remainingSize = bufSize - sizeof(out);
+ BOOST_REQUIRE(bq.Size() == remainingSize);
- RawBuffer buf1(bq1.Size(), 0x00);
- RawBuffer buf2(bq2.Size(), 0x00);
+ bq.FlattenConsume(out, remainingSize);
- bq1.Flatten(buf1.data(), buf1.size());
- bq2.Flatten(buf2.data(), buf2.size());
+ BOOST_REQUIRE(memcmp(buf + sizeof(out), out, remainingSize) == 0);
+ BOOST_REQUIRE(memcmp(buf + remainingSize,
+ out + remainingSize,
+ sizeof(out) - remainingSize) == 0);
- BOOST_REQUIRE(buf1 == buf2);
+ BOOST_REQUIRE(bq.Size() == 0);
}
-POSITIVE_TEST_CASE(bucket_visitor)
+NEGATIVE_TEST_CASE(flatten_consume)
{
- static std::vector<unsigned char> globalBuf;
-
- class BucketVisitorTest : public BinaryQueue::BucketVisitor {
- public:
- virtual void OnVisitBucket(const void *buffer, size_t bufferSize) override
- {
- for (size_t i = 0; i < bufferSize; ++i)
- globalBuf.push_back(static_cast<const unsigned char *>(buffer)[i]);
- }
- };
+ BinaryQueue bq;
- BucketVisitorTest visitor;
+ char out;
+ BOOST_REQUIRE_THROW(bq.FlattenConsume(&out, sizeof(out)),
+ BinaryQueue::Exception::OutOfData);
- constexpr size_t BucketNum = 3;
- BinaryQueue bq;
- for (size_t i = 0; i < BucketNum; ++i)
- bq.AppendCopy(buf.data(), buf.size());
+ bq.AppendCopy(buf, bufSize);
- bq.VisitBuckets(&visitor);
+ bq.FlattenConsume(&out, 0);
+ BOOST_REQUIRE(bq.Size() == bufSize);
- BOOST_REQUIRE(globalBuf.size() == buf.size() * BucketNum);
- for (size_t i = 0; i < BucketNum; ++i)
- for (size_t j = 0; j < buf.size(); ++j)
- BOOST_REQUIRE(globalBuf[i * buf.size() + j] == buf[j]);
+ char out2[bufSize + 1];
+ BOOST_REQUIRE_THROW(bq.FlattenConsume(out2, sizeof(out2)),
+ BinaryQueue::Exception::OutOfData);
+ BOOST_REQUIRE(bq.Size() == bufSize);
}
BOOST_AUTO_TEST_SUITE_END()