C pointers and memory management for generic containers part 2

Previous post discussed pointer arithmetic and common elements that goes with any generic container. This post would look in to the memory management part and add another common element to the struct of the generic container.

Primary functions that are being used for dynamic memory management are malloc, realloc and free functions.

Malloc – void *malloc(size_t number) takes the number of bytes that needs to be allocated as the input parameter and return the starting address of the allocated block in heap.

Realloc – void *realloc(void* ptr, size_t size) takes a pointer returned by malloc and the required new size and returns the address of the block. Realloc is basically for resizing a block allocated by malloc function. This function extends the size if there is enough contiguous memory starting from the input pointer, if contiguous memory block starting at the input pointer is not available it would relocate the block to a new place and copy the content in the old block and return the starting address of the new block.

Free – void *free(void *ptr) free the memory and donate it back to the heap. We must free up the memory after we are done using it so that enough space is available for new memory requests.

So, when someone initialize our container we should allocate memory using malloc, if our container allows resizing like a Vector we should use realloc for resizing rather than malloc and copy and free sequence by ourselves and finally we should free the memory used by our stack when user want to dispose the container.

Its quite simple. But think of the disposal. If the data type stored in our container is something like int or double they would get vanish when we clear the memory block of our container. But if the data type is a pointer to some struct on the heap, we would only lose the references that were stored in our container and the memory for the struct will not be donated back to the heap. Therefore we need a way to clear them, but unfortunately we don’t know how so the user have to tell us how by giving us a function which would free the memory and we would use that function to free up memory at the disposal of our container.

So, we got a new element to the common list of things that a container struct need to maintain, that is a pointer to a function to free up the memory. If the container holds built in types such as int and float user could pass in NULL and we don’t have to worry about it.

When an item is inserted to the container I assumed that the ownership is given to us that is the reason that we had to worry about cleaning the things that were still there in the container at the disposal. The ownership also implies that we need to copy whatever the element inserted to the container using memcpy so that it is available throughout the lifetime of the container.

So now we have the common elements and pointer arithmetic knowledge. It is time for an example. First the simple generic stack, then the generic vector which also introduce the memmove function.

Note: This is an old post moved here from a different location.

C pointers and memory management for generic containers

Generics and C looks far apart. But if we look closely we only need to understand little simple stuff. Then we are good to go except for one reason these compile without much of a problem but it doesn’t mean anything! So, what are those few things? Well, they are pointer arithmetic, memory management and bit about data types.

If we think of a data type such as int or float they will have size (number of bytes) required to store the data which is known at the compilation time. So, if we declare a pointer to any of these data types we know that the data that we are interested in is located in particular size of contiguous memory block and the address of the starting byte of that block is known to us. This information is used to perform pointer arithmetic. Let’s say that we have following,

int* i;
i+1;

C pointer arithmetic

The first statement declares an int pointer. Currently it has garbage. But let’s say that it points to a some meaningful address (EX: 5 – so it points to the byte which is addressed 5). Then if we have a statement like second one, which calculates an address. So, the value produced by i+1 would be i+1*sizeof(int). If the int is 4 bytes long this would point to the 9 th byte. When we do this compiler knows to multiply the added value by size of an int so that it points to the next int. Now that is simple enough.

Pointer arithmetic which involves void*

But when we need to support generics we have to use void* so that we can point to any type of data. But as soon as we do that we lose the size information of the data that we are pointing which was implicitly know at compilation for any given type like int, double etc. Therefore we cannot perform pointer arithmetic with a void* as with other pointers. In generic containers we store many data items in the memory block allocated for our container and we generally only keep track of the starting address of the memory block for our container. So, in order to find starting address of individual data items we must do pointer arithmetic. This is done with the following commonly used hack.

void* a;
(char*) a +2;

Here we have a void* named a. Second statement first cast our pointer to a char*, this tells the compiler to treat “a” as pointer to a character. Now the size of a character is 1 byte. Therefore if we add 2 as in the second statement we are effectively doing normal arithmetic. That is if ‘a’ points to the 5 th byte we would produce 7, this happens because 2 is multiplied by 1 (size of the character).

So, now we can do pointer arithmetic with the void*, but how do we calculate address of individual elements. We need the size of element type that is in our container, which means that we need to have in our struct.

So, what are the things that we need to maintain in our struct for the container? Well, we can see four items up to now. They are,

Pointer to the starting address of the container

