Malloc, Free, and the Mall of New Athens

Malloc and Free are commands in the C programming language that are used for dynamic memory allocation. Malloc allocates a block memory of a given size (passed in as an argument) and returns a pointer to that memory. Free takes in a pointer to a block of memory and releases that memory. While this level of memory management is often hidden in many modern programming languages, understanding it can provide valuable insights into how computer memory works.

In ancient times, the mall of New Athens served eighteen different neighboring kingdoms with a combined population of millions. The mall itself was an engineering marvel. It was designed by the the famous architect Hans Lloyd Wright IV. It had the first known three story eatery and the third known use of stained-glass skylights. Visitors would gasp in awe at the sheer number of shops and miles of kiosks. A shopper could find any item they were looking for in at least six different stores.

Even the parking lot itself was hundreds of years more advanced than any other civilization. It introduced an entirely new approach to parking lots: dynamic, coordinated parking. The system was devised by two entrepreneurial brothers: M'Alloc and F'Ree. They had first conceived of the dynamic parking allocation system after spending seventeen hours searching for a parking space in Alexandria. Frustrated, they eventually drove their horses home, vowing to never let this happen in their own town.

The coordinated parking system itself was relatively simple. It was based on centralized coordination with the brothers. The two brothers sat in a small, but surprisingly comfortable, kiosk at the parking lot's only entrance and exit. One brother sat facing a window toward the entrance and the other sat facing the exit. Between them was a giant map of every parking space around the mall.

Upon entry, visitors would pull their horses, carts, double-carts, or long-cart-trains up to the entry attendant M'Alloc's window. M'Alloc would consult the master map, find them spaces in which to park, and hand them a small blue stone token. The token would list the starting slot number where they could park. Horses needed one slot, carts needed three slots and double carts needed five. If there was an appropriately-sized, open space for you to park, M'Alloc would know about it and direct you there. He would also mark off the appropriate spaces as occupied, so that he would not accidentally send someone else there.

Shoppers would keep their small blue tokens while they shopped. If they ever needed to go put bags in their car, they would consult the token and know where they had parked. But if a shopper lost their token, they were in trouble. With nearly two million parking slots it took a lot of walking to find your cart. It is said that, it took one unfortunate shopper two years of checking different slots in order to locate his cart after he had made the blunder of mistaking his parking token for a piece of hard candy.

And on the way out of the mall, shoppers would return their token to the exit attendant F'Ree. F'Ree would mark the corresponding slots on the master map as open. He would smile, wish you a good day, and help point you to the freeway.

It was a great system. However, like all great systems, it relied on a certain level of competency among the shoppers. If a shopper lost a token, they had to slog through the entire parking lot looking for their carts. And without a token F'Ree refused to cross that space off the master map, so it would be marked "occupied" forever. In fact, after five years of operation there were over a thousand "wasted" spaces due to lazy shoppers losing tokens. It was a sore subject with the brothers.

Despite the downsides, the parking lot was a monumental achievement. It handled millions of shoppers coming in and leaving every week. Not until the opening of the Manhattan Mega Mall, which itself encompassed the entire island of Manhattan, would another parking lot even start to compete with its scale or efficiency.

Linked Lists, Kindergarten, and Ocean Voyages

Linked lists are simple data structures that store a list of items. Each node in the list consists of a few pieces of data: the information being stored at that node (or a pointer to it), a pointer to the next node in the list, and (optionally) a pointer to the previous node in the list. An algorithm can traverse the items in a list by simply following the pointer out of each node to the next. However, random access of nodes is not possible, unless additional pointers to the nodes are stored in an outside data structure. Linked lists support easy insertion and deletion of elements, by simply changing where appropriate nodes' pointers are pointing.

Ann had been excited about her ocean voyage to New Atlantis for approximately twenty minutes. She had stood at the ships railing, watching the shoreline move away and feeling the sea breeze on her face. The ship's sails had made a pleasant flapping noise as they caught the wind. It had been exhilarating. Then, much to her dismay, the ship had started a nauseating series of sways and lurches. That had been three days ago and the movement had not ceased for a moment.

Bundled up against the (now remarkably frigid) breeze, Ann sat on the ship's deck and watched the three ships following silently after them. The first was only four hundred meters behind, the second four hundred meters after that, and the third another four hundred. In addition, Ann knew there was another ship leading the way four hundred meters in front of them. Together the five ships made a convoy that stretched out in a mile-long line across the ocean.

Ann had found the arrangement of the convoy fascinating. When she had interrogated the captain to the convoy's linear arrangement, he had happily explained the line's functionality in exquisite detail. The convoy consisted of a chain of ships, navigating along the same route. The head ship led the convoy. Supposedly, this arrangement facilitated both navigation and safety.

Communication among the ships was also fascinating. Each ship had two crew members called pointers, whose job it was to communicate with the other ships. When someone on ship #2 wanted to pass a message to ship #5, the Pointer at the back of ship #2 would signal the message out to ship #3. Similarly, ship #3 would relay it to ship #4 and ship #4 to ship #5. It was a completely linear system, with the message passing through each ship on its way.

The whole arrangement reminded Ann of her days as a young kindergartener when the class would be forced to hold hands as they went on field trips. Each kid would maintain contact with exactly two classmates, assuring the full string of students stayed completely connected. The teachers would walk down the line carefully comparing the students to a list of names and ensuring that everyone was present.

