Buffering Up
Published: 2019-08-19 15:47:52

Part 4 in this meandering journey toward durable data structures. Part 3 was [here](https://dev.to/quoll/a-simple-structure-in-binary-6lj), or go back to [the beginning](https://dev.to/quoll/what-s-with-data-structures-2fk7).

A word of warning: like the previous post, this one is also very code-heavy. I explain it all in detail, so it may feel like it bogs down. But this also forms the basis of a lot of work moving forward, so I think it's important to be explicit in every aspect.

# Buffers
Today I'm going to switch gears and move to Java. There are several reasons for this:
- Java is a higher-level language than C. I was tempted to show strings in past posts but figured I'd end up spending far too much time explaining it, with no benefit. Suffice to say that no one wants to get into why we want `strncat` instead of `strcat`, using largish buffers for holding strings temporarily, and possibly having to allocate larger buffers as your string grows in size.
- Java is an Object-Oriented language. This allows objects to store some of the context, while C needed to explicitly pass context around. Objects are also referred to by reference, and pointers disappear.
- Java has a type of class called a `Buffer`. These can represent large blocks of memory, just like we got from `malloc` in C.
- Java can't layer records over a buffer like C can (or Erlang. This is a lovely feature in Erlang if you ever get to use that language). But it does provide addressed access to the buffer, with methods like `getLong` and `getByte`. It takes more work, but we can still get the functionality we want.
- Java buffers are designed specifically for I/O, meaning that they can be sent to disk easily.
- Java supports memory mapping files, and buffers are the interface for doing this.
- Anything that can be done in Java can be done in any other language that runs on the Java Virtual Machine (JVM). This includes one of my target languages: [Clojure](https://clojure.org/).

My other targeted system is Javascript, so for anyone who isn't interested in the JVM, please be assured that I will get there! Eventually.

# Getting a Buffer
In C we used the `malloc` call. We can do something similar in Java by asking for a buffer of the correct size. The size to ask for was the size of each element multiplied by the number of elements. In C it was easy to get the size of the structure with the `sizeof` operator, but no such operator exists in Java. This is partly because objects in Java always have extra space allocated for methods and type information, so the memory usage doesn't relate directly to the data being stored as it does in C. This means that we need to figure out the size for ourselves.

In this case, we're going to use 2 integers for the elements: the `next` pointer, and the `value` of the element. That's `2 * sizeof(int)`, except we don't have a `sizeof` operation. That's OK because for basic types the sizes are included:
`int ELEMENT_SIZE = 2 * Integer.BYTES`

We can then allocate a `ByteBuffer` of 10 elements with the static `allocate` method on `ByteBuffer`:
```java
ByteBuffer buffer = ByteBuffer.allocate(ELEMENT_SIZE * 10);
```

Java is an object-oriented language. That means that we can use an object to hold the management of the buffer and allocation of elements for us. I'm going to call this object `BufferList` since it will manage a list that is represented in a buffer. This object is also the natural place to store the constant values that we need, like the array size, and offsets for the parts of the `Element` objects.

The first part of an `Element` is the integer holding the pointer for `next`. Since this is at the start of the object, it will be offset from the object by `0`. The second part is the integer containing the `value`. This will be offset from the start of the object by the size of `1` integer. We can do this in bytes (`1 * Integer.BYTES`, which is 4 bytes), or if we present the same data as integers then we can represent it as an offset of `1`.

So here is the start of our BufferList class:
```java
  public static int ELEMENT_SIZE = 2 * Integer.BYTES;
  public static int NULL = -1;

  private static int NEXT_OFFSET = 0;
  private static int VALUE_OFFSET = 1;

  private ByteBuffer buffer;
  private int nextAvailable;

  public BufferList() {
    this(10);
  }

  public BufferList(int length) {
    buffer = ByteBuffer.allocate(ELEMENT_SIZE * length);
    nextAvailable = 0;
  }
```
This gives us the buffer to work with (just like the `malloc` in C), and also the size of each element and the locations of the fields within each element. We are handling it manually in Java whereas C had facilities to do it for us, but we are still getting the same effect.

# Buffer Management
The `BufferList` object is not just holding the buffer; it is also managing it. To do this, it remembers the latest place that it can allocate space from using the `nextAvailable` value. The constructor initializes this to the start of the buffer, which is offset `0`.

In our [Javascript linked list](https://dev.to/quoll/a-simple-structure-2cmh#listConstruction) we created a new element to add to the front of the list by using the `Element` constructor. To do [the same thing in C](https://dev.to/quoll/a-simple-structure-in-binary-6lj#add_element), we had a helper function that allocated the required memory and set the values, this was then updated to [a function](https://dev.to/quoll/a-simple-structure-in-binary-6lj#init_element) that captured the required memory from the overall buffer.

To do the same thing in Java, we can introduce an `addToHead` function. This will call the Element constructor the same way as the Javascript code did, but it can also provide the context of the allocated buffer and the location of the next free space to use. An additional benefit of Java is method overloading, so an extra `addToHead` method can be created that doesn't need a list provided. This is just a shortcut to create a single element list, and just calls the main version of the method with a `null` value for the next part of the list.
```java
  public Element addToHead(int value) {
    return addToHead(null, value);
  }

  public Element addToHead(Element nextElt, int value) {
    if (nextAvailable * ELEMENT_SIZE >= buffer.capacity()) {
      throw new RuntimeException("Out of memory");
    }
    return new Element(nextAvailable++, nextElt, value);
  }
```
The first thing that the `addToHead` method does is to ensure that the buffer isn't already full. That's not going to be the case in this code, since there is space for 10 elements, and I only ask for 9, but I get uncomfortable not doing the check. (I should have done it with the C code as well!)

We can see that the main work is done in the final line. It uses the current offset for the next element that can be allocated. It passes this, along with the arguments along to the `Element` constructor. After this, the next available element index is incremented. The buffer is not explicitly mentioned here, as it will be passed along automatically in the context of the `BufferList` class. We'll see how that happens now.

# Elements
Since `Element` objects will always be associated with the buffer it was created with, then it makes sense for `Element` objects to be associated with the buffer manager. Java supports this by allowing the `Element` class to be an inner class of `BufferList`. This way it has automatic access to all of the static constants, and the allocated buffer.

The best way for an `Element` to be associated with its associated data is to take a _slice_ of the buffer that refers to the relevant data. This is done by setting the `position` of the buffer as the start of the slice, and the `limit` as the end. Each method for these operations returns the modified buffer, so the operations can be chained:
`buffer.position(offset).limit(offset + ELEMENT_SIZE).slice()`

The data for these objects is going to consistently represent integers, so the bytes can be reinterpreted as integers by representing them in an `IntBuffer`.

In the C example, the element was constantly being derived out of the buffer from its index. In Java, the `Element` objects can get everything it needs during construction, which means that it will lose the index of the element if we don't save it, so that goes into an `index` field.

We also want a few different constructors.

## Constructors
The first constructor takes just the `index` of the element. This allows it to capture the appropriate slice of the buffer, wrapping any values that may already be there. This is how we set up a fresh element but is also how we can read an existing element.

The next constructor uses the previous one to capture the appropriate slice from the main buffer and then sets the `next` and `value` fields. Note that since this code is using `Element` objects, then the `next` need not be passed as an element index value in the way the C code did it. Instead, it expects an actual element.

The final constructor is just a convenience that doesn't have a `next` value, indicating that it is just the element at the end of the list. All it does it call another constructor using a `null` value for the `next` element.
```java
  Element(int index) {
    this.index = index;
    int offset = index * ELEMENT_SIZE;
    intBuffer = buffer.position(offset).limit(offset + ELEMENT_SIZE).slice().asIntBuffer();
  }

  Element(int index, Element next, int value) {
    this(index);
    setNext(next);
    setValue(value);
  }

  Element(int index, int value) {
    this(index, null, value);
  }
```
At this point, we have `Element` objects that wrap data from the buffer. So now we need to provide _getter_ and _setter_ methods that access that data.
<a name="getters"/>
## Getters
The method for `getIndex` just references the index provided when the `Element` object was created. The `getNext` and `getValue` methods are more interesting.

`getValue` reads the integer from the offset for values, which was defined as `VALUE_OFFSET`.

`getNext` is different, as it needs to return an `Element` object. It reads the integer at the `NEXT_OFFSET` as the index for the element to be read. If this number is `NULL` (defined as `-1`) then no object is returned. Otherwise, the first constructor is called, creating an object that reads from the given position.
```java
  public int getIndex() {
    return index;
  }

  public int getValue() {
    return intBuffer.get(VALUE_OFFSET);
  }
                                                                                                                                                                                                                                               
  public Element getNext() {
    int nextId = intBuffer.get(NEXT_OFFSET);
    return nextId == NULL ? null : new Element(nextId);
  }
```
## Setters
The `index` of the element never changes, so it does not need a _setter_ method. This means that only `setNext` and `setValue` need to be defined. Again, the `next` value is set to `NULL` (`-1`) if the provided object is `null`. Note that `this` is returned from setters, so that multiple setters can be called in a row, in the same way that the slice was done in the first constructor. This isn't necessary, but it's a useful standard to follow.
```java
  public Element setValue(int value) {
    intBuffer.put(VALUE_OFFSET, value);
    return this;
  }

  public Element setNext(Element next) {
    intBuffer.put(NEXT_OFFSET, next == null ? NULL : next.getIndex());
    return this;
  }
```
# Printing
Just like we did in the [Javascript code for `listString`](https://dev.to/quoll/a-simple-structure-2cmh#listString), we can traverse the list recursively. Unlike Javascript, converting numbers to strings with the `+` operator only ever occurs if the value on the left of the `+` sign is already a string. This isn't the case here, so we use the `Integer.toString()` method to do that for us. Otherwise, the function is quite similar to the Javascript function `listString`.
```java
public static String listString(Element element) {
  Element next = element.getNext();
  String valueString = Integer.toString(element.getValue());
  if (next == null) return valueString;
  else return valueString + ", " + listString(next);
}
```
The `listString` function does not reference the buffer itself, instead using the current element to obtain its information. Because of this, the method can be static, meaning that it doesn't need to access any of the values that are local to its context. It doesn't really matter, but it's slightly more efficient.

We can then define a `toString` method on Elements to call this.
```java
public String toString() {
  return listString(this);
}
```

# Building a List
With the buffer management in `BufferList` and the `Element` objects defined, the code for building a list is quite similar to what we built in other languages.
```java
BufferList bufferList = new BufferList(10);
BufferList.Element list = bufferList.addToHead(34);
list = bufferList.addToHead(list, 21);
list = bufferList.addToHead(list, 13);
list = bufferList.addToHead(list, 8);
list = bufferList.addToHead(list, 5);
list = bufferList.addToHead(list, 3);
list = bufferList.addToHead(list, 2);
list = bufferList.addToHead(list, 1);
list = bufferList.addToHead(list, 1);
System.out.println(list);
```

Running it all gives exactly the same result that we saw in previous iterations
```bash
~/src$ java buffer.ListExample
1, 1, 2, 3, 5, 8, 13, 21, 34
```
The complete java code for this program can be found [here](https://gist.github.com/quoll/98526b593f6f0150060acb9f1e983857). It's all in a package called `buffer`, so don't forget to put it in a directory of that name if you want to compile it.
# Recap
This post showed how the principles demonstrated when storing a Linked List structure in a memory buffer can be translated into another language. The tools of directly mapping the memory into the desired records may be missing, but object definitions can be used to fill this gap with getters and setters. At the same time, the encapsulation of context that objects provide can hide some of the manual aspects of managing the memory buffer.

# Up Next
The astute reader may have noticed that buffers are in a Java package called `nio`. This stands for "New I/O" and refers to a library of operations for efficiently storing and retrieving data, both on the network and on disk. We will start looking at how to save and retrieve the data that we have been working with, all in the [next post](https://dev.to/quoll/storage-8gp).