Coding in C

Align

<div class="IPBDescription">Queues/stacks without malloc</div>So I'm part of a group with a project to make our very own OS. One thing we need is queues and stacks (they're very similar, after all), but since we can't use stdio or any of the other standard files, we don't have access to memory allocation. This makes online examples by and large useless, since they rely on it. Still looking, though.
Is there a way to implement them without memory allocation?

douchebagatron

this past semester ive been coding (badly) in C and never used malloc once. I also used a lot of multithreading and never used mutual exclusion. im not sure how my programs worked, but they did enough for me to get 100s on each project.

i have no idea how to implement a stack for a general datatype though since we never did that. all my stacks were written specifically for a certain datatype. you could look and see if you can find code for writing a new malloc. cant be too impossible.

Align

Specific datatype would be fine too, but it turns out an implementation of such a queue was included in the example files anyway. Doh.
Problem solved.

[WHO]Them

I was about to say. If you're making an OS. The memory is all yours, as long as you know how much you have, you're responsible for creating the allocation scheme.

Gwahir

I once decided to take a look at memory allocation schemes, I eventually came up with one that really perked the interest of a CS professor.

No details, all mine.

Suffice it to say it had a really, really fast best fit algorithm.

[WHO]Them

Your mom has a really, really fast best fit algorithm.

moultano

<!--quoteo(post=1664007:date=Dec 14 2007, 04:36 PM:name=Gwahir)--><div class='quotetop'>QUOTE(Gwahir @ Dec 14 2007, 04:36 PM) <a href="index.php?act=findpost&pid=1664007"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->I once decided to take a look at memory allocation schemes, I eventually came up with one that really perked the interest of a CS professor.

No details, all mine.

Suffice it to say it had a really, really fast best fit algorithm.<!--QuoteEnd--></div><!--QuoteEEnd-->
I worked on something for a little bit that looked like it had some potential but I didn't really pursue. The intent was to reduce memory fragmentation by using a "modulus fit". My implementation just walked down an implicit free list one by one, but it plopped the allocation in the first area of memory which had a size that was evenly divided by the allocation size + overhead. The reasoning behind this is that common usage patterns tend to allocate many similarly sized regions of memory, so if you allocate things to regions they evenly divide, there will be no excess unusable memory when that region is filled to capacity. It worked well enough to get an 'A' on the assignment with much less work than implementing a red/black tree or some such.