Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Like
0Likes
Dislike

Introduction to Pointers, Structures and Linked-Lists Part 4

By Chris Bennett aka Dwarfsoft | Published Sep 30 2004 04:42 AM in General Programming

memory list block pointer function allocate return allocation cur
If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource



Introduction

Dynamic Memory Allocation is the method in which you can select a block of memory during the run-time of your program, and use this block of memory for storing more information. This is very
useful when using Linked Lists in that you can increase the size of your list without creating new variables. Usually, with your dynamic list, you have a specific function that is dedicated to
allocating the memory and adding the block to your list and one for freeing your memory and removing that block from the list.


Dynamic Memory Allocation

OK, so I mentioned allocation and deallocation. How do we go about this? Well, there is a standard function that is available from the library by including <malloc.h> or <stdlib.h> by
the name of 'malloc ()' and another that is the reverse of malloc, called 'free ()'. So how do these functions work? The malloc function has the following structure:



<span class="codekeyword">void</span> *malloc(size_t size);


This means, that when you use malloc, you call it with the parameter for the size of the memory that you want to allocate, and the function returns a pointer to the memory block. A 'void *' (void
pointer) is a special pointer. It has no defined type, and every defined type. You can cast this pointer to be any pointer you choose it to be. If I wanted to allocate a string of 20 characters
dynamically, then the following code would suffice



<span class="codekeyword">char</span> *Buffer; <span class="codecomment">// Pointer to our dynamic buffer</span>

Buffer = (<span class="codekeyword">char</span> *)malloc(20);


The '(char *)' part in the code is the 'casting' of the void pointer to be of type 'char *'. Type casting is very useful and in this case is very important. Without typecasting the pointer to the
allocated block, the program is likely to return errors. In the event that the memory allocation fails, the pointer that is returned is a NULL. The other thing that we need to have a look at in
detail is the size of memory to be allocated.


When it comes to allocating memory for structures and types, we need to be careful to specify the right size for what we want. If I wanted to allocate enough room for an array of 20 integers (long
integers) and I did the following then I would end up with unexpected errors



<span class="codekeyword">long</span> *LArray;

LArray = (<span class="codekeyword">long</span> *)malloc(20);


This would allocate enough room for 5 long integers. This is because size is measured in bytes, and a long integer is 4 bytes long. But what about when it comes to allocating for large structures?
Do we have to add up all of the elements to figure out how big it is? The answer is no, because we can use a keyword that was created for this specific reason. The sizeof keyword evaluates the size
of your structure, and by doing so you can allocate the correct memory for a new dynamic instance of that structure. Here is how we can make the above code correct for what we specified for it



<span class="codekeyword">long</span> *LArray;

LArray = (<span class="codekeyword">long</span> *)malloc(20*<span class="codekeyword">sizeof</span>(<span class="codekeyword">long</span>));


Before we actually use this array, we should ALWAYS check to see if the memory block was successfully allocated. That is quite simple, as in the event of failure to allocate the memory, the malloc
function returns a NULL, so therefore our pointer should be NULL in such a case. Usually I return from a function in the event of an allocation failure.



<span class="codekeyword">if</span> (!LArray)

  <span class="codekeyword">return</span>(<some error="" in="" allocation="">);

</some>


Now that we have the simple side of allocating memory, we can look at deallocation. Deallocation is quite a bit easier than what we had to go through for allocation. The one thing that you have to
be sure of about freeing memory is that there is an allocated block of memory to free. Fortunately, we can do a memory deallocation in a single line, and with a line that also handles the error
case.



<span class="codekeyword">if</span> (LArray) free(LArray);


This checks that the pointer actually references something, and if it actually points somewhere then the reference is freed.


If you already have an allocated block of memory then you can also use the realloc () function, which reallocates memory to the size that you wanted using the current block of memory. If we wanted
to reallocate the block for the LArray so that we could access 40 long integers, then we would do the following.



LArray = (<span class="codekeyword">long</span> *)realloc(LArray, <span class="codekeyword">sizeof</span>(<span class="codekeyword">long</span>)*40);


You need to get the return value to determine if there was a failure (in which case it returns NULL) or if the memory block was moved during the reallocation.


So now that we can allocate and deallocate memory for simple data types, let us use this knowledge in conjunction with the linked list from the previous section. We will now write a function that
allocates memory for a new Address to be added to the list.



<span class="codekeyword">int</span> NewAddress(AddressPtr_t Head,

               <span class="codekeyword">char</span> Name[30],

               <span class="codekeyword">char</span> Address[180],

               <span class="codekeyword">char</span> PhoneNo[10])

