Data Structures and Algorithms with Object-Oriented Design Patterns in C++

Projects

Compare experimentally the first-fit, best-fit, next-fit, and worst-fit storage allocation schemes described in Exercise by making suitable variations of the SinglyLinkedPool class declared in Program . Hint: Use a simulation program such as the one given in Program .
Complete the DoublyLinkedPool class declared in Program by providing suitable definitions for the following member functions: Unlink and InsertAfter. Write a test program and test your implementation.
Complete the BuddyPool class declared in Program by providing suitable definitions for the following member functions: Unlink and InsertAfter. Write a test program and test your implementation.
All three storage pool implementations given in this chapter allocate the memory used for the pool dynamically by using operator new in the pool constructor. Show by implementing suitable constructors for each of the classes that it is possible to allocate the memory used by one storage pool inside another storage pool. E.g., the code sequence
```
Pool& p = *new SinglyLinkedPool (8192);
Pool& q = *new (p) SinglyLinkedPool (1024, p);
```
creates two pools, p and q. Pool q is allocated in storage acquired from p.
Design and implement a storage pool class that manages a region of memory that is contained entirely within the pool object itself. Because the size of a class must be determined at compile time, this means that the size of the pool is a fixed constant. Write a test program and test your implementation.
Modify the SinglyLinkedPool class declared in Program so that instead of allocating memory in the constructor, we pass to the constructor the address and size of a region to be managed. Write a test program and test your implementation.
Find a C++ program that you have written which uses dynamically allocated storage. Replace the storage manager provided by your compiler and operating system by overloading operators new and delete to use one of the storage pool implementations presented in this chapter. Compare the performance of your program when using the different implementations.
Most C++ programs allocate dynamically only a small number of different object types. Consequently, only a small number of distinct sizes of areas need to be acquired.
Modify the simulation shown in Program as follows: In each cycle acquire either four bytes or 32 bytes. Use a suitable random number generator (see Section ) so that the smaller block is acquired 75% of the time.
In addition, suppose that the number of cycles that a block is in use is an exponentially distributed random variable. Assume that the smaller blocks are held on average for 10 cycles and that the larger blocks are held on average for 100 cycles.
Use the modified simulation program to compare the various storage pool implementations given in this chapter.