7 Records, pools, indexes

Builds on: Chapter 6 (collections), chapter 5 (stored text).

Questions this chapter answers

How are data with several fields held?
How are linked data such as trees and lists built without pointers?
How do I find a row by its name?
How do I read rows in order of a field?

7.1 Records and rows

record … end is a sequence of fields, each with a type (u8 u16 i32 int bool str(N) …): a u8 field reads as a u8 and takes a u8 only (2016 u16 b to book.year). Records do not travel as values. You declare a list (or array, or pool) of records and handle its rows. A row’s type is named after its table.

07-records.pnx

use io
record book
  title str(32)
  year u16
  pages u16
end
list shelf book 8
row shelf ("The C Programming Language", 1978, 228)
row shelf ("Thinking Forth", 1984, 300)
row shelf lua ("Programming in Lua", 2003)          rem a named row; pages left out: 0
word show (b shelf) cat (b book.year, " ", b book.title, ", ", b book.pages, " pages") io.println end
shelf do (b shelf) b show end each
2016 u16 lua to book.year                               rem value, row, to record.field
388 u16 lua to book.pages
lua show

Output

$ pnx 07-records.pnx
1978 The C Programming Language, 228 pages
1984 Thinking Forth, 300 pages
2003 Programming in Lua, 0 pages
2016 Programming in Lua, 388 pages

Fields are written RECORD.FIELD: b book.year reads, 2016 lua to book.year stores. row adds a row to a list outside definitions, and can name it. Adding rows while running is add_row.

07-add-row.pnx

use io
record point
  x i32
  y i32
end
list path point 4
word add_point (x int, y int or fail)
  path add_row or_fail to p                         rem a new, zeroed row at the end
  x i32 p to point.x
  y i32 p to point.y
end
word walk (or fail) 0 0 add_point or_fail  3 4 add_point or_fail  6 0 add_point or_fail end
walk or_else (e) e err_text io.println end
path do (p path) cat ("(", p point.x, ", ", p point.y, ")") io.print end each
"" io.println

Output

$ pnx 07-add-row.pnx
(0, 0)(3, 4)(6, 0)

Here are the words for rows together, with remarks. The r that add_row gives is a number inside the table; a field is stored with value row to record.field, and read with row record.field, which takes one row off and puts the field’s value on.

07-row-steps.pnx

use io
record item
  name str(12)                         rem stored text: 12 bytes inside the row
  price int
end
list cart item 4                       rem a table: room for 4 rows of item
word add_item (n str, p int or fail)
  cart add_row or_fail to r            rem a new row at the end; r is its number in the table
  n r to item.name                     rem value, row, to record.field: store a field
  p r to item.price
end
word total (gives int)
  0 to acc
  cart do (r cart) acc r item.price add to acc end each   rem each row of the table in turn
  acc
end
word main ()
  "pencil" 120 add_item or_else (e) end
  "eraser" 80 add_item or_else (e) end
  1 cart idx to second                 rem the row with number 1
  cat (second item.name, " costs ", second item.price) io.println
  cat ("total ", total) io.println
end
main

Output

$ pnx 07-row-steps.pnx
eraser costs 80
total 200

Token	Stack after it	What happened
`cart add_row`	`1`	Adds a row at the end and puts its number on (it can fail: `or_fail` follows).
`to r`	`—`	Keeps the number in `r`.
`n r`	`"eraser" 1`	The value to store, and the row.
`to item.name`	`—`	Stores into the `name` field of row 1; both come off.
`r item.price`	`80`	Takes one row off and puts its `price` on.

Q&A

Q. Is a row the address of a record?

A. No. A row is a number within its table, and its range is checked on every use. So holding the wrong row cannot damage memory; at worst it stops with a fault.

7.2 Linking by rows

A field whose type is the name of a table holds a row of that table. It starts as “none”, asked with is_none. That is how a tree is built without pointers. Since the record refers to the table that holds it, the table is announced first with forward. The cells of an array or a list hold rows in the same way: list order cities 8 (section 7.5).

07-tree.pnx

use io
use str
rem A binary search tree in a pool: rows point to rows by number, never by address.
forward pool nodes
record node
  key int
  left nodes
  right nodes
