Applied Pokology                                           Back to blog...

     _____
 ---'   __\_______
            ______)         
Interesting poke idiom: sparse tables
            __)             
           __)
 ---._______)

                                                          Jose E. Marchesi
                                                          January 28, 2023



During tonight poke online office hours our friend hdzki came with an
interesting use case.  He is poking at some binary structures that are
like sparse tables whose entries are distributed in the file in an
arbitrary way.

Each sparse table is characterized by an array of consecutive non-NULL
pointers.  Each pointer points to an entry in the table.  The table
entries can be anywhere in the IO space, and are not necessarily
consecutive, nor be in order.

Example of such a table with three entries:

,----
|          IO space
| 
|     |                |
| +-->|     item2      |
| |   |                |
| |   :      ...       :  
| |   |                |
| |   +----------------+ <------- table
| |   |      ptr1      |------+
| +---|      ptr2      |      |
|     |      ptr3      |---+  |
|     +----------------+   |  |
|     |                |   |  |
|     |                |   |  |
|     :      ...       :   |  |
|     |                |   |  |
|     |     item3      |<- +  |
|     |                |      |
|     :      ...       :      |
|     |                |      |
|     |     item1      |<-----+
|     |                |
|     :      ...       :
`----


How to poke at this?

First, we define the things themselves.  This can be any structure, but
this will serve for this example:

,----
| type Thing =
|   struct
|   {
|     byte control;
|     string data;
|   };
`----


Then, the pointers, which are 32-bit long, in bytes, and not NULL:

,----
| type Pointer =
|   struct
|   {
|     offset<uint<32>,B> ptr : ptr != 0#B;
|   };
`----


Then the sparse table itself:

,----
| type Sparse_Table =
|   struct
|   {
|     Pointer[] ptrs;
|     computed Thing[] items;
| 
|     method get_items = Thing[]:
|     {
|       var items = Thing[]();
| 
|       for (p in ptrs)
|         apush (items, Thing @ p.ptr);
|       return items;
|     }
| 
|     method _print = void:
|     {
|       printf "#<%v>", items;
|     }
|   };
`----


Interesting things to note:

- The array of pointers will cover every consecutive 32-bit pointer
  until the first NULL pointer, exclusive.  This is achieved by having
  the constraint in the Pointer struct.  Remember that unbounded array
  types are mapped until either EOF is encountered or a constraint
  fails.

- The computed field items constructs a _non-mapped_ array that
  contains mapped Things at the right place.  This is an interesting
  example where poke's ability to mix mapped and non-mapped values
  transparently really pays back.

- The pretty-printer helps to visualize the items stored in the sparse
  table.  However, we follow the poke convention of enclosing
  pretty-printed values between #<...> so the casual user of the
  definitions above won't be induced to thing that a sparse table is an
  array: it is not.

Let's see this in action.  First, we open an all-zeroed memory IO space
as our play ground:

,----
| (poke) .mem foo
`----


Then, lets plant a few Things around at some memorable offsets and the
table of consecutive pointers at offset 0:

,----
| (poke) Thing @ 100#B = Thing { control = 1UB, data = "one" }
| (poke) Thing @ 200#B = Thing { control = 2UB, data = "two" }
| (poke) Thing @ 300#B = Thing { control = 3UB, data = "three" }
| (poke) Pointer[] @ 0#B = [Pointer { ptr = 100#B }, Pointer { ptr = 200#B }, Pointer { ptr = 300#B }]
`----


And finally let's map our sparse table:

,----
| (poke) var table = Sparse_Table @ 0#B
| (poke) table
| #<[Thing {control=1UB,data="one"},Thing {control=2UB,data="two"},Thing {control=3UB,data="three"}]>
`----


At this point, we can access the items comfortably by using the computed
field.  Since the array elements are mapped, they will always show
actual contents, and modifying them modifies the underlying bytes in the
IO space:

,----
| (poke) table.items[1].data = "quux"
| (poke) Thing @ 200#B
| Thing {
|   control=2UB,
|   data="quux"
| }
`----


Disabling the pretty-printer we see the crude reality of what a
Sparse_Table structure really is, a sequence of pointers:

,----
| (poke) .set pretty-print no
| (poke) table
| Sparse_Table {
|   ptrs=[Pointer {
|     ptr=100U#B
|   },Pointer {
|     ptr=200U#B
|   },Pointer {
|     ptr=300U#B
| }]
`----


Happy poking!