Charles D Hixson wrote:
> 
> However I *did* take your suggestion about documenting it.
> 
> OTOH, it would be better if I could renumber the nodes sequentially, but doing that without a sort is difficult (i.e., I haven't figured out how).
> 
> A different organization would be to keep nodeIds in a queue, with pointers to the hash table, but that has other costs. Still, I SHOULD add a routine to renumber everything whenever the maxT value starts to get withing maxSize of ushort.max. This routine will probably be introduced at some later version.
> 
> Any suggestions for a quick and simple way to do this?

A good form of documentation is to use contracts for this sort of thing.

-Joel

janderson wrote:
> Charles D Hixson wrote:
>>
>> However I *did* take your suggestion about documenting it.
>>
>> OTOH, it would be better if I could renumber the nodes sequentially, but doing that without a sort is difficult (i.e., I haven't figured out how).
>>
>> A different organization would be to keep nodeIds in a queue, with pointers to the hash table, but that has other costs. Still, I SHOULD add a routine to renumber everything whenever the maxT value starts to get withing maxSize of ushort.max. This routine will probably be introduced at some later version.
>>
>> Any suggestions for a quick and simple way to do this?
> 
> A good form of documentation is to use contracts for this sort of thing.
> 
> -Joel
One of us is grossly misunderstanding the other.  I can't see any application of contracts to this problem.

Note that the maximum length is specified as a ushort, so it's guaranteed that there will always be enough allocatable nodeId's to hold all the entries in the list.  (This *doesn't* mean that this would be a good idea.  A cache that large would usually be a very bad idea.)

Also, an LRUCache is allowed to drop entries on the grounds that they "haven't been used recently enough", so you can't depend on the thing that you stuck in there awhile ago to still be there.

The problem was a quick way of renumbering the entries that retained the time ordering.  The current version gives up on retaining the time ordering, and after a cache clear that leaves the highest node near the maximum nodeId value, it just renumbers everything from by hashcode order.  This should work well enough in most cases, but it would be better if I didn't need to lose the order of last access.  I just haven't thought of a way to do that that's even close to efficient.

N.B.:  While thinking of this I've just noticed a potential flaw.  With frequent access and no additions the maximum nodeId could increase to too large a number without invoking a cache compression, so I'd better move the check for renumbering to where the nodeId is assigned.

BCS wrote:
> Reply to Charles,
> 
>> In the hopes that someone find this useful:
>> http://www.prowiki.org/wiki4d/wiki.cgi?CharlesHixson
>> This particular version presumes D2.x code, but I think the
>> adjustments are trivial for D1.x.
>>
> 
> Would you like to add this to scrapple?
> 
> I will get you access if you would.
> 
> 
I seem to have made a few errors that I can't figure out how to undo.
1) I've attached a copy of the program to the main scrapple page.  This should be deleted...but I don't know how.
2) I've attached a copy of the program named lrucache2.d to the lrucache page,  This one should also be deleted.  (I also attached the file with it's correct name, but this didn't override the prior attachment with an incorrect name.)

FWIW, there is no significant difference between lrucache.d and lrucache2.d, except that in lrucache2.d the tabs have been expanded into spaces (expand -t3 lrucache.d > lrucache2.d). Even then, I believe that for the version that I entered the tabs had already been converted to spaces.
(I much prefer to work with tabs, but apparently many people either prefer spaces, or have a toolchain that doesn't deal nicely with tabs...so I intend to be attaching a version with spaces, even though that's not "the preferred form of the work for making modifications to it".

Reply to Charles,

> I seem to have made a few errors that I can't figure out how
> to undo.
> 1) I've attached a copy of the program to the main scrapple
> page.  This should be deleted...but I don't know how.
> 2) I've attached a copy of the program named lrucache2.d to
> the lrucache page,  This one should also be deleted.  (I also
> attached the file with it's correct name, but this didn't
> override the prior attachment with an incorrect name.)
> FWIW, there is no significant difference between lrucache.d
> and lrucache2.d, except that in lrucache2.d the tabs have been
> expanded into spaces (expand -t3 lrucache.d > lrucache2.d).
> Even then, I believe that for the version that I entered the
> tabs had already been converted to spaces.
> (I much prefer to work with tabs, but apparently many people
> either prefer spaces, or have a toolchain that doesn't deal
> nicely with tabs...so I intend to be attaching a version with
> spaces, even though that's not "the preferred form of the work
> for making modifications to it".

With regards to the wiki, I don't known much about how things work. Ask around, I'm sure someone who knows more than me can help you.

As for the code, that should be put into the SVN repository rather than the wiki. I have added you to user list for SVN so you can now commit to it.