end
pool nodes node 16
global root nodes
word put_key (k int or fail)
  nodes alloc or_fail to n
  k n to node.key
  root is_none if n set root return end
  root to at
  loop
    k at node.key lt if
      at node.left is_none if n at to node.left return end
      at node.left to at
    else
      at node.right is_none if n at to node.right return end
      at node.right to at
    end
  end
end
word show (t nodes)                                  rem in order: left, self, right
  t is_none if return end
  t node.left show
  t node.key str.to_str io.print " " io.print
  t node.right show
end
word build (or fail) 50 put_key or_fail 30 put_key or_fail 70 put_key or_fail 20 put_key or_fail 40 put_key or_fail end
build or_else (e) e err_text io.println end
root show
"" io.println

Output

$ pnx 07-tree.pnx
20 30 40 50 70

Reading or storing a field of the “none” row is a fault. When following rows, ask is_none first (as the first line of show above does).

07-none-field.pnx

use io
forward list nodes
record node
  value int
  next nodes                           rem a row of nodes, or none
end
list nodes node 4
row nodes last (3)                     rem its next is none: nothing was given
last node.next node.value drop         rem reading a field of none ends the run

Fault

$ pnx 07-none-field.pnx
07-none-field.pnx:9: index out of range

7.3 Pools: taking and giving back

A pool is a table whose rows are taken (alloc) and given back (free). The row alloc gives is an owned value: on every path it shall be stored into a field or global, or given to free, exactly once. The processor checks this at load.

07-pool-leak.pnx

record node
  key int
end
pool nodes node 4
word new_node (k int or fail)
  nodes alloc or_fail to n
  k n to node.key
end

Refused

$ pnx 07-pool-leak.pnx
07-pool-leak.pnx:8:1: an owned value in a local is not given on every path (close, free or store it)

A row of a pool carries a generation besides its number. Using a row that was given back — even when someone has taken that slot again since — stops with a fault.

07-stale.pnx

use io
record node
  key int
end
pool nodes node 4
global keep nodes
word demo (or fail)
  nodes alloc or_fail to n
  n set keep
  keep nodes free
  "the row is given back" io.println
  keep node.key drop
end
demo or_else (e) end

Fault

$ pnx 07-stale.pnx
the row is given back
07-stale.pnx:12: a row or handle was used after it was given back
  n nodes = 4294967297

7.4 Indexes

index NAME TABLE RECORD.FIELD is a hash table that finds rows by one field. lookup finds the row of a key (failing with not_found when there is none). Rows written with row are in it from the start.

07-index.pnx

use io
record user
  name str(16)
  age u8
end
list users user 8
index by_name users user.name
row users ("kim", 30)
row users ("lee", 25)
word register (name str, age int or fail)
  users add_row or_fail to u
  name u to user.name
  age u8 u to user.age
  u by_name insert or_fail                          rem without this, lookup does not see it
end
word age_of (name str gives int or fail) name by_name lookup or_fail user.age raw end
"park" 41 register or_else (e) e err_text io.println end
"kim" 31 register or_else (e) cat ("kim again: ", e err_text) io.println end
word show (name str) cat (name, ": ", name age_of or_else (e) -1 end) io.println end
"lee" show
"park" show
"choi" show

Output

$ pnx 07-index.pnx
kim again: failed
lee: 25
park: 41
choi: -1

Common mistake: A row added with add_row is in the index too

It is not. A row added while running is found by lookup only after insert, as register above does. When the key is there already, insert fails and the row added with add_row stays in the list — so it is cleaner to lookup the key first and add after.

An index may also be over a pool. Then a store can both find its rows by key and give rows back: free takes the row out of every index over its pool, so a key given back is not found any more, and its slot is taken again by the next alloc. key INDEX has asks whether a key is there, without failing. A pool is walked with each, which visits the rows alive, in the order of their slots; to read them in another order, push them into a list of rows and sort that.

07-pool-index.pnx

use io
record item
  name str(12)
  count int
end
pool items item 3
index by_name items item.name
list order items 3
word count_in (name str or fail)
  name by_name has not if
    items alloc or_fail to r              rem a free row: three at most
    name r to item.name
    r by_name insert or_fail              rem the index keeps it now
  end
  name by_name lookup or_fail to r
  r item.count 1 add r to item.count
end
word drop_out (name str)
  name by_name lookup or_else (e) return end items free
