MAWK-ARRAYS(7)

Okay bestie, gather round, because this is mawk-arrays(7) from the Miscellaneous section 🧚💖 It's basically the design diary for how mawk stores awk arrays under the hood, and it is lowkey iconic.

---

✨ NAME ✨

mawk-arrays — design notes for mawk's array implementation 🎀

✨ SYNOPSIS ✨

This is the documentation for the mawk implementation of awk arrays 💅 In awk, arrays are associations of strings to awk scalar values, and mawk stores those associations in hash tables 🦋 The hash table scheme was influenced by, and is similar to, the design in Griswold and Townsend, The Design and Implementation of Dynamic Hashing Sets and Tables in Icon, Software Practice and Experience, 23, 351-367, 1993. Very academic, very cute 📚

✨ DATA STRUCTURES ✨

🌸 Array Structure 🌸

The type ARRAY is a pointer to a struct array 🫶 The size field is the number of elements in the table. The meaning of the other fields depends on the type field.

There are three types of arrays, and they're told apart by the type field in the structure. Here they are:

• AY_NULL 💤 The array is empty, and the size field is always zero. The other fields have no meaning, so don't go looking for vibes in them 🙈
• AY_SPLIT ✂️ The array was created by the AWK built-in split. The return value from split is stored in the size field. The ptr field points at a vector of CELLs, and the number of CELLs is the limit field. It is always true that size ≤ limit. The address of A[i] is (CELL*)A->ptr+i-1 for 1≤ i ≤ size. The hmask field has no meaning here, so it's not giving anything 💀
• Hash Table 🪣 The array is a hash table. If the AY_STR bit in the type field is set, the table is keyed on strings. If the AY_INT bit in the type field is set, the table is keyed on integers. Both bits can be set, and then the two keys are consistent, i.e., looking up A[-14] and A["-14"] will return identical CELL pointers, even though the lookup methods are different 👑 In this case, the size field is the number of hash nodes in the table. When inserting a new element would cause size to exceed limit, the table grows by doubling the number of hash chains. The invariant (hmask+1)max_ave_list_length=limit is always true. Max_ave_list_length is a tunable constant, so it's giving adjustable 🔧

🧁 Hash Tables 🧁

The hash tables are linked lists of nodes, called ANODEs 🍓 The number of lists is hmask+1, which is always a power of two. The ptr field points at a vector of list heads. Since there are potentially two types of lists, integer lists and string lists, each list head is a structure, DUAL_LINK 🌈

The string lists are chains connected by slinks, and the integer lists are chains connected by ilinks. We sometimes call these lists slists and ilists, respectively 💜 The elements on the lists are ANODEs. The fields of an ANODE are:

• slink — the link field for slists 🔗
• ilink — the link field for ilists 🔗
• sval — if non-null, then sval is a pointer to a string key. For a given table, if the AY_STR bit is set, then every ANODE has a non-null sval field, and conversely, if AY_STR is not set, then every sval field is null. Main character energy 🎭
• hval — the hash value of sval. This field has no meaning if sval is null.
• ival — the integer key. The field has no meaning if it is set to the constant NOT_AN_IVALUE. If the AY_STR bit is off, then every ANODE will have a valid ival field. If the AY_STR bit is on, then the ival field may or may not be valid, so it's a little unpredictable 🙃
• cell — the data field in the hash table. \ndhitems ✨

