libucommon-dev 6.0.7-1.1 / usr / include / ucommon / containers.h

// Copyright (C) 2006-2010 David Sugar, Tycho Softworks.
//
// This file is part of GNU uCommon C++.
//
// GNU uCommon C++ is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as published
// by the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// GNU uCommon C++ is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public License
// along with GNU uCommon C++.  If not, see <http://www.gnu.org/licenses/>.

/**
 * Threadsafe object containers.  This is used to better define
 * object containers and manipulating classes which can be presumed to be
 * fully threadsafe and thread-aware.  This has to be defined separately
 * to assure correct order of preceeding headers as well as to better
 * organize the library for clarity.  Most of these classes and templates
 * work with classes derived from Object and LinkedObject and make use of
 * conditional for time constrained acquisition of managed objects.
 * @file ucommon/containers.h
 */

#ifndef _UCOMMON_CONTAINERS_H_
#define _UCOMMON_CONTAINERS_H_

#ifndef _UCOMMON_CONFIG_H_
#include <ucommon/platform.h>
#endif

#ifndef _UCOMMON_PROTOCOLS_H_
#include <ucommon/protocols.h>
#endif

#ifndef  _UCOMMON_LINKED_H_
#include <ucommon/linked.h>
#endif

#ifndef  _UCOMMON_MEMORY_H_
#include <ucommon/memory.h>
#endif

#ifndef  _UCOMMON_THREAD_H_
#include <ucommon/thread.h>
#endif

NAMESPACE_UCOMMON

/**
 * Linked allocator helper for linked_allocator template.  This is used
 * to alloc an array of typed objects tied to a free list in a single
 * operation.
 * @author David Sugar <dyfet@gnutelephony.org>
 */
class __EXPORT LinkedAllocator : private Conditional
{
protected:
    LinkedObject *freelist;

    LinkedAllocator();

    LinkedObject *get(void);

    LinkedObject *get(timeout_t timeout);

    void release(LinkedObject *node);

public:
    /**
     * Test if there is still objects in the free list.
     * @return true if there are objects.
     */
    operator bool();

    /**
     * Test if the free list is empty.
     * @return true if the free list is empty.
     */
    bool operator!();
};

/**
 * A thread-safe buffer for serializing and streaming class data.  While
 * the queue and stack operate by managing lists of reference pointers to
 * objects of various mixed kind, the buffer holds physical copies of objects
 * that being passed through it, and all must be the same size.  For this
 * reason the buffer is normally used through the bufferof<type> template
 * rather than stand-alone.  The buffer is accessed in fifo order.
 * @author David Sugar <dyfet@gnutelephony.org>
 */
class __EXPORT Buffer : protected Conditional
{
private:
    size_t bufsize, objsize;
    caddr_t buf, head, tail;
    unsigned objcount, limit;

protected:
    /**
     * Create a buffer to hold a series of objects.
     * @param size of each object in buffer.
     * @param count of objects in the buffer.
     */
    Buffer(size_t typesize, size_t count);

    /**
     * Deallocate buffer and unblock any waiting threads.
     */
    virtual ~Buffer();

    /**
     * Get the next object from the buffer.
     * @param timeout to wait when buffer is empty in milliseconds.
     * @return pointer to next object in the buffer or NULL if timed out.
     */
    void *get(timeout_t timeout);

    /**
     * Get the next object from the buffer.  This blocks until an object
     * becomes available.
     * @return pointer to next object from buffer.
     */
    void *get(void);

    /**
     * Put (copy) an object into the buffer.  This blocks while the buffer
     * is full.
     * @param data to copy into the buffer.
     */
    void put(void *data);

    /**
     * Put (copy) an object into the buffer.
     * @param data to copy into the buffer.
     * @param timeout to wait if buffer is full.
     * @return true if copied, false if timed out while full.
     */
    bool put(void *data, timeout_t timeout);

    /**
     * Release must be called when we get an object from the buffer.  This
     * is because the pointer we return is a physical pointer to memory
     * that is part of the buffer.  The object we get cannot be removed or
     * the memory modified while the object is being used.
     */
    void release(void);

    /**
     * Copy the next object from the buffer.  This blocks until an object
     * becomes available.  Buffer is auto-released.
     * @param data pointer to copy into.
     */
    void copy(void *data);

    /**
     * Copy the next object from the buffer.  Buffer is auto-released.
     * @param data pointer to copy into.
     * @param timeout to wait when buffer is empty in milliseconds.
     * @return true if object copied, or false if timed out.
     */
    bool copy(void *data, timeout_t timeout);

    /**
     * Peek at pending data in buffer.  This returns a pointer to
     * objects relative to the head.  In effect it is the same as
     * get() for item = 0.
     * @param item to examine in buffer.
     * @return pointer to item or NULL if invalid item number.
     */
    void *peek(unsigned item);

    virtual void *invalid(void) const;

public:
    /**
     * Get the size of the buffer.
     * @return size of the buffer.
     */
    unsigned size(void);

    /**
     * Get the number of objects in the buffer currently.
     * @return number of objects buffered.
     */
    unsigned count(void);

    /**
     * Test if there is data waiting in the buffer.
     * @return true if buffer has data.
     */
    operator bool();

    /**
     * Test if the buffer is empty.
     * @return true if the buffer is empty.
     */
    bool operator!();
};

/**
 * Manage a thread-safe queue of objects through reference pointers.  This
 * can be particularly interesting when used to enqueue/dequeue reference
 * counted managed objects.  Thread-safe access is managed through a
 * conditional.  Both lifo and fifo forms of queue access  may be used.  A
 * pool of self-managed member objects are used to operate the queue.  This
 * queue is optimized for fifo access; while lifo is supported, it will be
 * slow.  If you need primarily lifo, you should use stack instead.
 * @author David Sugar <dyfet@gnutelephony.org>
 */
class __EXPORT Queue : protected OrderedIndex, protected Conditional
{
private:
    mempager *pager;
    LinkedObject *freelist;
    size_t used;

    class __LOCAL member : public OrderedObject
    {
    public:
        member(Queue *q, ObjectProtocol *obj);
        ObjectProtocol *object;
    };

    friend class member;

protected:
    size_t limit;

    virtual ObjectProtocol *invalid(void) const;

public:
    /**
     * Create a queue that uses a memory pager for internally managed
     * member objects for a specified maximum number of object pointers.
     * @param pager to use for internal member object or NULL to use heap.
     * @param number of pointers that can be in the queue or 0 for unlimited.
     * size limit.
     */
    Queue(mempager *pager = NULL, size_t number = 0);

    /**
     * Destroy queue.  If no mempager is used, then frees heap.
     */
    ~Queue();

    /**
     * Remove a specific object pointer for the queue.  This can remove
     * a member from any location in the queue, whether beginning, end, or
     * somewhere in the middle.  This also releases the object.
     * @param object to remove.
     * @return true if object was removed, false if not found.
     */
    bool remove(ObjectProtocol *object);

    /**
     * Post an object into the queue by it's pointer.  This can wait for
     * a specified timeout if the queue is full, for example, for another
     * thread to remove an object pointer.  This also retains the object.
     * @param object to post.
     * @param timeout to wait if queue is full in milliseconds.
     * @return true if object posted, false if queue full and timeout expired.
     */
    bool post(ObjectProtocol *object, timeout_t timeout = 0);

    /**
     * Examine pending existing object in queue.  Does not remove it.
     * @param number of elements back.
     * @return object in queue or NULL if invalid value.
     */
    ObjectProtocol *get(unsigned offset = 0);

    /**
     * Get and remove last object posted to the queue.  This can wait for
     * a specified timeout of the queue is empty.  The object is still
     * retained and must be released or deleted by the receiving function.
     * @param timeout to wait if empty in milliseconds.
     * @return object from queue or NULL if empty and timed out.
     */
    ObjectProtocol *fifo(timeout_t timeout = 0);

    /**
     * Get and remove first object posted to the queue.  This can wait for
     * a specified timeout of the queue is empty.  The object is still
     * retained and must be released or deleted by the receiving function.
     * @param timeout to wait if empty in milliseconds.
     * @return object from queue or NULL if empty and timed out.
     */
    ObjectProtocol *lifo(timeout_t timeout = 0);

    /**
     * Get number of object points currently in the queue.
     * @return number of objects in queue.
     */
    size_t count(void);
};

/**
 * Manage a thread-safe stack of objects through reference pointers.  This
 * Thread-safe access is managed through a conditional.  This differs from
 * the queue in lifo mode because delinking the last object is immediate,
 * and because it has much less overhead.  A pool of self-managed
 * member objects are used to operate the stack.
 * @author David Sugar <dyfet@gnutelephony.org>
 */
class __EXPORT Stack : protected Conditional
{
private:
    LinkedObject *freelist, *usedlist;
    mempager *pager;
    size_t used;

    class __LOCAL member : public LinkedObject
    {
    public:
        member(Stack *s, ObjectProtocol *obj);
        ObjectProtocol *object;
    };

    friend class member;

protected:
    size_t limit;

    virtual ObjectProtocol *invalid(void) const;

public:
    /**
     * Create a stack that uses a memory pager for internally managed
     * member objects for a specified maximum number of object pointers.
     * @param pager to use for internal member object or NULL to use heap.
     * @param number of pointers that can be in the stack or 0 if unlimited.
     */
    Stack(mempager *pager = NULL, size_t number = 0);

    /**
     * Destroy queue.  If no pager is used, then frees heap.
     */
    virtual ~Stack();

    /**
     * Remove a specific object pointer for the queue.  This can remove
     * a member from any location in the queue, whether beginning, end, or
     * somewhere in the middle.  This also releases the object.
     * @param object to remove.
     * @return true if object was removed, false if not found.
     */
    bool remove(ObjectProtocol *object);

    /**
     * Push an object into the stack by it's pointer.  This can wait for
     * a specified timeout if the stack is full, for example, for another
     * thread to remove an object pointer.  This also retains the object.
     * @param object to push.
     * @param timeout to wait if stack is full in milliseconds.
     * @return true if object pushed, false if stack full and timeout expired.
     */
    bool push(ObjectProtocol *object, timeout_t timeout = 0);

    /**
     * Get and remove last object pushed on the stack.  This can wait for
     * a specified timeout of the stack is empty.  The object is still
     * retained and must be released or deleted by the receiving function.
     * @param timeout to wait if empty in milliseconds.
     * @return object pulled from stack or NULL if empty and timed out.
     */
    ObjectProtocol *pull(timeout_t timeout = 0);

    /**
     * Examine an existing object on the stack.
     * @param offset to stack entry.
     * @return object examined.
     */
    ObjectProtocol *get(unsigned offset = 0);

    /**
     * Get number of object points currently in the stack.
     * @return number of objects in stack.
     */
    size_t count(void);

    const ObjectProtocol *peek(timeout_t timeout = 0);
};

/**
 * Linked allocator template to gather linked objects.  This allocates the
 * object pool in a single array as a single heap allocation, and releases
 * the whole pool with a single delete when done.  It is also threadsafe.
 * The types used must be derived of LinkedObject.
 * @author David Sugar <dyfet@gnutelephony.org>
 */
template <class T>
class linked_allocator : public LinkedAllocator
{
private:
    T* array;

public:
    inline linked_allocator(size_t size) : LinkedAllocator() {
        array = new T[size];
        for(unsigned i = 0; i < size; ++i)
            array[i].enlist(&freelist);
    }

    ~linked_allocator()
        {delete[] array;};

    inline T *get(void)
        {return static_cast<T *>(LinkedAllocator::get());};

    inline T *get(timeout_t timeout)
        {return static_cast<T *>(LinkedAllocator::get(timeout));};

    inline void release(T *node)
        {LinkedAllocator::release(node);};
};

/**
 * A templated typed class for buffering of objects.  This operates as a
 * fifo buffer of typed objects which are physically copied into the buffer.
 * The objects that are buffered are accessed from allocated buffer space.
 * As designed this may be used with multiple producer threads and one
 * consumer thread.  To use multiple consumers, one can copy the typed object
 * from the buffer through the get pointer and then call release.  The
 * copied object can then be used safely.  This is what the copy method is
 * used for.
 * @author David Sugar <dyfet@gnutelephony.org>
 */
