Path: utzoo!attcan!uunet!tank!ncar!mailrus!utah-gr!utah-cs!sunset.utah.edu!u-dmfloy
From: u-dmfloy%sunset.utah.edu@utah-cs.UUCP (Daniel M Floyd)
Newsgroups: comp.lang.c
Subject: Re: memory allocation
Message-ID: <5702@utah-cs.UUCP>
Date: 7 Sep 88 09:41:42 GMT
References: <1262@micomvax.UUCP>
Sender: news@utah-cs.UUCP
Reply-To: u-dmfloy%sunset.utah.edu.UUCP@utah-cs.UUCP (Daniel M Floyd)
Distribution: comp.lang.c,comp.os.misc
Organization: University of Utah, Computer Science Dept.
Lines: 55


It sounds like you want to make your own allocator to by pass
some less desireable (slower) system allocator.

You might try an allocation scheme similar to a DOS (i.e. MS/PS)
disk space allocation.

Divide your memory into convinient chunks. Then refer to those
chunks in some sort of look up table. Keep a pointer to the first
used block and the last. Always allocate at the end. The table will
either contain some sort of chain (if you can segment your allocation),
or a flag that says used or not. In all probablity, you're not going
to waste a lot of time searching for the next allocation (it's at
the end-oh yes I almost forgot when the end is at the end you wrap around).
Most likely, your deletions will occur in a first in first out method or
nearly enough that your active used area will sort of crawl toward the end
then wrap and start over. This method *will* waste memory and fragmenation
will occur in the active used area for more waste. But, you say you've
got memory to burn. If you end up with insufficient space at the end
pointer, then search for the next unused block (in the active used area)
and try it. This should happen rarely (hopefully never). I saw an article
in byte doing this with disks. The author showed conincingly, that
fragmentation won't be a big issue this way.

For example:
Divide the 4M into 1k blocks. Set asside 537k bytes to use as your
table (if you're paranoid about droping a bit, do it twice). Each
bit within the 537k represents a 1k block, 0 if not used, 1 if used.
beginpointer=start of 537k block
endpointer=start of 537k block

then in psuedo run-time

allocate 2k
  set 2 bits accoringly
  endpointer=endpointer+2

allocate 3k ...alocate...

deallocate 3k
  unset 3 bits

allocate ...

deallocate first 2k
  unset 2 bits
  move startpointer to first set bit
  (you'll have to search, but you can search a byte or a word
  at a time and then narrow it down to the bit.)


As you can see the allocation is quick (usually), with a small cost on
deallocation.

It's just an idea. Hope it helps. Hope I was clear.