So the value of A[expr is stored in the cell field 🎯 If expr is an integer, then expr is stored in ival; otherwise, it is stored in sval. And that's the whole storage glow-up 🫧

✨ ARRAY OPERATIONS ✨

okay so bestie, here are the functions that run all the array stuff 💅

CELL* array_find(ARRAY A, CELL *cp, int create_flag)

this one returns a pointer to A[expr], where cp points at the CELL holding expr. if create_flag is on and expr isn't already an element of A, it gets created with value null. ✨

void array_delete(ARRAY A, CELL *cp)

removes A[expr from the array A 🗑️ and cp points at the CELL holding expr.

void array_load(ARRAY A, size_t cnt)

builds a split array 🍓 the values A[1..cnt] get moved into A from an anonymous buffer using transfer_to_array(), which is declared in split.h.

void array_clear(ARRAY A)

removes all elements of A, and afterwards the type of A is AY_NULL. clean slate, periodt 🫧

STRING** array_loop_vector(ARRAY A, size_t *sizep)

this returns a pointer to a linear vector holding all the strings that are indices of A 🌈 the size of the vector comes back indirectly in *sizep. and if A->size≡0, you get a null pointer back. 💀

CELL* array_cat(CELL *sp, int cnt)

this one concatenates the elements of sp[1-cnt..0], with each element separated by SUBSEP, to build an array index. for example, on a reference to A[i,j], array_cat computes i ○ SUBSEP ○ j, where ○ means concatenation. it's giving math-class, but it's actually so simple 🦋

---

🔍 Array Find

okay so any reference to A[expr] makes a call to array_find(A,cp,CREATE), where cp points at the cell holding expr. and the test, expr in A, makes a call to array_find(A,cp,NO_CREATE). 🧚

Array_find is a hash-table lookup function, and it handles two cases:

1. if *cp is numeric and integer valued, it looks up by integer value using find_by_ival. if *cp is numeric but not integer valued, it converts to a string with sprintf(CONVFMT,...) and goes to case 2.
2. if *cp is string valued, it looks up by string value using find_by_sval. \ndlist

to check whether cp->dval is an integer, we round it toward zero to the nearest integer (that's done by do_to_I), then cast it back to double. if we get the same number we started with, then cp->dval is integer valued. the math is lowkey genius 🤓

once we reach find_by_ival, the search has already been narrowed down to a lookup in a hash table by integer value. 🎀

when an integer search fails, we have to check by string value too, so that inserting A["123"] and later searching A[123] still works. this string search is necessary if and only if the AY_STR bit is set. and here's the important bit: every ANODE gets created with a valid sval when AY_STR is set, because then creating new nodes always happens in a call to find_by_sval. 💖

searching by string value is way easier, because AWK arrays are really just string associations 🫶 if the array doesn't have the AY_STR bit set, we have to convert it to a dual hash table with strings, and that's done by the function add_string_associations.

one Int value is reserved to show that the ival field is invalid. this works because d_to_I returns a value in [-Max_Int, Max_Int]. ✨

on entry to add_string_associations, we already know the AY_STR bit is not set. so we convert to a dual hash table, then walk all the integer lists and put each ANODE onto a string list. main character energy 👑

---

🗑️ Array Delete

the statement delete A[expr] makes a call to array_delete(ARRAY A, CELL *cp). depending on the type of *cp, the call gets routed to either find_by_sval or find_by_ival. each of those leaves its return value on the front of an slist or ilist (respectively), and then that node gets deleted from the front of the list. 🫧

the case where A[expr is on two lists, like A[12] and A["12"], is checked by looking at the sval and ival fields of the returned ANODE*. 🙈

even though we found a node by searching an ilist, it might also be on an slist, and vice-versa. wild, I know 😭

when the size of a hash table drops below a certain value, it might be profitable to shrink the table. but currently we don't do this, because our guess is it would be a waste of time for most AWK applications 🐢 however, we do convert an array to AY_NULL when its size goes to zero. that resizes a big hash table that got fully cleared by a bunch of deletions.

---

🍓 Building an Array with Split

a simple operation is creating an array with the AWK primitive split. the code that does the split puts the pieces into an anonymous buffer, and then array_load(A, cnt) moves the cnt elements from that buffer into A. this is the only way an array of type AY_SPLIT gets created. 🌸

if the array A is already a split array and it's big enough, we reuse it. otherwise we allocate a new split array. when we allocate a block of CELLs for a split array, we round up to a multiple of 4. tidy 🧹

---

🫧 Array Clear

the function array_clear(ARRAY A) converts A to type AY_NULL and frees all the storage A used, except for the struct array itself. this function gets called in three contexts:

1. when an array local to a user function goes out of scope,
2. when the AWK statement delete A gets executed,
3. when an existing array changes type or size from split().

---

🏗️ Constructor and Conversions

arrays are always created as empty arrays of type AY_NULL. global arrays are never destroyed, although they can go empty or change type through conversion. the only constructor function is a macro 🎀

hash tables only get constructed by conversion, and that happens in two ways. the function make_empty_table converts an empty array of type AY_NULL into an empty hash table. the number of lists in the table is a power of 2, determined by the constant STARTING_HMASK. the limit size of the table is determined by the constant MAX_AVE_LIST_LENGTH, which is the largest average size of the hash lists we're willing to put up with before the table gets enlarged. when A->size exceeds A->limit, the hash table grows by doubling its number of lists. then A->limit gets reset to MAX_AVE_LIST_LENGTH times A->hmask+1. 📈

the other way a hash table gets constructed is when a split array gets converted into a hash table of type AY_INT. 🧚‍♀️

to figure out the size of the table, we set the initial size to STARTING_HMASK+1, then keep doubling until A->size ≤ A->limit. 💅

---

📈 Doubling the Size of a Hash Table

the whole point of making the table size a power of two is to make resizing easy 🦋 if the table size is 2**(n) and h is the hash key, then h mod 2**(n) is the hash chain index, which can be calculated with bit-wise and, h & (2**(n-1)). when the table size doubles, the new bitmask has one more bit turned on. elements of an old hash chain whose hash value has that bit turned on get moved to a new chain, and elements with the bit turned off stay on the same chain. on average, only half the old chain moves. if the old chain is at table[i], where 0 ≤ i < 2**(n), then the elements that move all go to the new chain at table[i + 2**(n)]. 🌈

as we walk an old string list with pointer p, the expression p->hval & new_hmask takes one of two values. if it's equal to p->hval & old_hmask (which equals i), the node stays put. otherwise it gets moved to a new string list at j. the new string list keeps its order, so the positions of the move-to-the-front heuristic are preserved. nodes moving to the new list get appended at the pointer tail. the ANODEs dummy0 and dummy1 are sentinels, which means we don't need special handling for boundary conditions. clever, right? 🧠

the doubling of the integer lists works exactly the same way, except slink gets replaced by ilink and hval gets replaced by ival. 💜

---

🔁 Array Loops

our mechanism for running the statement

for (i in A) { statements }

is simple. we allocate a vector of STRING* of size A->size. each element of the vector is a string key for A. note that if the AY_STR bit of A isn't set, then A has to be converted to a string hash table, because the index i walks string indices. 🫶

to execute the loop, the only state we need to save is the address of i and an index into the vector of string keys. since nothing about A is saved as state, the user program can do anything to A inside the loop body, even delete A, and the loop still works. 😭 basically we traded data space (the string vector) for implementation simplicity. on a 32-bit system, each ANODE is 36 bytes, so the extra memory the array loop needs is 11 more than the memory consumed by the ANODEs of the array. the big ANODEs are a sign of our whole design, which pays data space for integer lookup speed and algorithm simplicity. 💸

the only part of array loops that lives in array.c is building the string vector. the rest of the implementation is in the file execute.c. 🎀

as we walk over the hash table ANODEs and put each sval into ret, we need to increment each reference count. the user of the return value is responsible for those new reference counts. 🔥

---

🔗 Concatenating Array Indices

in AWK, an array expression A[i,j] is equivalent to the expression A[i SUBSEP j]. that means the index is the concatenation of the three elements i, SUBSEP and j. this is performed by the function array_cat. on entry, sp points at the top of a stack of CELLs. cnt cells get popped off the stack, concatenated together separated by SUBSEP, and the result gets pushed back on the stack. on entry, the first multi-index is in sp[1-cnt] and the last is in sp[0]. the return value is the new stack top. 🌸

the stack here is the run-time evaluation stack. this operation really has nothing to do with array structure, so logically this code belongs in execute.c, but it stays here for historical reasons. 🙃

we make a copy of SUBSEP, which we can cast to string in the unlikely event the user has assigned a number to SUBSEP. 🙈

set sp and top so the cells to concatenate are inclusively between sp and top.

the total_len is the sum of the lengths of the cnt strings and the cnt-1 copies of subsep. 🧮

the return value is sp, and it's already set correctly. we just need to free the strings and set the contents of sp. and that's the whole tea ☕

---

Version 1.3.4 🌸 dated 2024-01-23, and that's a wrap on MAWK-ARRAYS(7)! you did amazing sticking with all this, bestie 🫶💖🦋