Coding in C

AlignAlign Remain CalmForum Moderators, Constellation Join Date: 2002-11-02 Member: 5216Posts: 8,206 mod
Queues/stacks without malloc
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?

Comments

  • douchebagatrondouchebagatron Custom member title Members, Constellation, Reinforced - Shadow Join Date: 2003-12-20 Member: 24581Posts: 3,509
    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.
    the artist formerly known as 6john
    and
    the artist currently known as d*uchebagatron
  • AlignAlign Remain Calm Forum Moderators, Constellation Join Date: 2002-11-02 Member: 5216Posts: 8,206 mod
    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[WHO]Them You can call me Dave Members, Constellation Join Date: 2002-12-11 Member: 10593Posts: 2,813 Fully active user
    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.
    image
    Zoc.php FTW
    "Build a tent and say the world is dry." -Tay Zonday
  • GwahirGwahir Members, Constellation Join Date: 2002-04-24 Member: 513Posts: 4,270
    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.
    QUOTE
    Sanity is just a weird form of madness.
  • [WHO]Them[WHO]Them You can call me Dave Members, Constellation Join Date: 2002-12-11 Member: 10593Posts: 2,813 Fully active user
    Your mom has a really, really fast best fit algorithm.
    image
    Zoc.php FTW
    "Build a tent and say the world is dry." -Tay Zonday
  • moultanomoultano Creator of ns_shiva. Members, NS1 Playtester, Contributor, Constellation, NS2 Playtester, Squad Five Blue, Reinforced - Shadow, WC 2013 - Gold, NS2 Community Developer, Pistachionauts Join Date: 2002-12-14 Member: 10806Posts: 4,219 Advanced user
    QUOTE(Gwahir @ Dec 14 2007, 04:36 PM) »
    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.

    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.
Sign In or Register to comment.