Войти
Вело-изобретателиФорумОколоигровой флейм

Контейнеры :)

#0
14:16, 6 дек. 2007
template<class TValue>
class TRawVector
{
public:

  inline TRawVector(unsigned long ulGrowStep)
  :
    m_pData(0), 
    m_ulGrowStep(ulGrowStep), 
    m_ulCap(0), 
    m_ulPtr(0) {}

  virtual ~TRawVector()
  {
    FreeMemory();
  }

  inline void FreeMemory()
  {
    if(m_pData)
      free(m_pData);

    m_pData = 0;
    m_ulCap = 0;
    m_ulPtr = 0;
  }

  inline bool ResizeFast(unsigned long ulCap)
  {
    if(ulCap > m_ulCap)
    {
      TValue* pData = (TValue*)malloc(sizeof(TValue) * ulCap);
      if(!pData)
        return false;

      if(m_pData)
        free(m_pData);

      m_pData = pData;
      m_ulCap = ulCap;
    }

    m_ulPtr = 0;
    return true;
  }

  inline bool ResizeCopy(unsigned long ulCap)
  {
    if(ulCap > m_ulCap)
    {
      TValue* pData = (TValue*)malloc(sizeof(TValue) * ulCap);
      if(!pData)
        return false;

      if(m_pData)
      {
        memcpy(pData, m_pData, sizeof(TValue) * m_ulCap);
        free(m_pData);
      }

      m_pData = pData;
      m_ulCap = ulCap;
    }

    return true;
  }

  inline bool Push(const TValue& rValue, unsigned long& rId)
  {
    if(_Resize())
    {
      m_pData[m_ulPtr] = rValue;
      rId = m_ulPtr;
      m_ulPtr++;
      return true;
    }

    return false;
  }

  inline bool Push(const TValue& rValue)
  {
    if(_Resize())
    {
      m_pData[m_ulPtr] = rValue;
      m_ulPtr++;
      return true;
    }

    return false;
  }

  inline bool Pop(TValue& rValue)
  {
    if(m_ulPtr > 0)
    {
      m_ulPtr--;
      rValue = m_pData[m_ulPtr];
      return true;
    }

    return false;
  }

  inline void Set(unsigned long ulId, const TValue& rValue)
  {
    T_ASSERTD(ulId < m_ulCap);
    m_pData[ulId] = rValue;
  }

  inline TValue& Get(unsigned long ulId)
  {
    T_ASSERTD(ulId < m_ulCap);
    return m_pData[ulId];
  }

  inline const TValue& Get(unsigned long ulId) const
  {
    T_ASSERTD(ulId < m_ulCap);
    return m_pData[ulId];
  }

private:

  inline bool _Resize()
  {
    if(m_ulPtr < m_ulCap)
      return true;
    else if(m_ulPtr > 0)
      return ResizeCopy(m_ulCap + m_ulGrowStep);
    else
      return ResizeFast(m_ulGrowStep);
  }

public:

  inline TValue* GetData() {return m_pData;}
  inline const TValue* GetData() const {return m_pData;}

  inline unsigned long GetCap() const {return m_ulCap;}
  inline unsigned long GetPtr() const {return m_ulPtr;}

private:

  TValue* m_pData;
  unsigned long m_ulGrowStep;
  unsigned long m_ulCap;
  unsigned long m_ulPtr;
};

#1
14:16, 6 дек. 2007
template<class TValue>
class TRawStack
{
private:

  struct SNode
  {
    SNode* pPrev;
    SNode* pNext;
    TValue* pData;
    unsigned long ulCap;
    unsigned long ulPtr;
  };

public:

  inline TRawStack(unsigned long ulGrowStep)
  :
    m_pHead(0), 
    m_pTail(0), 
    m_ulGrowStep(ulGrowStep), 
    m_ulSize(0) {}

  virtual ~TRawStack()
  {
    FreeMemory();
  }

