aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/heap.h40
-rw-r--r--src/itoheap.cpp9
-rw-r--r--src/itoheap.h154
-rw-r--r--src/tests/heap.cpp41
-rw-r--r--src/tests/itoheap.cpp64
5 files changed, 287 insertions, 21 deletions
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
24 { 24 {
25 bool operator()( const item &a, const item &b ) 25 bool operator()( const item &a, const item &b )
26 { 26 {
27 return a <= b; 27 return a < b;
28 } 28 }
29 }; 29 };
30 30
@@ -33,7 +33,7 @@ namespace Bu
33 { 33 {
34 bool operator()( const item &a, const item &b ) 34 bool operator()( const item &a, const item &b )
35 { 35 {
36 return a >= b; 36 return a > b;
37 } 37 }
38 }; 38 };
39 39
@@ -42,7 +42,7 @@ namespace Bu
42 { 42 {
43 bool operator()( const item &a, const item &b ) 43 bool operator()( const item &a, const item &b )
44 { 44 {
45 return *a <= *b; 45 return *a < *b;
46 } 46 }
47 }; 47 };
48 48
@@ -51,7 +51,7 @@ namespace Bu
51 { 51 {
52 bool operator()( const item &a, const item &b ) 52 bool operator()( const item &a, const item &b )
53 { 53 {
54 return *a >= *b; 54 return *a > *b;
55 } 55 }
56 }; 56 };
57 57
@@ -74,7 +74,7 @@ namespace Bu
74 aItem = NULL; 74 aItem = NULL;
75 } 75 }
76 76
77 void push( item i ) 77 void enqueue( item i )
78 { 78 {
79 if( iFill+1 >= iSize ) 79 if( iFill+1 >= iSize )
80 upSize(); 80 upSize();
@@ -96,14 +96,17 @@ namespace Bu
96 } 96 }
97 } 97 }
98 ia.construct( &aItem[iFill], i ); 98 ia.construct( &aItem[iFill], i );
99 for( int j = iFill; j >= 0; ) 99 if( iFill > 0 )
100 { 100 {
101 int k = (j-1)/2; 101 for( int j = iFill; j >= 0; )
102 if( cmp( aItem[k], aItem[j] ) ) 102 {
103 break; 103 int k = (j-1)/2;
104 if( cmp( aItem[k], aItem[j] ) )
105 break;
104 106
105 swap( aItem[k], aItem[j] ); 107 swap( aItem[k], aItem[j] );
106 j = k; 108 j = k;
109 }
107 } 110 }
108 iFill++; 111 iFill++;
109 } 112 }
@@ -115,10 +118,11 @@ namespace Bu
115 return aItem[0]; 118 return aItem[0];
116 } 119 }
117 120
118 void pop() 121 item dequeue()
119 { 122 {
120 if( iFill == 0 ) 123 if( iFill == 0 )
121 throw HeapException("Heap empty."); 124 throw HeapException("Heap empty.");
125 item iRet = aItem[0];
122 int j; 126 int j;
123 for( j = 0; j < iFill; ) 127 for( j = 0; j < iFill; )
124 { 128 {
@@ -138,6 +142,18 @@ namespace Bu
138 aItem[j] = aItem[iFill-1]; 142 aItem[j] = aItem[iFill-1];
139 ia.destroy( &aItem[iFill-1] ); 143 ia.destroy( &aItem[iFill-1] );
140 iFill--; 144 iFill--;
145
146 return iRet;
147 }
148
149 bool isEmpty()
150 {
151 return (iFill==0);
152 }
153
154 int getSize()
155 {
156 return iFill;
141 } 157 }
142 158
143 void print() 159 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 @@
1/*
2 * Copyright (C) 2007-2008 Xagasoft, All rights reserved.
3 *
4 * This file is part of the libbu++ library and is released under the
5 * terms of the license contained in the file LICENSE.
6 */
7
8#include "bu/itoheap.h"
9
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 @@
1/*
2 * Copyright (C) 2007-2008 Xagasoft, All rights reserved.
3 *
4 * This file is part of the libbu++ library and is released under the
5 * terms of the license contained in the file LICENSE.
6 */
7
8#ifndef BU_ITO_HEAP_H
9#define BU_ITO_HEAP_H
10
11#include "bu/heap.h"
12#include "bu/itomutex.h"
13#include "bu/itocondition.h"
14
15namespace Bu
16{
17 class ItoMutex;
18 class ItoCondition;
19
20 template<typename item, typename cmpfunc=__basicLTCmp<item>,
21 typename itemalloc=std::allocator<item> >
22 class ItoHeap
23 {
24 public:
25 ItoHeap()
26 {
27 }
28
29 virtual ~ItoHeap()
30 {
31 }
32
33 void enqueue( item i )
34 {
35 imData.lock();
36 hData.enqueue( i );
37 icBlock.signal();
38 imData.unlock();
39 }
40
41 item dequeue( bool bBlock=false )
42 {
43 imData.lock();
44 if( hData.isEmpty() )
45 {
46 imData.unlock();
47
48 if( bBlock )
49 {
50 icBlock.lock();
51
52 while( hData.isEmpty() )
53 icBlock.wait();
54
55 imData.lock();
56 try
57 {
58 item iRet = hData.dequeue();
59 imData.unlock();
60 icBlock.unlock();
61 return iRet;
62 }
63 catch(...)
64 {
65 imData.unlock();
66 icBlock.unlock();
67 throw;
68 }
69 }
70 throw HeapException("Heap empty.");
71 }
72 else
73 {
74 try
75 {
76 item iRet = hData.dequeue();
77 imData.unlock();
78 return iRet;
79 }
80 catch(...)
81 {
82 imData.unlock();
83 throw;
84 }
85 }
86 }
87
88 item dequeue( int iSec, int iUSec )
89 {
90 imData.lock();
91 if( hData.isEmpty() )
92 {
93 imData.unlock();
94
95 icBlock.lock();
96
97 icBlock.wait( iSec, iUSec );
98
99 imData.lock();
100 try
101 {
102 item iRet = hData.dequeue();
103 imData.unlock();
104 icBlock.unlock();
105 return iRet;
106 }
107 catch(...)
108 {
109 imData.unlock();
110 icBlock.unlock();
111 throw;
112 }
113 }
114 else
115 {
116 try
117 {
118 item iRet = hData.dequeue();
119 imData.unlock();
120 return iRet;
121 }
122 catch(...)
123 {
124 imData.unlock();
125 throw;
126 }
127 }
128 }
129
130 bool isEmpty()
131 {
132 imData.lock();
133 bool bRet = hData.isEmpty();
134 imData.unlock();
135 return bRet;
136 }
137
138 int getSize()
139 {
140 imData.lock();
141 int iRet = hData.getSize();
142 imData.unlock();
143 return iRet;
144 }
145
146 private:
147 Heap< item, cmpfunc, itemalloc > hData;
148 ItoMutex imData;
149 ItoCondition icBlock;
150 };
151};
152
153#endif
154
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 @@
3 3
4#include "bu/heap.h" 4#include "bu/heap.h"
5 5
6typedef struct num
7{
8 num( int iNum, int iOrder ) : iNum( iNum ), iOrder( iOrder )
9 {
10 }
11
12 num( const num &src ) : iNum( src.iNum ), iOrder( src.iOrder )
13 {
14 }
15
16 int iNum;
17 int iOrder;
18
19 bool operator<( const num &oth ) const
20 {
21 if( iNum == oth.iNum )
22 return iOrder < oth.iOrder;
23 return iNum < oth.iNum;
24 }
25 bool operator>( const num &oth ) const
26 {
27 return iNum > oth.iNum;
28 }
29} num;
30
6int main() 31int main()
7{ 32{
8 Bu::Heap<int, Bu::__basicGTCmp<int> > hInt; 33 Bu::Heap<num> hNum;
9 34
10 for( int j = 0; j < 15; j++ ) 35 for( int j = 0; j < 30; j++ )
11 { 36 {
12 int r = rand()%10; 37 int r = rand()%10;
13 printf("Pushing: %d, top: ", r ); 38 printf("Pushing: %d, top: ", r );
14 hInt.push( r ); 39 hNum.enqueue( num( r, j ) );
15 printf("%d\n", hInt.peek() ); 40 printf("%d\n", hNum.peek().iNum );
16 } 41 }
17 42
18 for( int j = 0; j < 15; j++ ) 43 while( !hNum.isEmpty() )
19 { 44 {
20 printf("%d ", hInt.peek() ); 45 printf("(%d:%d) ", hNum.peek().iOrder, hNum.peek().iNum );
21 hInt.pop(); 46 hNum.dequeue();
22 } 47 }
23 printf("\n"); 48 printf("\n");
24
25// hInt.print();
26 49
27 return 0; 50 return 0;
28} 51}
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 @@
1#include <stdio.h>
2#include <stdlib.h>
3
4#include "bu/itoheap.h"
5#include "bu/ito.h"
6
7class Consumer : public Bu::Ito
8{
9public:
10 Consumer()
11 {
12 }
13
14 virtual ~Consumer()
15 {
16 }
17
18 void *run()
19 {
20 for( int j = 0; j < 10; j++ )
21 {
22 printf("Trying to read [%d].\n", j );
23
24 try
25 {
26 int iNum = hInt.dequeue( 0, 500000 );
27 printf("Read %d\n", iNum );
28 }
29 catch( Bu::HeapException &e )
30 {
31 printf("Nothing yet...\n");
32 }
33 }
34
35 return NULL;
36 }
37
38 Bu::ItoHeap<int> hInt;
39};
40
41
42int main()
43{
44 Consumer c;
45
46 for( int j = 0; j < 3; j++ )
47 {
48 int iNum = rand()%10;
49 printf("Enqueuing %d.\n", iNum );
50 c.hInt.enqueue( iNum );
51 }
52
53 printf("Sarting consumer.\n");
54 c.start();
55
56 for( int j = 0; j < 5; j++ )
57 {
58 sleep( 1 );
59 int iNum = rand()%10;
60 printf("Enqueuing %d.\n", iNum );
61 c.hInt.enqueue( iNum );
62 }
63}
64
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-11 14:11:52 +0000