From a4c22303b1044eee5ccbf0766895a879a8f4810e Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Tue, 19 Feb 2008 21:51:48 +0000 Subject: Oops. I made the Bu::Heap API look like a stack, not a queue, that's been fixed, and the Bu::ItoHeap is working and tested. Note that when multiple items have the same sort order, they will come out in random order. --- build.conf | 3 +- src/heap.h | 40 +++++++++---- src/itoheap.cpp | 9 +++ src/itoheap.h | 154 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/tests/heap.cpp | 41 +++++++++++--- src/tests/itoheap.cpp | 64 +++++++++++++++++++++ 6 files changed, 289 insertions(+), 22 deletions(-) create mode 100644 src/tests/itoheap.cpp diff --git a/build.conf b/build.conf index e3603ae..31d33a8 100644 --- a/build.conf +++ b/build.conf @@ -45,7 +45,8 @@ filesIn("src/tests") filter regexp("^src/tests/(.*)\\.cpp$", "tests/{re:1}"): set "LDFLAGS" += "-L. -lbu++", input "src/{target}.cpp" -["tests/itoqueue1", "tests/itoqueue2", "tests/socketblock", "tests/itoserver"]: +["tests/itoqueue1", "tests/itoqueue2", "tests/socketblock", "tests/itoserver", + "tests/itoheap"]: set "LDFLAGS" += "-lpthread" filesIn("src/unit") filter regexp("^src/unit/(.*)\\.cpp$", "unit/{re:1}"): diff --git a/src/heap.h b/src/heap.h index f276157..dd2764f 100644 --- a/src/heap.h +++ b/src/heap.h @@ -24,7 +24,7 @@ namespace Bu { bool operator()( const item &a, const item &b ) { - return a <= b; + return a < b; } }; @@ -33,7 +33,7 @@ namespace Bu { bool operator()( const item &a, const item &b ) { - return a >= b; + return a > b; } }; @@ -42,7 +42,7 @@ namespace Bu { bool operator()( const item &a, const item &b ) { - return *a <= *b; + return *a < *b; } }; @@ -51,7 +51,7 @@ namespace Bu { bool operator()( const item &a, const item &b ) { - return *a >= *b; + return *a > *b; } }; @@ -74,7 +74,7 @@ namespace Bu aItem = NULL; } - void push( item i ) + void enqueue( item i ) { if( iFill+1 >= iSize ) upSize(); @@ -96,14 +96,17 @@ namespace Bu } } ia.construct( &aItem[iFill], i ); - for( int j = iFill; j >= 0; ) + if( iFill > 0 ) { - int k = (j-1)/2; - if( cmp( aItem[k], aItem[j] ) ) - break; + for( int j = iFill; j >= 0; ) + { + int k = (j-1)/2; + if( cmp( aItem[k], aItem[j] ) ) + break; - swap( aItem[k], aItem[j] ); - j = k; + swap( aItem[k], aItem[j] ); + j = k; + } } iFill++; } @@ -115,10 +118,11 @@ namespace Bu return aItem[0]; } - void pop() + item dequeue() { if( iFill == 0 ) throw HeapException("Heap empty."); + item iRet = aItem[0]; int j; for( j = 0; j < iFill; ) { @@ -138,6 +142,18 @@ namespace Bu aItem[j] = aItem[iFill-1]; ia.destroy( &aItem[iFill-1] ); iFill--; + + return iRet; + } + + bool isEmpty() + { + return (iFill==0); + } + + int getSize() + { + return iFill; } void print() diff --git a/src/itoheap.cpp b/src/itoheap.cpp index e69de29..f4582bc 100644 --- a/src/itoheap.cpp +++ b/src/itoheap.cpp @@ -0,0 +1,9 @@ +/* + * Copyright (C) 2007-2008 Xagasoft, All rights reserved. + * + * This file is part of the libbu++ library and is released under the + * terms of the license contained in the file LICENSE. + */ + +#include "bu/itoheap.h" + diff --git a/src/itoheap.h b/src/itoheap.h index e69de29..59a8158 100644 --- a/src/itoheap.h +++ b/src/itoheap.h @@ -0,0 +1,154 @@ +/* + * Copyright (C) 2007-2008 Xagasoft, All rights reserved. + * + * This file is part of the libbu++ library and is released under the + * terms of the license contained in the file LICENSE. + */ + +#ifndef BU_ITO_HEAP_H +#define BU_ITO_HEAP_H + +#include "bu/heap.h" +#include "bu/itomutex.h" +#include "bu/itocondition.h" + +namespace Bu +{ + class ItoMutex; + class ItoCondition; + + template, + typename itemalloc=std::allocator > + class ItoHeap + { + public: + ItoHeap() + { + } + + virtual ~ItoHeap() + { + } + + void enqueue( item i ) + { + imData.lock(); + hData.enqueue( i ); + icBlock.signal(); + imData.unlock(); + } + + item dequeue( bool bBlock=false ) + { + imData.lock(); + if( hData.isEmpty() ) + { + imData.unlock(); + + if( bBlock ) + { + icBlock.lock(); + + while( hData.isEmpty() ) + icBlock.wait(); + + imData.lock(); + try + { + item iRet = hData.dequeue(); + imData.unlock(); + icBlock.unlock(); + return iRet; + } + catch(...) + { + imData.unlock(); + icBlock.unlock(); + throw; + } + } + throw HeapException("Heap empty."); + } + else + { + try + { + item iRet = hData.dequeue(); + imData.unlock(); + return iRet; + } + catch(...) + { + imData.unlock(); + throw; + } + } + } + + item dequeue( int iSec, int iUSec ) + { + imData.lock(); + if( hData.isEmpty() ) + { + imData.unlock(); + + icBlock.lock(); + + icBlock.wait( iSec, iUSec ); + + imData.lock(); + try + { + item iRet = hData.dequeue(); + imData.unlock(); + icBlock.unlock(); + return iRet; + } + catch(...) + { + imData.unlock(); + icBlock.unlock(); + throw; + } + } + else + { + try + { + item iRet = hData.dequeue(); + imData.unlock(); + return iRet; + } + catch(...) + { + imData.unlock(); + throw; + } + } + } + + bool isEmpty() + { + imData.lock(); + bool bRet = hData.isEmpty(); + imData.unlock(); + return bRet; + } + + int getSize() + { + imData.lock(); + int iRet = hData.getSize(); + imData.unlock(); + return iRet; + } + + private: + Heap< item, cmpfunc, itemalloc > hData; + ItoMutex imData; + ItoCondition icBlock; + }; +}; + +#endif + diff --git a/src/tests/heap.cpp b/src/tests/heap.cpp index 3217715..e35ea2a 100644 --- a/src/tests/heap.cpp +++ b/src/tests/heap.cpp @@ -3,26 +3,49 @@ #include "bu/heap.h" +typedef struct num +{ + num( int iNum, int iOrder ) : iNum( iNum ), iOrder( iOrder ) + { + } + + num( const num &src ) : iNum( src.iNum ), iOrder( src.iOrder ) + { + } + + int iNum; + int iOrder; + + bool operator<( const num &oth ) const + { + if( iNum == oth.iNum ) + return iOrder < oth.iOrder; + return iNum < oth.iNum; + } + bool operator>( const num &oth ) const + { + return iNum > oth.iNum; + } +} num; + int main() { - Bu::Heap > hInt; + Bu::Heap hNum; - for( int j = 0; j < 15; j++ ) + for( int j = 0; j < 30; j++ ) { int r = rand()%10; printf("Pushing: %d, top: ", r ); - hInt.push( r ); - printf("%d\n", hInt.peek() ); + hNum.enqueue( num( r, j ) ); + printf("%d\n", hNum.peek().iNum ); } - for( int j = 0; j < 15; j++ ) + while( !hNum.isEmpty() ) { - printf("%d ", hInt.peek() ); - hInt.pop(); + printf("(%d:%d) ", hNum.peek().iOrder, hNum.peek().iNum ); + hNum.dequeue(); } printf("\n"); - -// hInt.print(); return 0; } diff --git a/src/tests/itoheap.cpp b/src/tests/itoheap.cpp new file mode 100644 index 0000000..67169e7 --- /dev/null +++ b/src/tests/itoheap.cpp @@ -0,0 +1,64 @@ +#include +#include + +#include "bu/itoheap.h" +#include "bu/ito.h" + +class Consumer : public Bu::Ito +{ +public: + Consumer() + { + } + + virtual ~Consumer() + { + } + + void *run() + { + for( int j = 0; j < 10; j++ ) + { + printf("Trying to read [%d].\n", j ); + + try + { + int iNum = hInt.dequeue( 0, 500000 ); + printf("Read %d\n", iNum ); + } + catch( Bu::HeapException &e ) + { + printf("Nothing yet...\n"); + } + } + + return NULL; + } + + Bu::ItoHeap hInt; +}; + + +int main() +{ + Consumer c; + + for( int j = 0; j < 3; j++ ) + { + int iNum = rand()%10; + printf("Enqueuing %d.\n", iNum ); + c.hInt.enqueue( iNum ); + } + + printf("Sarting consumer.\n"); + c.start(); + + for( int j = 0; j < 5; j++ ) + { + sleep( 1 ); + int iNum = rand()%10; + printf("Enqueuing %d.\n", iNum ); + c.hInt.enqueue( iNum ); + } +} + -- cgit v1.2.3