[Last Call] Learn about multicloud storage options and how to improve your company's cloud strategy. Register Now

x
?
Solved

M-alloc

Posted on 2000-03-23
12
Medium Priority
?
264 Views
Last Modified: 2010-04-02
IMPLEMENTATION OF MALLOC & CALLOC USING LINKED LISTS?
0
Comment
Question by:babs02_99
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
12 Comments
 

Expert Comment

by:amador
ID: 2648851
FAST


//Structure

structure list
{
 list*next;
 char buffer[10];
}
--------------------------
structure list cel1;

// Alloc base pointer

*(*lst) = (char *) calloc (1,sizeof(cel1))

or

*(*lst) = (char *) malloc (sizeof(cel1))

--------------------------
// if alread exist cel1, the list is not null
// increase in last position

strcpy (cel2.buffer,"cel 2");

cel1.next = &cel1;
cel1.next = NULL;

// you will have test if is the first cel to be increased

// if you want increase in any position, or if you want a .c detailed
// is more complicated, give more points
0
 

Expert Comment

by:amador
ID: 2648857
FAST


//Structure

structure list
{
 list*next;
 char buffer[10];
}
--------------------------
structure list cel1;

// Alloc base pointer

*(*lst) = (char *) calloc (1,sizeof(cel1))

or

*(*lst) = (char *) malloc (sizeof(cel1))

--------------------------
// if alread exist cel1, the list is not null
// increase in last position

strcpy (cel2.buffer,"cel 2");

cel1.next = &cel1;
cel1.next = NULL;

// you will have test if is the first cel to be increased

// if you want increase in any position, or if you want a .c detailed
// is more complicated, give more points

0
 
LVL 22

Expert Comment

by:nietod
ID: 2649014
Are you asking how to impliment a linked list using malloc/calloc?    Or are you asking how to impliment a heap (the memory pool from which dynamically allocated memory is drawn) that uses a linked list.
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 22

Expert Comment

by:nietod
ID: 2649020
amador, I don't know if babs02_99 can understand that. I can't.
0
 

Expert Comment

by:amador
ID: 2650263
nietod

I don´t know too, but...
0
 
LVL 22

Expert Comment

by:nietod
ID: 2650430
My point is that you answer doesn't seem comprehensible.  I can't tell what you are saying.  You may wish to explain it better, beceause I don't think babs02_99 will be able to understand it.
0
 

Author Comment

by:babs02_99
ID: 2652290

i want to know how to implement a heap, as was asked by nietod?
0
 
LVL 22

Accepted Solution

by:
nietod earned 200 total points
ID: 2652939
You start with a "chunk" of memory from which you will carve out your heap.  This chunk will be divided into blocks by the allocation and deletion process.  The blocks will be different sizes, but adjacent blocks touch each other, that is, every byte of the heap is part of some block, there are no gaps between blocks.  Ther are two types of blocks.  There are free blocks, which are not being used and there are allocated blocks which are being used to store allocated memory.  In a basic heap, the free blocks are recorded in a linked list, which will be used to find free blocks when an allocation needs to be performed.  But the allocted blocks are not stored in a linked list or other mechanism.    In more advanced heaps, more complex structures than simple linked lists may be used for recording blocks and the allocated blocks might be recorded to.  (Lets not go there!)

continues
0
 
LVL 22

Expert Comment

by:nietod
ID: 2652963
now each free block will begin with a structure that records the block size and has a pointer to (or offset of) the next block free block in the heap.  this pointer will be set to NULL for the last block in the heap.  So this structure might look like

struct FreeBlock
{
   size_t BlockSize;
   FreeBlock *Next;
};

Now the free block can be bigger than this structure (It really should be) it just begins with this structure, and then contains unused space after it.

An allocate block begins with a structure that just records the block's ize (in a simple design at least.)  Like

struct AllocatedBlock
{
   size_t BlockSize;
};

Now to start out with the heap is empty, so you initialize the heap by making it one big free block.  In other words, you fill in a FreeBlock at the very start of the heap memory that has BlockSize set to the size of th heap memory and that has the Next pointer set to NULL.  You also will need a static pointer somewhere that points to the first free block in the list, this pointer would be initialized to point to the start of the heap memory.

continues
0
 
LVL 22

Expert Comment

by:nietod
ID: 2653003
Now when an allocation is performed, you need to search the linked list for the smallest block that you can find that is at least as large as the requested size.  (Actually, you need to remember to take into account the size of the AllocateBloch structure, so if they request X bytes, you need to find a block that is at least X + sizeof(AllocatedBlock)  So you use the static pointer that you have that points to the start of the linked list and you proceed down the list looking for blocks that are at least as large as the size requested.  Each time you come to a block that is at least a large as the size requested, you compare the block size to the size of the last block found (if one was found)  if the size is smaller than the last block found, you will use this new block instead of the one previously found.   i.e the new block becomes the last block found. and you continue the search.  when you reach the end of the list you will either have the smallest block that is large enough for the request or you won't have found any block large enough to fill the request.  if that later the case, you have run out of memory in the heap and have to fail the allocation.  If the former is the case, you can perform the allocation.   To perform the allocation, you test to see if the block should be divided into a free block and an allocated block or if it should just become an allocated block.  I the block's size is greater than the needed size plus the minimum size of of a free block, i.e. if it is greater than X+sizeof(AllocatedBlock)+sizeof(FreeBloc) then the block should be divided, otherwise it should be coonverted.   (Actually, you probably want to add a little extra onto that to prevent very small free blocks from forming.)  If the block is to be converted, you just adjust the linked list to skip the block and you fill in a AllocatedBlockat the start of the memory.   If the block is divided, you adjust the size recorded in the FreeBlock structure at the start of the block, so that it is decreased by the size of the allocated block you are making and then you create an allocated block by filling in a AllocatedBlock structure in what had been the memory of the free block.  This structure shoudl be positioned right past the new end of the free block and the new allocated block should extend to the next  block in the heap (or the end of the heap if it is last.)
0
 
LVL 22

Expert Comment

by:nietod
ID: 2653033
In either case you now hav an allocated block that begins with an AllocatedBlock struct that has the Size set to the need size (or perhaps a little greter than the needed size.)  You then return a pointer, but not to the block, but to the unused space inside the block.  That is, you return a pointer points right past the AllocatedBlock structure that begins the block.

Now when a release occurs you are given a pointer that is again, just past the AllocateBlock structure.  You adjusts this pointer to make it point to the AllocatedBlock strucutre.  Then you need to search the free block linked list to see of the block is adjacent to free blocks.  That is, to see if the block before the block released is free or to see of the block after the released block is free, or both.   If there are free adjacent blocks, the block being released will be merged into these blocks, for form larger blocks.  (To be precise, if the block after it is free, the two blocks will be merged by finilin in a FreeBlock structure at the start of the block being released.  This strucutre will specify a Size that is the total of the two block's sizes.  Then the linked list will be adjusted to point to this merged block, not the free block that had followed the one being released.  If the block before the released block is free, you just increase the size of this block to include the size of the block beign released.  If the the blocks before and after the block being released are free, you adjust size recorded in the block before so that it is the total size of all three blocks and you adjust its Next pointer so that it points to the place that pointer in the block that the free block after the released block had pointed to.)   If merging is not possible, then you just convert the block to a free block, by filling in a FreeBlock structure at the start of the block and by insertng the block in the list.

Wow.   Probably more than you wanted to know.  any questions?
0
 
LVL 9

Expert Comment

by:Pacman
ID: 2653653
listening with a smile ...

alex02_99 ;)
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

650 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question