  inline void FreeMemory()
  {
    SNode* pPool = m_pHead;
    while(pPool)
    {
      SNode* pTemp = pPool;
      pPool = pPool->pNext;
      free(pTemp->pData);
      free(pTemp);
    }

    m_pHead = 0;
    m_pTail = 0;
    m_ulSize = 0;
  }

  inline bool Push(const TValue& rValue)
  {
    if(_Resize())
    {
      _Push(rValue);
      return true;
    }

    return false;
  }

  inline bool Pop(TValue& rValue)
  {
    if(m_ulSize > 0)
    {
      if(m_pTail->ulPtr > 0)
      {
        _Pop(rValue);
        return true;
      }

      if(m_pTail->pPrev)
      {
        m_pTail = m_pTail->pPrev;
        _Pop(rValue);
        return true;
      }
    }

    return false;
  }

private:

  inline bool _Resize()
  {
    if(m_pTail)
    {
      if(m_pTail->ulPtr < m_pTail->ulCap)
        return true;

      if(m_pTail->pNext)
      {
        m_pTail = m_pTail->pNext;
        return true;
      }

      SNode* pPool = _CreatePool(m_pTail);
      if(pPool)
      {
        m_pTail->pNext = pPool;
        m_pTail = pPool;
        return true;
      }

      return false;
    }

    SNode* pPool = _CreatePool(0);
    if(pPool)
    {
      m_pHead = m_pTail = pPool;
      return true;
    }

    return false;
  }

  inline SNode* _CreatePool(SNode* pPrev)
  {
    SNode* pPool = (SNode*)malloc(sizeof(SNode));
    if(pPool)
    {
      pPool->pData = (TValue*)malloc(sizeof(TValue) * m_ulGrowStep);
      if(pPool->pData)
      {
        pPool->pPrev = pPrev;
        pPool->pNext = 0;
        pPool->ulCap = m_ulGrowStep;
        pPool->ulPtr = 0;
        return pPool;
      }

      free(pPool);
    }

    return 0;
  }

  inline void _Push(const TValue& rValue)
  {
    m_pTail->pData[m_pTail->ulPtr++] = rValue;
    m_ulSize++;
  }

  inline void _Pop(TValue& rValue)
  {
    rValue = m_pTail->pData[--m_pTail->ulPtr];
    m_ulSize--;
  }

  inline unsigned long GetSize() const {return m_ulSize;}

private:

  SNode* m_pHead;
  SNode* m_pTail;
  unsigned long m_ulGrowStep;
  unsigned long m_ulSize;
};
#2
14:16, 6 дек. 2007
template<class TValue>
class TRawPool
{
private:

  struct SNode
  {
    SNode* pNext;
    TValue* pData;
    unsigned long ulCap;
    unsigned long ulPtr;
  };

public:

  inline TRawPool(unsigned long ulGrowStep)
  :
    m_ValueStack(ulGrowStep), 
    m_pHead(0), 
    m_pTail(0), 
    m_ulGrowStep(ulGrowStep), 
    m_ulNumPools(0) {}

  virtual ~TRawPool()
  {
    FreeMemory();
  }

  inline void FreeMemory()
  {
    m_ValueStack.FreeMemory();

    SNode* pPool = m_pHead;
    while(pPool)
    {
      SNode* pTemp = pPool;
      pPool = pPool->pNext;
      free(pTemp->pData);
      free(pTemp);
    }

    m_pHead = 0;
    m_pTail = 0;
    m_ulNumPools = 0; 
  }

  inline bool Get(TValue*& rpValue)
  {
    if(m_ValueStack.Pop(rpValue))
      return true;

    if(m_pTail)
      return _Get(rpValue);

    return _New(rpValue);
  }

  inline bool Get(TValue*& rpValue, bool& rPooled)
  {
    if(m_ValueStack.Pop(rpValue))
    {
      rPooled = true;
      return true;
    }

    rPooled = false;

    if(m_pTail)
      return _Get(rpValue);

    return _New(rpValue);
  }