But in Ann's mind, the best thing about the kindergarten lines were their ability to be dynamic. When one student had to visit the restroom, they would leave the line by simply making sure that the students on either side of them held hands with each other. This operation was usually marked with a careful shuffling of grips, but always resulted in the class maintaining its line (minus the kid running to the restroom). And, when the student returned, they would: pick a point to insert themselves in the line, break the line at that point, and make sure they reformed the connections by holding hands of the correct two people. This line concept had made such an impression, that Ann had spent years marveling at the power of pointers and dynamic data structures.

"Captain, do your convoys ever get additions or removals?" Ann asked one morning. "Or is the convoy fixed once it departs?"

"Of course the convoy changes." the captain answered. "In fact, later today we have three ships joining us from North Patagonia." He gestured vaguely toward the direction of North Patagonia as if to illustrate his point.

"Will they join the end of the line?" asked Ann, eager to understand the convoy's dynamics. It would make sense to simply append the new ships to the end of the line. That way only the first ship of the new arrivals and the last ship of the current convoy would need to connect. That is how they had merged lines in kindergarten.

"No, no." insisted the captain. "They will join between ships #4 and #5. Ship #5 is a special warship with extra rear facing cannons. It always has to be in the back. One by one the ships will insert themselves into the chain, coordinating through their pointers. Good sailors, those pointers."

"But how?" asked Ann. For the first time in days she had forgotten her sea sickness. She was distracted by the beauty of dynamic structures.

"All very simply, I assure you. The new ship, let's call it D, will pull up next to our head ship (A) and then slow down. It will slowly work its way down the convoy until it finds a location to be inserted: let's say after ship A. Then the D's pointer coordinates with B's pointer to say 'You are now behind us.' and ship B moves back to let D in. At the same time D's other pointer coordinates with ship A's pointer to say 'We are now behind you.' It is all very organized."

(Ship D joins convoy between ships A and B)

Ann was thrilled. When the ships arrived that afternoon, she watched their coordinated dance with glee. The simplicity of it amazed her. Inserting new ship into the line was only a matter of four pointers, two in each direction. In her excitement over the dynamic operations of the convoy, Ann even managed to forget about her seasickness.

---------------------

Interested in learning more about linked lists? See why choose your own adventure stories should never be linked lists or how Zed used linked lists while expanding his coffee shop.

Pointers and Walk-In Closets

Pointers are variables that hold a particular type of data: addresses in the computer's memory. A main advantage of using pointers is the flexibility that they provide when interacting with data stored in memory. A single, relatively small, pointer can give the location of a massive chunk of data sitting in memory, allowing functions to access the data without having to pass around the full block of data itself. Programmers can also create complex data structures by using pointers to link different blocks of data.

The powerful Wizard Marcus lived in a small apartment in downtown New Athens. The rent was high and the views were terrible, but that was the price of living downtown. To be honest, neither of those factors bothered Marcus. What annoyed him was the size of the apartment. Marcus had accumulated many belongings over the years, and he liked having a place to put them all. The apartment had only one pathetically small closet.

Being a wise and powerful magician, Marcus turned to magical solutions to make his life better. First, he shrunk all of his belongings so that they would all fit in his closet. This created quite a mess. There were so many tiny items thrown into the closet that he could never find anything. One night it took him hours of searching with a magnifying glass in order to find his favorite wizard's hat. As a result, he was tremendously late for a date.

Next, he tried dehydrating all of his possessions down to powder and putting them in labeled jars. His closet soon resembled a spice rack filled with hundreds of tiny jars. Unfortunately, rehydrating cloths left them thoroughly soaked, and a single poorly timed sneeze scattered his favorite cloak over his living room. Marcus quickly abandoned that idea as well.

Finally, he realized that he did not need to actually keep all of his possessions “right here” as long as he could easily retrieve them. He bought a huge castle in the rural outlands to store his belongings. When he needed an object, he would summon it. Similarly, when he was done with using it, he would send it back. The process effectively gave him a giant virtual closet.

In only a short matter of time, Marcus found that he had a new problem. He no longer remembered what was in the castle or even how much space he had left. He found himself randomly summoning items from different rooms in the castle just to see what was there. Marcus needed a better system.

In order to keep track of what he stored in the castle and where it was, Marcus created a formal accounting system. He divided the castle into a giant labeled grid of squares, each indicating different spaces where items could be. Then he created a scroll listing all of his items. Each time he sent an item to the castle, he carefully recorded a pointer to where that object was sent. Using this scroll he could quickly find the location from which to summon any item. He only needed to keep one small scroll of pointers in his downtown apartment. This system worked great.

Or, at least, the system worked great most of the time. Occasionally, Marcus got careless and forgot to record where he sent an item. As a result the item was lost and the space inside the castle wasted. Other times, Marcus would forget to check that a space was free before sending an object there. One night, after returning from a party, he accidentally sent his coat to the same location as a priceless vase. The vase exploded as the large coat appeared inside it. These were the inherent dangers of carelessness with his pointers.

Despite the occasional accident, the system worked well. Marcus learned to be careful about tracking everything in his scroll, and he was able to live for many years in the most fashionable neighborhoods.