You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@httpd.apache.org by Cliff Woolley <jw...@virginia.edu> on 2002/08/14 00:31:19 UTC
cache_pq in right order??
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
Re: cache_pq in right order??
Posted by Cliff Woolley <jw...@virginia.edu>.
On Tue, 13 Aug 2002, Cliff Woolley wrote:
> 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.
Well, the good news is that the PQ seems to be in working order. The main
bug was a single missing minus sign in *my* code (not the PQ). Sheeeiitt.
Turns out, though, that the main reason the bug snuck in was because of
the funky API of change_priority(), which I'll probably change soonish.
Anyway, I'm pretty confident in the PQ code at this point. :) I still
need to test the remove() function and I need to make sure I didn't break
its iteraction with cache_cache.c in some unexpected way, but I don't
forsee any major problems. I'll clean up the bits tomorrow.
--Cliff