advanced code snippet search

Posted By

edmmapi on 06/25/09


Tagged


Versions (?)

Epic Delusions Multimedia API: Key List Template Class

 / Published in: C++
 
Expand | Embed | Plain Text 
  1. // file: edmem.h
  2. /*
  3.  * Epic Delusions Multimedia API v0.5b
  4.  * Cross platform API for games and multimedia applications
  5.  *
  6.  * Memory Management Module Revision 1
  7.  *
  8.  * Copyright (c) 1993-2009, Orlando Llanes ([email protected])
  9.  * All rights reserved.
  10.  *
  11.  * Redistribution and use in source and binary forms, with or without
  12.  * modification, are permitted provided that the following conditions
  13.  * are met:
  14.  * - Redistributions of source code must retain the above copyright
  15.  *   notice, this list of conditions and the following disclaimer. 
  16.  * - Redistributions in binary form must reproduce the above copyright
  17.  *   notice, this list of conditions and the following disclaimer in the
  18.  *   documentation and/or other materials provided with the distribution. 
  19.  * - Neither the name of the Epic Delusions Development Team nor the
  20.  *   names of its contributors may be used to endorse or promote products
  21.  *   derived from this software without specific prior written permission. 
  22.  *
  23.  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24.  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25.  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  26.  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  27.  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  28.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  29.  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  30.  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  31.  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  33.  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  34.  * POSSIBILITY OF SUCH DAMAGE.
  35.  */
  36. #ifndef edmem_h
  37. #define edmem_h
  38.  
  39.   #include "eddef.h"
  40.  
  41.  
  42. /*
  43.  * Memory allocation object
  44.  */
  45.   class CEDMemBuf
  46.   {
  47.     public:
  48.       CEDMemBuf();
  49.       virtual ~CEDMemBuf();
  50.  
  51.       bool Create( edu32 p_size, bool p_clear = true );
  52.       void Destroy();
  53.       void* KeepBuf();
  54.  
  55.       void* BufPtr( edu32 p_ofs = 0 );
  56.       edu32 BufSize( edu32 p_ofs = 0 );
  57.  
  58.       bool Resize( edu32 p_newSize );
  59.       bool Grow( edu32 p_newSize, edu32 p_gapOfs = 0,
  60.         edu32 p_gapSize = 0 );
  61.       bool Shrink( edu32 p_newSize, edu32 p_gapOfs = 0,
  62.         edu32 p_gapSize = 0 );
  63.  
  64.       bool InsertGap( edu32 p_ofs, edu32 p_size, edu32 p_limit = 0 );
  65.       bool DeleteGap( edu32 p_ofs, edu32 p_size, edu32 p_limit = 0 );
  66.  
  67.     protected:
  68.       edu8* m_buf;
  69.       edu32 m_size;
  70.   };
  71.  
  72.   void CEDMemBuf_Free( void** p_buf );
  73.  
  74. #endif
  75.  
  76.  
  77. // file: edmem.cpp
  78. /*
  79.  * Epic Delusions Multimedia API v0.5b
  80.  * Cross platform API for games and multimedia applications
  81.  *
  82.  * Memory Management Module Revision 1
  83.  *
  84.  * Copyright (c) 1993-2009, Orlando Llanes ([email protected])
  85.  * All rights reserved.
  86.  *
  87.  * Redistribution and use in source and binary forms, with or without
  88.  * modification, are permitted provided that the following conditions
  89.  * are met:
  90.  * - Redistributions of source code must retain the above copyright
  91.  *   notice, this list of conditions and the following disclaimer. 
  92.  * - Redistributions in binary form must reproduce the above copyright
  93.  *   notice, this list of conditions and the following disclaimer in the
  94.  *   documentation and/or other materials provided with the distribution. 
  95.  * - Neither the name of the Epic Delusions Development Team nor the
  96.  *   names of its contributors may be used to endorse or promote products
  97.  *   derived from this software without specific prior written permission. 
  98.  *
  99.  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  100.  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  101.  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  102.  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  103.  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  104.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  105.  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  106.  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  107.  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  108.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  109.  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  110.  * POSSIBILITY OF SUCH DAMAGE.
  111.  */
  112. #include "edmem.h"
  113.  
  114. #include <stddef.h>
  115. #include <string.h>
  116.  
  117. /*
  118.  * Memory allocation object
  119.  */
  120.   CEDMemBuf::CEDMemBuf():
  121.     m_buf(NULL),
  122.     m_size(0)
  123.   {
  124.   }
  125.  
  126.   CEDMemBuf::~CEDMemBuf()
  127.   {
  128.     Destroy();
  129.   }
  130.  
  131.   bool CEDMemBuf::Create( edu32 p_size, bool p_clear )
  132.   {
  133.     if( p_size )
  134.     {
  135.       Destroy();
  136.  
  137.       m_buf = new edu8[p_size];
  138.       if( m_buf )
  139.       {
  140.         if( p_clear )
  141.           memset( m_buf, 0, p_size );
  142.  
  143.         m_size = p_size;
  144.         return true;
  145.       }
  146.     }
  147.  
  148.     return false;
  149.   }
  150.  
  151.   void CEDMemBuf::Destroy()
  152.   {
  153.     if( m_buf )
  154.       delete[] m_buf;
  155.     m_buf = NULL;
  156.  
  157.     m_size = 0;
  158.   }
  159.  
  160.   void* CEDMemBuf::KeepBuf()
  161.   {
  162.     edu8* l_buf;
  163.  
  164.     if( m_buf )
  165.     {
  166.       l_buf = (edu8*)m_buf;
  167.  
  168.       m_buf  = NULL;
  169.       m_size = 0;
  170.  
  171.       return l_buf;
  172.     }
  173.  
  174.     return NULL;
  175.   }
  176.  
  177.   void* CEDMemBuf::BufPtr( edu32 p_ofs )
  178.   {
  179.     if( m_buf && (p_ofs < m_size) )
  180.       return (((edu8*)m_buf) + p_ofs);
  181.     return NULL;
  182.   }
  183.  
  184.   edu32 CEDMemBuf::BufSize( edu32 p_ofs )
  185.   {
  186.     if( m_buf && (p_ofs < m_size) )
  187.       return (m_size - p_ofs);
  188.     return 0;
  189.   }
  190.  
  191.   bool CEDMemBuf::Resize( edu32 p_newSize )
  192.   {
  193.     edu32 l_size;
  194.     edu8* l_buf;
  195.  
  196.     if( p_newSize == 0 )
  197.       return false;
  198.  
  199.     if( p_newSize == m_size )
  200.       return (m_buf != NULL);
  201.  
  202.     l_buf = new edu8[p_newSize];
  203.     if( l_buf == NULL )
  204.       return false;
  205.  
  206.     l_size = m_size;
  207.     if( p_newSize < l_size )
  208.       l_size = p_newSize;
  209.  
  210.     if( m_buf )
  211.     {
  212.       memcpy( l_buf, m_buf, l_size );
  213.  
  214.       delete[] m_buf;
  215.     }
  216.  
  217.     m_buf  = l_buf;
  218.     m_size = p_newSize;
  219.  
  220.     return true;
  221.   }
  222.  
  223.   bool CEDMemBuf::Grow( edu32 p_newSize, edu32 p_gapOfs, edu32 p_gapSize )
  224.   {
  225.     edu32 l_gapEnd = p_gapOfs + p_gapSize;
  226.     edu32 l_size;
  227.     edu8* l_buf;
  228.  
  229.     if( m_buf == NULL )
  230.       return Resize(p_newSize);
  231.  
  232.     if( p_newSize == m_size )
  233.       return InsertGap( p_gapOfs, p_gapSize );
  234.  
  235.     l_buf = new edu8[p_newSize];
  236.     if( l_buf == NULL )
  237.       return false;
  238.  
  239.     if( p_gapOfs < m_size )
  240.     {
  241.       memcpy( l_buf, m_buf, p_gapOfs );
  242.  
  243.       if( (l_gapEnd + (m_size - p_gapOfs)) <= p_newSize )
  244.         memcpy( l_buf + p_gapOfs + p_gapSize, m_buf + p_gapOfs, m_size - p_gapOfs );
  245.     }
  246.     else
  247.     {
  248.       l_size = m_size;
  249.       if( p_newSize < l_size )
  250.         l_size = p_newSize;
  251.  
  252.       memcpy( l_buf, m_buf, l_size );
  253.     }
  254.  
  255.     delete[] m_buf;
  256.  
  257.     m_buf  = l_buf;
  258.     m_size = p_newSize;
  259.  
  260.     return true;
  261.   }
  262.  
  263.   bool CEDMemBuf::Shrink( edu32 p_newSize, edu32 p_gapOfs, edu32 p_gapSize )
  264.   {
  265.     edu32 l_gapEnd = p_gapOfs + p_gapSize;
  266.     edu8* l_buf;
  267.  
  268.     if( !(m_buf && p_gapSize) )
  269.       return Resize(p_newSize);
  270.  
  271.     if( p_gapOfs >= p_newSize )
  272.       return (p_gapOfs == p_newSize);
  273.  
  274.     if( p_newSize >= m_size )
  275.       return (p_newSize == m_size);
  276.  
  277.     if( l_gapEnd > m_size )
  278.       return false;
  279.  
  280.     l_buf = new edu8[p_newSize];
  281.     if( l_buf == NULL )
  282.       return false;
  283.  
  284.     memcpy( l_buf, m_buf, p_gapOfs );
  285.  
  286.     memcpy( l_buf + p_gapOfs, m_buf + l_gapEnd, p_newSize - p_gapOfs );
  287.  
  288.     delete[] m_buf;
  289.  
  290.     m_buf  = l_buf;
  291.     m_size = p_newSize;
  292.  
  293.     return true;
  294.   }
  295.  
  296.   bool CEDMemBuf::InsertGap( edu32 p_ofs, edu32 p_size, edu32 p_limit )
  297.   {
  298.     edu32 l_tmp = p_ofs + p_size;
  299.  
  300.     if( (l_tmp > m_size) || (p_limit > m_size) )
  301.       return false;
  302.  
  303.     if( p_limit == 0 )
  304.       p_limit = m_size;
  305.     if( m_buf )
  306.     {
  307.       memmove( m_buf + l_tmp, m_buf + p_ofs, p_limit - l_tmp );
  308.       return true;
  309.     }
  310.  
  311.     return false;
  312.   }
  313.  
  314.   bool CEDMemBuf::DeleteGap( edu32 p_ofs, edu32 p_size, edu32 p_limit )
  315.   {
  316.     edu32 l_end = p_ofs + p_size;
  317.  
  318.     if( !(m_buf && p_size) )
  319.       return false;
  320.  
  321.     if( p_limit == 0 )
  322.       p_limit = m_size;
  323.  
  324.     if( p_limit > m_size )
  325.       return false;
  326.  
  327.     if( p_ofs >= p_limit )
  328.       return (p_ofs == p_limit);
  329.  
  330.     memmove( m_buf + p_ofs, m_buf + l_end, p_limit - p_ofs );
  331.     return true;
  332.   }
  333.  
  334.  
  335. // file: edlist.h
  336. /*
  337.  * Epic Delusions Multimedia API v0.5b
  338.  * Cross platform API for games and multimedia applications
  339.  *
  340.  * List Module Revision 4
  341.  *
  342.  * Copyright (c) 1993-2009, Orlando Llanes ([email protected])
  343.  * All rights reserved.
  344.  *
  345.  * Redistribution and use in source and binary forms, with or without
  346.  * modification, are permitted provided that the following conditions
  347.  * are met:
  348.  * - Redistributions of source code must retain the above copyright
  349.  *   notice, this list of conditions and the following disclaimer. 
  350.  * - Redistributions in binary form must reproduce the above copyright
  351.  *   notice, this list of conditions and the following disclaimer in the
  352.  *   documentation and/or other materials provided with the distribution. 
  353.  * - Neither the name of the Epic Delusions Development Team nor the
  354.  *   names of its contributors may be used to endorse or promote products
  355.  *   derived from this software without specific prior written permission. 
  356.  *
  357.  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  358.  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  359.  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  360.  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  361.  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  362.  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  363.  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  364.  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  365.  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  366.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  367.  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  368.  * POSSIBILITY OF SUCH DAMAGE.
  369.  */
  370. #ifndef edlist_h
  371. #define edlist_h
  372.  
  373.   #include "eddef.h"
  374.   #include "edmem.h"
  375.  
  376.   template<typename editem_t, typename edkey_t>
  377.   class CEDKeyList
  378.   {
  379.     public:
  380.       CEDKeyList();
  381.       virtual ~CEDKeyList();
  382.  
  383.       virtual bool Create( edu32 p_nItems = 0 );
  384.       virtual void Destroy();
  385.  
  386.       virtual bool Sort();
  387.  
  388.       edu32 ItemCount();
  389.  
  390.       bool RemoveItem( edu32 p_index );
  391.       bool Remove( const edkey_t p_key );
  392.  
  393.     protected:
  394.       edu32 FindItem( const edkey_t p_key );
  395.  
  396.       virtual bool GetItem( edu32 p_index, editem_t& p_item );
  397.       virtual bool SetItem( edu32 p_index, editem_t& p_item );
  398.  
  399.       bool InsertItem( edu32 p_index, const editem_t& p_item );
  400.  
  401.       bool FreeItem( edu32 p_index );
  402.  
  403.       bool AddItem( const editem_t& p_item );
  404.  
  405.       virtual int CompareKey( const editem_t& p_item, const edkey_t p_key );
  406.       virtual int CompareItem( const editem_t& p_left, const editem_t& p_right );
  407.  
  408.       bool SwapItem( edu32 p_indexa, edu32 p_indexb );
  409.  
  410.     protected:
  411.       CEDMemBuf m_listbuf;
  412.       editem_t* m_list;
  413.       edu32     m_nItems;
  414.       edu32     m_nMax;
  415.       edu32     m_growBy;
  416.   };
  417.  
  418.   template<typename editem_t, typename edkey_t>
  419.   CEDKeyList<editem_t, edkey_t>::CEDKeyList():
  420.     m_list(0),
  421.     m_nItems(0),
  422.     m_nMax(0),
  423.     m_growBy(2 << 4) // Set default growth rate to 4 items
  424.   {
  425.   }
  426.  
  427.   template<typename editem_t, typename edkey_t>
  428.   CEDKeyList<editem_t, edkey_t>::~CEDKeyList()
  429.   {
  430.     Destroy();
  431.   }
  432.  
  433.   template<typename editem_t, typename edkey_t>
  434.   bool CEDKeyList<editem_t, edkey_t>::Create( edu32 p_nItems )
  435.   {
  436.     Destroy();
  437.  
  438.     if( p_nItems == 0 )
  439.       p_nItems = 1;
  440.  
  441.     if( !m_listbuf.Create(p_nItems * sizeof(editem_t)) )
  442.       return false;
  443.  
  444.     m_list = (editem_t*)m_listbuf.BufPtr();
  445.     if( m_list )
  446.     {
  447.       m_nItems = 0;
  448.       m_nMax   = p_nItems;
  449.       return true;
  450.     }
  451.  
  452.     Destroy();
  453.     return false;
  454.   }
  455.  
  456.   template<typename editem_t, typename edkey_t>
  457.   void CEDKeyList<editem_t, edkey_t>::Destroy()
  458.   {
  459.     m_listbuf.Destroy();
  460.     m_list = NULL;
  461.  
  462.     m_nItems = 0;
  463.     m_nMax   = 0;
  464.  
  465.     m_growBy = 2 << 4; // Set default growth rate to 4 items
  466.   }
  467.  
  468.   template<typename editem_t, typename edkey_t>
  469.   bool CEDKeyList<editem_t, edkey_t>::Sort()
  470.   {
  471.     return false;
  472.   }
  473.  
  474.   template<typename editem_t, typename edkey_t>
  475.   edu32 CEDKeyList<editem_t, edkey_t>::ItemCount()
  476.   {
  477.     if( m_list && (m_nItems < m_nMax) )
  478.       return m_nItems;
  479.     return 0;
  480.   }
  481.  
  482.   template<typename editem_t, typename edkey_t>
  483.   bool CEDKeyList<editem_t, edkey_t>::RemoveItem( edu32 p_index )
  484.   {
  485.     edu32 l_nMax;
  486.  
  487.     if( !(m_list && m_nItems) )
  488.       return false;
  489.  
  490.     if( m_nItems > m_nMax )
  491.       return false;
  492.  
  493.     if( !FreeItem(p_index) )
  494.       return false;
  495.  
  496.     if( (m_growBy >> 4) != (m_nMax - m_nItems - 1) )
  497.     {
  498.       if( !m_listbuf.DeleteGap(p_index * sizeof(editem_t), sizeof(editem_t),
  499.           m_nItems * sizeof(editem_t)) )
  500.         return false;
  501.  
  502.       m_nItems--;
  503.       return true;
  504.     }
  505.  
  506.     l_nMax = m_nMax - ((edu32)1 << (m_growBy >> 4));
  507.  
  508.     if( !m_listbuf.Shrink(l_nMax * sizeof(editem_t),
  509.         p_index * sizeof(editem_t), sizeof(editem_t)))
  510.       return false;
  511.  
  512.     m_list = (testitem_t*)m_listbuf.BufPtr();
  513.     if( m_list == NULL )
  514.       return false;
  515.  
  516.     m_nMax = l_nMax;
  517.     m_nItems--;
  518.  
  519.     if( m_growBy & 15 )
  520.       m_growBy--;
  521.  
  522.     return true;
  523.   }
  524.  
  525.   template<typename editem_t, typename edkey_t>
  526.   bool CEDKeyList<editem_t, edkey_t>::Remove( const edkey_t p_key )
  527.   {
  528.     edu32 l_index;
  529.  
  530.     l_index = FindItem(p_key);
  531.  
  532.     if( l_index != ED_INVALID )
  533.       return RemoveItem(l_index);
  534.  
  535.     return false;
  536.   }
  537.  
  538.   template<typename editem_t, typename edkey_t>
  539.   edu32 CEDKeyList<editem_t, edkey_t>::FindItem( const edkey_t p_key )
  540.   {
  541.     edu32 l_left  = 0;
  542.     edu32 l_mid   = m_nItems >> 1;
  543.     edu32 l_right = m_nItems;
  544.     int   l_code;
  545.  
  546.     if( !(m_list && m_nItems) )
  547.       return ED_INVALID;
  548.  
  549.     while( l_left < l_right )
  550.     {
  551.       l_code = CompareKey(m_list[l_mid], p_key);
  552.  
  553.       if( l_code == 0 )
  554.         return l_mid;
  555.  
  556.       if( l_code < 0 )
  557.         l_left = l_mid + 1;
  558.       else
  559.         l_right = l_mid;
  560.  
  561.       l_mid = (l_left + l_right) >> 1;
  562.     }
  563.  
  564.     return ED_INVALID;
  565.   }
  566.  
  567.   template<typename editem_t, typename edkey_t>
  568.   bool CEDKeyList<editem_t, edkey_t>::GetItem( edu32 p_index, editem_t& p_item )
  569.   {
  570.     if( (p_index >= m_nItems) || (&p_item == NULL) )
  571.       return false;
  572.  
  573.     p_item = m_list[p_index];
  574.     return true;
  575.   }
  576.  
  577.   template<typename editem_t, typename edkey_t>
  578.   bool CEDKeyList<editem_t, edkey_t>::SetItem( edu32 p_index, editem_t& p_item )
  579.   {
  580.     if( (p_index >= m_nItems) || (&p_item == NULL) )
  581.       return false;
  582.  
  583.     m_list[p_index] = p_item;
  584.     return true;
  585.   }
  586.  
  587.   template<typename editem_t, typename edkey_t>
  588.   bool CEDKeyList<editem_t, edkey_t>::InsertItem( edu32 p_index, const editem_t& p_item )
  589.   {
  590.     edu32 l_nMax;
  591.  
  592.     if( !(m_list && (&p_item)) )
  593.       return false;
  594.  
  595.     if( p_index > m_nMax )
  596.       return false;
  597.  
  598.     if( m_nItems < m_nMax )
  599.     {
  600.       if( !m_listbuf.InsertGap(p_index * sizeof(editem_t),
  601.           sizeof(editem_t), (m_nItems + 1) * sizeof(editem_t)) )
  602.         return false;
  603.  
  604.       m_list[p_index] = p_item;
  605.       m_nItems++;
  606.       return true;
  607.     }
  608.  
  609.     l_nMax = m_nMax + ((edu32)1 << (m_growBy >> 4));
  610.  
  611.     // Check for integer overflow
  612.     if( l_nMax < m_nMax )
  613.       return false;
  614.  
  615.     // Limit growth rate to 1 << 8 [256]
  616.     if( m_growBy < ((edu32)8 << 4) )
  617.     {
  618.       m_growBy++;
  619.  
  620.       if( (m_growBy & 15) == 15 )
  621.         m_growBy = (m_growBy & (~15)) << 1;
  622.     }
  623.  
  624.     if( !m_listbuf.Grow(l_nMax * sizeof(editem_t),
  625.         p_index * sizeof(editem_t), sizeof(editem_t)) )
  626.       return false;
  627.  
  628.     m_list = (editem_t*)m_listbuf.BufPtr();
  629.     if( m_list == NULL )
  630.       return false;
  631.  
  632.     m_nMax = l_nMax;
  633.  
  634.     m_list[p_index] = p_item;
  635.     m_nItems++;
  636.     return true;
  637.   }
  638.  
  639.   template<typename editem_t, typename edkey_t>
  640.   bool CEDKeyList<editem_t, edkey_t>::FreeItem( edu32 p_index )
  641.   {
  642.     return true;
  643.   }
  644.  
  645.   template<typename editem_t, typename edkey_t>
  646.   bool CEDKeyList<editem_t, edkey_t>::AddItem( const editem_t& p_item )
  647.   {
  648.     edu32 l_left;
  649.     edu32 l_mid = 0;
  650.     edu32 l_right;
  651.     int   l_code;
  652.  
  653.     if( m_list == NULL )
  654.       return false;
  655.  
  656.     if( m_nItems == 0 )
  657.     {
  658.       m_list[0] = p_item;
  659.       m_nItems++;
  660.       return true;
  661.     }
  662.  
  663.     // Special case last item, no duplicates allowed
  664.     l_code = CompareItem(m_list[m_nItems - 1], p_item);
  665.     if( l_code == 0 )
  666.       return false;
  667.  
  668.     // If insert position is at end, skip search
  669.     if( l_code < 0 )
  670.     {
  671.       l_mid = m_nItems;
  672.       goto Add_SkipSearch;
  673.     }
  674.  
  675.     l_left  = 0;
  676.     l_right = m_nItems;
  677.     l_mid   = (l_left + l_right) >> 1;
  678.  
  679.     while( l_left < l_right )
  680.     {
  681.       // No duplicates allowed
  682.       l_code = CompareItem(m_list[l_mid], p_item);
  683.       if( l_code == 0 )
  684.         return false;
  685.  
  686.       if( l_code < 0 )
  687.         l_left = l_mid + 1;
  688.       else
  689.         l_right = l_mid;
  690.  
  691.       l_mid = (l_left + l_right) >> 1;
  692.     }
  693.  
  694.   Add_SkipSearch:
  695.     return InsertItem(l_mid, p_item);
  696.   }
  697.  
  698.   template<typename editem_t, typename edkey_t>
  699.   int CEDKeyList<editem_t, edkey_t>::CompareKey( const editem_t& p_item, const edkey_t p_key )
  700.   {
  701.     return 0;
  702.   }
  703.  
  704.   template<typename editem_t, typename edkey_t>
  705.   int CEDKeyList<editem_t, edkey_t>::CompareItem( const editem_t& p_left, const editem_t& p_right )
  706.   {
  707.     return 0;
  708.   }
  709.  
  710.   template<typename editem_t, typename edkey_t>
  711.   bool CEDKeyList<editem_t, edkey_t>::SwapItem( edu32 p_indexa, edu32 p_indexb )
  712.   {
  713.     editem_t l_tmp;
  714.  
  715.     if( m_list == NULL )
  716.       return false;
  717.  
  718.     if( (p_indexa > m_nItems) || (p_indexb > m_nItems) )
  719.       return false;
  720.  
  721.     l_tmp = m_list[p_indexa];
  722.     m_list[p_indexa] = m_list[p_indexb];
  723.     m_list[p_indexb] = l_tmp;
  724.  
  725.     return true;
  726.   }
  727. #endif

Report this snippet  

Comments

RSS Icon Subscribe to comments
Posted By: edmmapi on June 25, 2009

CEDMemBuf is a general memory allocator which intends to simplify management of dynamic data. Shrink, Grow, InsertGap and DeleteGap are made to work with list classes based on arrays.

CEDKeyList is a template class for sorted data, based on a dynamic array which grows as needed. Every 16th growth, the growth rate doubles until it hits 256. Insertions are sorted using a modified Binary Search algorithm.

By default, CEDKeyList does not allow duplicates. Duplicates work by deriving a CompareItem function which does not return 0. Note that CompareKey must return 0 on a match.

You need to login to post a comment.