view release on metacpan or  search on metacpan

generator/parser/rpp/appendedlist.h  view on Meta::CPAN

   This library 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
   Library General Public License for more details.

   You should have received a copy of the GNU Library General Public License
   along with this library; see the file COPYING.LIB.  If not, write to
   the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
   Boston, MA 02110-1301, USA.
*/

#ifndef APPENDEDLIST_H
#define APPENDEDLIST_H

#include <QtCore/QMutex>
#include <QtCore/QVector>
#include <QtCore/QStack>
#include <QtCore/QPair>
// #include <kglobal.h>
// #include <kdebug.h>
#include "../kdevvarlengtharray.h"
#include <iostream>
#include <time.h>

namespace KDevelop {
class AbstractItemRepository;
/**
 * This file contains macros and classes that can be used to conveniently implement classes that store the data of an arbitrary count
 * of additional lists within the same memory block directly behind the class data, in a way that one the whole data can be stored by one copy-operation
 * to another place, like needed in ItemRepository. These macros simplify having two versions of a class: One that has its lists attached in memory,
 * and one version that has them contained as a directly accessible KDevVarLengthArray. Both versions have their lists accessible through access-functions,
 * have a completeSize() function that computes the size of the one-block version, and a copyListsFrom(..) function which can copy the lists from one
 * version to the other.
 *
 * @warning Always follow these rules:
 * You must call initalizeAppendedLists(bool) on construction, also in any copy-constructor, but before calling copyFrom(..).
 * The parameter to that function should be whether the lists in the items should be dynamic, and thus most times "true".
 * You must call freeAppendedLists() on destruction, our you will be leaking memory(only when dynamic)
 *
 * For each embedded list, you must use macros to define a global hash that will be used to allocate the temporary lists, example fir identifier.cpp:
 * DEFINE_LIST_MEMBER_HASH(IdentifierPrivate, templateIdentifiers, uint);
 *
 * See identifier.cpp for an example how to use these classes. @todo Document this a bit more
 * */


enum {
  DynamicAppendedListMask = 1 << 31
};
enum {
  DynamicAppendedListRevertMask = 0xffffffff - DynamicAppendedListMask
};
/**
 * Manages a repository of items for temporary usage. The items will be allocated with an index on alloc(),
 * and freed on free(index). When freed, the same index will be re-used for a later allocation, thus no real allocations
 * will be happening in most cases.
 * The returned indices will always be ored with DynamicAppendedListMask.
 *
 */
template<class T, bool threadSafe = true>
class TemporaryDataManager {
  public:
    TemporaryDataManager(QString id = QString()) : m_itemsUsed(0), m_itemsSize(0), m_items(0), m_id(id) {
      uint first = alloc();  //Allocate the zero item, just to reserve that index
      Q_ASSERT(first == (uint)DynamicAppendedListMask);
    }
    ~TemporaryDataManager() {
      free(DynamicAppendedListMask); //Free the zero index, so we don't get wrong warnings
      uint cnt = usedItemCount();
      if(cnt) //Don't use kDebug, because that may not work during destruction
        std::cout << m_id.toLocal8Bit().data() << " There were items left on destruction: " << usedItemCount() << "\n";

      for(uint a = 0; a < m_itemsUsed; ++a)
        delete m_items[a];
    }

    inline T& getItem(uint index) {
      //For performance reasons this function does not lock the mutex, it's called too often and must be
      //extremely fast. There is special measures in alloc() to make this safe.
      Q_ASSERT(index & DynamicAppendedListMask);

      return *m_items[index & KDevelop::DynamicAppendedListRevertMask];
    }

    ///Allocates an item index, which from now on you can get using getItem, until you call free(..) on the index.
    ///The returned item is not initialized and may contain random older content, so you should clear it after getting it for the first time
    uint alloc() {

      if(threadSafe)
        m_mutex.lock();

      uint ret;
      if(!m_freeIndicesWithData.isEmpty()) {
        ret = m_freeIndicesWithData.pop();
      }else if(!m_freeIndices.isEmpty()) {
        ret = m_freeIndices.pop();
        Q_ASSERT(!m_items[ret]);
        m_items[ret] = new T;
      }else{

        if(m_itemsUsed >= m_itemsSize) {
          //We need to re-allocate
          uint newItemsSize = m_itemsSize + 20 + (m_itemsSize/3);
          T** newItems = new T*[newItemsSize];
          memcpy(newItems, m_items, sizeof(T*) * m_itemsSize);

          T** oldItems = m_items;
          m_items = newItems;
          m_itemsSize = newItemsSize;
          //The only function that does not lock the mutex is getItem(..), because that function must be very efficient.
          //Since it's only a few instructions from the moment m_items is read to the moment it's used,
          //deleting the old data after a few seconds should be safe.
          m_deleteLater.append(qMakePair(time(0), oldItems));

          //We do this in this place so it isn't called too often. The result is that we will always have some additional data around.
          //However the index itself should anyway not consume too much data.
          if(!m_deleteLater.isEmpty()) {
            while(!m_deleteLater.isEmpty()) {
              //We delete after 5 seconds
              if(time(0) - m_deleteLater.first().first > 5) {
                delete[] m_deleteLater.first().second;
                m_deleteLater.removeFirst();
              }else{
                break;
              }
            }
          }
        }

        ret = m_itemsUsed;
        m_items[m_itemsUsed] = new T;
        ++m_itemsUsed;
        Q_ASSERT(m_itemsUsed <= m_itemsSize);
      }

      if(threadSafe)
        m_mutex.unlock();

      Q_ASSERT(!(ret & DynamicAppendedListMask));

      return ret | DynamicAppendedListMask;
    }

    void free(uint index) {
      Q_ASSERT(index & DynamicAppendedListMask);
      index &= KDevelop::DynamicAppendedListRevertMask;

      if(threadSafe)
        m_mutex.lock();

      freeItem(m_items[index]);

      m_freeIndicesWithData.push(index);

      //Hold the amount of free indices with data between 100 and 200
      if(m_freeIndicesWithData.size() > 200) {
        for(int a = 0; a < 100; ++a) {
          uint deleteIndexData = m_freeIndicesWithData.pop();
          delete m_items[deleteIndexData];
          m_items[deleteIndexData] = 0;
          m_freeIndices.push(deleteIndexData);
        }
      }

      if(threadSafe)
        m_mutex.unlock();
    }

    uint usedItemCount() const {
      uint ret = 0;
      for(uint a = 0; a < m_itemsUsed; ++a)
        if(m_items[a])
          ++ret;
      return ret - m_freeIndicesWithData.size();
    }

  private:
    //To save some memory, clear the lists
    void freeItem(T* item) {
      item->clear(); ///@todo make this a template specialization that only does this for containers
    }

    uint m_itemsUsed, m_itemsSize;
    T** m_items;
    QStack<uint> m_freeIndicesWithData;
    QStack<uint> m_freeIndices;
    QMutex m_mutex;
    QString m_id;
    QList<QPair<time_t, T**> > m_deleteLater;
};

///Foreach macro that takes a container and a function-name, and will iterate through the vector returned by that function, using the length returned by the function-name with "Size" appended.
//This might be a little slow
#define FOREACH_FUNCTION(item, container) for(uint a = 0, mustDo = 1, containerSize = container ## Size(); a < containerSize; ++a) if((mustDo == 0 || mustDo == 1) && (mustDo = 2)) for(item(container()[a]); mustDo; mustDo = 0)
//More efficient version that does not repeatedly call functions on the container, but the syntax is a bit less nice
// #define FOREACH_FUNCTION_EFFICIENT(itemType, itemName, container) for(itemType* start = container(), end = start + container ## Size(), fake = start; start != end; ++start) for( itemType itemName(*start); fake != end; fake = end)

#define DEFINE_LIST_MEMBER_HASH(container, member, type) \
    typedef TemporaryDataManager<KDevVarLengthArray<type, 10> > temporaryHash ## container ## member ## Type; \
    Q_GLOBAL_STATIC_WITH_ARGS(temporaryHash ## container ## member ## Type, temporaryHash ## container ## member ## Static, ( #container "::" #member )) \
    temporaryHash ## container ## member ## Type& temporaryHash ## container ## member() { \
        return *temporaryHash ## container ## member ## Static; \
    }

#define DECLARE_LIST_MEMBER_HASH(container, member, type) KDevelop::TemporaryDataManager<KDevVarLengthArray<type, 10> >& temporaryHash ## container ## member();

///This implements the interfaces so this container can be used as a predecessor for classes with appended lists.
///You should do this within the abstract base class that opens a tree of classes that can have appended lists,
///so each class that uses them, can also give its predecessor to START_APPENDE_LISTS, to increase flexibility.
///This  creates a boolean entry that is initialized when initializeAppendedLists is called.
///You can call appendedListsDynamic() to find out whether the item is marked as dynamic.
///When this item is used, the same rules have to be followed as for a class with appended lists: You have to call
///initializeAppendedLists(...) and freeAppendedLists(..)
///Also, when you use this, you have to implement a size_t classSize() function, that returns the size of the class including derived classes,
///but not including the dynamic data. Optionally you can implement a static bool appendedListDynamicDefault() function, that returns the default-value for the "dynamic" parameter.
///to initializeAppendedLists.
#define APPENDED_LISTS_STUB(container) \
bool m_dynamic : 1;                          \
unsigned int offsetBehindLastList() const { return 0; } \
size_t dynamicSize() const { return classSize(); } \
template<class T> bool listsEqual(const T& /*rhs*/) const { return true; } \
template<class T> void copyAllFrom(const T& /*rhs*/) const { } \
void initializeAppendedLists(bool dynamic = appendedListDynamicDefault()) { m_dynamic = dynamic; }  \
void freeAppendedLists() { } \
bool appendedListsDynamic() const { return m_dynamic; }