Size of a single element in our container (in bytes – to calculate addresses of individual elements)

Size of the memory block for container (in bytes – for boundary checking)

Count of the number of elements currently in the container (boundary checking and insertions).

There is one more thing that we need. You would guess that it is about memory management. Well, that’s right but it would be in the next post.

Note: This is an old post moved here from different location.

cpp object size

If you have ever noticed that objects of empty classes have a non zearo size or variable reordering can change the size of the objects,
 you probably wanted to figureout whats going on! Guess what, you are at the right place :D if you know this, you can probably write space efficient code.
So what are the things that affect a size of a object? as you would guess size of the non static member variables. But thats not all there are two other things. They are,
 alignment requirements of those member variables and the alignment requirement of the struct or class (which depends on the alignment requirements of the member variables).
There are other things which are imposed by the langues. Those are order of the varibles, presence of virtual members and inheritance.

Size of empty objects
Now lets inspect what is the deal with non zearo size of the empty objects. The standard has the following.

Unless it is a bit-field (9.6), a most derived object shall have a non-zero size and shall occupy one or more bytes of storage.
Base class subobjects may have zero size. An object of trivially copyable or standard-layout type (3.9) shall occupy contiguous bytes of storage

Lets clarify what the above says with examples.

class A

{}; // size = 1



class B:public A

{}; // size =1;



class C

{   A a;  A b; }; // size = 2

Presence of virtual members

Now what happens when there are virtual functions? When virtual members are present each class that has them has virtual table and each instance of the of these classes contains a pointer to that table. Therefore the size would require the additional amout of pointer size irrespective of the number of virtual members. Here is an example.

class D

{   virtual void tt(){}; }; // size = 4



class E{ virtual void t1(){}; virtual void t2(){}; }; // size = 4

Alignment and Ordering of member variables

alignment requirements of data types are not enforced by the language rarther it is imposed by the processor architecture or OS. These requirements are

enforced for efficient data fetching from memory. The alignment requirement is influenced by the bus width. Processor can fetch a word in a single cycle,

that would be 4 bytes in a 32 bit machine. Alignments are enforced so that the processor can fetch data with minimum number of memory cycles. This would suggest

that alignment requirement of int would be 4 so that it would be stored in a single word rather than spread in two different words. Can you guess the alignment requirement

of a short type? it would be 2 otherwise if odd starting addresses were allowed it can spread to two different words requiring two memory cycles. What about a double?

"A double (eight bytes) will be 8-byte aligned on Windows and 4-byte aligned on Linux (8-byte with -malign-double compile time option)."

- http://en.wikipedia.org/wiki/Data_structure_alignment

You can try using google for the reason behind this type of differences :( similarly there are alignment requirements for structs as well. That is the alignment requirement of a

struct would be same as the alignment requirement of the member that has the largest requirement. That is if a struct has a int and a short alignment requirement of the struct would be

4(int has the largest alingment (4) in this struct ). This is needed to create array of struct because arrays elements occupy contigues memory without padding thus it could violate

alignments of memebers of the struct.

Having known these, now we can try to guess the size of different structs. Note that sizes and alignments of int = 4, short = 2, char = 1 in windows 32 bit machine. So lets go,

struct first{char a; int b;}; // size = 8

sizeof(char) + 3 byte padding (to aling int to multiple of 4) + sizeof(int)

struct first_c{int b; char a;}; // size = 8

sizeof(int) + sizeof(char) + 3 byte padding to make the size multipe of 4 (largest type is int)
This shows that reordering does not always improves the size.

struct second{char a; short b;}; // size = 4

sizeof(char) + 1 byte padding (to aling short to multiple of 2) + sizeof(short)

struct third{short a;int b;short c; int d;}; // size =16

sizeof(short) + 2 byte padding (to aling int to multiple of 4) + sizeof(int) + sizeof(short) + 2 byte padding (to aling int to multiple of 4)  + sizeof(int)

Well how to reorder the elements so that the size is minimized? arrange them in the decending order of their aligning requirements. This way only the padding at the end of the

struct would be added to match the requirements of the struct and we can avoid padding in between the members.

Now can't the compilers do it by themselves. The standard has things like following to restrict the comilers.

Nonstatic data members of a (non-union) class declared without an intervening access-specifier are allocated so that later members have higher addresses within a class object.

The order of allocation of nonstatic data members separated by an access-specifier is unspecified (11.1)"

So thats about it! C U :D