[MUD-Dev] caved in: Algorithms for for storing free space.

[Cimri]

I've always loved and still remain attached to the VMS lookaside list
mechanism, but then I suppose the reason is more emotional and
nostalgic
now.  But anyway, it actually had 4 lists:

- pagedyn - a big pile o' mem in one huge piece, pageable
- npageyn - same, but locked in mem
- srp     - small request packets, 32 bytes in size
- irp     - i/o request packets, forgetting size now
- lrp     - large request packets, 512 byes in size as I recall

Strictly speaking only the last three were the lookaside lists.

Anyway, so whenever possible you allocate in chunks tailored to
the thing you are allocating, and of course keep a bitmap in
npagedyn representing the used/unused status of any packet in
the respective lookaside list.

Memory fragmentation of course never happened in the lookaside lists.
They could be grown dynamically too, if you like.  Page and npage dyn
could theoretically become fragmented, but you just made sure you
only used them for things that either aren't going to be released,
or are in very nice sizes for ease of release, etc.

Oh well, hope that helps.

Jay//Cimri

Ben Greear wrote:
> 
> Well, after I quit being so bone-headed, (and envisioned a delete option
> for my db) I quickly saw that I needed to manage free space much
> better for my db.
> 
> I'm sure this has been done many times before, but any quick hints would
> be welcome.  I want to keep with a single db-file approach, wich rules out
> the (really cool) idea involving powers of 2 that was posted recently...
> 
> Perhaps an array of linked lists(stacks would be fine), the array being 32
> long, mimicing the powers of two idea?
> 
> Each stack will hold seek positions into the DB file....
> 
> So here's a question, what's a good way to determine the
> power of two that is optimal for the storage space needed?
> 
> A binary search wouldn't be too bad, just wondering if there's
> a better (constant) method??
> 
> Enjoy,
> Ben
> 
> Ben Greear (greear at cyberhighway.net)  http://www.primenet.com/~greear
> Author of ScryMUD:  mud.primenet.com 4444
> http://www.primenet.com/~greear/ScryMUD/scry.html