8000 Merge branch 'hotfix/60' into develop · zendframework/zend-stdlib@b4d1950 · GitHub
[go: up one dir, main page]
Skip to content
This repository was archived by the owner on Jan 31, 2020. It is now read-only.

Commit b4d1950

Browse files
weierophinneyweierophinney
committed
Merge branch 'hotfix/60' into develop
Conflicts: test/StringWrapper/CommonStringWrapperTest.php
2 parents c0404b3 + e392d54 commit b4d1950

File tree

3 files changed

+94
-7
lines changed

3 files changed

+94
-7
lines changed

‎CHANGELOG.md

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -36,7 +36,11 @@ All notable changes to this project will be documented in this file, in reverse
3636

3737
### Fixed
3838

39-
- Nothing.
39+
- [#60](https://github.com/zendframework/zend-stdlib/pull/60) fixes an issue whereby calling `remove()` would
40+
incorrectly re-calculate the maximum priority stored in the queue.
41+
42+
- [#60](https://github.com/zendframework/zend-stdlib/pull/60) fixes an infinite loop condition that can occur when
43+
inserting an item at 0 priority.
4044

4145
## 3.1.0 - 2016-09-13
4246

‎src/FastPriorityQueue.php

Lines changed: 34 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -57,9 +57,9 @@ class FastPriorityQueue implements Iterator, Countable, Serializable
5757
/**
5858
* Max priority
5959
*
60-
* @var integer
60+
* @var integer|null
6161
*/
62-
protected $maxPriority = 0;
62+
protected $maxPriority = null;
6363

6464
/**
6565
* Total number of elements in the queue
@@ -86,7 +86,7 @@ class FastPriorityQueue implements Iterator, Countable, Serializable
8686
* Insert an element in the queue with a specified priority
8787
*
8888
* @param mixed $value
89-
* @param integer $priority a positive integer
89+
* @param integer $priority
9090
*/
9191
public function insert($value, $priority)
9292
{
@@ -96,7 +96,7 @@ public function insert($value, $priority)
9696
$this->values[$priority][] = $value;
9797
if (! isset($this->priorities[$priority])) {
9898
$this->priorities[$priority] = $priority;
99-
$this->maxPriority = max($priority, $this->maxPriority);
99+
$this->maxPriority = $this->maxPriority === null ? $priority : max($priority, $this->maxPriority);
100100
}
101101
++$this->count;
102102
}
@@ -132,11 +132,35 @@ public function extract()
132132
*/
133133
public function remove($datum)
134134
{
135+
$currentIndex = $this->index;
136+
$currentSubIndex = $this->subIndex;
137+
$currentPriority = $this->maxPriority;
138+
135139
$this->rewind();
136140
while ($this->valid()) {
137141
if (current($this->values[$this->maxPriority]) === $datum) {
138142
$index = key($this->values[$this->maxPriority]);
139143
unset($this->values[$this->maxPriority][$index]);
144+
145+
// The `next()` method advances the internal array pointer, so we need to use the `reset()` function,
146+
// otherwise we would lose all elements before the place the pointer points.
147+
reset($this->values[$this->maxPriority]);
148+
149+
$this->index = $currentIndex;
150+
$this->subIndex = $currentSubIndex;
151+
152+
// If the array is empty we need to destroy the unnecessary priority,
153+
// otherwise we would end up with an incorrect value of `$this->count`
154+
// {@see \Zend\Stdlib\FastPriorityQueue::nextAndRemove()}.
155+
if (empty($this->values[$this->maxPriority])) {
156+
unset($this->values[$this->maxPriority]);
157+
unset($this->priorities[$this->maxPriority]);
158+
if ($this->maxPriority === $currentPriority) {
159+
$this->subIndex = 0;
160+
}
161+
}
162+
163+
$this->maxPriority = empty($this->priorities) ? null : max($this->priorities);
140164
--$this->count;
141165
return true;
142166
}
@@ -191,11 +215,15 @@ public function key()
191215
*/
192216
protected function nextAndRemove()
193217
{
218+
$key = key($this->values[$this->maxPriority]);
219+
194220
if (false === next($this->values[$this->maxPriority])) {
195221
unset($this->priorities[$this->maxPriority]);
196222
unset($this->values[$this->maxPriority]);
197-
$this->maxPriority = empty($this->priorities) ? 0 : max($this->priorities);
223+
$this->maxPriority = empty($this->priorities) ? null : max($this->priorities);
198224
$this->subIndex = -1;
225+
} else {
226+
unset($this->values[$this->maxPriority][$key]);
199227
}
200228
++$this->index;
201229
++$this->subIndex;
@@ -211,7 +239,7 @@ public function next()
211239
if (false === next($this->values[$this->maxPriority])) {
212240
unset($this->subPriorities[$this->maxPriority]);
213241
reset($this->values[$this->maxPriority]);
214-
$this->maxPriority = empty($this->subPriorities) ? 0 : max($this->subPriorities);
242+
$this->maxPriority = empty($this->subPriorities) ? null : max($this->subPriorities);
215243
$this->subIndex = -1;
216244
}
217245
++$this->index;

‎test/FastPriorityQueueTest.php

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -290,4 +290,59 @@ public function testIterativelyRemovingItemsShouldRemoveAllItems()
290290
$this->assertFalse($queue->contains($listener), sprintf('Listener %s remained in queue', $i));
291291
}
292292
}
293+
294+
public function testRemoveShouldNotAffectExtract()
295+
{
296+
// Removing an element with low priority
297+
$queue = new FastPriorityQueue();
298+
$queue->insert('a1', 1);
299+
$queue->insert('a2', 1);
300+
$queue->insert('b', 2);
301+
$queue->remove('a1');
302+
$expected = ['b', 'a2'];
303+
$test = [];
304+
while ($value = $queue->extract()) {
305+
$test[] = $value;
306+
}
307+
$this->assertEquals($expected, $test);
308+
$this->assertTrue($queue->isEmpty());
309+
310+
// Removing an element in the middle of a set of elements with the same priority
311+
$queue->insert('a1', 1);
312+
$queue->insert('a2', 1);
313+
$queue->insert('a3', 1);
314+
$queue->remove('a2');
315+
$expected = ['a1', 'a3'];
316+
$test = [];
317+
while ($value = $queue->extract()) {
318+
$test[] = $value;
319+
}
320+
$this->assertEquals($expected, $test);
321+
$this->assertTrue($queue->isEmpty());
322+
323+
// Removing an element with high priority
324+
$queue->insert('a', 1);
325+
$queue->insert('b', 2);
326+
$queue->remove('b');
327+
$expected = ['a'];
328+
$test = [];
329+
while ($value = $queue->extract()) {
330+
$test[] = $value;
331+
}
332+
$this->assertEquals($expected, $test);
333+
$this->assertTrue($queue->isEmpty());
334+
}
335+
336+
public function testZeroPriority()
337+
{
338+
$queue = new FastPriorityQueue();
339+
$queue->insert('a', 0);
340+
$queue->insert('b', 1);
341+
$expected = ['b', 'a'];
342+
$test = [];
343+
foreach ($queue as $value) {
344+
$test[] = $value;
345+
}
346+
$this->assertEquals($expected, $test);
347+
}
293348
}

0 commit comments

Comments
 (0)
0