Solved

M-alloc

Posted on 2000-03-23
12
227 Views
Last Modified: 2010-04-02
IMPLEMENTATION OF MALLOC & CALLOC USING LINKED LISTS?
0
Comment
Question by:babs02_99
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
 
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
Do You Know the 4 Main Threat Actor Types?

Do you know the main threat actor types? Most attackers fall into one of four categories, each with their own favored tactics, techniques, and procedures.

 

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 50 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

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

760 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

Need Help in Real-Time?

Connect with top rated Experts

27 Experts available now in Live!

Get 1:1 Help Now