  inline bool Add(TValue* pValue)
  {
    return m_ValueStack.Push(pValue);
  }

private:

  inline bool _Get(TValue*& rpValue)
  {
    if(m_pTail->ulPtr < m_pTail->ulCap)
    {
      _GetPtr(rpValue, *m_pTail);
      return true;
    }

    SNode* pPool = _CreatePool();
    if(pPool)
    {
      m_pTail->pNext = pPool;
      m_pTail = pPool;
      _GetPtr(rpValue, *m_pTail);
      return true;
    }

    return false;
  }

  inline bool _New(TValue*& rpValue)
  {
    SNode* pPool = _CreatePool();
    if(pPool)
    {
      m_pHead = m_pTail = pPool;
      _GetPtr(rpValue, *m_pTail);
      return true;
    }

    return false;
  }

  inline void _GetPtr(TValue*& rpValue, SNode& rNode)
  {
    rpValue = rNode.pData + rNode.ulPtr;
    rNode.ulPtr++;
  }

  inline SNode* _CreatePool()
  {
    SNode* pPool = (SNode*)malloc(sizeof(SNode));
    if(pPool)
    {
      pPool->pData = (TValue*)malloc(sizeof(TValue) * m_ulGrowStep);
      if(pPool->pData)
      {
        pPool->pNext = 0;
        pPool->ulCap = m_ulGrowStep;
        pPool->ulPtr = 0;
        m_ulNumPools++;
        return pPool;
      }

      free(pPool);
    }

    return 0;
  }

private:

  TRawStack<TValue*> m_ValueStack;
  SNode* m_pHead;
  SNode* m_pTail;
  unsigned long m_ulGrowStep;
  unsigned long m_ulNumPools;
};
#3
14:17, 6 дек. 2007
template<class TValue>
class TRawArray
{
private:

  struct SNode
  {
    TValue tValue;
    unsigned long ulId;
    bool bActive;
  };

public:

  inline TRawArray(unsigned long ulGrowStep)
  :
    m_NodePool(ulGrowStep), 
    m_NodeVec(ulGrowStep) {}

  virtual ~TRawArray()
  {
    FreeMemory();
  }

  inline void FreeMemory()
  {
    m_NodePool.FreeMemory();
    m_NodeVec.FreeMemory();
  }

  inline bool Add(unsigned long& rId, const TValue& rValue)
  {
    SNode* pNode;
    bool bPooled;

    if(m_NodePool.Get(pNode, bPooled))
    {
      if(bPooled)
      {
        rId = pNode->ulId;
        pNode->tValue = rValue;
        pNode->bActive = true;
        return true;
      }

      if(m_NodeVec.Push(pNode, rId))
      {
        pNode->tValue = rValue;
        pNode->ulId = rId;
        pNode->bActive = true;
        return true;
      }

      m_NodePool.Add(pNode);
    }

    return false;
  }

  inline bool Reserve(unsigned long& rId, TValue*& rpValue)
  {
    SNode* pNode;
    bool bPooled;

    if(m_NodePool.Get(pNode, bPooled))
    {
      if(bPooled)
      {
        rId = pNode->ulId;
        rpValue = &pNode->tValue;
        pNode->bActive = true;
        return true;
      }

      if(m_NodeVec.Push(pNode, rId))
      {
        rpValue = &pNode->tValue;
        pNode->ulId = rId;
        pNode->bActive = true;
        return true;
      }

      m_NodePool.Add(pNode);
    }

    return false;
  }

  inline bool Remove(unsigned long ulId)
  {
    if(ulId < m_NodeVec.GetPtr())
    {
      SNode* pNode = m_NodeVec.Get(ulId);
      if(pNode->bActive)
      {
        pNode->bActive = false;
        m_NodePool.Add(pNode);
        return true;
      }
    }

    return false;
  }