{

   AddressPtr_t Temp, Cur = Head;

   <span class="codecomment">// Go to the end of the list</span>

   <span class="codekeyword">if</span>(Cur)

    <span class="codekeyword">while</span>(Cur->Next)

       Cur = Cur->Next;



   <span class="codecomment">// Allocate a new block of</span>

   <span class="codecomment">// memory for this address</span>

   Temp = (AddressPtr_t)malloc(<span class="codekeyword">sizeof</span>(Address_t));



   <span class="codecomment">// ensure that the allocation passed</span>

   <span class="codekeyword">if</span> (!Temp) <span class="codekeyword">return</span> (FAILURE);



   <span class="codecomment">// Add the block to the end of the list</span>

   Temp->Next = NULL;

   Cur->Next = Temp;



   <span class="codecomment">// Update the values of the new block</span>

   strcpy(Temp->Name, Name);

   strcpy(Temp->Address, Address);

   strcpy(Temp->PhoneNo, PhoneNo);

   <span class="codekeyword">return</span> (SUCCESS);

}


Firstly, the return values of 'FAILURE' and 'SUCCESS' are just macros defined in a way similar to SUCCESS being 0 and failure being 1, or however you want your errors handled through return
values. I think that the function is fairly self-explanatory. There still remains one error though. It will not show up unless there was no original list to begin with. If the list was empty, then we
need to modify it to avoid getting assertion errors.



<span class="codekeyword">int</span> NewAddress(AddressPtr_t Head,

               <span class="codekeyword">char</span> Name[30],

               <span class="codekeyword">char</span> Address[180],

               <span class="codekeyword">char</span> PhoneNo[10])

{

  AddressPtr_t Temp, Cur = Head;



  <span class="codecomment">// Go to the end of the list</span>

  <span class="codekeyword">if</span>(Cur)

    <span class="codekeyword">while</span>(Cur->Next)

      Cur = Cur->Next;



  <span class="codecomment">// Allocate a new block of memory 

  // for this address</span>

  Temp = (AddressPtr_t)malloc(<span class="codekeyword">sizeof</span>(Address_t));



  <span class="codecomment">// ensure that the allocation passed</span>

  <span class="codekeyword">if</span> (!Temp) <span class="codekeyword">return</span> (FAILURE);



  <span class="codecomment">// Put a plug on the end of the list</span>

  Temp->Next = NULL;



  <span class="codekeyword">if</span> (!Cur)

  {

    <span class="codecomment">// If this is the first element, 

    // then avoid assertion</span>

    Cur = Temp;

  }

  <span class="codekeyword">else</span>

  {

    <span class="codecomment">// Add to the end of the list</span>

    Cur->Next = Temp;

  }



  <span class="codecomment">// Update the values of the new block</span>

  strcpy(Temp->Name, Name);

  strcpy(Temp->Address, Address);

  strcpy(Temp->PhoneNo, PhoneNo);

  <span class="codekeyword">return</span> (SUCCESS);

}


Do you understand what I did just there? Basically, if there was no elements in the list to start with, then Cur was pointing to NULL. If I tried to add to the end of the list by using
'Cur->Next' then I would be causing an assertion. There is no way to point to a NULL->Next, so we need to include a way of avoiding this.


We also need to include a CleanUp routine for when we have finished with our program, so as not to leave memory allocated where the system can't access it. For this, we can use the simple
following function



<span class="codekeyword">int</span> CleanUp (AddressPtr_t Head)

{

  AddressPtr_t Cur = Head;

  <span class="codekeyword">while</span> (Cur)

  {

    Head = Cur;

    Cur = Cur->Next;

    free(Head);

  }

  <span class="codekeyword">return</span>(SUCCESS);

}


Conclusion

Well, there you have it, a simple introduction to Dynamic Memory allocation for use in linked lists. Next I will be talking about specific algorithms for use in linked list systems in the region
of Sorts, Searches and Saves.


One quick note before I go, though. In the two functions listed above, there is a parameter 'AddressPtr_t Head'. This is the start of the list. Seeing as we are using a single linked list, there
needs to be a pointer to the beginning of the list so that each function can start at the beginning of the list and work to the end.


Cheers, Chris (aka. Dwarfsoft)


Author: Chris Bennett aka Dwarfsoft
Contact: dwarfsoft@hotmail.com
November 26, 2000
© Copyright Chris Bennett, 2000-2001








Comments

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS