Dynamically Growing Your Arrays
Write a main() routine to go with the above function, check the original storage array, and
fill it with enough elements that you cause a reallocation to take place.
Extra Credit:
Add a couple of statements to add_element() so that it is also responsible for the initial
memory allocation of the dynamic area. What are the advantages and disadvantages of
doing this? How could you use setjmp()/longjmp() to gracefully cope with an error in
growing the table?
This technique of simulating dynamic arrays was extensively applied to SunOS in version 5.0. All the
important fixed-size tables (the ones that imposed limits which people hit in practice) were changed to
grow as needed. It has also been incorporated in much other system software, like compilers and
debuggers. The technique is not suitable for blanket use everywhere, for the following reasons:
- The system may slow down at unpredictable points when a large table suddenly needs to
grow. The growth multiple is a vital parameter. - The reallocation operation may well move the entire memory area to a different location, so
addresses of elements within the table will no longer be valid. Use indices instead of element
addresses to avoid trouble. - All "add" and "delete" operations must be made through routines that preserve the integrity of
the table— changing the table now involves more than just subscripting into it. - If the number of entries shrinks, maybe you should now shrink the table and free up the
memory. The shrinkage multiple is a vital parameter. Everything that searches the table had
better know how big it is at any given instant. - You may have to protect table access with locks to prevent one thread reading it while
another thread is reallocating it. Locking may well be required for multithreaded code anyway.
An alternative approach for a dynamically growing data structure is a linked list, at the cost of no
random access. A linked list can only be accessed serially (unless you start caching addresses of
frequently accessed elements), whereas arrays give you random access. This can make a huge
difference to performance.
Some Light Relief—The Limitations of Program Proofs
The problem with engineers is that they cheat in order to get results.
The problem with mathematicians is that they work on toy problems in order to get results.