  inline bool Get(unsigned long ulId, TValue& rValue)
  {
    if(ulId < m_NodeVec.GetPtr())
    {
      SNode* pNode = m_NodeVec.Get(ulId);
      if(pNode->bActive)
      {
        rValue = pNode->tValue;
        return true;
      }
    }

    return false;
  }

  inline bool GetPtr(unsigned long ulId, TValue*& rpValue)
  {
    if(ulId < m_NodeVec.GetPtr())
    {
      SNode* pNode = m_NodeVec.Get(ulId);
      if(pNode->bActive)
      {
        rpValue = &pNode->tValue;
        return true;
      }
    }

    return false;
  }

public:

  class CIter
  {
  private:

    friend class TRawArray<TValue>;

    inline CIter(TRawVector<SNode*>& rVec)
    :
      m_rVec(rVec), 
      m_ulPtr(0) {}

    inline void operator=(const CIter&) {}

  public:

    inline bool Valid()
    {
      return (m_ulPtr < m_rVec.GetPtr());
    }

    inline bool ReadValue(TValue& rValue)
    {
      SNode* pNode = m_rVec.Get(m_ulPtr);
      m_ulPtr++;

      if(pNode->bActive)
      {
        rValue = pNode->tValue;
        return true;
      }

      return false;
    }

    inline unsigned long GetId() const {return m_ulPtr;}

  private:

    TRawVector<SNode*>& m_rVec;
    unsigned long m_ulPtr;
  };

public:

  inline CIter GetIter() {return CIter(m_NodeVec);}

private:

  TRawPool<SNode> m_NodePool;
  TRawVector<SNode*> m_NodeVec;
};
#4
14:18, 6 дек. 2007
template<class TKey, class TValue>
class TRawHashMap
{
private:

  struct SNode
  {
    SNode* pNext;
    SNode* pLo;
    SNode* pHi;
    TKey tKey;
    TValue tValue;
    uint32_t uiHash;
    bool bActive;
  };

public:

  typedef bool (*CompareFuncPtr)(const TKey& rKey1, const TKey& rKey2);

  inline TRawHashMap(unsigned long ulGrowStep, CompareFuncPtr pCompareFunc)
  :
    m_NodePool(ulGrowStep), 
    m_pCompareFunc(pCompareFunc), 
    m_pRoot(0), 
    m_ulSize(0) {}

  virtual ~TRawHashMap()
  {
    FreeMemory();
  }

  inline void FreeMemory()
  {
    m_NodePool.FreeMemory();

    m_pRoot = 0;
    m_ulSize = 0;
  }

  inline bool Add(const TKey& rKey, const TValue& rValue)
  {
    return (_Add(rKey, rValue) ? true : false);
  }

  inline bool Add(const TKey& rKey, const TValue& rValue, void*& rpHandle)
  {
    SNode* pNode = _Add(rKey, rValue);
    if(pNode)
    {
      rpHandle = pNode;
      return true;
    }

    return false;
  }

  inline bool Get(const TKey& rKey, TValue& rValue)
  {
    if(m_ulSize)
    {
      uint32_t uiHash = _ComputeHash(rKey);
      SNode* pNode = _FindActiveNode(rKey, uiHash);
      if(pNode)
      {
        rValue = pNode->tValue;
        return true;
      }
    }

    return false;
  }

  inline bool Remove(const TKey& rKey)
  {
    if(m_ulSize)
    {
      uint32_t uiHash = _ComputeHash(rKey);
      SNode* pNode = _FindActiveNode(rKey, uiHash);
      if(pNode)
      {
        pNode->bActive = false;
        m_ulSize--;
        return true;
      }
    }

    return false;
  }

  inline bool RemoveByHandle(void* pHandle)
  {
    if(m_ulSize)
    {
      SNode* pNode = (SNode*)pHandle;
      pNode->bActive = false;
      m_ulSize--;
      return true;
    }

    return false;
  }

private:

