_____
 ---'   __\_______
            ______)         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 #&lt;...&gt; 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!