template<class T>
class bufferof : public Buffer
{
public:
    /**
     * Create a buffer to hold a series of typed objects.
     * @param count of typed objects in the buffer.
     */
    inline bufferof(unsigned capacity) :
        Buffer(sizeof(T), capacity) {};

    /**
     * Get the next typed object from the buffer.  This blocks until an object
     * becomes available.
     * @return pointer to next typed object from buffer.
     */
    inline T *get(void)
        {return static_cast<T*>(get());};

    /**
     * Get the next typed object from the buffer.
     * @param timeout to wait when buffer is empty in milliseconds.
     * @return pointer to next typed object in the buffer or NULL if timed out.
     */
    inline T *get(timeout_t timeout)
        {return static_cast<T*>(get(timeout));};

    /**
     * Put (copy) a typed object into the buffer.  This blocks while the buffer
     * is full.
     * @param object to copy into the buffer.
     */
    inline void put(T *object)
        {put(object);};

    /**
     * Put (copy) an object into the buffer.
     * @param object to copy into the buffer.
     * @param timeout to wait if buffer is full.
     * @return true if copied, false if timed out while full.
     */
    inline bool put(T *object, timeout_t timeout)
        {return put(object, timeout);};

    /**
     * Copy the next typed object from the buffer.  This blocks until an object
     * becomes available.
     * @param object pointer to copy typed object into.
     */
    inline void copy(T *object)
        {copy(object);};

    /**
     * Copy the next typed object from the buffer.
     * @param object pointer to copy typed object into.
     * @param timeout to wait when buffer is empty in milliseconds.
     * @return true if object copied, or false if timed out.
     */
    inline bool get(T *object, timeout_t timeout)
        {return copy(object, timeout);};

    /**
     * Examine past item in the buffer.  This is a typecast of the peek
     * operation.
     * @param item in buffer.
     * @return item pointer if valid or NULL.
     */
    inline const T& at(unsigned item)
        {return static_cast<const T&>(Buffer::peek(item));};

    /**
     * Examine past item in the buffer.  This is a typecast of the peek
     * operation.
     * @param item in buffer.
     * @return item pointer if valid or NULL.
     */
    inline T&operator[](unsigned item)
        {return static_cast<T&>(Buffer::peek(item));};

    inline T* operator()(unsigned offset = 0)
        {return static_cast<T*>(Buffer::peek(offset));}
};

/**
 * A templated typed class for thread-safe stack of object pointers.  This
 * allows one to use the stack class in a typesafe manner for a specific
 * object type derived from Object rather than generically for any derived
 * object class.
 * @author David Sugar <dyfet@gnutelephony.org>
 */
template<class T>
class stackof : public Stack
{
public:
    /**
     * Create templated stack of typed objects.
     * @param memory pool for internal use of stack.
     * @param size of stack to construct.  Uses 0 if no size limit.
     */
    inline stackof(mempager *memory, size_t size = 0) : Stack(memory, size) {};

    /**
     * Remove a specific typed object pointer for the stack.  This can remove
     * a member from any location in the stack, whether beginning, end, or
     * somewhere in the middle.  This releases the object.
     * @param object to remove.
     * @return true if object was removed, false if not found.
     */
    inline bool remove(T *object)
        {return Stack::remove(object);};

    /**
     * Push a typed object into the stack by it's pointer.  This can wait for
     * a specified timeout if the queue is full, for example, for another
     * thread to remove an object pointer.  This retains the object.
     * @param object to push.
     * @param timeout to wait if queue is full in milliseconds.
     * @return true if object pushed, false if queue full and timeout expired.
     */
    inline bool push(T *object, timeout_t timeout = 0)
        {return Stack::push(object);};

    /**
     * Get and remove last typed object posted to the stack.  This can wait for
     * a specified timeout of the stack is empty.  The object is still retained
     * and must be released or deleted by the receiving function.
     * @param timeout to wait if empty in milliseconds.
     * @return object from queue or NULL if empty and timed out.
     */
    inline T *pull(timeout_t timeout = 0)
        {return static_cast<T *>(Stack::pull(timeout));};

    /**
     * Examine last typed object posted to the stack.  This can wait for
     * a specified timeout of the stack is empty.
     * @param timeout to wait if empty in milliseconds.
     * @return object in queue or NULL if empty and timed out.
     */
    inline const T *peek(timeout_t timeout = 0)
        {return static_cast<const T *>(Stack::peek(timeout));};

    inline T* operator()(unsigned offset = 0)
        {return static_cast<T*>(Stack::get(offset));}

    /**
     * Examine past item in the stack.  This is a typecast of the peek
     * operation.
     * @param offset in stack.
     * @return item pointer if valid or NULL.
     */
    inline const T& at(unsigned offset = 0)
        {return static_cast<const T&>(Stack::get(offset));};

    /**
     * Examine past item in the stack.  This is a typecast of the peek
     * operation.
     * @param offset in stack.
     * @return item pointer if valid or NULL.
     */
    inline const T& operator[](unsigned offset)
        {return static_cast<T&>(Stack::get(offset));};

};

/**
 * A templated typed class for thread-safe queue of object pointers.  This
 * allows one to use the queue class in a typesafe manner for a specific
 * object type derived from Object rather than generically for any derived
 * object class.
 * @author David Sugar <dyfet@gnutelephony.org>
 */
template<class T>
class queueof : public Queue
{
public:
    /**
     * Create templated queue of typed objects.
     * @param memory pool for internal use by queue.
     * @param size of queue to construct.  Uses 0 if no size limit.
     */
    inline queueof(mempager *memory, size_t size = 0) : Queue(memory, size) {};

    /**
     * Remove a specific typed object pointer for the queue.  This can remove
     * a member from any location in the queue, whether beginning, end, or
     * somewhere in the middle. This releases the object.
     * @param object to remove.
     * @return true if object was removed, false if not found.
     */
    inline bool remove(T *object)
        {return Queue::remove(object);};

    /**
     * Post a typed object into the queue by it's pointer.  This can wait for
     * a specified timeout if the queue is full, for example, for another
     * thread to remove an object pointer.  This retains the object.
     * @param object to post.
     * @param timeout to wait if queue is full in milliseconds.
     * @return true if object posted, false if queue full and timeout expired.
     */
    inline bool post(T *object, timeout_t timeout = 0)
        {return Queue::post(object);};

    /**
     * Get and remove first typed object posted to the queue.  This can wait for
     * a specified timeut of the queue is empty.  The object is still retained
     * and must be released or deleted by the receiving function.
     * @param timeout to wait if empty in milliseconds.
     * @return object from queue or NULL if empty and timed out.
     */
    inline T *fifo(timeout_t timeout = 0)
        {return static_cast<T *>(Queue::fifo(timeout));};

    /**
     * Get and remove last typed object posted to the queue.  This can wait for
     * a specified timeout of the queue is empty.  The object is still retained
     * and must be released or deleted by the receiving function.
     * @param timeout to wait if empty in milliseconds.
     * @return object from queue or NULL if empty and timed out.
     */
    inline T *lifo(timeout_t timeout = 0)
        {return static_cast<T *>(Queue::lifo(timeout));};

    /**
     * Examine past item in the queue.  This is a typecast of the peek
     * operation.
     * @param offset in queue.
     * @return item pointer if valid or NULL.
     */
    inline const T& at(unsigned offset = 0)
        {return static_cast<const T&>(Queue::get(offset));};

    /**
     * Examine past item in the queue.  This is a typecast of the peek
     * operation.
     * @param offset in queue.
     * @return item pointer if valid or NULL.
     */
    inline T& operator[](unsigned offset)
        {return static_cast<T&>(Queue::get(offset));};

    inline T* operator()(unsigned offset = 0)
        {return static_cast<T*>(Queue::get(offset));}
};

/**
 * Convenience type for using thread-safe object stacks.
 */
typedef Stack stack_t;

/**
 * Convenience type for using thread-safe object fifo (queue).
 */
typedef Queue fifo_t;

END_NAMESPACE

#endif