Posted By

edmmapi on 06/25/09


Tagged


Versions (?)

Epic Delusions Multimedia API: Key List Template Class


 / Published in: C++
 

  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.