end
word show ()
  order clear
  items do (r items) r order push or_else (e) end end each
  order items sort_by item.name
  order do (r items) cat (r item.name, " ", r item.count) io.println end each
end
"pear" count_in or_else (e) end
"fig" count_in or_else (e) end
"pear" count_in or_else (e) end
"plum" count_in or_else (e) end
"kiwi" count_in or_else (e) cat ("kiwi: ", e err_text) io.println end
"fig" drop_out
"kiwi" count_in or_else (e) end           rem the row fig gave back
show

Output

$ pnx 07-pool-index.pnx
kiwi: full
kiwi 1
pear 2
plum 1

Common mistake: After insert the local still holds the new row

It does not. A row alloc has just given is owned, and insert takes it over as storing it in a field does: when the key is there already, insert gives the row back to the pool and fails, so nothing is lost. Fill the row before insert, and find it again by its key afterwards, as count_in above does.

07-pool-insert-gone.pnx

record item
  name str(12)
  count int
end
pool items item 3
index by_name items item.name
word enter (name str or fail)
  items alloc or_fail to r
  name r to item.name
  r by_name insert or_fail
  1 r to item.count
end

Refused

$ pnx 07-pool-insert-gone.pnx
07-pool-insert-gone.pnx:11:5: this local gave its owned value away; it holds nothing to read

Q&A

Q. Can a row of one table go into another table?

A. No. The type of a row is the name of its table. A row of cart is used with cart only; given to a field or a list of another table it is refused as the wrong type. To move a row between two tables of the same record, read the fields one by one into a new row, or copy with filter_into (chapter 6).

7.5 Rows in order

sort puts the cells of an array or a list in order, from the smallest; sort_desc from the largest. Rows are not sorted that way: an index, a field or a global may keep a row by its number, and moving the rows would make those wrong. A list of the rows is sorted instead, by a field of the rows: order cities sort_by city.name, where order is declared as list order cities 8, a list whose cells are rows of cities. The rows stay where they are and order says in which order to read them. A list of row numbers (int) is sorted the same way.

07-sort.pnx

use io
record city
  name str(16)
  people int
end
list cities city 8
list order cities 8                           rem rows of cities
list sizes int 8
word city_of (n str, p int or fail)
  cities add_row or_fail to r
  n r to city.name
  p r to city.people
  p sizes push or_fail
end
word main (or fail)
  "Lyon" 522 city_of or_fail  "Nice" 342 city_of or_fail  "Paris" 2103 city_of or_fail  "Lille" 236 city_of or_fail
  sizes sort_desc
  cat ("largest: ", 0 sizes idx) io.println
  cities do (c cities gives cities) c end order map_into or_fail
  order cities sort_by city.name
  order do (c cities) c city.name io.println end each
end
main or_else (e) e err_text io.println end

Output

$ pnx 07-sort.pnx
largest: 2103
Lille
Lyon
Nice
Paris

07-sort-rows.pnx

record city
  name str(16)
  people int
end
list cities city 8
index by_name cities city.name
word order_them () cities sort end

Refused

$ pnx 07-sort-rows.pnx
07-sort-rows.pnx:7:27: rows do not move: sort a list of their numbers by a field: order table sort_by record.field

Q&A

Q. How do I sort by two fields?

A. Sort twice, the less important field first: order t sort_by r.name and then order t sort_by_desc r.count gives the largest counts first, and the same count by name. A sort keeps the order of equal keys, so the second sort leaves the first one’s order among the rows it finds equal.

Common mistake: sort_desc is sort read backwards

Only for cells, where two equal cells cannot be told apart. For rows it is not: sort_by_desc keeps equal keys in the order they had, as sort_by does, and reading a sort_by backwards would reverse them.

Summary

Cells are sorted with sort and sort_desc; rows through a list of the rows (or of their numbers) with sort_by and sort_by_desc, which keep the order of equal keys (standard 15.3).
Records are handled as rows of tables; fields are read and stored as RECORD.FIELD (standard 8.8).
A row is a number checked on every use; a field of the none row is a fault (8.8).
A row of a pool is handed over once; a row given back is a fault (8.9, 12.4).
An index holds the rows of row; rows added while running are inserted (8.10).
An index may be over a pool: insert takes over a row just taken, free takes a row out of the indexes, has asks for a key, and each walks the live rows (8.9, 8.10).