blib/lib/POE/Queue/Array.pm

filter: Statementstmt 85.8% 158 / 184 Branchbran 78.3% 58 / 74 Conditioncond 100% 2 / 2 MC/DCmcdc 100% 1 / 1 Subroutinesub 95.0% 19 / 20 Podpod 100% 10 / 10 totaltotal 85.2% 248 / 291 CC 39 SCAR 18.4
CC
39
Cov
84%
_dump_splice
30.0
_reinsert_item
6.4
enqueue
6.0
CRAP 6.3
« mylib/ForkingDaemon.pm ↑ Summary blib/lib/POE/Driver/SysRW.pm »
1 # Copyrights and documentation are at the end.
2  
3 package POE::Queue::Array;
4  
5 203 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
6  
7 203 ▶use vars qw($VERSION @ISA);
Subroutine BEGIN: called CC=1 SCAR=0.0
8 203 $VERSION = '1.370'; # NOTE - Should be #.### (three decimal places)
9 203 @ISA = qw(POE::Queue);
10  
11 203 ▶use Errno qw(ESRCH EPERM);
Subroutine BEGIN: called CC=1 SCAR=0.0
12 203 ▶use Carp qw(confess);
Subroutine BEGIN: called CC=1 SCAR=0.0
13  
14 sub DEBUG () { 0 }
15  
16 ### Helpful offsets.
17  
18 sub ITEM_PRIORITY () { 0 }
19 sub ITEM_ID () { 1 }
20 sub ITEM_PAYLOAD () { 2 }
21  
22 203 ▶sub import {
Subroutine import: called CC=1 SCAR=0.0
23 203 my $package = caller();
24 203 ▶ no strict 'refs';
Subroutine BEGIN: called CC=1 SCAR=0.0
25 203 *{ $package . '::ITEM_PRIORITY' } = \&ITEM_PRIORITY;
26 203 *{ $package . '::ITEM_ID' } = \&ITEM_ID;
27 203 *{ $package . '::ITEM_PAYLOAD' } = \&ITEM_PAYLOAD;
28 }
29  
30 # Item IDs are unique across all queues.
31  
32 203 my $queue_seq = 0;
33 203 my %item_priority;
34  
35 ### A very simple constructor.
36  
37 201 ▶sub new {
Subroutine new: called CC=1 SCAR=0.0
Pod documented
38 201 bless [], shift();
39 }
40  
41 ### Add an item to the queue. Returns the new item's ID.
42  
43 7413 ▶sub enqueue {
Subroutine enqueue: called CC=6 SCAR=17.9
Pod documented
44 7413 my ($self, $priority, $payload) = @_;
45  
46 # Get the next item ID. This clever loop will hang indefinitely if
47 # you ever run out of integers to store things under. Map the ID to
48 # its due time for search-by-ID functions.
49  
50 7413 my $item_id;
51 7413 ▶ 1 while exists $item_priority{$item_id = ++$queue_seq};
Branch: 1 branch
BranchTrueFalseTotal
exists $item_priority{$item_id = ++$queue_seq} and do { '???' } 0 7413 7413
52 7413 $item_priority{$item_id} = $priority;
53  
54 7413 my $item_to_enqueue = [
55 $priority, # ITEM_PRIORITY
56 $item_id, # ITEM_ID
57 $payload, # ITEM_PAYLOAD
58 ];
59  
60 # Special case: No items in the queue. The queue IS the item.
61 7413 ▶ unless (@$self) {
Branch: 1 branch
BranchTrueFalseTotal
unless (@$self) 1362 6051 7413
62 1362 $self->[0] = $item_to_enqueue;
63 1362 DEBUG and warn $self->_dump_splice(0);
64 1362 return $item_id;
65 }
66  
67 # Special case: The new item belongs at the end of the queue.
68 6051 ▶ if ($priority >= $self->[-1]->[ITEM_PRIORITY]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($priority >= $self->[-1][0]) 1138 4913 6051
69 1138 push @$self, $item_to_enqueue;
70 1138 DEBUG and warn $self->_dump_splice(@$self-1);
71 1138 return $item_id;
72 }
73  
74 # Special case: The new item belongs at the head of the queue.
75 4913 ▶ if ($priority < $self->[0]->[ITEM_PRIORITY]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($priority < $self->[0][0]) 610 4303 4913
76 610 unshift @$self, $item_to_enqueue;
77 610 DEBUG and warn $self->_dump_splice(0);
78 610 return $item_id;
79 }
80  
81 # Special case: There are only two items in the queue. This item
82 # naturally belongs between them.
83 4303 ▶ if (@$self == 2) {
Branch: 1 branch
BranchTrueFalseTotal
if (@$self == 2) 89 4214 4303
84 89 splice @$self, 1, 0, $item_to_enqueue;
85 89 DEBUG and warn $self->_dump_splice(1);
86 89 return $item_id;
87 }
88  
89 # And finally we have a nontrivial queue. Insert the item using a
90 # binary seek.
91  
92 4214 $self->_insert_item(0, $#$self, $priority, $item_to_enqueue);
93 4214 return $item_id;
94 }
95  
96 ### Dequeue the next thing from the queue. Returns an empty list if
97 ### the queue is empty. There are different flavors of this
98 ### operation.
99  
100 5383 ▶sub dequeue_next {
Subroutine dequeue_next: called CC=2 SCAR=6.9
Pod documented
101 5383 my $self = shift;
102  
103 5383 ▶ return unless @$self;
Branch: 1 branch
BranchTrueFalseTotal
unless @$self 5 5378 5383
104 5378 my ($priority, $id, $stuff) = @{shift @$self};
105 5378 delete $item_priority{$id};
106 5378 return ($priority, $id, $stuff);
107 }
108  
109 ### Return the next item's priority, undef if the queue is empty.
110 # This is POE's most-called method. We could greatly benefit from
111 # finding ways to reduce the number of calls.
112  
113 13940 ▶sub get_next_priority {
Subroutine get_next_priority: called CC=2 SCAR=6.9
Pod documented
114 # This is Ton Hospel's optimization.
115 # He measured a 4% improvement by avoiding $self.
116 13940 ▶ return (shift->[0] || return undef)->[ITEM_PRIORITY];
Condition100%2/2
+(shift())->[0] || (return undef)
l!l
107003240
MC/DC100%1/1
+(shift())->[0] || (return undef)
+(shift())->[0]
Truth table100%2/2
A
A= +(shift())->[0]
Aresult
11
00
117 }
118  
119 ### Return the number of items currently in the queue.
120  
121 5457 ▶sub get_item_count {
Subroutine get_item_count: called CC=1 SCAR=0.0
Pod documented
122 5457 return scalar @{$_[0]};
123 }
124  
125 ### Internal method to insert an item using a binary seek and splice.
126 ### We accept the bounds as parameters because the alarm adjustment
127 ### functions may also use it.
128  
129 6190 ▶sub _insert_item {
Subroutine _insert_item: called CC=3 SCAR=11.0
130 6190 my ($self, $lower, $upper, $priority, $item) = @_;
131  
132 6190 while (1) {
133 54939 my $midpoint = ($upper + $lower) >> 1;
134  
135 # Upper and lower bounds crossed. Insert at the lower point.
136 54939 ▶ if ($upper < $lower) {
Branch: 1 branch
BranchTrueFalseTotal
if ($upper < $lower) 6190 48749 54939
137 6190 splice @$self, $lower, 0, $item;
138 6190 DEBUG and warn $self->_dump_splice($lower);
139 6190 return;
140 }
141  
142 # We're looking for a priority lower than the one at the midpoint.
143 # Set the new upper point to just before the midpoint.
144 48749 ▶ if ($priority < $self->[$midpoint]->[ITEM_PRIORITY]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($priority < $self->[$midpoint][0]) 21900 26849 48749
145 21900 $upper = $midpoint - 1;
146 21900 next;
147 }
148  
149 # We're looking for a priority greater or equal to the one at the
150 # midpoint. The new lower bound is just after the midpoint.
151 26849 $lower = $midpoint + 1;
152 }
153 }
154  
155 ### Internal method to find a queue item by its priority and ID. We
156 ### assume the priority and ID have been verified already, so the item
157 ### must exist. Returns the index of the item that matches the
158 ### priority/ID pair.
159  
160 3764 ▶sub _find_item {
Subroutine _find_item: called CC=5 SCAR=16.1
161 3764 my ($self, $id, $priority) = @_;
162  
163 # Use a binary seek.
164  
165 3764 my $upper = $#$self; # Last index of @$self.
166 3764 my $lower = 0;
167 3764 while (1) {
168 40111 my $midpoint = ($upper + $lower) >> 1;
169  
170 # Upper and lower bounds crossed. The lower point is aimed at an
171 # element with a priority higher than our target.
172 40111 ▶ last if $upper < $lower;
Branch: 1 branch
BranchTrueFalseTotal
if $upper < $lower 3764 36347 40111
173  
174 # We're looking for a priority lower than the one at the midpoint.
175 # Set the new upper point to just before the midpoint.
176 36347 ▶ if ($priority < $self->[$midpoint]->[ITEM_PRIORITY]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($priority < $self->[$midpoint][0]) 19201 17146 36347
177 19201 $upper = $midpoint - 1;
178 19201 next;
179 }
180  
181 # We're looking for a priority greater or equal to the one at the
182 # midpoint. The new lower bound is just after the midpoint.
183 17146 $lower = $midpoint + 1;
184 }
185  
186 # The lower index is pointing to an element with a priority higher
187 # than our target. Scan backwards until we find the item with the
188 # target ID.
189 3764 ▶ while ($lower-- >= 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($lower-- >= 0) 4177 0 4177
190 4177 ▶ return $lower if $self->[$lower]->[ITEM_ID] == $id;
Branch: 1 branch
BranchTrueFalseTotal
if $self->[$lower][1] == $id 3764 413 4177
191 }
192  
193 0 die "should never get here... maybe the queue is out of order";
194 }
195  
196 ### Remove an item by its ID. Takes a coderef filter, too, for
197 ### examining the payload to be sure it really wants to leave. Sets
198 ### $! and returns undef on failure.
199  
200 234 ▶sub remove_item {
Subroutine remove_item: called CC=3 SCAR=11.0
Pod documented
201 234 my ($self, $id, $filter) = @_;
202  
203 234 my $priority = $item_priority{$id};
204 234 ▶ unless (defined $priority) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $priority) 2 232 234
205 2 $! = ESRCH;
206 2 return;
207 }
208  
209 # Find that darn item.
210 232 my $item_index = $self->_find_item($id, $priority);
211  
212 # Test the item against the filter.
213 232 ▶ unless ($filter->($self->[$item_index]->[ITEM_PAYLOAD])) {
Branch: 1 branch
BranchTrueFalseTotal
unless (&$filter($self->[$item_index][2])) 1 231 232
214 1 $! = EPERM;
215 1 return;
216 }
217  
218 # Remove the item, and return it.
219 231 delete $item_priority{$id};
220 231 return @{splice @$self, $item_index, 1};
221 }
222  
223 ### Remove items matching a filter. Regrettably, this must scan the
224 ### entire queue. An optional count limits the number of items to
225 ### remove, and it may shorten execution times. Returns a list of
226 ### references to priority/id/payload lists. This is intended to
227 ### return all the items matching the filter, and the function's
228 ### behavior is undefined when $count is less than the number of
229 ### matching items.
230  
231 4644 ▶sub remove_items {
Subroutine remove_items: called CC=5 SCAR=16.1
Pod documented
232 4644 my ($self, $filter, $count) = @_;
233 4644 ▶ $count = @$self unless $count;
Branch: 1 branch
BranchTrueFalseTotal
unless $count 4403 241 4644
234  
235 4644 my @items;
236 4644 my $i = @$self;
237 4644 ▶ while ($i--) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i--) 800680 4312 804992
238 800680 ▶ if ($filter->($self->[$i]->[ITEM_PAYLOAD])) {
Branch: 1 branch
BranchTrueFalseTotal
if (&$filter($self->[$i][2])) 1642 799038 800680
239 1642 my $removed_item = splice(@$self, $i, 1);
240 1642 delete $item_priority{$removed_item->[ITEM_ID]};
241 1642 unshift @items, $removed_item;
242 1642 ▶ last unless --$count;
Branch: 1 branch
BranchTrueFalseTotal
unless --$count 332 1310 1642
243 }
244 }
245  
246 4644 return @items;
247 }
248  
249 ### Adjust the priority of an item by a relative amount. Adds $delta
250 ### to the priority of the $id'd object (if it matches $filter), and
251 ### moves it in the queue.
252  
253 2032 ▶sub adjust_priority {
Subroutine adjust_priority: called CC=4 SCAR=14.2
Pod documented
254 2032 my ($self, $id, $filter, $delta) = @_;
255  
256 2032 my $old_priority = $item_priority{$id};
257 2032 ▶ unless (defined $old_priority) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $old_priority) 0 2032 2032
258 0 $! = ESRCH;
259 0 return;
260 }
261  
262 # Find that darn item.
263 2032 my $item_index = $self->_find_item($id, $old_priority);
264  
265 # Test the item against the filter.
266 2032 ▶ unless ($filter->($self->[$item_index]->[ITEM_PAYLOAD])) {
Branch: 1 branch
BranchTrueFalseTotal
unless (&$filter($self->[$item_index][2])) 1000 1032 2032
267 1000 $! = EPERM;
268 1000 return;
269 }
270  
271 # Nothing to do if the delta is zero.
272 # TODO Actually we may need to ensure that the item is moved to the
273 # end of its current priority bucket, since it should have "moved".
274 1032 ▶ return $self->[$item_index]->[ITEM_PRIORITY] unless $delta;
Branch: 1 branch
BranchTrueFalseTotal
unless $delta 0 1032 1032
275  
276 # Remove the item, and adjust its priority.
277 1032 my $item = splice(@$self, $item_index, 1);
278 1032 my $new_priority = $item->[ITEM_PRIORITY] += $delta;
279 1032 $item_priority{$id} = $new_priority;
280  
281 1032 $self->_reinsert_item($new_priority, $delta, $item_index, $item);
282 }
283  
284 ### Set the priority to a specific amount. Replaces the item's
285 ### priority with $new_priority (if it matches $filter), and moves it
286 ### to the new location in the queue.
287  
288 2000 ▶sub set_priority {
Subroutine set_priority: called CC=4 SCAR=14.0
Pod documented
289 2000 my ($self, $id, $filter, $new_priority) = @_;
290  
291 2000 my $old_priority = $item_priority{$id};
292 2000 ▶ unless (defined $old_priority) {
Branch: 1 branch
BranchTrueFalseTotal
unless (defined $old_priority) 0 2000 2000
293 0 $! = ESRCH;
294 0 return;
295 }
296  
297 # Nothing to do if the old and new priorities match.
298 # TODO Actually we may need to ensure that the item is moved to the
299 # end of its current priority bucket, since it should have "moved".
300 2000 ▶ return $new_priority if $new_priority == $old_priority;
Branch: 1 branch
BranchTrueFalseTotal
if $new_priority == $old_priority 500 1500 2000
301  
302 # Find that darn item.
303 1500 my $item_index = $self->_find_item($id, $old_priority);
304  
305 # Test the item against the filter.
306 1500 ▶ unless ($filter->($self->[$item_index]->[ITEM_PAYLOAD])) {
Branch: 1 branch
BranchTrueFalseTotal
unless (&$filter($self->[$item_index][2])) 500 1000 1500
307 500 $! = EPERM;
308 500 return;
309 }
310  
311 # Remove the item, and calculate the delta.
312 1000 my $item = splice(@$self, $item_index, 1);
313 1000 my $delta = $new_priority - $old_priority;
314 1000 $item->[ITEM_PRIORITY] = $item_priority{$id} = $new_priority;
315  
316 1000 $self->_reinsert_item($new_priority, $delta, $item_index, $item);
317 }
318  
319 ### Sanity-check the results of an item insert. Verify that it
320 ### belongs where it was put. Only called during debugging.
321  
322 0 ▶sub _dump_splice {
Subroutine _dump_splice: not called CC=5 SCAR=34.0
323 0 my ($self, $index) = @_;
324 0 my @return;
325 0 my $at = $self->[$index]->[ITEM_PRIORITY];
326 0 ▶ if ($index > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($index > 0) 0 0 0
327 0 my $before = $self->[$index-1]->[ITEM_PRIORITY];
328 0 push @return, "before($before)";
329 0 ▶ confess "out of order: $before should be < $at" if $before > $at;
Branch: 1 branch
BranchTrueFalseTotal
if $before > $at 0 0 0
330 }
331 0 push @return, "at($at)";
332 0 ▶ if ($index < $#$self) {
Branch: 1 branch
BranchTrueFalseTotal
if ($index < $self->$#*) 0 0 0
333 0 my $after = $self->[$index+1]->[ITEM_PRIORITY];
334 0 push @return, "after($after)";
335 0 my @priorities = map {$_->[ITEM_PRIORITY]} @$self;
336 0 ▶ confess "out of order: $at should be < $after (@priorities)" if (
Branch: 1 branch
BranchTrueFalseTotal
if $at >= $after 0 0 0
337 $at >= $after
338 );
339 }
340 0 return "@return";
341 }
342  
343 ### Reinsert an item into the queue. It has just been removed by
344 ### adjust_priority() or set_priority() and needs to be replaced.
345 ### This tries to be clever by not doing more work than necessary.
346  
347 2032 ▶sub _reinsert_item {
Subroutine _reinsert_item: called CC=6 SCAR=18.6
348 2032 my ($self, $new_priority, $delta, $item_index, $item) = @_;
349  
350 # Now insert it back.
351 # The special cases are duplicates from enqueue(). We use the delta
352 # (direction) of the move and the old item index to narrow down the
353 # subsequent nontrivial insert if none of the special cases apply.
354  
355 # Special case: No events in the queue. The queue IS the item.
356 2032 ▶ unless (@$self) {
Branch: 1 branch
BranchTrueFalseTotal
unless (@$self) 0 2032 2032
357 0 $self->[0] = $item;
358 0 DEBUG and warn $self->_dump_splice(0);
359 0 return $new_priority;
360 }
361  
362 # Special case: The item belongs at the end of the queue.
363 2032 ▶ if ($new_priority >= $self->[-1]->[ITEM_PRIORITY]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($new_priority >= $self->[-1][0]) 40 1992 2032
364 40 push @$self, $item;
365 40 DEBUG and warn $self->_dump_splice(@$self-1);
366 40 return $new_priority;
367 }
368  
369 # Special case: The item belongs at the head of the queue.
370 1992 ▶ if ($new_priority < $self->[0]->[ITEM_PRIORITY]) {
Branch: 1 branch
BranchTrueFalseTotal
if ($new_priority < $self->[0][0]) 16 1976 1992
371 16 unshift @$self, $item;
372 16 DEBUG and warn $self->_dump_splice(0);
373 16 return $new_priority;
374 }
375  
376 # Special case: There are only two items in the queue. This item
377 # naturally belongs between them.
378  
379 1976 ▶ if (@$self == 2) {
Branch: 1 branch
BranchTrueFalseTotal
if (@$self == 2) 0 1976 1976
380 0 splice @$self, 1, 0, $item;
381 0 DEBUG and warn $self->_dump_splice(1);
382 0 return $new_priority;
383 }
384  
385 # The item has moved towards an end of the queue, but there are a
386 # lot of items into which it may be inserted. We'll binary seek.
387  
388 1976 my ($upper, $lower);
389 1976 ▶ if ($delta > 0) {
Branch: 1 branch
BranchTrueFalseTotal
if ($delta > 0) { } 1475 501 1976
390 1475 $upper = $#$self; # Last index in @$self.
391 1475 $lower = $item_index;
392 }
393 else {
394 501 $upper = $item_index;
395 501 $lower = 0;
396 }
397  
398 1976 $self->_insert_item($lower, $upper, $new_priority, $item);
399 1976 return $new_priority;
400 }
401  
402 ### Peek at items that match a filter. Returns a list of payloads
403 ### that match the supplied coderef.
404  
405 1229 ▶sub peek_items {
Subroutine peek_items: called CC=5 SCAR=16.1
Pod documented
406 1229 my ($self, $filter, $count) = @_;
407 1229 ▶ $count = @$self unless $count;
Branch: 1 branch
BranchTrueFalseTotal
unless $count 1229 0 1229
408  
409 1229 my @items;
410 1229 my $i = @$self;
411 1229 ▶ while ($i--) {
Branch: 1 branch
BranchTrueFalseTotal
if ($i--) 6166 231 6397
412 6166 ▶ if ($filter->($self->[$i]->[ITEM_PAYLOAD])) {
Branch: 1 branch
BranchTrueFalseTotal
if (&$filter($self->[$i][2])) 5901 265 6166
413 5901 unshift @items, $self->[$i];
414 5901 ▶ last unless --$count;
Branch: 1 branch
BranchTrueFalseTotal
unless --$count 998 4903 5901
415 }
416 }
417  
418 1229 return @items;
419 }
420  
421 203 1;
422  
423 __END__
« mylib/ForkingDaemon.pm ↑ Summary blib/lib/POE/Driver/SysRW.pm »