1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
#ifndef __UTIL_LOCKED_PQUEUE_H
#define __UTIL_LOCKED_PQUEUE_H
#include <util/locked/queue.H>
namespace Util
{
namespace Locked
{
template <typename _T, typename _K,
bool locked = false, typename _S = int>
class PQueue : public Queue<_T, locked, _S>
{
public:
void insert(_T*);
_T* remove_if(_K&);
private:
void bubbleUp(_T*);
};
template <typename _T, typename _K, bool locked, typename _S>
void PQueue<_T,_K,locked,_S>::insert(_T* item)
{
this->__lock();
if (this->head == NULL)
{
item->next = item->prev = NULL;
this->head = this->tail = item;
}
else
{
item->prev = NULL;
item->next = this->head;
this->head = this->head->prev = item;
bubbleUp(item);
}
this->__unlock();
}
template <typename _T, typename _K, bool locked, typename _S>
_T* PQueue<_T,_K,locked,_S>::remove_if(_K& key)
{
_T* item = NULL;
this->__lock();
if ((this->tail != NULL) && (this->tail->key <= key))
{
item = this->tail;
if (this->head == this->tail)
this->head = this->tail = NULL;
else
this->tail = item->prev;
}
this->__unlock();
return item;
}
template <typename _T, typename _K, bool locked, typename _S>
void PQueue<_T,_K,locked,_S>::bubbleUp(_T* item)
{
if (!item->next)
return;
if (item->next->key <= item->key)
return;
if (this->head == item)
this->head = item->next;
if (this->tail == item->next)
this->tail = item;
_T* temp = item->next;
if (temp->next)
{
temp->next->prev = item;
item->next = item->next->next;
}
else
{
item->next = NULL;
}
if (item->prev)
{
item->prev->next = temp;
temp->prev = item->prev;
}
else
{
temp->prev = NULL;
}
temp->next = item;
item->prev = temp;
bubbleUp(item);
}
};
};
#endif
|
