Author : Filipe Medeiros
Page : << Previous 7 Next >>
if we ever run out of room we can just make the arrays a bit bigger.
To do this we use the function `malloc'. This standard C function takes a parameter of type `size_t' (basically, a number) and allocates that many of bytes of memory. The return value is a `void *', pointing to the block of memory allocated.
So, we want to create an array of `num_circles' circles. Each circle will be represented by a `struct circle_t'. We can use the `sizeof' keyword to find out how many bytes we need for each struct, and allocate the memory like this:
struct circle_t *circles; ... circles = (struct circle_t *) malloc (num_circles * sizeof (struct circle_t));
The cast to `struct circle_t *' is optional in C programs; a C++ compiler will complain if you don't use it, though. Its use is largely a matter of taste.
If the allocation failed (e.g. out of memory), `malloc' will return `NULL'. Under some circumstances you might like to detect this and inform the user. It's good practice to do this, but often people don't bother because there may be no useful way to recover. If you're using djgpp with a robust DPMI host (e.g. CWSDPMI) it will terminate your program if you ever try to use the NULL pointer. Some other DPMI hosts just let your program carry on, which hides the problem from you; it's best to avoid these when developping, or at least to use CWSDPMI sometimes (i.e. from plain DOS, no Windows) to check that things still seem OK.
After the allocation, we can refer to the circles as circles[0], circles[1], etc, as if we'd made a real array. What we have is not an array in the strict C sense; it's just a pointer to a block of memory. In many ways this behaves much like an array, though.
Finally, when we've finished with the memory we should free it so that malloc can reuse it later if necessary:
free (circles);
Now try modifying your program from section 5.1 (just circles, no squares or triangles) to allow the user to specify the number of circles at the start of the program. If you get stuck, have a look at `src/5.3/i/circles'. Modifying `src/5.2/a' in the same way should be fairly simple. Modifying `src/5.2/b' will need more mallocs.
Now, what about letting the game expand the array as it runs? This isn't possible with a real array, but as noted earlier our `array' is not really an array. It was dynamically allocated, so we can use the realloc() function to reallocate it with a different size. The data that was in it before will still be there when we expand the allocation. If we're shrinking it, the data that's still in the new block stays there of course but the data that is cut off the end of the block is lost. Even if you reexpand the block, you shouldn't rely on regaining the data.
The problem with reallocating the block like this often is that if the memory area just after our block is already taken then realloc needs to copy the whole block to somewhere else. This isn't particularly slow (memory copy operations are pretty fast actually) but it's not the sort of thing you want to happen too often.
As it happens, djgpp v2.01's malloc puts some empty space at the end of each block, but we shouldn't rely too heavily on this. It's better to reduce the number of reallocations some other way. The simplest way to do this is to always request plenty of extra space - then we don't need to call realloc so often.
So, we need to keep track of a few things:
int num_objs; /* how many are active */
int alloced_objs; /* how many have been allocated */
int block_size; /* how many we should allocate at a time */
Then when we want to add a new object, we first check whether we already have enough space (is `alloced_objs > num_objs'?). If so, we can just increase `num_objs' and use that space. Otherwise, we need to increase `alloced_objs' by block_size and realloc the block like this:
objects = (struct obj_t *) realloc (objects, alloced_objs * sizeof (stuct obj_t));
Note that realloc's syntax is like malloc's, but you must pass the pointer's old value. After calling realloc, you shouldn't use the pointer's old value any more -- if realloc has moved the block, the old value is now invalid. If you'd assigned another pointer the value of `objects' and realloc had to move the block somewhere else, the other pointer would be pointing at a bad block.
After reallocating the new block size, we can of course increase `num_objs' and use the newly allocated objects.
5.3.2 Linked lists
Linked lists are an extremely useful data structure. Unfortunately, for some reason many people find them hard to understand. If you can get a good visualisation of them in your mind, though, they're really very simple, and when you've used them a few times you get an intuitive feel for how to maintain them.
In this section we'll look at three types of linked list, and try using them in the circles/squares/triangles programs from earlier on.
5.3.2.1 Singly linked lists
Firstly you'll need to be comfortable with pointers. Pointers are just objects that can point to other objects. Try not to think of them exactly as memory addresses; this is a common analogy, but it isn't necessarily correct, and pointer arithmetic becomes confusing if you think of them in this way.
So pointers can point at other data objects. Most pointers are designed to point at a certain type of data. In particular, they can point at user-defined structs:
struct little_struct { int number; } *ptr;
Here `ptr' can point at any object of type `struct little_struct'. To access the field `number' in the object that `ptr' is pointing at we can write `(*ptr).number' or use the shorthand `ptr->number', which means the same thing. Note that the above definition doesn't actually create an object for `ptr' to point at; it just creates the object `ptr', which is capable of pointing at objects of type `struct little_struct' but initially points nowhere in particular. Now how about:
struct linked_list_node { int number; struct linked_list_node *next; } *ptr;
Here the `linked_list_node' struct contains not only an integer `number', but also a pointer `next' which can point at an object of type `struct linked_list_node'. So if we create an object of this type, and point `ptr' at it, `ptr->next' can point at another object of this type. And `ptr->next->next' can point at another... so you see we can have a whole list of these structures, allocated one at a time (rather than in one large block), and we can keep track of them all using just one pointer to the start of the list. To mark the end of the list we can set the last node's `next' pointer to NULL.
The diagram above shows `ptr' pointing to the first of a list of three records. The first record, with `number' 7, has its `next' pointer pointing at the second, with `number' 3. That record's `next' pointer points at record 3, which has `number' 285, and record 3's `next' pointer is NULL because it's the last record in the list. The whole list is storing the numbers 7, 3, and 285, in that order.
You're probably wondering why we bother with this system. It has several advantages and several disadvantages when compared to the linear dynamic block storage mentioned above.
Firstly, it's very easy to manipulate things in the linked list. New records can be added, old records can be removed, existing records can be reordered, or moved from list to list, and lists can be split or joined with little hassle; you just need to change the values of some of the `next' pointers. Any of these operations would be awkward and time consuming to perform on a linear block -- we might have to move large amounts of data.
For example, imagine removing the second data item in a large sequential list -- we'd have to move the rest of the list forward one place. In a linked list, we just have to set the first item's `next' pointer to whatever the second item's `next' pointer is set to (i.e. point it to the third item, or NULL if there is no third item), and then we can `free' the second item's struct.
Similarly, adding a new item to the list is simple. Assuming we have a pointer to the item in the list before the place where
Page : << Previous 7 Next >>