  inline SNode* _Add(const TKey& rKey, const TValue& rValue)
  {
    uint32_t uiHash = _ComputeHash(rKey);

    if(!m_pRoot)
    {
      SNode* pNode = _InitNode(rKey, rValue, uiHash);
      if(pNode)
      {
        m_pRoot = pNode;
        return pNode;
      }

      return 0;
    }

    SNode* pParent = 0;
    SNode* pTreeNode = m_pRoot;

    while(pTreeNode)
    {
      uint32_t uiTreeHash = pTreeNode->uiHash;

      if(uiHash == uiTreeHash)
      {
        SNode* pFirstInactive = 0;
        do
        {
          if(pTreeNode->bActive)
          {
            bool res = m_pCompareFunc(rKey, pTreeNode->tKey);
            if(res)
              return 0;
          }
          else if(!pFirstInactive)
            pFirstInactive = pTreeNode;

          pParent = pTreeNode;
          pTreeNode = pTreeNode->pNext;
        }
        while(pTreeNode);

        if(pFirstInactive)
        {
          pFirstInactive->tKey = rKey;
          pFirstInactive->tValue = rValue;
          pFirstInactive->uiHash = uiHash;
          pFirstInactive->bActive = true;
          m_ulSize++;
          return pFirstInactive;
        }

        SNode* pNode = _InitNode(rKey, rValue, uiHash);
        if(pNode)
        {
          pParent->pNext = pNode;
          return pNode;
        }
      }

      pParent = pTreeNode;

      if(uiHash < uiTreeHash)
        pTreeNode = pTreeNode->pLo;
      else
        pTreeNode = pTreeNode->pHi;
    }

    SNode* pNode = _InitNode(rKey, rValue, uiHash);
    if(pNode)
    {
      if(uiHash < pParent->uiHash)
        pParent->pLo = pNode;
      else
        pParent->pHi = pNode;

      return pNode;
    }

    return 0;
  }

  inline SNode* _FindActiveNode(const TKey& rKey, uint32_t uiHash)
  {
    SNode* pNode = m_pRoot;
    while(pNode)
    {
      uint32_t uiNodeHash = pNode->uiHash;

      if(uiHash == uiNodeHash)
      {
        do
        {
          if(pNode->bActive)
          {
            bool res = m_pCompareFunc(rKey, pNode->tKey);
            if(res)
              return pNode;
          }

          pNode = pNode->pNext;
        }
        while(pNode);

        return 0;
      }

      if(uiHash < uiNodeHash)
        pNode = pNode->pLo;
      else if(uiHash > uiNodeHash)
        pNode = pNode->pHi;
    }

    return 0;
  }

  inline SNode* _InitNode(const TKey& rKey, const TValue& rValue, uint32_t uiHash)
  {
    SNode* pNode;
    if(m_NodePool.Get(pNode))
    {
      pNode->pNext = 0;
      pNode->pLo = 0;
      pNode->pHi = 0;
      pNode->tKey = rKey;
      pNode->tValue = rValue;
      pNode->uiHash = uiHash;
      pNode->bActive = true;
      m_ulSize++;
      return pNode;
    }

    return 0;
  }

  inline uint32_t _ComputeHash(const TKey& rKey)
  {
    return adler32((const uint8_t*)&rKey, sizeof(TKey));
  }

public:

  inline unsigned long GetSize() const {return m_ulSize;}

private:

  TRawPool<SNode> m_NodePool;
  CompareFuncPtr m_pCompareFunc;
  SNode* m_pRoot;
  unsigned long m_ulSize;
};
#5
11:40, 7 дек. 2007

baga
СИ++ плохой язык, потому что в нем нет смайлов :)
А серьезно - такое лучше в статью оформить.

Вело-изобретателиФорумОколоигровой флейм

Тема в архиве.