Coding in C

AlignAlign Remain Calm Join Date: 2002-11-02 Member: 5216Forum Moderators, Constellation
in Off-Topic
<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?
Off Topic Disagree Agree Awesome

Comments

  • douchebagatrondouchebagatron Custom member title Join Date: 2003-12-20 Member: 24581Members, Constellation, Reinforced - Shadow
    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.
    Off Topic Disagree Agree Awesome
  • AlignAlign Remain Calm Join Date: 2002-11-02 Member: 5216Forum Moderators, Constellation
    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.
    Off Topic Disagree Agree Awesome
  • [WHO]Them[WHO]Them You can call me Dave Join Date: 2002-12-11 Member: 10593Members, Constellation
    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.
    Off Topic Disagree Agree Awesome
  • GwahirGwahir Join Date: 2002-04-24 Member: 513Members, Constellation
    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.
    Off Topic Disagree Agree Awesome
  • [WHO]Them[WHO]Them You can call me Dave Join Date: 2002-12-11 Member: 10593Members, Constellation
    Your mom has a really, really fast best fit algorithm.
    Off Topic Disagree Agree Awesome
  • moultanomoultano Creator of ns_shiva. Join Date: 2002-12-14 Member: 10806Members, NS1 Playtester, Contributor, Constellation, NS2 Playtester, Squad Five Blue, Reinforced - Shadow, WC 2013 - Gold, NS2 Community Developer, Pistachionauts
    <!--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.
    Off Topic Disagree Agree Awesome
Sign In or Register to comment.