httpd-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Cliff Woolley <jwool...@virginia.edu>
Subject cache_pq in right order??
Date Tue, 13 Aug 2002 22:31:19 GMT

I have reason to believe that the cache_pq code isn't working quite right.
I'm not sure why yet (and for all I know it's my fault since I touched
that code last).  Just wanted to give you guys a heads-up.

Basically it's just popping things in not quite the right order.  For
example:

popped value = -1.305

followed by a cache_pq_dump():

posn    left    right   parent  minchild        ...
1       2       3       0       3       (-1.305/1)
2       4       5       1       4       (-1.305/2)
3       6       7       1       7       (-1.305/3)
4       8       9       2       8       (-1.305/4)
5       10      11      2       10      (-1.305/5)
6       12      13      3       13      (-1.305/6)
7       14      15      3       14      (-1.305/7)
8       16      17      4       17      (-1.305/8)
9       18      19      4       19      (-1.305/9)
10      20      21      5       20      (-1.419/10)
11      22      23      5       22      (-1.430/11)
12      24      25      6       24      (-1.459/12)
13      26      27      6       27      (-1.305/13)
14      28      29      7       28      (-1.305/14)
15      30      31      7       31      (-1.305/15)
16      32      33      8       33      (-1.305/16)
17      34      35      8       34      (-1.305/17)
18      36      37      9       36      (-3.260/18)
19      38      39      9       38      (-1.374/19)
20      40      41      10      41      (-1.449/20)
21      42      43      10      43      (-1.854/21)
22      44      45      11      44      (-1.683/22)
23      46      47      11      46      (-2.396/23)
24      48      49      12      48      (-1.591/24)
25      50      51      12      51      (-1.597/25)
26      52      53      13      53      (-1.683/26)
27      54      55      13      55      (-1.305/27)
28      56      57      14      56      (-1.305/28)
29      58      59      14      59      (-2.001/29)
30      60      61      15      61      (-1.421/30)
31      62      63      15      63      (-1.305/31)
32      64      65      16      64      (-1.459/32)
33      66      67      16      67      (-1.374/33)
34      68      69      17      68      (-1.305/34)
35      70      71      17      70      (-1.378/35)
36      72      73      18      73      (-1.448/36)
37      74      75      18      75      (-1.449/37)
38      76      77      19      76      (-1.683/38)
39      78      79      19      78      (-1.683/39)
40      80      81      20      80      (-1.509/40)
41      82      83      20      83      (-1.459/41)
42      84      85      21      84      (-1.261/42)
43      86      87      21      87      (-1.130/43)
44      88      89      22      88      (-1.261/44)
[snip]

There are many more entries in this particular PQ, but what's here is
enough to see the problem.  I popped the top value which was -1.305 and
then immediately dumped the rest of the PQ.  You can clearly see that
of the entries shown here, -1.130 should have been the thing popped, not
-1.305.

It's moderately likely that the bug is in the change_priority function, as
I have a test program that inserts and then removes a set of values, and
that works fine.

More details as I figure out what's up.

--Cliff


Mime
View raw message