{
    "mode": "man",
    "parameter": "mawk-arrays",
    "section": "7",
    "url": "https://www.chedong.com/phpMan.php/man/mawk-arrays/7/json",
    "generated": "2026-10-05T00:07:45Z",
    "synopsis": "This is the documentation for the mawk implementation of awk arrays.  Arrays in awk are asso‐\nciations of strings to awk scalar values.  The mawk implementation stores the associations in\nhash  tables.  The hash table scheme was influenced by and is similar to the design presented\nin Griswold and Townsend, The Design and Implementation of Dynamic Hashing Sets and Tables in\nIcon, Software Practice and Experience, 23, 351-367, 1993.",
    "sections": {
        "NAME": {
            "content": "mawk-arrays - design notes for mawk's array implementation\n",
            "subsections": []
        },
        "SYNOPSIS": {
            "content": "This is the documentation for the mawk implementation of awk arrays.  Arrays in awk are asso‐\nciations of strings to awk scalar values.  The mawk implementation stores the associations in\nhash  tables.  The hash table scheme was influenced by and is similar to the design presented\nin Griswold and Townsend, The Design and Implementation of Dynamic Hashing Sets and Tables in\nIcon, Software Practice and Experience, 23, 351-367, 1993.\n",
            "subsections": []
        },
        "DATA STRUCTURES": {
            "content": "",
            "subsections": [
                {
                    "name": "Array Structure",
                    "content": "The type ARRAY is a pointer to a struct array.  The size field is the number of  elements  in\nthe table.  The meaning of the other fields depends on the type field.\n\nThere  are  three types of arrays and these are distinguished by the type field in the struc‐\nture.  The types are:\n\nAYNULL\nThe array is empty and the size field is always zero.  The other fields have no meaning.\n\nAYSPLIT\nThe array was created by the AWK built-in split.  The return value from split is  stored\nin  the  size field.  The ptr field points at a vector of CELLs.  The number of CELLs is\nthe limit field.  It  is  always  true  that  size ≤ limit.   The  address  of  A[i]  is\n(CELL*)A->ptr+i-1 for 1≤ i ≤ size.  The hmask field has no meaning.\n\nHash Table\nThe  array  is a hash table.  If the AYSTR bit in the type field is set, then the table\nis keyed on strings.  If the AYINT bit in the type field is  set,  then  the  table  is\nkeyed  on  integers.   Both bits can be set, and then the two keys are consistent, i.e.,\nlook up of A[-14] and A[\"-14\"] will return identical CELL pointers although the look  up\nmethods  will be different.  In this case, the size field is the number of hash nodes in\nthe table.  When insertion of a new element would cause size to exceed limit, the  table\ngrows     by    doubling    the    number    of    hash    chains.     The    invariant,\n(hmask+1)maxavelistlength=limit is always true.   Maxavelistlength  is  a  tunable\nconstant.\n"
                },
                {
                    "name": "Hash Tables",
                    "content": "The  hash  tables  are  linked lists of nodes, called ANODEs.  The number of lists is hmask+1\nwhich is always a power of two.  The ptr field points at a vector of list heads.  Since there\nare potentially two types of lists, integer lists and strings lists,  each  list  head  is  a\nstructure, DUALLINK.\n\nThe string lists are chains connected by slinks and the integer lists are chains connected by\nilinks.   We sometimes refer to these lists as slists and ilists, respectively.  The elements\non the lists are ANODEs.  The fields of an ANODE are:\n\nslink The link field for slists.  ilink The link field for ilists.  sval  If  non-null,  then\nsval  is  a  pointer to a string key.  For a given table, if the AYSTR bit is set then every\nANODE has a non-null sval field and conversely, if AYSTR is not set, then every  sval  field\nis null.\n\nhval The hash value of sval.  This field has no meaning if sval is null.\n\nival  The  integer  key.  The field has no meaning if set to the constant, NOTANIVALUE.  If\nthe AYSTR bit is off, then every ANODE will have a valid ival field.  If the AYSTR  bit  is\non, then the ival field may or may not be valid.\n\ncell The data field in the hash table.  \\ndhitems\n\nSo  the  value of A[expr is stored in the cell field, and if expr is an integer, then expr is\nstored in ival, else it is stored in sval.\n"
                }
            ]
        },
        "ARRAY OPERATIONS": {
            "content": "The functions that operate on arrays are,\n\nCELL* arrayfind(ARRAY A, CELL *cp, int createflag)\nreturns a pointer to A[expr] where cp is a pointer to the CELL  holding  expr.   If  the\ncreateflag  is  on  and  expr  is not an element of A, then the element is created with\nvalue null.\n\nvoid arraydelete(ARRAY A, CELL *cp)\nremoves an element A[expr from the array A.  cp points at the CELL holding expr.\n\nvoid arrayload(ARRAY A, sizet cnt)\nbuilds a split array.  The values A[1..cnt] are moved into A from  an  anonymous  buffer\nwith transfertoarray() which is declared in split.h.\n\nvoid arrayclear(ARRAY A) removes all elements of A.\nThe type of A is then AYNULL.\n\nSTRING arrayloopvector(ARRAY A, sizet *sizep)\nreturns  a  pointer to a linear vector that holds all the strings that are indices of A.\nThe size of the the vector is returned indirectly  in  *sizep.   If  A->size≡0,  a  null\npointer is returned.\n\nCELL* arraycat(CELL *sp, int cnt)\nconcatenates  the  elements  of  sp[1-cnt..0], with each element separated by SUBSEP, to\ncompute an array index.  For example, on a reference to A[i,j], arraycat computes  i  ○\nSUBSEP ○ j where ○ denotes concatenation.\n",
            "subsections": [
                {
                    "name": "Array Find",
                    "content": "Any  reference  to  A[expr]  creates a call to arrayfind(A,cp,CREATE) where cp points at the\ncell holding expr.  The test, expr in A, creates a call to arrayfind(A,cp,NOCREATE).\n\nArrayfind is a hash-table lookup function that handles two cases:\n\n1.   If *cp is numeric and integer valued, then lookup by integer value  using  findbyival.\nIf  *cp  is  numeric,  but  not integer valued, then convert to string with sprintf(CON‐\nVFMT,...) and go to case~2.\n\n2.   If *cp is string valued, then lookup by string value using findbysval.  \\ndlist\n\nTo test whether cp->dval is integer, we convert to the nearest integer  by  rounding  towards\nzero  (done  by  dotoI) and then cast back to double.  If we get the same number we started\nwith, then cp->dval is integer valued.\n\nWhen we get to the function findbyival, the search has been reduced to lookup in a hash ta‐\nble by integer value.\n\nWhen a search by integer value fails, we have to check by string value  to  correctly  handle\nthe  case  insertion by A[\"123\"] and later search as A[123].  This string search is necessary\nif and only if the AYSTR bit is set.  An important point is that all ANODEs get created with\na valid sval if AYSTR is set, because then creation of new nodes always occurs in a call  to\nfindbysval.\n\nSearching  by  string  value is easier because AWK arrays are really string associations.  If\nthe array does not have the AYSTR bit set, then we have to convert the array to a dual  hash\ntable with strings which is done by the function addstringassociations.\n\nOne  Int value is reserved to show that the ival field is invalid.  This works because dtoI\nreturns a value in [-MaxInt, MaxInt].\n\nOn entry to addstringassociations, we know that the AYSTR bit is not set.  We convert to a\ndual hash table, then walk all the integer lists and put each ANODE on a string list.\n"
                },
                {
                    "name": "Array Delete",
                    "content": "The execution of the statement, delete A[expr], creates a call to arraydelete(ARRAY A,  CELL\n*cp).   Depending  on  the  type  of *cp, the call is routed to findbysval or findbyival.\nEach of these functions leaves its return value on the front of an slist  or  ilist,  respec‐\ntively,  and  then it is deleted from the front of the list.  The case where A[expr is on two\nlists, e.g., A[12] and A[\"12\"] is checked by examining the sval and ival fields  of  the  re‐\nturned ANODE*.\n\nEven  though  we  found  a  node by searching an ilist it might also be on an slist and vice-\nversa.\n\nWhen the size of a hash table drops below a certain value, it might be profitable  to  shrink\nthe hash table.  Currently we don't do this, because our guess is that it would be a waste of\ntime  for  most  AWK  applications.  However, we do convert an array to AYNULL when the size\ngoes to zero which would resize a large hash table that had been completely cleared  by  suc‐\ncessive deletions.\n"
                },
                {
                    "name": "Building an Array with Split",
                    "content": "A  simple  operation  is to create an array with the AWK primitive split.  The code that per‐\nforms split puts the pieces in an anonymous buffer.  arrayload(A, cnt) moves  the  cnt  ele‐\nments  from  the  anonymous buffer into A.  This is the only way an array of type AYSPLIT is\ncreated.\n\nIf the array A is a split array and big enough then we reuse it, otherwise we need  to  allo‐\ncate  a new split array.  When we allocate a block of CELLs for a split array, we round up to\na multiple of 4.\n"
                },
                {
                    "name": "Array Clear",
                    "content": "The function arrayclear(ARRAY A) converts A to type AYNULL and frees all storage used by  A\nexcept for the struct array itself.  This function gets called in three contexts:\n\n(1)  when an array local to a user function goes out of scope,\n\n(2)  execution of the AWK statement, delete A and\n\n(3)  when an existing changes type or size from split().\n"
                },
                {
                    "name": "Constructor and Conversions",
                    "content": "Arrays are always created as empty arrays of type AYNULL.  Global arrays are never destroyed\nalthough  they  can  go  empty or have their type change by conversion.  The only constructor\nfunction is a macro.\n\nHash tables only get constructed by conversion.  This happens  in  two  ways.   The  function\nmakeemptytable  converts an empty array of type AYNULL to an empty hash table.  The number\nof lists in the table is a power of 2 determined by the constant STARTINGHMASK.   The  limit\nsize  of the table is determined by the constant MAXAVELISTLENGTH which is the largest av‐\nerage size of the hash lists that we are willing to  tolerate  before  enlarging  the  table.\nWhen  A->size exceeds A->limit, the hash table grows in size by doubling the number of lists.\nA->limit is then reset to MAXAVELISTLENGTH times A->hmask+1.\n\nThe other way a hash table gets constructed is when a split array is converted to a hash  ta‐\nble of type AYINT.\n\nTo determine the size of the table, we set the initial size to STARTINGHMASK+1 and then dou‐\nble the size until A->size ≤ A->limit.\n"
                },
                {
                    "name": "Doubling the Size of a Hash Table",
                    "content": "The  whole point of making the table size a power of two is to facilitate resizing the table.\nIf the table size is 2(n) and h is the hash key, then h mod 2(n) is the hash chain  index\nwhich  can be calculated with bit-wise and, h & (2(n-1)).  When the table size doubles, the\nnew bit-mask has one more bit turned on.  Elements of an old hash chain whose hash value have\nthis bit turned on get moved to a new chain.  Elements with this bit turned off stay  on  the\nsame  chain.  On average only half the old chain moves to the new chain.  If the old chain is\nat table[i], 0 ≤ i < 2(n), then the elements that move, all move to the new  chain  at  ta‐\nble[i + 2(n)].\n\nAs we walk an old string list with pointer p, the expression p->hval & newhmask takes one of\ntwo values.  If it is equal to p->hval & oldhmask (which equals i), then the node stays oth‐\nerwise  it gets moved to a new string list at j.  The new string list preserves order so that\nthe positions of the move-to-the-front heuristic are preserved.  Nodes moving to the new list\nare appended at pointer tail.  The ANODEs, dummy0~and dummy1, are sentinels that remove  spe‐\ncial handling of boundary conditions.\n\nThe  doubling of the integer lists is exactly the same except that slink is replaced by ilink\nand hval is replaced by ival.\n"
                },
                {
                    "name": "Array Loops",
                    "content": "Our mechanism for dealing with execution of the statement,\n\nfor (i in A) { statements }\n\nis simple.  We allocate a vector of STRING* of size, A->size.  Each element of the vector  is\na  string key for~A.  Note that if the AYSTR bit of A is not set, then A has to be converted\nto a string hash table, because the index i walks string indices.\n\nTo execute the loop, the only state that needs to be saved is the address of i and  an  index\ninto  the  vector  of string keys.  Since nothing about A is saved as state, the user program\ncan do anything to A inside the body of the loop, even delete A, and the  loop  still  works.\nEssentially,  we  have  traded  data space (the string vector) in exchange for implementation\nsimplicity.  On a 32-bit system, each ANODE is 36 bytes, so the extra memory needed  for  the\narray  loop  is  11  more than the memory consumed by the ANODEs of the array.  Note that the\nlarge size of the ANODEs is indicative of our whole design which pays data space for  integer\nlookup speed and algorithm simplicity.\n\nThe  only  aspect of array loops that occurs in array.c is construction of the string vector.\nThe rest of the implementation is in the file execute.c.\n\nAs we walk over the hash table ANODEs, putting each sval in ret, we need  to  increment  each\nreference count.  The user of the return value is responsible for these new reference counts.\n"
                },
                {
                    "name": "Concatenating Array Indices",
                    "content": "In  AWK,  an array expression A[i,j] is equivalent to the expression A[i SUBSEP j], i.e., the\nindex is the concatenation of the three elements i, SUBSEP and j.  This is performed  by  the\nfunction  arraycat.   On  entry,  sp  points  at the top of a stack of CELLs.  Cnt cells are\npopped off the stack and concatenated together separated by SUBSEP and the result  is  pushed\nback on the stack.  On entry, the first multi-index is in sp[1-cnt] and the last is in sp[0].\nThe  return  value  is the new stack top.  (The stack is the run-time evaluation stack.  This\noperation really has nothing to do with array structure, so logically this  code  belongs  in\nexecute.c, but remains here for historical reasons.)\n\nWe  make  a copy of SUBSEP which we can cast to string in the unlikely event the user has as‐\nsigned a number to SUBSEP.\n\nSet sp and top so the cells to concatenate are inclusively between sp and top.\n\nThe totallen is the sum of the lengths of the cnt strings and the cnt-1 copies of subsep.\n\nThe return value is sp and it is already set correctly.  We just need to free the strings and\nset the contents of sp.\n\nVersion 1.3.4                                2024-01-23                               MAWK-ARRAYS(7)"
                }
            ]
        }
    },
    "summary": "mawk-arrays - design notes for mawk's array implementation",
    "flags": [],
    "examples": [],
    "see_also": []
}