Review

Linked data structures are extremely useful in both C and C++ programming, and they are employed for modeling many diverse aspects of real systems. They are used in situations where the data structure must be built dynamically, or where its parts are built at different times, or where the mutual relationships among the constituent parts change in time. They are extremely flexible, making it easy to add, remove, or modify a part of the data structure. They can also be fashioned to provide maximally efficient access to the data they store. Usually, linked data structures are created on the heap (dynamic memory), and pointers are used as the links. However, it is also possible to build linked data structures on the system stack and/or without pointers.

The flexibility of linked data structures, though desirable and welcome, is an obstacle to three increasingly common tasks in an age of networks and distributed computing: (a) moving a structure to another place in memory; (b) storing a structure in a disk file and restoring it from the disk file; and (c) transmitting a structure across a communication channel.

We say that a linked data structure is serialized if it is stored in several contiguous memory segments and if all the addresses in the structure are relative to the beginning of the segment in which they are located. We use the term relativization to denote the process of replacing the actual addresses by these "relative" ones. The reverse process, which restores the relative addresses back to actual addresses, is called absolutization. We have shown by example how to serialize a binary tree using the technique of memory allocation from a specific arena and properly overloading operators new and delete . A handy aspect of this approach is the need to append just slightly to the existing code for the data structure, code that otherwise remains intact. Besides that, our approach preserves padding and so the usual referencing of items by pointers or as members works well. A serialized structure can be easily moved, recorded/restored, or transmitted as long as source and destination places have the same memory alignment.

We call a linked data structure compacted if it is stored in a single contiguous memory segment and if all the addresses in the structure are relative to the beginning of the segment. We gave an example of compacting a search tree. In our approach, the padding is intentionally not preserved. A compacted structure can be easily moved, recorded/restored, or transmitted even if the source and destination places have different memory alignments. However, items in a compacted structure cannot be accessed through the usual referencing by pointers or members. Specialized access functions allowing retrieval and storage in locations not properly aligned must be provided.

Allocation from a specific arena can greatly improve the performance of any program that does a lot of allocation and deallocation of small chunks of memory. In the arena approach, only the whole arena is allocated via a call to the process memory manager ( malloc() , new ) and deallocated as a whole when no longer needed; the allocation and deallocation of smaller items is handled within the arena much faster and more efficiently .