#!/bin/sh
# -*- indent-tabs-mode: nil; -*-
#:
#: A simple library to emulate simple arrays (one-dimensional) and alists
#: in FreeBSD's POSIX shell :command:`/bin/sh`.
#:
#: :Author:    Franz Glasner
#: :Copyright: (c) 2024 Franz Glasner.
#:             All rights reserved.
#: :License:   BSD 3-Clause "New" or "Revised" License.
#:             See LICENSE for details.
#:             If you cannot find LICENSE see
#:             <https://opensource.org/licenses/BSD-3-Clause>
#: :ID:        @(#)@@SIMPLEVERSIONTAG@@
#:
#: This implementation is somewhat inspired by
#: https://unix.stackexchange.com/questions/137566/arrays-in-unix-bourne-shell
#:
#: Is implements one-dimensional array with one-based indexing.
#:
#: Hints and rules for arrays:
#:
#: - Every array has a NAME.
#: - One-based indexing is used.
#: - The array with name NAME is associated with a primary global or local
#:   shell variable with the same name. Its value contains a token TOKEN that
#:   is used in variable names that make up the backing store of the array.
#:   The value of this variable has the form ``_farr_A[?]:<TOKEN>``.
#: - Array elements for array NAME that has associated TOKEN are stored in
#:   global variables named ``_farr_A_<TOKEN>_<index-number>`` (values)
#:   and ``_farr_A_<TOKEN>__`` (length).
#: - An array name must conform to shell variable naming conventions.
#: - Currently the number of of elements of an array must be >= 0.
#: - Variable NAME can also be a local variable. In this case it MUST
#:   be initialized with an empty value first.
#: - Any unset global variables ``_farr_A_<TOKEN>__`` variable is a severe
#:   error normally and forces an immediate error ``exit``.
#:   Exceptions to this rule are documented.
#:
#:
#: This module also contains a very rough implementation of an alist
#: (aka dict, aka map).
#: This is implemented somewhat similar to arrays.
#:
#: Hints and rules for alists:
#:
#: - Every alist has a NAME.
#: - The alist with name NAME is associated with a primary global or local
#:   shell variable with the same name. Its value contains a token TOKEN that
#:   is used in variable names that make up the backing stores of the alist.
#:   The value of this variable is of the form ``_farr_KV[?,?]:<TOKEN>``.
#: - The logical length of the alist (i.e. the number of key-value pairs)
#:   is stored in a global ``_farr_KV_<TOKEN>__``.
#: - Every key-value pair has an associated storage "pointer" SPTR.
#:
#:   * Keys are stored in an associated global ``_farr_Ks_<TOKEN>_<SPTR>``.
#:     They are stored in the form ``<sptr-prev>;<sptr-next>@<key>``.
#:     They make up a double-linked list and preserve information about
#:     the insertion order.
#:   * Values are stored in an associated global ``_farr_Vs_<TOKEN>_<SPTR>``.
#:     They are stored in undecorated form.
#:
#:   Deleted entries are removed instantly from this lists.
#:
#:   "Pointers" to the first and last items are stored in a variabled named
#:   ``_farr_KV_<TOKEN>_P`` in the form ``<sptr-first>;<sptr-last>``.
#:
#: - Additionally each key is stored in an array-like lexicographically ordered
#:   structure at an index BSIDX. The name of the corresponding shell
#:   variables are ``_farr_Kb_<TOKEN>_<BSIDX>. Its length is stored in
#:   ``_farr_KV_<TOKEN>_B``. The form is ``<sptr>;V@<key>``.
#:   Deletions are stored as "tombstones" in the form ``0;D@<key>``.
#: - An alist name must conform to shell variable naming conventions.
#: - Currently the number of of elements of an alist must be >= 0.
#: - Variable NAME can also be a local variable. In this case it MUST
#:   be initialized with an empty value first.
#: - Any unset global variables ``_farr_KV_<TOKEN>__`` variable is a severe
#:   error normally and forces an immediate fatal error exit by calling
#:   ``exit``.
#: - The same is true if other backing shell variables are unexpectedly unset.
#:   Exceptions to this rule are documented.
#: - An alist preserves insertion order. Note that updating a key does not
#:   affect the order. Keys added after deletion are inserted at the end.
#: - Alists compare equal if and only if they have the same (key, value) pairs
#:   (regardless of insertion order).
#:
#: Hints and rules for indexes:
#:
#:   For all functions these facts hold:
#:
#:   - Every object (array, alist) has a current length LEN.
#:   - Indexes range from 1 <= INDEX <= LEN.
#:   - Indexes 0, -1, -2 are evaluated to LEN + given index.
#:     So `0` indexes the last item, `-1` the second last and `-LEN+1` the
#:     first item.
#:   - All index (and length) values must be given as decimal numbers.
#:
#:   `null` (aka empty) and/or missing indexes are handled differently in
#:   the function context.
#:
#: Resource management:
#:
#:   Done by reference counting of arrays and alists. No borrowed references
#:   are ever returned. Every array and alist must be released using
#:   `farray_release` or `falist_release`.
#:
#: Important:
#:   All names that start with ``_farr_`` or ``__farr_`` are reserved
#:   for private use in this module.
#:   Do not use such names in your scripts.
#:
#:   Do also not use local variables starting with ``__farr_``
#:   or ``___farr_``-
#:
#:   Public functions start with ``farray_, ``falist_`` or ``fobject_``.
#:


_farr_array_token_prefix='_farr_A[?]:'         # token value prefix
_farr_array_prefix=_farr_A_
_farr_alist_token_prefix='_farr_KV[?,?]:'      # token value prefix
_farr_alist_prefix=_farr_KV_                   # alist as object
_farr_alist_key_bs_prefix=_farr_Kb_            # alist keys in list for binary
                                               #    search
_farr_alist_key_prefix=_farr_Ks_               # alist keys in storage
_farr_alist_value_prefix=_farr_Vs_             # alist values in storage


#:
#: Internal error for fatal errors.
#:
#: Args:
#:   $@ (str): The error messages.
#:
_farr_fatal() {
    echo "ERROR:" "$@" 1>&2
    exit 70    # EX_SOFTWARE
}


:
#: Internal error for other error message.
#:
#: Args:
#:   $@ (str): The error messages.
#:
_farr_err() {
    echo "ERROR:" "$@" 1>&2
}


#:
#: Check whether given argument string is a decimal number string
#:
#: Args:
#:   $1: The string to be checked
#:
#: Returns:
#:   int: 0 (truish) if `$1` is a valid decimal number,
#:        1 (falsy) otherwise
#:
#: See Also:
#:   https://mywiki.wooledge.org/BashFAQ/054
#:
_farr_is_decimal_number() {
    case "$1" in
        '')
            # empty is not allowed
            return 1;;
        +|-)
            # just the sign is not allowed
            return 1;;
        *)
            # FALL THROUGH
            ;;
    esac
    # here we can trim the optional sign safely
    case "${1#[-+]}" in
        0*[!01234567]*)
            # non-octal
            return 1;;
        *[!0123456789]*)
            # non-decimal
            return 1;;
        *)
            return 0;;
    esac
}


#:
#: Check whether given argument string is formally a storage pointer value.
#:
#: A valid storage pointer is just a decimal number (base 10) without any
#: sign and other decorations.
#:
#: Args:
#:   $1: The string to be checked
#:
#: Returns:
#:   int: 0 (truish) if `$1` is a valid decimal number,
#:        1 (falsy) otherwise
#:
_farr_is_valid_storage_ptr() {
    case "$1" in
        '')
            # empty is not allowed
            return 1;;
        0)
            # a single 0 is allowed
            return 0;;
        0*)
            # other "octal" numbers of having a leading zero are not allowed
            return 1;;
        *[!0123456789]*)
            # non-decimal
            return 1;;
        *)
            return 0;;
    esac
}


#:
#: Check whether given argument string is formally a valid object token.
#:
#: A given valid object token is a hexadecimal value in lower-case.
#:
#: Args:
#:   $1: The string to be checked
#:
#: Returns:
#:   int: 0 (truish) if `$1` is a valid decimal number,
#:        1 (falsy) otherwise
#:
_farr_is_valid_object_token() {

    case "$1" in
        '')
            # empty is not allowed
            return 1;;
        *[!abcdef0123456789]*)
            # non-hexadecimal
            return 1;;
        *)
            return 0;;
    esac
}


#:
#: From an input index value compute an effective index value and store
#: it into a variable with a given name.
#:
#: Args:
#:   $1 (str): The name of a variable where to store the result
#:   $2 (int, null): The index value to check.
#:                   It must be a valid decimal number or the `null` value.
#:                   If the argument is `null` then ``$3 + 1`` is used as the
#:                   resulting effective index value. For this to work a
#:                   valid length must be given in `$3`.
#:                   If the argument is `<= 0` then -- if `$3` is given
#:                   the effective index is computed as ``$3 + $2``.
#:   $3 (int, optional): If given a length value that is used to compute
#:                       effective index values in some cases (`$2` is null or
#:                       `$2` <= 0).
#:
_farr_make_index() {
    local __farr_mi_varname __farr_mi_index __farr_mi_length

    __farr_mi_varname="$1"
    __farr_mi_index="$2"
    __farr_mi_length="${3-}"

    # If it is given and non-null it must be a valid decimal length number
    if [ -n "${__farr_mi_length}" ]; then
        _farr_is_decimal_number "${__farr_mi_length}" || _farr_fatal "given length is not a valid decimal number"
    fi

    if [ -z "${__farr_mi_index}" ]; then
        if [ -n "${__farr_mi_length}" ]; then
            setvar "${__farr_mi_varname}" $((__farr_mi_length + 1))
        else
            _farr_fatal "length not given: cannot autocompute index"
        fi
    else
        _farr_is_decimal_number "${__farr_mi_index}" || _farr_fatal "given index is not a valid decimal number"
        if [ "${__farr_mi_index}" -le 0 ]; then
            if [ -n "${__farr_mi_length}" ]; then
                setvar "${__farr_mi_varname}" $((__farr_mi_length + __farr_mi_index))
            else
                _farr_fatal "cannot compute effective index because no length is given"
            fi
        else
            setvar "${__farr_mi_varname}" "${__farr_mi_index}"
        fi
    fi
}


#:
#: Quote the given input using "Dollar-Single-Quotes" to be safely used in
#: evals.
#:
#: Args:
#:   $1: The value to be quoted.
#:
#: Output (stdout):
#:   The properly quoted string including surrounding "Dollar-Single-Quotes"
#:   (e.g. $'...').
#:
#: Using "Dollar-Single-Quotes" is not strictly posixly correct. But
#: FreeBSD's :command:`/bin/sh` understands them.
#:
#: From FreeBSD's :manpage:`sh(1)`:
#:
#:   Dollar-Single Quotes
#:
#:     Enclosing characters between ``$'`` and ``'`` preserves the literal
#:     meaning of all characters except backslashes and single quotes.
#:
#:     A backslash introduces a C-style escape sequence.
#:     Most important here:
#:
#:       ``\\``
#:                Literal backslash
#:
#:       ``\'``
#:                Literal single-quote
#:
_farr_quote_for_eval_dsq() {
    printf "\$'%s'" "$(_farr_inner_quote_for_dsq "${1}")"
}


#:
#: Helper to quote for "Dollar-Single-Quotes".
#:
#: This function handles just the quoting mechanics. It does not surround
#: the result with any other string decoration.
#: See also `_farr_quote_for_eval_dsq`.
#:
_farr_inner_quote_for_dsq() {
    printf "%s" "${1}" \
        | LC_ALL=C /usr/bin/sed -e $'s/\\\\/\\\\\\\\/g' -e $'s/\'/\\\\\'/g'
    #                              escape a backslash      escape a single quote
    # '    # make Emacs happy for correct syntax highlighting
}


#:
#: Quote the given input string for eval.
#:
#: If the argument contains a ``'`` character then "Dollar-Single-Quotes"
#: are used; "Single-Quotes" otherwise.
#:
#: Args:
#:   $1: The value to be quoted.
#:
#: Output (stdout):
#:   The properly quoted string including surrounding quotes.
#:
#:
_farr_quote_for_eval() {
    case "${1}" in
        *\'*)
            _farr_quote_for_eval_dsq "${1}"
            ;;
        *)
            printf "'%s'" "${1}"
            ;;
    esac
}


#:
#: Quote the given input using just POSIX correct "Single-Quotes" to be safely
#: used in evals.
#:
#: Args:
#:   $1: The value to be quoted.
#:
#: Output (stdout):
#:   The properly quoted string including surrounding "Single-Quotes"
#:   (e.g. '...').
#:
#:
#: From FreeBSD's :manpage:`sh(1)`:
#:
#:   Single Quotes
#:
#:     Enclosing characters in single quotes preserves the literal
#:     meaning of all the characters (except single quotes, making it
#:     impossible to put single-quotes in a single-quoted string).
#:
_farr_quote_for_eval_sq() {
    printf "'%s'" "$(_farr_inner_quote_for_sq "${1}")"
}


#:
#: Helper to quote for "Single-Quotes".
#:
#: This function handles just the quoting mechanics. It does not surround
#: the result with any other string decoration.
#: See also `_farr_quote_for_eval_dsq`.
#:
_farr_inner_quote_for_sq() {
    printf "%s" "${1}" \
        | LC_ALL=C /usr/bin/sed -e $'s/\'/\'\\\\\\\'\'/g'
    #                             escape a single quote
    #                             (here double-escaped: for $'...' AND sed
    # '    # make Emacs happy for correct syntax highlighting
}


#:
#: Quote the given input string for `eval` and produce a strictly posixly
#: correct encoding.
#:
#: It does not use FreeBSD's ``$'...'`` feature in its :command:`/bin/sh`.
#:
#: If the argument contains a ``'`` character then a proper "Single-Quotes"
#: combination is used.
#:
#: Args:
#:   $1: The value to be quoted.
#:
#: Output (stdout):
#:   The properly quoted string including surrounding quotes.
#:
#:
_farr_quote_for_eval_strict() {
    case "${1}" in
        *\'*)
            _farr_quote_for_eval_sq "${1}"
            ;;
        *)
            printf "'%s'" "${1}"
            ;;
    esac
}


#:
#: Implementation of typing
#:
#: Args:
#:   $1 (str): The (variable) name of an object
#:
#: Output (stdout):
#:   - array: an array
#:   - alist: an alist
#:   - null: an empty thing
#:   - value: some other shell type (string, number, ...)
#:   - unknown: if the name in `$1` was not given
#:
#: Returns:
#:   int: 0 always
#:
fobject_type() {
    local __farr_type_name

    local __farr_type_token

    __farr_type_name="${1-}"
    if [ -n "${__farr_type_name}" ] ; then
        eval __farr_type_token=\"\$\{"${__farr_type_name}"+SET\}\"
        if [ "${__farr_type_token}" = 'SET' ] ; then
            if eval __farr_type_token=\"\$\{"${__farr_type_name}"\}\" ; then
                case "${__farr_type_token}" in
                    '')
                        printf '%s' 'null';;
                    "${_farr_array_token_prefix}"*)
                        printf '%s' 'array';;
                    "${_farr_alist_token_prefix}"*)
                        printf '%s' 'alist';;
                    *)
                        printf '%s' 'value';;
                esac
            else
                # error in evaluation
                printf '%s' 'error'
            fi
        else
            # unset
            printf '%s' 'unknown'
        fi
    else
        # no name given
        printf '%s' 'unknown'
    fi
    return 0
}


#:
#: Just an official alias for `fobject_type`
#:
farray_type() {
    fobject_type "$@"
}


#:
#: Test whether `$1` is an array.
#:
#: Args:
#:   $1 (str): The name of an object
#:
#: Returns:
#:   int: 0 if `$1` is an array, 1 otherwise
#:
farray_isarray() {
    [ "$(fobject_type "$@")" = 'array' ]
}


#:
#: Create a new array.
#:
#: It is assumed that the array does not exist already.
#:
#: Args:
#:   $1 (str): The name of the array.
#:             Must conform to shell variable naming conventions.
#:   $2... (optional): Initialization values that will be appended to the
#:                     freshly created array.
#:
#: Exit:
#:   Iff the array already exists in some fashion (token and/or storage).
#:
farray_create() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len

    __farr_name="${1-}"
    [ -z "${__farr_name}" ] && _farr_fatal "missing farray name"
    eval __farr_token=\"\$\{"${__farr_name}"-\}\"
    [ -n "${__farr_token}" ] && _farr_fatal "object \`${__farr_name}' already created (value \`${__farr_token}')"

    __farr_token="$(/usr/bin/hexdump -v -e '/1 "%02x"' -n 16 '/dev/urandom')"

    __farr_gvrname="${_farr_array_prefix}${__farr_token}"

    # Check whether the variable already exists
    eval __farr_len=\"\$\{"${__farr_gvrname}"__+SET\}\"
    [ -n "${__farr_len}" ] && _farr_fatal "farray \`${__farr_name}' already exists: existing token \`${__farr_token}'"

    # Really create the storage by initializing its length ...
    setvar "${__farr_gvrname}__" 0
    # ... and its reference count
    setvar "${__farr_gvrname}_C" 1
    # And associate the token with the array name
    setvar "${__farr_name}" "${_farr_array_token_prefix}${__farr_token}"

    #
    # When there are values to populate the array with.
    # Note that the array's name is not shifted away yet and must be taken
    # into account. It is also needed for `farray_append`.
    #
    if [ $# -gt 1 ]; then
	farray_append "$@"
    fi
}


#:
#: Internal helper to get all the metadata for an array.
#:
#: Args:
#:   $1 (str): The name of the array or a complete array value with prefix
#:
#: Output (Globals):
#:   __farr_name (str): The name of the array if the name is given,
#:                      empty if a token value is given.
#:   __farr_token (str): The token that is the value of the name without its
#:                       token prefix.
#:   __farr_gvrname (str): The variable prefix for all items.
#:   __farr_len (int): The length of the array.
#:
#: Exit:
#:   Iff the array does not exist in some fashion (token and/or storage).
#:
_farr_array_get_meta() {
    local __farr_gm_name_or_value

    local __farr_tmp_refcount

    __farr_gm_name_or_value="${1-}"
    case "${__farr_gm_name_or_value}" in
        '')
            # ambiguous
            _farr_fatal "missing farray name or token value"
            ;;
        "${_farr_array_token_prefix}"*)
            # A prefixed token value
            __farr_name=''
            __farr_token="${__farr_gm_name_or_value#"${_farr_array_token_prefix}"}"
            ;;
        *)
            # A variable name: go through one indirection
            __farr_name="${__farr_gm_name_or_value}"
            eval __farr_token=\"\$\{"${__farr_name}"-\}\"
            case "${__farr_token}" in
                '')
                    _farr_fatal "object \`${__farr_name}' not created properly: token empty"
                    ;;

                "${_farr_array_token_prefix}"*)
                    __farr_token="${__farr_token#"${_farr_array_token_prefix}"}"
                    ;;
                *)
                    _farr_fatal "object \`${__farr_name}' is not an array"
                    ;;
            esac
            ;;
    esac
    __farr_gvrname="${_farr_array_prefix}${__farr_token}"

    eval __farr_len=\"\$\{"${__farr_gvrname}"__:+SET\}\"
    [ -z "${__farr_len}" ] && _farr_fatal "farray \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no storage for token \`${__farr_token}'"
    eval __farr_tmp_refcount=\"\$\{"${__farr_gvrname}"_C:+SET\}\"
    [ -z "${__farr_tmp_refcount}" ] && _farr_fatal "farray \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no refcnt for token \`${__farr_token}'"
    eval __farr_len=\"\$\{"${__farr_gvrname}"__\}\"
    return 0
}


#:
#: Internal helper to try to get all the metadata for an array.
#:
#: Args:
#:   $1 (str): The name of the array or a complete array value with prefix
#:
#: Output (Globals):
#:   __farr_name (str): The name of the array if the name is given,
#:                      empty if a token value is given.
#:   __farr_token (str): The token that is the value of the name without its
#:                       token prefix.
#:   __farr_gvrname (str): The variable prefix for all items.
#:   __farr_len (int): The length of the array
#:
#: Returns:
#:   0 if the array exists, 1 if something is missing.
#:
_farr_array_tryget_meta() {
    local __farr_gm_name_or_value

    local __farr_tmp_refcount

    __farr_token=''
    __farr_gvrname=''
    __farr_len=''
    __farr_name="${1-}"

    __farr_gm_name_or_value="${1-}"
    case "${__farr_gm_name_or_value}" in
        '')
            # ambiguous
            _farr_err "missing farray name or token value"
            return 1
            ;;
        "${_farr_array_token_prefix}"*)
            # A prefixed token value
            __farr_name=''
            __farr_token="${__farr_gm_name_or_value#"${_farr_array_token_prefix}"}"
            ;;
        *)
            # A variable name: go through one indirection
            __farr_name="${__farr_gm_name_or_value}"
            eval __farr_token=\"\$\{"${__farr_name}"-\}\"
            case "${__farr_token}" in
                '')
                    _farr_err "object \`${__farr_name}' not created properly: token empty"
                    return 1
                    ;;

                "${_farr_array_token_prefix}"*)
                    __farr_token="${__farr_token#"${_farr_array_token_prefix}"}"
                    ;;
                *)
                    _farr_err "object \`${__farr_name}' is not an array"
                    return 1
                    ;;
            esac
            ;;
    esac
    __farr_gvrname="${_farr_array_prefix}${__farr_token}"

    eval __farr_len=\"\$\{"${__farr_gvrname}"__:+SET\}\"
    if [ -z "${__farr_len}" ] ; then
        _farr_err "farray \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no storage for token \`${__farr_token}'"
        return 1
    fi
    eval __farr_tmp_refcount=\"\$\{"${__farr_gvrname}"_C:+SET\}\"
    if [ -z "${__farr_tmp_refcount}" ] ; then
        _farr_err "farray \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no refcnt for token \`${__farr_token}'"
        return 1
    fi
    eval __farr_len=\"\$\{"${__farr_gvrname}"__\}\"
    return 0
}


#:
#: Internal helper to try to get all the metadata for an array.
#:
#: This function is similar to `_farr_array_tryget_meta` but normally fatal
#: errors are reported with a "normal" error return.
#:
#: All output variables are properly initialized to the `null` value.
#:
#: Args:
#:   $1 (str): The name of the array or a complete array value with prefix
#:
#: Output (Globals):
#:   __farr_name (str): The name of the array if the name is given,
#:                      empty if a token value is given.
#:   __farr_token (str): The token that is the value of the name without its
#:                       token prefix.
#:   __farr_gvrname (str): The variable prefix for all items.
#:   __farr_len (int): The length of the array
#:
#: Returns:
#:   0 if the array exists, 1 if something is missing or `$1` is not an array
#:
#: Important:
#:   No fatal error exits should happen.
#:
_farr_array_tryget_meta_nonfatal() {
    local __farr_gm_name_or_value

    local __farr_tmp_refcount

    __farr_token=''
    __farr_gvrname=''
    __farr_len=''
    __farr_name="${1-}"

    __farr_gm_name_or_value="${1-}"
    case "${__farr_gm_name_or_value}" in
        '')
            # ambiguous
            return 1
            ;;
        "${_farr_array_token_prefix}"*)
            # A prefixed token value
            __farr_name=''
            __farr_token="${__farr_gm_name_or_value#"${_farr_array_token_prefix}"}"
            ;;
        *)
            # A variable name: go through one indirection
            __farr_name="${__farr_gm_name_or_value}"
            eval __farr_token=\"\$\{"${__farr_name}"-\}\"
            case "${__farr_token}" in
                '')
                    return 1
                    ;;

                "${_farr_array_token_prefix}"*)
                    __farr_token="${__farr_token#"${_farr_array_token_prefix}"}"
                    ;;
                *)
                    return 1
                    ;;
            esac
            ;;
    esac
    __farr_gvrname="${_farr_array_prefix}${__farr_token}"

    eval __farr_len=\"\$\{"${__farr_gvrname}"__:+SET\}\"
    [ -z "${__farr_len}" ] && return 1
    eval __farr_tmp_refcount=\"\$\{"${__farr_gvrname}"_C:+SET\}\"
    [ -z "${__farr_tmp_refcount}" ] && return 1
    eval __farr_len=\"\$\{"${__farr_gvrname}"__\}\"
    return 0
}


#:
#: Get the length of an array and put it into a variable
#:
#: Args:
#:   $1 (str): The name of the variable to put the length into.
#:   $2 (str): The name of the array.
#:
farray_length() {
    local __farr_varname __farr_name

    local __farr_token __farr_gvrname __farr_len

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift
    _farr_array_get_meta "$@"
    setvar "${__farr_varname}" "${__farr_len}"
}


#:
#: Get the length of an array and print it to stdout.
#:
#: Args:
#:   $1 (str): The name of the array.
#:
#: Output (stdout):
#:   The number of elements of the array.
#:   If the array does not exist the output is -1.
#:
#: Returns:
#:   0 (truthy)
#:
farray_print_length() {
    local __farr_vn

    ( farray_length __farr_vn "$@" && printf '%s' "${__farr_vn}"; ) \
    || printf '%s' "-1"
}


#:
#: Append one or more values to an existing array.
#:
#: Args:
#:   $1 (str): The name of the existing array.
#:   $2...: The values to append.
#:
farray_append() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len __farr_len_1 \
          __farr_newval

    _farr_array_get_meta "$@"
    shift

    for __farr_newval in "$@"; do
        __farr_len_1=$((__farr_len + 1))

        #
        # Set value Escape properly: use $' ' and escape any
        # backslashes and single quotes.
        #
        _farr_acquire_object "${__farr_newval}"
        setvar "${__farr_gvrname}_${__farr_len_1}" "${__farr_newval}"
        # the implementation below line does not escape properly
        #   eval ${__farr_gvrname}_${__farr_len_1}="\"${__farr_value}\""

        # Set new array length
        #  ... persistently in the array data storage
        setvar "${__farr_gvrname}__" "${__farr_len_1}"
        #  ... and locally (to make looping happy)
        __farr_len="${__farr_len_1}"
    done
}


#:
#: Set an array at an index to a value.
#:
#: Args:
#:   $1 (str): The name of the existing array.
#:   $2 (int): The index.
#:   $3 (optional): The value to set. If the value is not given the null
#:                  will be set.
#:
#: No holes are allowed in an array: only values at existing indices are
#: allowed. As an exception a value can be appended if the given index
#: is exactly the current length + 1.
#:
farray_set() {
    local __farr_name __farr_index __farr_value

    local __farr_token __farr_gvrname __farr_len __farr_len_1 \
          __farr_old_value

    _farr_array_get_meta "$@"
    _farr_make_index __farr_index "${2-}" "${__farr_len}"
    # first check
    [ "${__farr_index}" -lt 1 ] && _farr_fatal "index must be >= 1"
    __farr_value="${3-}"

    # For proper quoting: see farray_append
    if [ \( "${__farr_index}" -ge 1 \) -a \( "${__farr_index}" -le "${__farr_len}" \) ]; then
        _farr_acquire_object "${__farr_value}"
        # replace a value at an existing index
        eval __farr_old_value=\"\$\{"${__farr_gvrname}"_"${__farr_index}"\}\"
        _farr_release_object "${__farr_old_value}"
        setvar "${__farr_gvrname}_${__farr_index}" "${__farr_value}"
    else
        __farr_len_1=$((__farr_len + 1))
        if [ "${__farr_index}" -eq "${__farr_len_1}" ]; then
            _farr_acquire_object "${__farr_value}"
            # append value
            setvar "${__farr_gvrname}_${__farr_len_1}" "${__farr_value}"
            # and set new length
            setvar "${__farr_gvrname}__" "${__farr_len_1}"
        else
            _farr_fatal "array index out of bounds (cannot create holes)"
        fi
    fi
}


#:
#: Get an array value from a given index and put it into given variable.
#:
#: Args:
#:   $1 (str): The name of the variable to put the value into.
#:   $2 (str): The name of the existing array.
#:   $3 (int): The index.
#:
farray_get() {
    local __farr_varname __farr_name __farr_index

    local __farr_token __farr_gvrname __farr_len \
          __farr_get_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift
    _farr_array_get_meta "$@"
    _farr_make_index __farr_index "${2-}" "${__farr_len}"
    # check index range
    if [ \( "${__farr_index}" -lt 1 \) -o \( "${__farr_index}" -gt "${__farr_len}" \) ]; then
	_farr_fatal "array index out of bounds"
    fi

    eval __farr_get_value=\"\$\{"${__farr_gvrname}"_"${__farr_index}"\}\"
    _farr_acquire_object "${__farr_get_value}"
    setvar "${__farr_varname}" "${__farr_get_value}"
}


#:
#: Try to get an array value from a given index into a variable
#:
#: Args:
#:   $1 (str): The name of the variable to put the value into.
#:   $2 (str): The name of the existing array.
#:   $3 (int): The index.
#:
#: Returns:
#:   0 (truthy) on success,
#:   1 (falsy) if the given index is out of bounds (i.e. EOD).
#:
#: Exit:
#:   Other errors (missing array name, missing index value) are considered
#:   fatal and call `_farr_fatal` (i.e. `exit`).
#:
farray_tryget() {
    local __farr_varname __farr_name __farr_index

    local __farr_token __farr_gvrname __farr_len \
          __farr_get_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift

    _farr_array_get_meta "$@"
    _farr_make_index __farr_index "${2-}" "${__farr_len}"
    # check index range
    if [ \( "${__farr_index}" -lt 1 \) -o \( "${__farr_index}" -gt "${__farr_len}" \) ]; then
	return 1
    fi

    eval __farr_get_value=\"\$\{"${__farr_gvrname}"_"${__farr_index}"\}\"
    _farr_acquire_object "${__farr_get_value}"
    setvar "${__farr_varname}" "${__farr_get_value}"
    return 0
}


#:
#: Delete an array value at a given index.
#:
#: Args:
#:   $1 (str): The name of the existing array.
#:   $2 (int): The index to delete to.
#:
farray_del() {
    local __farr_name __farr_index

    local __farr_token __farr_gvrname __farr_len __farr_idx \
          __farr_del_value

    _farr_array_get_meta "$@"
    _farr_make_index __farr_index "${2-}" "${__farr_len}"
    # check index range
    if [ \( "${__farr_index}" -lt 1 \) -o \( "${__farr_index}" -gt "${__farr_len}" \) ]; then
	_farr_fatal "array index out of bounds"
    fi

    # Release the item at index
    eval __farr_del_value=\"\$\{"${__farr_gvrname}"_"${__farr_index}"\}\"
    _farr_release_object "${__farr_del_value}"

    # Move all other items down by one
    __farr_idx="${__farr_index}"
    while [ "${__farr_idx}" -lt "${__farr_len}" ]; do
        # copy the following value to the current index
        eval "${__farr_gvrname}"_"${__farr_idx}"=\"\$\{"${__farr_gvrname}"_$((__farr_idx + 1))\}\"
        __farr_idx=$((__farr_idx + 1))
    done
    # Drop the last item
    eval unset "${__farr_gvrname}"_"${__farr_idx}"
    # Set the new length
    setvar "${__farr_gvrname}__" $((__farr_len - 1))
}


#:
#: Remove the elements designated by an index and a length from an array,
#: and replace them with the elements of another array list, if any.
#:
#: Args:
#:   $1 (str, null): The name of an array where the deleted items will be
#:                   appended to. May be the `null` value if this is not
#:                   desired: nothing will be done with the deleted elements.
#:   $2 (str): The name of the array that is to be spliced
#:   $3 (int, null): Index, where to remove and/or insert elements.
#:                   A `null` index value is evaluated to `len + 1`.
#:   $4 (int, null): The length -- the number of elements to delete at given
#:                   index.
#:                   If `null` then the length from index to the end of the
#:                   array is applied ("automatic").
#:   $5 (str, null, optional): An array whose elements will be inserted at
#:                             given index.
#:
#: Using this universal function you can insert, replace or delete items.
#:
#: Examples:
#:
#:   Using ARRAY for the array to be changed and INSERTED for the new
#:   items and DELETED/POPPED for the returned items:
#:
#:   Prepend (insert at the start position)::
#:
#:     farray_splice "" ARRAY 1 0 INSERTED
#:
#:   Extend (insert after the end position)::
#:
#:     farray_splice "" ARRAY "" 0 INSERTED
#:
#:   Copy INSERTED into ARRAY, replacing the complete existing content::
#:
#:     farray_splice "" ARRAY 1 "" INSERTED
#:
#:   Copy INSERTED into ARRAY, replacing the complete existing content and
#:   returning it in DELETED::
#:
#:     farray_splice DELETED ARRAY 1 "" INSERTED
#:
#:   Pop the first item::
#:
#:     farray_splice POPPED ARRAY 1 1
#:
#:   Pop the last item::
#:
#:     farray_splice POPPED ARRAY 0 1
#:
#:   Shift by one item (similar to pop the first item, but no return value)::
#:
#:     farray_splice "" ARRAY 1 1
#:
farray_splice() {
    local __farr_del_array __farr_l_name __farr_index __farr_length \
          __farr_r_name

    local __farr_del_name __farr_del_token __farr_del_gvrname __farr_del_len \
          __farr_l_token __farr_l_gvrname __farr_l_len \
          __farr_r_token __farr_r_gvrname __farr_r_len \
          __farr_name __farr_token __farr_gvrname __farr_len \
          __farr_off __farr_v __farr_delta __farr_src_idx __farr_dst_idx

    [ $# -lt 4 ] && _farr_fatal "missing required arguments"

    __farr_del_name=''
    if [ -n "${1}" ] && _farr_array_tryget_meta "${1}"; then
        __farr_del_array="${1}"
        __farr_del_name="${__farr_name}"
        __farr_del_token="${__farr_token}"
        __farr_del_gvrname="${__farr_gvrname}"
        __farr_del_len="${__farr_len}"
    fi
    _farr_array_get_meta "${2}"
    __farr_l_name="${__farr_name}"
    __farr_l_token="${__farr_token}"
    __farr_l_gvrname="${__farr_gvrname}"
    __farr_l_len="${__farr_len}"

    __farr_index="${3}"
    __farr_length="${4}"

    if _farr_array_tryget_meta_nonfatal "${5-}"; then
        __farr_r_name="${__farr_name}"
        __farr_r_token="${__farr_token}"
        __farr_r_gvrname="${__farr_gvrname}"
        __farr_r_len="${__farr_len}"
    else
        __farr_r_name=''
        __farr_r_len=0
    fi

    _farr_make_index __farr_index "${__farr_index}" "${__farr_l_len}"
    # NOTE: index value array_length + 1 is allowed: splice at the end
    [ \( "${__farr_index}" -lt 1 \) -o \( "${__farr_index}" -gt "$((__farr_l_len + 1))" \) ] && _farr_fatal "index out of range"

    # also check the given length
    if [ -z "${__farr_length}" ]; then
        __farr_length="$((__farr_l_len - __farr_index + 1))"
    else
        _farr_is_decimal_number "${__farr_length}" || _farr_fatal "given length is not a valid number"
        [ \( "${__farr_length}" -lt 0 \) -o \( "${__farr_length}" -gt $((__farr_l_len - __farr_index + 1)) \) ] && _farr_fatal "length out of valid range"
    fi
    if [ "${__farr_length}" -eq "${__farr_r_len}" ]; then
        # Just replace
        __farr_off=0
        while [ "${__farr_off}" -lt "${__farr_length}" ]; do
            eval __farr_v=\"\$\{"${__farr_l_gvrname}"_$((__farr_index + __farr_off))\}\"
            if [ -n "${__farr_del_array}" ]; then
                farray_append "${__farr_del_array}" "${__farr_v}"
            fi
            _farr_release_object "${__farr_v}"
            eval __farr_v=\"\$\{"${__farr_r_gvrname}"_$((__farr_off + 1))\}\"
            _farr_acquire_object "${__farr_v}"
            setvar "${__farr_l_gvrname}"_$((__farr_index + __farr_off)) "${__farr_v}"
            __farr_off=$((__farr_off + 1))
        done
    elif [ "${__farr_length}" -gt "${__farr_r_len}" ]; then
        # More to delete than to copy: the resulting array shrinks
        __farr_delta=$((__farr_length - __farr_r_len))
        __farr_off=0
        while [ "${__farr_off}" -lt "${__farr_r_len}" ]; do
            eval __farr_v=\"\$\{"${__farr_l_gvrname}"_$((__farr_index + __farr_off))\}\"
            if [ -n "${__farr_del_array}" ]; then
                farray_append "${__farr_del_array}" "${__farr_v}"
            fi
            _farr_release_object "${__farr_v}"
            eval __farr_v=\"\$\{"${__farr_r_gvrname}"_$((__farr_off + 1))\}\"
            _farr_acquire_object "${__farr_v}"
            setvar "${__farr_l_gvrname}"_$((__farr_index + __farr_off)) "${__farr_v}"
            __farr_off=$((__farr_off + 1))
        done
        # Copy / unset the rest that is to delete
        while [ "${__farr_off}" -lt "${__farr_length}" ]; do
            eval __farr_v=\"\$\{"${__farr_l_gvrname}"_$((__farr_index + __farr_off))\}\"
            if [ -n "${__farr_del_array}" ]; then
                farray_append "${__farr_del_array}" "${__farr_v}"
            fi
            _farr_release_object "${__farr_v}"
            eval unset "${__farr_l_gvrname}"_$((__farr_index + __farr_off))
            __farr_off=$((__farr_off + 1))
        done
        # Move the rest -- here no refcount changes
        __farr_src_idx=$((__farr_index + __farr_length))
        __farr_dst_idx=$((__farr_index + __farr_r_len))
        while [ "${__farr_src_idx}" -le "${__farr_l_len}" ]; do
            eval __farr_v=\"\$\{"${__farr_l_gvrname}"_"${__farr_src_idx}"\}\"
            setvar "${__farr_l_gvrname}"_"${__farr_dst_idx}" "${__farr_v}"
            eval unset "${__farr_l_gvrname}"_"${__farr_src_idx}"
            __farr_src_idx=$((__farr_src_idx + 1))
            __farr_dst_idx=$((__farr_dst_idx + 1))
        done
        # Adjust the length
        setvar "${__farr_l_gvrname}__" $((__farr_l_len - __farr_delta))
    else
        # More to copy than to delete: the resulting array grows
        __farr_delta=$((__farr_r_len - __farr_length))
        __farr_off=0
        while [ "${__farr_off}" -lt "${__farr_length}" ]; do
            eval __farr_v=\"\$\{"${__farr_l_gvrname}"_$((__farr_index + __farr_off))\}\"

            if [ -n "${__farr_del_array}" ]; then
                farray_append "${__farr_del_array}" "${__farr_v}"
            fi
            _farr_release_object "${__farr_v}"
            eval __farr_v=\"\$\{"${__farr_r_gvrname}"_$((__farr_off + 1))\}\"
            _farr_acquire_object "${__farr_v}"
            setvar "${__farr_l_gvrname}"_$((__farr_index + __farr_off)) "${__farr_v}"
            __farr_off=$((__farr_off + 1))
        done
        #
        # Make room from last item to the first non-deleted
        # -- no refcount changes
        #
        __farr_src_idx=${__farr_l_len}
        __farr_dst_idx=$((__farr_src_idx + __farr_delta))
        while [ "${__farr_src_idx}" -ge $((__farr_index + __farr_length)) ]; do
            eval __farr_v=\"\$\{"${__farr_l_gvrname}"_"${__farr_src_idx}"\}\"
            setvar "${__farr_l_gvrname}"_"${__farr_dst_idx}" "${__farr_v}"
            __farr_src_idx=$((__farr_src_idx - 1))
            __farr_dst_idx=$((__farr_dst_idx - 1))
        done
        #
        # Copy the rest of the given data to be inserted
        #
        # NOTE: The offset variable __farr_off from above is NOT changed in
        #       between and valid here!
        #
        while [ "${__farr_off}" -lt "${__farr_r_len}" ]; do
            eval __farr_v=\"\$\{"${__farr_r_gvrname}"_$((__farr_off + 1))\}\"
            _farr_acquire_object "${__farr_v}"
            setvar "${__farr_l_gvrname}"_$((__farr_index + __farr_off)) "${__farr_v}"
            __farr_off=$((__farr_off + 1))
        done
        # Adjust the length
        setvar "${__farr_l_gvrname}"__ $((__farr_l_len + __farr_delta))
    fi
    return 0
}


#:
#: Merge two *sorted* arrays using the mergesort algorithm.
#:
#: Sources: - https://de.wikipedia.org/wiki/Mergesort
#:          - https://en.wikipedia.org/wiki/Merge_sort
#:
#: Args:
#:   $1 (str): The result array where all the sorted items will be appended to
#:   $2 (str): The first sorted input array
#:   $3 (str): The second sorted input array
#:
farray_merge() {
    local __farr_result __farr_input_1 __farr_input_2

    local __farr_name __farr_token __farr_gvrname __farr_len \
          __farr_name_1 __farr_token_1 __farr_gvrname_1 __farr_len_1 \
          __farr_name_2 __farr_token_2 __farr_gvrname_2 __farr_len_2 \
          __farr_idx_1 __farr_idx_2 __farr_item_1 __farr_item_2

    _farr_array_get_meta "$2"
    __farr_input_1="$2"
    __farr_name_1="${__farr_name}"
    __farr_token_1="${__farr_token}"
    __farr_gvrname_1="${__farr_gvrname}"
    __farr_len_1="${__farr_len}"
    _farr_array_get_meta "$3"
    __farr_input_2="$3"
    __farr_name_2="${__farr_name}"
    __farr_token_2="${__farr_token}"
    __farr_gvrname_2="${__farr_gvrname}"
    __farr_len_2="${__farr_len}"
    _farr_array_get_meta "$1"
    __farr_result="$1"

    __farr_idx_1=1
    if [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; then
        eval __farr_item_1=\"\$\{"${__farr_gvrname_1}"_"${__farr_idx_1}"\}\"
    fi
    __farr_idx_2=1
    if [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; then
        eval __farr_item_2=\"\$\{"${__farr_gvrname_2}"_"${__farr_idx_2}"\}\"
    fi
    while [ \( "${__farr_idx_1}" -le "${__farr_len_1}" \) -a \( "${__farr_idx_2}" -le "${__farr_len_2}" \) ]; do
        if [ \( "${__farr_item_1}" '<' "${__farr_item_2}" \) -o \( "${__farr_item_1}" '=' "${__farr_item_2}" \) ] ; then
            farray_append "${__farr_result}" "${__farr_item_1}"
            __farr_idx_1=$((__farr_idx_1 + 1))
            if [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; then
                eval __farr_item_1=\"\$\{"${__farr_gvrname_1}"_"${__farr_idx_1}"\}\"
            fi
        else
            farray_append "${__farr_result}" "${__farr_item_2}"
            __farr_idx_2=$((__farr_idx_2 + 1))
            if [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; then
                eval __farr_item_2=\"\$\{"${__farr_gvrname_2}"_"${__farr_idx_2}"\}\"
            fi
        fi
    done
    # Only one of the two while-loops below will be entered
    while [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; do
        eval __farr_item_1=\"\$\{"${__farr_gvrname_1}"_"${__farr_idx_1}"\}\"
        farray_append "${__farr_result}" "${__farr_item_1}"
        __farr_idx_1=$((__farr_idx_1 + 1))
    done
    while [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; do
        eval __farr_item_2=\"\$\{"${__farr_gvrname_2}"_"${__farr_idx_2}"\}\"
        farray_append "${__farr_result}" "${__farr_item_2}"
        __farr_idx_2=$((__farr_idx_2 + 1))
    done
    return 0
}


#:
#: Empty an existing array.
#:
#: Args:
#:   $1 (str): The name of the existing array.
#:
farray_clear() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len __farr_idx __farr_del_value

    _farr_array_get_meta "$@"

    __farr_idx=1
    while [ "${__farr_idx}" -le "${__farr_len}" ]; do
        eval __farr_del_value=\"\$\{"${__farr_gvrname}"_"${__farr_idx}"\}\"
        _farr_release_object "${__farr_del_value}"
	eval unset "${__farr_gvrname}"_"${__farr_idx}"
	__farr_idx=$((__farr_idx + 1))
    done

    # Length is now zero
    setvar "${__farr_gvrname}"__ 0
}


#:
#: Release an array.
#:
#: Decrement its reference count. If it reaches zero then destroy and
#: unset an array and all its elements.
#:
#: Args:
#:   $1 (str): The name of an array. The array may exist or not.
#:
#: Returns:
#:   - A truthy value if the array existed and has been deleted.
#:   - A falsy value if the array does not exist.
#:
farray_release() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len \
          __farr_idx __farr_del_value \
          __farr_refcnt

    _farr_array_tryget_meta "$@" || return 1

    #
    # Decrement the reference count.
    # Note that the existence of the reference count proper is already
    # checked by `_farr_array_tryget_meta`.
    #
    eval __farr_refcnt=\"\$\{"${__farr_gvrname}"_C\}\"
    __farr_refcnt=$((__farr_refcnt - 1))
    setvar "${__farr_gvrname}"_C "${__farr_refcnt}"
    if [ "${__farr_refcnt}" -ne 0 ] ; then
        # Clean out the array name from the token always
        [ -n "${__farr_name}" ] && eval "${__farr_name}=''"
        return 0
    fi

    # Remove "storage" because the reference count is 0
    __farr_idx=1
    while [ "${__farr_idx}" -le "${__farr_len}" ]; do
        eval __farr_del_value=\"\$\{"${__farr_gvrname}"_"${__farr_idx}"\}\"
        _farr_release_object "${__farr_del_value}"
	eval unset "${__farr_gvrname}"_"${__farr_idx}"
	__farr_idx=$((__farr_idx + 1))
    done

    # Remove length itself ...
    eval unset "${__farr_gvrname}__"
    # ... and the reference count
    eval unset "${__farr_gvrname}_C"
    # Clean out the array name from the token
    [ -n "${__farr_name}" ] && setvar "${__farr_name}" ''
    return 0
}


#:
#: Test the boolean truth of an array.
#:
#: Args:
#:   $1 (str): The name of the array.
#:
#: Returns:
#:   int: 0 (truthy) if the array contains elements,
#:        1 (falsy) otherwise (empty or not created/destroyed properly).
#:
farray_istrue() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len

    _farr_array_tryget_meta "$@" || return 1
    if [ "${__farr_len}" -gt 0 ]; then
        return 0
    else
        return 1
    fi
}


#:
#: Determine whether any of given values is found within the array.
#:
#: Args:
#:   $1 (str): The name of an existing array.
#:   $2...: The value to search for.
#:
#: Returns:
#:   int: 0 (truish) if any of the argument value is found within the given
#:        array,
#:        1 (falsy) if the value is not found.
#:
farray_contains() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len \
           __farr_idx __farr_existing_value __farr_searched_value

    _farr_array_get_meta "$@"
    shift
    [ $# -lt 1 ] && _farr_fatal "no search value given"
    for __farr_searched_value in "$@"; do
        __farr_idx=1
        while [ "${__farr_idx}" -le "${__farr_len}" ]; do
            eval __farr_existing_value=\"\$\{"${__farr_gvrname}"_"${__farr_idx}"\}\"
            [ "${__farr_existing_value}" = "${__farr_searched_value}" ] && return 0
	    __farr_idx=$((__farr_idx + 1))
        done
    done
    return 1
}


#:
#: Try to find the index of a given value in an existing array.
#:
#: Args:
#:   $1 (str): The name of a variable where to put the found index into
#:   $2 (str): The name of an existing array
#:   $3: The value to search for
#:   $4 (int, nuĺl, optional): The start index to search for (inclusive).
#:                             If not given or `null` then `1` is used.
#:   $5 (int, null, optional):  The index to stop (inclusive).
#:                              If not given or `null` then the length of
#:                              `$2` is used.
#:
#: Returns:
#:   - 0 (truish) if the argument value is found within the given array
#:     and index constraints
#:   - 1 (falsy) otherwise
#:
farray_find() {
    local __farr_varname __farr_name __farr_searched_value \
          __farr_start __farr_end

    local __farr_token __farr_gvrname __farr_len \
          __farr_cur_find_idx __farr_existing_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift

    _farr_array_get_meta "$@"

    __farr_searched_value="${2+SET}"
    [ -z "${__farr_searched_value}" ] && _farr_fatal "no search value given"
    __farr_searched_value="$2"

    __farr_start="${3-}"
    [ -z "${__farr_start}" ] && __farr_start=1
    _farr_make_index __farr_start "${__farr_start}" "${__farr_len}"
    [ "${__farr_start}" -lt 1 ] && _farr_fatal "start index must be >= 1"
    __farr_end="${4-}"
    [ -z "${__farr_end}" ] && __farr_end="${__farr_len}"
    _farr_make_index __farr_end "${__farr_end}" "${__farr_len}"
    [ "${__farr_end}" -lt 1 ] && [ "${__farr_len}" -gt 0 ] && _farr_fatal "end index must be >= 1"
    [ "${__farr_end}" -gt "${__farr_len}" ] && _farr_fatal "end index exceeds array length"

    __farr_cur_find_idx="${__farr_start}"
    while [ "${__farr_cur_find_idx}" -le "${__farr_end}" ]; do
        eval __farr_existing_value=\"\$\{"${__farr_gvrname}"_"${__farr_cur_find_idx}"\}\"
        if [ "${__farr_existing_value}" = "${__farr_searched_value}" ]; then
            #printf "%d" ${__farr_cur_find_idx}
            setvar "${__farr_varname}" "${__farr_cur_find_idx}"
            return 0
        fi
	__farr_cur_find_idx=$((__farr_cur_find_idx + 1))
    done
    return 1
}


#:
#: Sort using Gnome Sort.
#:
#: This is a very simple stable sort (a variant of insertion sort).
#:
#: See: https://en.wikipedia.org/wiki/Gnome_sort
#:
#: Args:
#:   $1: The array to sort to
#:
farray_sort() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len \
          __farr_pos __farr_val __farr_val_1

    _farr_array_get_meta "$@"

    __farr_pos=1
    while [ "${__farr_pos}" -le "${__farr_len}" ]; do
        if [ "${__farr_pos}" -eq 1 ]; then
            __farr_pos=$((__farr_pos + 1))
        else
            eval __farr_val=\"\$\{"${__farr_gvrname}"_"${__farr_pos}"\}\"
            eval __farr_val_1=\"\$\{"${__farr_gvrname}"_$((__farr_pos - 1))\}\"
            if [ "${__farr_val}" '>' "${__farr_val_1}" ] || [ "${__farr_val}" '=' "${__farr_val_1}" ] ; then
                __farr_pos=$((__farr_pos + 1))
            else
                # swap
                setvar "${__farr_gvrname}_${__farr_pos}" "${__farr_val_1}"
                setvar "${__farr_gvrname}_$((__farr_pos - 1))" "${__farr_val}"
                __farr_pos=$((__farr_pos - 1))
            fi
        fi
    done
}


#:
#: Try to find the index of a given value in an existing array.
#:
#: It assumes that the array is sorted and uses a binary search algorithm
#: and uses lexicographical comparisons.
#:
#: Args:
#:   $1 (str): The name of a variable where to put the found index into
#:   $2 (str): The name of an existing array
#:   $3: The value to search for
#:   $4 (int, nuĺl, optional): The start index to search for (inclusive).
#:                             If not given or `null` then `1` is used.
#:   $5 (int, null, optional):  The index to stop (inclusive).
#:                              If not given or `null` then the length of
#:                              `$2` is used.
#:
#: Returns:
#:   - 0 (truish) if the argument value is found within the given array
#:     and index constraints
#:   - 1 (falsy) otherwise
#:
farray_binsearch() {
    local __farr_varname __farr_name __farr_searched_value \
          __farr_start __farr_end

    local __farr_token __farr_gvrname __farr_len \
          __farr_lo __farr_hi __farr_mid __farr_mid_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift

    _farr_array_get_meta "$@"

    __farr_searched_value="${2+SET}"
    [ -z "${__farr_searched_value}" ] && _farr_fatal "no search value given"
    __farr_searched_value="$2"

    __farr_start="${3-}"
    [ -z "${__farr_start}" ] && __farr_start=1
    _farr_make_index __farr_start "${__farr_start}" "${__farr_len}"
    [ "${__farr_start}" -lt 1 ] && _farr_fatal "start index must be >= 1"
    __farr_end="${4-}"
    [ -z "${__farr_end}" ] && __farr_end="${__farr_len}"
    _farr_make_index __farr_end "${__farr_end}" "${__farr_len}"
    [ "${__farr_end}" -lt 1 ] && [ "${__farr_len}" -gt 0 ] && _farr_fatal "end index must be >= 1"
    [ "${__farr_end}" -gt "${__farr_len}" ] && _farr_fatal "end index exceeds array length"
    __farr_lo="${__farr_start}"
    __farr_hi="${__farr_end}"
    while [ "${__farr_lo}" -le "${__farr_hi}" ]; do
        __farr_mid=$((__farr_lo + ((__farr_hi-__farr_lo)/2) ))
        eval __farr_mid_value=\"\$\{"${__farr_gvrname}"_"${__farr_mid}"\}\"
        if [ "${__farr_searched_value}" '<' "${__farr_mid_value}" ]; then
            __farr_hi=$((__farr_mid - 1))
        elif [ "${__farr_searched_value}" '>' "${__farr_mid_value}" ]; then
            __farr_lo=$((__farr_mid + 1))
        else
            # found
            setvar "${__farr_varname}" "${__farr_mid}"
            return 0
        fi
    done
    return 1    # not found
}


#:
#: Try to find the index of a given value in an existing array.
#:
#: It assumes that the array is sorted and uses an approximate binary search
#: algorithm: it finds the leftmost match:
#:
#:    On duplicate keys it is the left mode one that is found.
#:    On missing keys it is the index position at which the given key
#:    would need to be inserted.
#:
#: Comparisons are lexicographic.
#:
#: Args:
#:   $1 (str): The name of a variable where to put the found index into
#:   $2 (str): The name of an existing array
#:   $3: The value to search for
#:
#: Returns:
#:   int: 0
#:
farray_binsearch_leftmost() {
    local __farr_varname __farr_name __farr_searched_value

    local __farr_token __farr_gvrname __farr_len \
          __farr_lo __farr_hi __farr_mid __farr_mid_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift

    _farr_array_get_meta "$@"

    __farr_searched_value="${2+SET}"
    [ -z "${__farr_searched_value}" ] && _farr_fatal "no search value given"
    __farr_searched_value="$2"

    __farr_lo=1
    __farr_hi=$((__farr_len + 1))
    while [ "${__farr_lo}" -lt "${__farr_hi}" ]; do
        __farr_mid=$((__farr_lo + ((__farr_hi-__farr_lo)/2) ))
        eval __farr_mid_value=\"\$\{"${__farr_gvrname}"_"${__farr_mid}"\}\"
        if [ "${__farr_searched_value}" '>' "${__farr_mid_value}" ]; then
            __farr_lo=$((__farr_mid + 1))
        else
            __farr_hi=${__farr_mid}
        fi
    done
    setvar "${__farr_varname}" "${__farr_lo}"
    return 0
}


#:
#: Join all the elements in given array with a separator and put the result
#: into a variable.
#:
#: Args:
#:   $1 (str): The name of a variable where to put joined string value into.
#:   $2 (str): The name of an existing array.
#:   $3 (str, optional): The separator (default: a space `` ``).
#:
farray_join() {
    local __farr_varname __farr_name __farr_separator

    local __farr_token __farr_gvrname __farr_len __farr_join_idx \
          __farr_command __farr_real_separator __farr_current_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift

    _farr_array_get_meta "$@"

    __farr_separator="${2-" "}"

    __farr_real_separator=''
    __farr_command=''

    __farr_join_idx=1
    while [ "${__farr_join_idx}" -le "${__farr_len}" ]; do
	eval __farr_current_value=\"\$\{"${__farr_gvrname}"_"${__farr_join_idx}"\}\"
	__farr_command="${__farr_command}${__farr_real_separator}${__farr_current_value}"
	__farr_real_separator="${__farr_separator}"
	__farr_join_idx=$((__farr_join_idx + 1))
    done
    setvar "${__farr_varname}" "${__farr_command}"
}


#:
#: Join all the elements in given array with a space `` `` character while
#: escaping properly for feeding into shell's ``eval`` and put it into a
#: variable.
#:
#: It is meant that ``eval "$(farray_join_for_eval ARRAY)"`` is safe:
#: every item of the array becomes a word when the eval evaluates the
#: joined string.
#:
#: Args:
#:   $1 (str): The name of a variable where to put joined and properly encoded
#:             string value into.
#:   $2 (str): The name of an existing array.
#:
#: Output (stdout):
#:   The result string.
#:
farray_join_for_eval() {
    local __farr_varname  __farr_name

    local __farr_token __farr_gvrname __farr_len \
          __farr_join_idx __farr_command __farr_real_separator \
          __farr_current_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    shift

    _farr_array_get_meta "$@"

    __farr_real_separator=''
    __farr_command=''

    __farr_join_idx=1
    while [ "${__farr_join_idx}" -le "${__farr_len}" ]; do
	eval __farr_current_value=\"\$\{"${__farr_gvrname}"_"${__farr_join_idx}"\}\"
	__farr_command="${__farr_command}${__farr_real_separator}$(_farr_quote_for_eval "${__farr_current_value}")"
	__farr_real_separator=' '
	__farr_join_idx=$((__farr_join_idx + 1))
    done
    setvar "${__farr_varname}" "${__farr_command}"
}


#:
#: Join all the elements in given array with a space `` `` character while
#: escaping properly for feeding into shell's ``eval``.
#:
#: ``eval "$(farray_join_for_eval ARRAY)"`` is safe:
#: every item of the array becomes a word when the eval evaluates the
#: joined string.
#:
#: Args:
#:   $1 (str): The name of an existing array.
#:
#: Output (stdout):
#:   The joined and properly encoded string.
#:
farray_print_join_for_eval() {
    local __farr_name

    local __farr_token __farr_gvrname __farr_len \
          __farr_join_idx __farr_current_value

    _farr_array_get_meta "$@"

    __farr_join_idx=1
    while [ "${__farr_join_idx}" -le "${__farr_len}" ]; do
	eval __farr_current_value=\"\$\{"${__farr_gvrname}"_"${__farr_join_idx}"\}\"
        if [ "${__farr_join_idx}" -gt 1 ]; then
            printf '%s' " "
        fi
        printf '%s' "$(_farr_quote_for_eval "${__farr_current_value}")"
	__farr_join_idx=$((__farr_join_idx + 1))
    done
}


#:
#: Test whether two arrays are equal.
#:
#: Two arrays are equal if they have both the same length and if
#: all elements are equal (using ``test value1 = value2``).
#:
#: Args:
#:   $1 (str): The name of the first array
#:   $2 (str): The name of the second array
#:
#: Returns:
#:   int: 0 if both input arrays are equal, 1 otherwise
#:
farray_are_equal() {
    local __farr_l_name __farr_r_name

    local __farr_l_token __farr_l_gvrname __farr_l_len \
          __farr_r_token __farr_r_gvrname __farr_r_len \
          __farr_name __farr_token __farr_gvrname __farr_len \
          __farr_idx __farr_vl __farr_vr

    [ $# -ne 2 ] && _farr_fatal "missing array"

    _farr_array_get_meta "$1"
    __farr_l_name="${__farr_name}"
    __farr_l_token="${__farr_token}"
    __farr_l_gvrname="${__farr_gvrname}"
    __farr_l_len="${__farr_len}"

    _farr_array_get_meta "$2"
    __farr_r_name="${__farr_name}"
    __farr_r_token="${__farr_token}"
    __farr_r_gvrname="${__farr_gvrname}"
    __farr_r_len="${__farr_len}"

    [ "${__farr_l_len}" -ne "${__farr_r_len}" ] && return 1

    __farr_idx=1
    while [ "${__farr_idx}" -le "${__farr_l_len}" ]; do
        eval __farr_vl=\"\$\{"${__farr_l_gvrname}"_"${__farr_idx}"\}\"
        eval __farr_vr=\"\$\{"${__farr_r_gvrname}"_"${__farr_idx}"\}\"
        [ "${__farr_vl}" != "${__farr_vr}" ] && return 1
        __farr_idx=$((__farr_idx + 1))
    done
    return 0
}


#:
#: Call a function for every element in an array starting at the first index.
#:
#: The function to be called must accept at least three arguments:
#: - the array name
#: - the current index
#: - the element value at the current index
#: - all the extra arguments (`$3`, `$4`, ...) given as arguments are
#:   forwarded also
#:
#: The iteration stops if the called function returns a falsy value.
#:
#: Args:
#:   $1 (str): The name of an existing array.
#:   $2 (str): The name of a function to be called with three arguments.
#:   $3... (optional): Extra arguments forwared to `$2` also
#:
#: Warning:
#:   If the number of elements changes while being in `farray_for_each` then
#:   the behaviour is undefined.
#:   The current implementation determines the length of the array once
#:   at the start of execution.
#:
farray_for_each() {
    local __farr_name __farr_callback

    local __farr_token __farr_gvrname __farr_len __farr_idx __farr_rv \
          __farr_gm_name_or_value __farr_feval

    __farr_gm_name_or_value="${1-}"
    _farr_array_get_meta "$@"

    __farr_callback="${2-}"
    [ -z "${__farr_callback}" ] && _farr_fatal "missing callback function name"

    shift 2

    __farr_idx=1
    while [ "${__farr_idx}" -le "${__farr_len}" ]; do
        eval __farr_feval=\"\$\{"${__farr_gvrname}"_"${__farr_idx}"\}\"
        _farr_acquire_object "${__farr_feval}"
	eval "${__farr_callback} \"\${__farr_name:-\"\${__farr_gm_name_or_value}\"}\" \"\${__farr_idx}\" \"\${__farr_feval}\" \"\$@\""
	__farr_rv=$?
        _farr_release_object "${__farr_feval}"
	[ "${__farr_rv}" -ne 0 ] && return "${__farr_rv}"
	__farr_idx=$((__farr_idx + 1))
    done
    return 0
}


#:
#: Like `farray_for_each`, but the callback function is called in reversed
#: order -- beginning with the last index.
#:
farray_reversed_for_each() {
    local __farr_name __farr_callback

    local __farr_token __farr_gvrname __farr_len __farr_idx __farr_rv \
          __farr_gm_name_or_value __farr_feval

    __farr_gm_name_or_value="${1-}"
    _farr_array_get_meta "$@"
    __farr_callback="${2-}"
    [ -z "${__farr_callback}" ] && _farr_fatal "missing callback function name"

    shift 2

    __farr_idx="${__farr_len}"
    while [ "${__farr_idx}" -gt 0 ]; do
        eval __farr_feval=\"\$\{"${__farr_gvrname}"_"${__farr_idx}"\}\"
        _farr_acquire_object "${__farr_feval}"
	eval "${__farr_callback} \"\${__farr_name:-\"\${__farr_gm_name_or_value}\"}\" \"\${__farr_idx}\" \"\${__farr_feval}\" \"\$@\""
	__farr_rv=$?
        _farr_release_object "${__farr_feval}"
	[ "${__farr_rv}" -ne 0 ] && return ${__farr_rv}
	__farr_idx=$((__farr_idx - 1))
    done
    return 0
}


#:
#: Print the contents of an array to stderr.
#:
#: Args:
#:   $1 (str): The name of an array. The array may exist or not.
#:
#: Returns:
#:   int: 0
#:
farray_debug() {
    _farr_array_debug '' "$@"
}


#:
#: Internal implementation of `farray_debug`.
#:
#: Args:
#:   $1 (str): The indent
#:   $2 (str): The name or the complete prefixed token of an array
#:
#: Returns:
#:   int: 0
#:
_farr_array_debug() {
    local __farr_debug_indent __farr_name

    local __farr_token __farr_gvrname __farr_len __farr_name_or_token

    __farr_debug_indent="${1}"
    shift
    if ! _farr_array_tryget_meta "$@"; then
        printf "%sDEBUG: no (meta-)data for farray \`%s'\\n" "${__farr_debug_indent}" "${1-}" 1>&2
        return 0
    fi
    __farr_name_or_token="${__farr_name:-"${1}"}"
    if [ -n "${__farr_name}" ]; then
        printf "%sDEBUG: array \`%s' has length %s\\n" "${__farr_debug_indent}" "${__farr_name}" "${__farr_len}" 1>&2
    else
        printf "%sDEBUG: array with token \`%s' has length %s\\n" "${__farr_debug_indent}" "${__farr_token}" "${__farr_len}" 1>&2
    fi
    if [ "${__farr_len}" -gt 0 ]; then
        printf '%sDEBUG:   the items:\n' "${__farr_debug_indent}" 1>&2
        farray_for_each "${__farr_name_or_token}" _farr_debug_print_value  "${__farr_debug_indent}" || true
    fi
    return 0
}


#:
#: Debug output helper for `farray_debug`.
#:
#: Args:
#:   $4: The current indentation string
#:
_farr_debug_print_value() {
    case "$3" in
        "${_farr_array_token_prefix}"*)
            printf "%sDEBUG:     %s: >>>\\n" "$4" "$2" 1>&2
            _farr_array_debug "$4    " "$3"
            # let the return value pass through
            ;;
        "${_farr_alist_token_prefix}"*)
            printf "%sDEBUG:     %s: >>>\\n" "$4" "$2" 1>&2
            _farr_alist_debug "$4    " "$3"
            # let the return value pass through
            ;;
        *)
            printf "%sDEBUG:     %s: \`%s'\\n" "$4" "$2" "$3" 1>&2
            ;;
    esac
    return 0
}


#:
#: Just an official alias for `fobject_type`
#:
falist_type() {
    fobject_type "$@"
}


#:
#: Test whether `$1` is an alist.
#:
#: Args:
#:   $1 (str): The name of an object
#:
#: Returns:
#:   int: 0 if `$1` is an alist, 1 otherwise
#:
falist_isalist() {
    [ "$(fobject_type "$@")" = 'alist' ]
}


#:
#: Create a new alist.
#:
#: Args:
#:   $1 (str): The name of the alist.
#:             Must conform to shell variable naming conventions.
#:   $2, $3 ... (optional): A sequence of key-value pairs the alist will be
#:                          populated with.
#:
#: Exit:
#:   Iff the alist already exists.
#:
falist_create() {
    local __farr_name

    local __farr_token __farr_objname __farr_bskeyname __farr_keyname \
          __farr_valname __farr_llen

    __farr_name="${1-}"
    [ -z "${__farr_name}" ] && _farr_fatal "missing falist name"
    eval __farr_token=\"\$\{"${__farr_name}"-\}\"
    [ -n "${__farr_token}" ] && _farr_fatal "object \`${__farr_name}' already created (value \`${__farr_token}')"

    __farr_token="$(/usr/bin/hexdump -v -e '/1 "%02x"' -n 16 '/dev/urandom')"

    __farr_objname=${_farr_alist_prefix}${__farr_token}
    __farr_bskeyname=${_farr_alist_key_bs_prefix}${__farr_token}
    __farr_keyname=${_farr_alist_key_prefix}${__farr_token}
    __farr_valname=${_farr_alist_value_prefix}${__farr_token}

    # Check whether the variable already exists
    eval __farr_llen=\"\$\{"${__farr_objname}"__+SET\}\"
    [ -n "${__farr_llen}" ] && _farr_fatal "falist \`${__farr_name}' already exists: existing token \`${__farr_token}'"

    # Really create the object by ...
    # ... initializing its logical length ...
    setvar "${__farr_objname}__" 0
    # ... initializing its reference count ...
    setvar "${__farr_objname}_C" 1
    # ... initializing the storage pointers ...
    setvar "${__farr_objname}_P" "0;0"    # <first>;<last>
    #
    # ... initializing the length of the binary search key list (including
    #         tombstones
    #
    setvar "${__farr_objname}_B" 0

    # And associate the object token with the array name
    setvar "${__farr_name}" "${_farr_alist_token_prefix}${__farr_token}"

    #
    # When there are key-value pairs populate the alist with.
    # Note that the alist's name is not shifted away yet and must be taken
    # into account. It is also needed for `falist_set`.
    #
    if [ $# -gt 2 ]; then
	falist_set "$@"
    fi
}


#:
#: Internal helper to get all the metadata for an alist.
#:
#: Args:
#:   $1 (str): The name of the alist or a complete alist value with prefix
#:
#: Output (Globals):
#:   __farr_name (str): The name of the alist if the name is given,
#:                      empty if a token value is given.
#:   __farr_token (str): The token that is the value of the name.
#:   __farr_objname (str): The variable prefix for the length ("object").
#:   __farr_bskeyname (str): The variable prefix for all keys in the ordered
#:                           binary  search list
#:   __farr_keyname (str): The variable prefix for all item keys.
#:   __farr_valname (str): The variable prefix for all item values.
#:   __farr_llen (int): The logical length of the alist.
#:   __farr_bslen (int): The real length of the binsearch key list.
#:   __farr_sptr_first (str): The "pointer" to the first storage item or empty.
#:   __farr_sptr_last (str): The "pointer" to the last storage item or empty.
#:
#: Exit:
#:   Iff the array does not exist in some fashion (token and/or storage).
#:
_farr_alist_get_meta() {
    # __farr_gm_name_or_value $1

    local __farr_tmp_refcount __farr_tmp_sptr

    case "${1-}" in
        '')
            _farr_fatal "missing falist name or token value"
            ;;
        "${_farr_alist_token_prefix}"*)
            # A prefixed token value
            __farr_name=''
            __farr_token="${1#"${_farr_alist_token_prefix}"}"
            ;;
        *)
            # A variable name: go through one indirection
            __farr_name="${1}"
            eval __farr_token=\"\$\{"${__farr_name}"-\}\"
            case "${__farr_token}" in
                '')
                    _farr_fatal "object \`${__farr_name}' not created properly: token empty"
                    ;;

                "${_farr_alist_token_prefix}"*)
                    __farr_token="${__farr_token#"${_farr_alist_token_prefix}"}"
                    ;;
                *)
                    _farr_fatal "object \`${__farr_name}' is not an alist"
                    ;;
            esac
            ;;
    esac

    __farr_objname="${_farr_alist_prefix}${__farr_token}"
    __farr_bskeyname="${_farr_alist_key_bs_prefix}${__farr_token}"
    __farr_keyname="${_farr_alist_key_prefix}${__farr_token}"
    __farr_valname="${_farr_alist_value_prefix}${__farr_token}"

    eval __farr_llen=\"\$\{"${__farr_objname}"__-\}\"
    [ -z "${__farr_llen}" ] && _farr_fatal "falist \`${__farr_name:-"${1}"}' not created properly: no object for token \`${__farr_token}'"
    # Check whether the object's reference count is set properly
    eval __farr_tmp_refcount=\"\$\{"${__farr_objname}"_C:+SET\}\"
    [ -z "${__farr_tmp_refcount}" ] && _farr_fatal "falist \`${__farr_name:-"${1}"}' not created properly: no refcnt for token \`${__farr_token}'"
    # Get the storage pointers to first and last item
    eval __farr_tmp_sptr=\"\$\{"${__farr_objname}"_P-\}\"
    [ -z "${__farr_tmp_sptr}" ] && _farr_fatal "falist \`${__farr_name:-"${1}"}' not created properly: no storage pointers for token \`${__farr_token}'"
    __farr_sptr_first="${__farr_tmp_sptr%;*}"
    __farr_sptr_last="${__farr_tmp_sptr#*;}"
    eval __farr_bslen=\"\$\{"${__farr_objname}"_B-\}\"
    return 0
}


#:
#: Internal helper to try to get all the metadata for an alist.
#:
#: Args:
#:   $1 (str): The name of the alist or a complete alist value with prefix
#:
#: Output (Globals):
#:   __farr_name (str): The name of the alist if the name is given,
#:                      empty if a token value is given.
#:   __farr_token (str): The token that is the value of the name without its
#:                       token prefix.
#:   __farr_objname (str): The variable prefix for the length ("object").
#:   __farr_bskeyname (str): The variable prefix for all keys in the ordered
#:                           binary  search list
#:   __farr_keyname (str): The variable prefix for all item keys.
#:   __farr_valname (str): The variable prefix for all item values.
#:   __farr_llen (int): The logical length of the alist.
#:   __farr_bslen (int): The real length of the binsearch key list.
#:   __farr_sptr_first (str): The "pointer" to the first storage item or empty.
#:   __farr_sptr_last (str): The "pointer" to the last storage item or empty.
#:
#: Returns:
#:   0 if the array exists, 1 if something is missing.
#:
_farr_alist_tryget_meta() {
    # __farr_gm_name_or_value $1

    local __farr_tmp_refcount __farr_tmp_sptr

    case "${1-}" in
        '')
            _farr_err "missing falist name or token value"
            return 1
            ;;
        "${_farr_alist_token_prefix}"*)
            # A prefixed token value
            __farr_name=''
            __farr_token="${1#"${_farr_alist_token_prefix}"}"
            ;;
        *)
            # A variable name: go through one indirection
            __farr_name="${1}"
            eval __farr_token=\"\$\{"${__farr_name}"-\}\"
            case "${__farr_token}" in
                '')
                    _farr_err "object \`${__farr_name}' not created properly: token empty"
                    return 1
                    ;;

                "${_farr_alist_token_prefix}"*)
                    __farr_token="${__farr_token#"${_farr_alist_token_prefix}"}"
                    ;;
                *)
                    _farr_err "object \`${__farr_name}' is not an alist"
                    return 1
                    ;;
            esac
            ;;
    esac

    __farr_objname="${_farr_alist_prefix}${__farr_token}"
    __farr_bskeyname="${_farr_alist_key_bs_prefix}${__farr_token}"
    __farr_keyname="${_farr_alist_key_prefix}${__farr_token}"
    __farr_valname="${_farr_alist_value_prefix}${__farr_token}"

    eval __farr_llen=\"\$\{"${__farr_objname}"__-\}\"
    if [ -z "${__farr_llen}" ] ; then
        _farr_err "falist \`${__farr_name:-"${1}"}' not created properly: no object for token \`${__farr_token}'"
        return 1
    fi
    eval __farr_tmp_refcount=\"\$\{"${__farr_objname}"_C:+SET\}\"
    if [ -z "${__farr_tmp_refcount}" ] ; then
        _farr_err "falist \`${__farr_name:-"${1}"}' not created properly: no refcnt for token \`${__farr_token}'"
        return 1
    fi
    # Get the storage pointers to first and last item
    eval __farr_tmp_sptr=\"\$\{"${__farr_objname}"_P-\}\"
    if [ -z "${__farr_tmp_sptr}" ] ; then
        _farr_err "falist \`${__farr_name:-"${1}"}' not created properly: no storage pointers for token \`${__farr_token}'"
        return 1
    fi
    __farr_sptr_first="${__farr_tmp_sptr%;*}"
    __farr_sptr_last="${__farr_tmp_sptr#*;}"
    eval __farr_bslen=\"\$\{"${__farr_objname}"_B-\}\"
    return 0
}


#:
#: Internal helper to try to parse and get all the metadata from a storage
#: cookie.
#:
#: A storage cookie generally has the form
#: ``<storage-ptr>/<storage-prev-ptr>;<storage-next-ptr>@<object-token>``.
#:
#: Args:
#:   $1 (str): The value of the storage cookie
#:
#: Output (Globals):
#:   __farr_token (str): The token that is the value of the name without its
#:                       token prefix.
#:   __farr_objname (str): The variable prefix for the length ("object").
#:   __farr_keyname (str): The variable prefix for all item keys.
#:   __farr_valname (str): The variable prefix for all item values.
#:   __farr_sptr (str): The storage pointer.
#:   __farr_sptr_prev (str): The storage pointer to the previous entry.
#:   __farr_sptr_next (str): The storage pointer to the next entry.
#:
#: Returns:
#:   0 if the array exists, 1 if something is missing.
#:
_farr_alist_tryparse_cookie() {
    # __farr_gm_name_or_value $1

    local __farr_tmp

    if [ -z "${1}" ] ; then
        _farr_err "missing storage cookie value"
        return 1
    fi
    __farr_token="${1#*@}"
    if [ "${__farr_token}" = "${1}" ]; then
        _farr_err "not a valid storage cookie: ${1}"
        return 1
    fi
    if ! _farr_is_valid_object_token "${__farr_token}"; then
        _farr_err "not a valid object token form: ${__farr_token}"
        return 1
    fi
    __farr_tmp="${1%%@*}"
    __farr_sptr="${__farr_tmp%%/*}"
    if [ "${__farr_sptr}" = "${__farr_tmp}" ]; then
        _farr_err "not a valid storage cookie: ${1}"
        return 1
    fi
    if ! _farr_is_valid_storage_ptr "${__farr_sptr}"; then
        _farr_err "not a valid storage pointer form: ${__farr_sptr}"
        return 1
    fi
    __farr_tmp="${__farr_tmp#*/}"
    __farr_sptr_prev="${__farr_tmp%%;*}"
    if [ "${__farr_sptr_prev}" = "${__farr_tmp}" ]; then
        _farr_err "not a valid storage cookie: ${1}"
        return 1
    fi
    if ! _farr_is_valid_storage_ptr "${__farr_sptr_prev}"; then
        _farr_err "not a valid storage pointer form: ${__farr_sptr_prev}"
        return 1
    fi
    __farr_sptr_next="${__farr_tmp#*;}"

    __farr_objname="${_farr_alist_prefix}${__farr_token}"
    __farr_keyname="${_farr_alist_key_prefix}${__farr_token}"
    __farr_valname="${_farr_alist_value_prefix}${__farr_token}"

    return 0
}


#:
#: Get the logical length of an alist and put it into a variable.
#:
#: Args:
#:   $1 (str): The name of the variable to put the length info.
#:   $2 (str): The name of the alist.
#:
falist_length() {
    # __farr_varname $1
    # __farr_name $2

    local __farr_name __farr_token __farr_objname __farr_bskeyname \
          __farr_keyname __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last

    [ -z "${1-}" ] && _farr_fatal "missing variable name"
    _farr_alist_get_meta "$2"
    setvar "${1}" "${__farr_llen}"
}


#:
#: Get the length of an alist and print it to stdout.
#:
#: Args:
#:   $1 (str): The name of the alist.
#:
#: Output (stdout):
#:   The number of elements in the alist.
#:   If the array does not exist the output is -1.
#:
#: Returns:
#:   0 (truthy)
#:
falist_print_length() {
    # $1

    local __farr_vn_pl

    ( falist_length __farr_vn_pl "$@" && printf "%s" "${__farr_vn_pl}"; ) \
    || printf "%s" "-1"
}


#:
#: Empty an existing alist.
#:
#: Args:
#:   $1 (str): The name of the existing alist.
#:
falist_clear() {
    # __farr_name $1

    local __farr_name __farr_token __farr_objname __farr_bskeyname \
          __farr_keyname __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_bsidx __farr_sptr __farr_sptr_next \
          __farr_del_value __farr_del_key

    _farr_alist_get_meta "$@"

    # Remove "storage" because the reference count is 0
    __farr_sptr="${__farr_sptr_first}"
    while [ "${__farr_sptr}" -ne 0 ]; do
        eval __farr_del_value=\"\$\{"${__farr_valname}"_"${__farr_sptr}"\}\"
        _farr_release_object "${__farr_del_value}"
        eval __farr_del_key=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
        __farr_sptr_next="${__farr_del_key%%@*}"
        __farr_sptr_next="${__farr_sptr_next#*;}"
        #__farr_del_key="${__farr_del_key#*@}"
        #_farr_release_object "${__farr_del_key}"
        eval unset "${__farr_valname}"_"${__farr_sptr}"
        eval unset "${__farr_keyname}"_"${__farr_sptr}"
        __farr_sptr="${__farr_sptr_next}"
    done
    # Remove the binary search list
    __farr_bsidx=1
    while [ "${__farr_bsidx}" -le "${__farr_bslen}" ]; do
        eval unset "${__farr_bskeyname}"_"${__farr_bsidx}"
        __farr_bsidx=$((__farr_bsidx + 1))
    done

    # Reset object (length) itself
    setvar "${__farr_objname}__" 0
    # Reset binary search list length
    setvar "${__farr_objname}_B" 0
    # Reset storage pointer
    setvar "${__farr_objname}_P" '0;0'
    return 0
}


#:
#: Release an alist.
#:
#: Decrement its reference count. If it reaches zero then destroy and
#: unset an alist and all its items.
#:
#: Args:
#:   $1 (str): The name of an alist. The alist may exist or not.
#:
#: Returns:
#:   - A truthy value if the alist existed and has been deleted.
#:   - A falsy value if the alist does not exist.
#:
falist_release() {
    local __farr_name

    local __farr_token __farr_objname __farr_bskeyname __farr_keyname \
          __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_sptr __farr_del_value __farr_del_key \
          __farr_sptr_next __farr_bsidx \
          __farr_refcnt

    _farr_alist_tryget_meta "$@" || return 1

    #
    # Decrement the reference count.
    # Note that the existence of the reference count proper is already
    # checked by `_farr_alist_tryget_meta`.
    #
    eval __farr_refcnt=\"\$\{"${__farr_objname}"_C\}\"
    __farr_refcnt=$((__farr_refcnt - 1))
    setvar "${__farr_objname}_C" "${__farr_refcnt}"
    if [ "${__farr_refcnt}" -ne 0 ] ; then
        # Clean out the alist name from the token always
        [ -n "${__farr_name}" ] && setvar "${__farr_name}" ''
        return 0
    fi

    # Remove "storage" because the reference count is 0
    __farr_sptr="${__farr_sptr_first}"
    while [ "${__farr_sptr}" -ne 0 ]; do
        eval __farr_del_value=\"\$\{"${__farr_valname}"_"${__farr_sptr}"\}\"
        _farr_release_object "${__farr_del_value}"
        eval __farr_del_key=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
        __farr_sptr_next="${__farr_del_key%%@*}"
        __farr_sptr_next="${__farr_sptr_next#*;}"
        #__farr_del_key="${__farr_del_key#*@}"
        #_farr_release_object "${__farr_del_key}"
        eval unset "${__farr_valname}"_"${__farr_sptr}"
        eval unset "${__farr_keyname}"_"${__farr_sptr}"
        __farr_sptr="${__farr_sptr_next}"
    done
    # Remove the binary search list
    __farr_bsidx=1
    while [ "${__farr_bsidx}" -le "${__farr_bslen}" ]; do
        eval unset "${__farr_bskeyname}"_"${__farr_bsidx}"
        __farr_bsidx=$((__farr_bsidx + 1))
    done

    # Remove object (length) itself ...
    eval unset "${__farr_objname}__"
    # ... and its reference count
    eval unset "${__farr_objname}_C"
    # ... and its storage pointers
    eval unset "${__farr_objname}_P"
    # ... and its binsearch length
    eval unset "${__farr_objname}_B"
    # Clean out the alist name from the token
    [ -n "${__farr_name}" ] && setvar "${__farr_name}" ''
    return 0
}


#:
#: Do an exact binary search in the ordered key list.
#:
#: Comparisons are lexicographic. It skips tombstones.
#:
#: Args:
#:   $1 (str): The name of a variable where to store a index into the
#:             binary search list. This is either the index of the found
#:             key (real or tombstone) or the index where the key should be
#:             inserted into if `$2` is given as ``i`` (to inserted) or ``a``
#:             (to be appended). It may be the `null` value.
#:   $2 (str): The "pointer" to the storage where the key and the value live.
#:             These are "double-linked" lists and preserve the insertion
#:             order. This variable is only set if `$2` is either ``V`` or
#:             ``i``. It may be the `null` value
#:   $3 (str): The key that is to be searched to.
#:
#: Input (Globals):
#:   __farr_bskeyname (str): The prefix of the binary search list
#:   __farr_bslen (int): The current length of the binary search list
#:                       (including valid items *and* tombstones).
#:
_farr_alist_bsearch() {
    local __farr_varname_bsidx __farr_varname_sptr __farr_searched_value

    local __farr_lo __farr_hi __farr_mid __farr_mid_value \
          __farr_bs_sptr __farr_bs_stype

    __farr_varname_bsidx="$1"
    __farr_varname_sptr="$2"
    __farr_searched_value="$3"

    __farr_lo=1
    __farr_hi="${__farr_bslen}"
    while [ "${__farr_lo}" -le "${__farr_hi}" ]; do
        __farr_mid=$((__farr_lo + ((__farr_hi-__farr_lo)/2) ))
        eval __farr_mid_value=\"\$\{"${__farr_bskeyname}"_"${__farr_mid}"\}\"
        # <storage-ptr;<storage-type>@<key>
        __farr_bs_sptr="${__farr_mid_value%%@*}"
        __farr_bs_stype="${__farr_bs_sptr#*;}"
        __farr_bs_sptr="${__farr_bs_sptr%;*}"
        __farr_mid_value="${__farr_mid_value#*@}"
        if [ "${__farr_searched_value}" '<' "${__farr_mid_value}" ]; then
            __farr_hi=$((__farr_mid - 1))
        elif [ "${__farr_searched_value}" '>' "${__farr_mid_value}" ]; then
            __farr_lo=$((__farr_mid + 1))
        else
            # if it is a tombstone it is not found
            [ "${__farr_bs_stype}" = 'D' ] && return 1
            # yes it is not a tombstone
            [ -n "${__farr_varname_bsidx}" ] && setvar "${__farr_varname_bsidx}" "${__farr_mid}"
            [ -n "${__farr_varname_sptr}" ] && setvar "${__farr_varname_sptr}" "${__farr_bs_sptr}"
            return 0
        fi
    done
    return 1         # not found
}


#:
#: Do a "leftmost" binary search in the ordered key list.
#:
#: Comparisons are lexicographic.
#:
#: Args:
#:   $1 (str): The name of a variable where to store a index into the
#:             binary search list. This is either the index of the found
#:             key (real or tombstone) or the index where the key should be
#:             inserted into if `$2` is given as ``i`` (to inserted) or ``a``
#:             (to be appended).
#:   $2 (str): The name of a variable where to store the storage type into.
#:             This is a single character value and can be one of ``V``
#:             (found an active real value), ``D`` (deleted value, this is
#:             a tombstone), ``i`` (the value is not found) or
#:             ``a`` (the value is not found and would be appended at the end).
#:   $3 (str): The "pointer" to the storage where the key and the value live.
#:             These are "double-linked" lists and preserve the insertion
#:             order. This variable is only set if `$2` is either ``V`` or
#:             ``i``.
#:   $4 (str): The key that is to be searched to.
#:
#: Input (Globals):
#:   __farr_bskeyname (str): The prefix of the binary search list
#:   __farr_bslen (int): The current length of the binary search list
#:                       (including valid items *and* tombstones).
#:
_farr_alist_bsearch_lm() {
    local __farr_varname_bsidx __farr_varname_stype __farr_varname_sptr \
          __farr_searched_value

    local __farr_lo __farr_hi __farr_mid __farr_mid_value \
          __farr_bs_sptr __farr_bs_stype

    __farr_varname_bsidx="$1"
    __farr_varname_stype="$2"
    __farr_varname_sptr="$3"
    __farr_searched_value="$4"

    __farr_lo=1
    __farr_hi=$((__farr_bslen + 1))
    while [ "${__farr_lo}" -lt "${__farr_hi}" ]; do
        __farr_mid=$((__farr_lo + ((__farr_hi-__farr_lo)/2) ))
        eval __farr_mid_value=\"\$\{"${__farr_bskeyname}"_"${__farr_mid}"\}\"
        # <storage-ptr;<storage-type>@<key>
        __farr_mid_value="${__farr_mid_value#*@}"
        if [ "${__farr_searched_value}" '>' "${__farr_mid_value}" ]; then
            __farr_lo=$((__farr_mid + 1))
        else
            __farr_hi=${__farr_mid}
        fi
    done
    setvar "${__farr_varname_bsidx}" "${__farr_lo}"
    if [ "${__farr_lo}" -gt "${__farr_bslen}" ]; then
        # no slot (neither a value or a tombstone) found: append
        setvar "${__farr_varname_stype}" a
        setvar "${__farr_varname_sptr}" ''
    else
        # Reuse variable name
        eval __farr_mid_value=\"\$\{"${__farr_bskeyname}"_"${__farr_lo}"\}\"
        __farr_bs_sptr="${__farr_mid_value%%@*}"
        __farr_bs_stype="${__farr_bs_sptr#*;}"
        __farr_bs_sptr="${__farr_bs_sptr%;*}"
        __farr_mid_value="${__farr_mid_value#*@}"
        if [ "${__farr_searched_value}" = "${__farr_mid_value}" ]; then
            #
            # Key is already there:
            # Analyze whether it is a real value or tombstone
            #
            case "${__farr_bs_stype}" in
                V)
                # real value
                    # tombstone/deleted: reuse all slots
                    setvar "${__farr_varname_stype}" "${__farr_bs_stype}"
                    setvar "${__farr_varname_sptr}" "${__farr_bs_sptr}"
                    ;;
                D)
                    # tombstone/deleted: reuse search list slot, new storage ptr
                    setvar "${__farr_varname_stype}" "${__farr_bs_stype}"
                    setvar "${__farr_varname_sptr}" ''
                    ;;
                *)
                    # unknown
                    _farr_fatal "unexpected low-level storage type in binsearch list: ${__farr_bs_stype}"
                    ;;
            esac
        else
            # insert at __farr_lo, need new storage pointer
            setvar "${__farr_varname_stype}" i
            setvar "${__farr_varname_sptr}" "${__farr_bs_sptr}"
        fi
    fi

    return 0
}


#:
#: Map a key to a value.
#:
#: Args:
#:   $1 (str): The name of an existing alist.
#:   $2, $3 ... (optional): A sequence of key-value pairs the alist will be
#:                          populated with.
#:
#: Exit:
#:   If one of the underlying arrays that implement the alist does not exist
#:   or if an internal inconsistency will be detected.
#:
falist_set() {
    # __farr_name $1
    local __farr_key __farr_value     # ...

    local __farr_name __farr_token __farr_objname __farr_bskeyname \
          __farr_keyname __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_bsidx __farr_tmp_bsidx \
          __farr_tmp_value __farr_tmp_key __farr_prev_key \
          __farr_stype __farr_sptr __farr_prev_sptr __farr_tmp_prev_sptr

    _farr_alist_get_meta "${1-}"
    shift

    while [ $# -ne 0 ]; do
        [ $# -lt 1 ] && _farr_fatal "missing key"
        __farr_key="$1"
        [ $# -lt 2 ] && _farr_fatal "missing value"
        __farr_value="$2"

        _farr_alist_bsearch_lm __farr_bsidx __farr_stype __farr_sptr "${__farr_key}"
        case "${__farr_stype}" in
            V)
                #
                # Just replace the value at the found position.
                # Key needs no replacement/change.
                #
                eval __farr_tmp_value=\"\$\{"${__farr_valname}"_"${__farr_sptr}"\}\"
                _farr_release_object "${__farr_tmp_value}"
                _farr_acquire_object "${__farr_value}"
                setvar "${__farr_valname}_${__farr_sptr}" "${__farr_value}"
                ;;
            D)
                __farr_sptr=$((__farr_sptr_last + 1))
                setvar "${__farr_bskeyname}_${__farr_bsidx}" "${__farr_sptr};V@${__farr_key}"

                if [ "${__farr_sptr_first}" -eq 0 ]; then
                    __farr_sptr_first="${__farr_sptr}"
                fi
                __farr_prev_sptr="${__farr_sptr_last}"   # may be 0
                __farr_sptr_last="${__farr_sptr}"
                # append key at the end of storage
                setvar "${__farr_keyname}_${__farr_sptr}" "${__farr_prev_sptr};0@${__farr_key}"
                # store the value
                _farr_acquire_object "${__farr_value}"
                setvar "${__farr_valname}_${__farr_sptr}" "${__farr_value}"
                # increase logical length
                __farr_llen=$((__farr_llen + 1))
                setvar "${__farr_objname}__" "${__farr_llen}"
                setvar "${__farr_objname}_P" "${__farr_sptr_first};${__farr_sptr_last}"
                # no change of bs search list length

                # adjust "next ptr" of previous last item -- if any
                if [ "${__farr_prev_sptr}" -ne 0 ]; then
                    eval __farr_prev_key=\"\$\{"${__farr_keyname}"_"${__farr_prev_sptr}"\}\"
                    __farr_tmp_prev_sptr="${__farr_prev_key%%@*}"
                    __farr_tmp_prev_sptr="${__farr_tmp_prev_sptr%;*}"
                    setvar "${__farr_keyname}_${__farr_prev_sptr}" "${__farr_tmp_prev_sptr};${__farr_sptr}@${__farr_prev_key#*@}"
                fi
                ;;
            i)
                __farr_sptr=$((__farr_sptr_last + 1))
                if [ "${__farr_sptr_first}" -eq 0 ]; then
                    __farr_sptr_first="${__farr_sptr}"
                fi
                __farr_prev_sptr="${__farr_sptr_last}"   # may be 0
                __farr_sptr_last="${__farr_sptr}"
                #
                # Make room and move existing binsearch list entries and
                # insert the key into the binary search list
                #
                __farr_tmp_bsidx="${__farr_bslen}"
                while [ "${__farr_tmp_bsidx}" -ge "${__farr_bsidx}" ]; do
                    eval "${__farr_bskeyname}"_$((__farr_tmp_bsidx + 1))=\"\$\{"${__farr_bskeyname}"_"${__farr_tmp_bsidx}"\}\"
                    __farr_tmp_bsidx=$((__farr_tmp_bsidx - 1))
                done
                setvar "${__farr_bskeyname}_${__farr_bsidx}" "${__farr_sptr};V@${__farr_key}"
                # append key at the end of storage
                setvar "${__farr_keyname}_${__farr_sptr}" "${__farr_prev_sptr};0@${__farr_key}"
                # store the value
                _farr_acquire_object "${__farr_value}"
                setvar "${__farr_valname}_${__farr_sptr}" "${__farr_value}"
                # increase logical length
                __farr_llen=$((__farr_llen + 1))
                setvar "${__farr_objname}__" "${__farr_llen}"
                __farr_bslen=$((__farr_bslen + 1))
                setvar "${__farr_objname}_B" "${__farr_bslen}"
                setvar "${__farr_objname}_P" "${__farr_sptr_first};${__farr_sptr_last}"
                # adjust "next ptr" of previous last item -- if any
                if [ "${__farr_prev_sptr}" -ne 0 ]; then
                    eval __farr_prev_key=\"\$\{"${__farr_keyname}"_"${__farr_prev_sptr}"\}\"
                    __farr_tmp_prev_sptr="${__farr_prev_key%%@*}"
                    __farr_tmp_prev_sptr="${__farr_tmp_prev_sptr%;*}"
                    setvar "${__farr_keyname}_${__farr_prev_sptr}" "${__farr_tmp_prev_sptr};${__farr_sptr}@${__farr_prev_key#*@}"
                fi
                ;;
            a)
                __farr_sptr=$((__farr_sptr_last + 1))
                setvar "${__farr_bskeyname}_$((__farr_bslen + 1))" "${__farr_sptr};V@${__farr_key}"

                if [ "${__farr_sptr_first}" -eq 0 ]; then
                    __farr_sptr_first="${__farr_sptr}"
                fi
                __farr_prev_sptr="${__farr_sptr_last}"   # may be 0
                __farr_sptr_last="${__farr_sptr}"
                # append key at the end of storage
                setvar "${__farr_keyname}_${__farr_sptr}" "${__farr_prev_sptr};0@${__farr_key}"
                # store the value
                _farr_acquire_object "${__farr_value}"
                setvar "${__farr_valname}_${__farr_sptr}" "${__farr_value}"
                # increase logical length
                __farr_llen=$((__farr_llen + 1))
                setvar "${__farr_objname}__" "${__farr_llen}"
                __farr_bslen=$((__farr_bslen + 1))
                setvar "${__farr_objname}_B" "${__farr_bslen}"
                setvar "${__farr_objname}_P" "${__farr_sptr_first};${__farr_sptr_last}"
                # adjust "next ptr" of previous last item -- if any
                if [ "${__farr_prev_sptr}" -ne 0 ]; then
                    eval __farr_prev_key=\"\$\{"${__farr_keyname}"_"${__farr_prev_sptr}"\}\"
                    __farr_tmp_key="${__farr_prev_key#*@}"
                    __farr_tmp_prev_sptr="${__farr_prev_key%%@*}"
                    __farr_tmp_prev_sptr="${__farr_tmp_prev_sptr%;*}"
                   setvar "${__farr_keyname}_${__farr_prev_sptr}" "${__farr_tmp_prev_sptr};${__farr_sptr}@${__farr_tmp_key}"
                fi
                ;;
            *)
                _farr_fatal "unexpected storage type: ${__farr_stype}"
                ;;
        esac
        shift 2
    done
    return 0
}


#:
#: Map a key to a value while assuming that the given keys are not already
#: in the alist.
#:
#: Args:
#:   $1 (str): The name of an existing alist.
#:   $2, $3 ... (optional): A sequence of key-value pairs the alist will be
#:                          populated with.
#:
#: Exit:
#:   If one of the underlying arrays that implement the alist does not exist
#:   or if an internal inconsistency will be detected.
#:
falist_add() {
    # __farr_name $1
    local __farr_key __farr_value    # ...

    local __farr_name __farr_token __farr_objname __farr_bskeyname \
          __farr_keyname __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_prev_key __farr_sptr \
          __farr_tmp_key __farr_tmp_prev_sptr __farr_prev_sptr

    _farr_alist_get_meta "${1-}"
    shift

    while [ $# -ne 0 ]; do
        [ $# -lt 1 ] && _farr_fatal "missing key"
        __farr_key="$1"
        [ $# -lt 2 ] && _farr_fatal "missing value"
        __farr_value="$2"

        #
        # We do just append ...
        #

        #
        # But check first for proper key ordering
        # This relies on the fact that deleting/tombstoning
        # (see `falist_trydel`) removes all trailing tombstoned entries.
        #
        if [ "${__farr_bslen}" -gt 0 ]; then
            eval __farr_prev_key=\"\$\{"${__farr_bskeyname}"_"${__farr_bslen}"\}\"
            __farr_prev_key="${__farr_prev_key#*@}"
            if [ \( "${__farr_key}" = "${__farr_prev_key}" \) -o \( "${__farr_key}" '<' "${__farr_prev_key}" \) ] ; then
                _farr_fatal "falist_add() would violate key order"
            fi
        fi

        # now add as in falist_set()
        __farr_sptr=$((__farr_sptr_last + 1))
        setvar "${__farr_bskeyname}_$((__farr_bslen + 1))" "${__farr_sptr};V@${__farr_key}"

        if [ "${__farr_sptr_first}" -eq 0 ]; then
            __farr_sptr_first="${__farr_sptr}"
        fi
        __farr_prev_sptr="${__farr_sptr_last}"   # may be 0
        __farr_sptr_last="${__farr_sptr}"
        # append key at the end of storage
        setvar "${__farr_keyname}_${__farr_sptr}" "${__farr_prev_sptr};0@${__farr_key}"
        # store the value
        _farr_acquire_object "${__farr_value}"
        setvar "${__farr_valname}_${__farr_sptr}" "${__farr_value}"
        # increase logical length
        __farr_llen=$((__farr_llen + 1))
        setvar "${__farr_objname}__" "${__farr_llen}"
        __farr_bslen=$((__farr_bslen + 1))
        setvar "${__farr_objname}_B" "${__farr_bslen}"
        setvar "${__farr_objname}_P" "${__farr_sptr_first};${__farr_sptr_last}"
        # adjust "next ptr" of previous last item -- if any
        if [ "${__farr_prev_sptr}" -ne 0 ]; then
            eval __farr_prev_key=\"\$\{"${__farr_keyname}"_"${__farr_prev_sptr}"\}\"
            __farr_tmp_key="${__farr_prev_key#*@}"
            __farr_tmp_prev_sptr="${__farr_prev_key%%@*}"
            __farr_tmp_prev_sptr="${__farr_tmp_prev_sptr%;*}"
            setvar "${__farr_keyname}_${__farr_prev_sptr}" "${__farr_tmp_prev_sptr};${__farr_sptr}@${__farr_tmp_key}"
        fi

        shift 2
    done
    return 0
}


#:
#: Map a key to a value but error if the alist contains already an item
#: with the given key.
#:
#: Args:
#:   $1 (str): The name of an existing alist.
#:   $2, $3 ... (optional): A sequence of key-value pairs the alist will be
#:                          populated with.
#:
#: Returns:
#:   int: 0 (truthy) if the item got set, 1 (falsy) if there is already an
#:        item with key `$1` in the alist
#:
#: Exit:
#:   If one of the underlying arrays that implement the alist does not exist
#:   or if an internal inconsistency will be detected.
#:
falist_set_unique() {
    # __farr_name $1
    local __farr_key __farr_value     # ...

    local __farr_name __farr_token __farr_objname __farr_bskeyname \
          __farr_keyname __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_bsidx __farr_tmp_bsidx \
          __farr_tmp_value __farr_tmp_key __farr_prev_key \
          __farr_stype __farr_sptr __farr_prev_sptr __farr_tmp_prev_sptr

    _farr_alist_get_meta "${1-}"
    shift

    while [ $# -ne 0 ]; do
        [ $# -lt 1 ] && _farr_fatal "missing key"
        __farr_key="$1"
        [ $# -lt 2 ] && _farr_fatal "missing value"
        __farr_value="$2"

        _farr_alist_bsearch_lm __farr_bsidx __farr_stype __farr_sptr "${__farr_key}"
        case "${__farr_stype}" in
            V)
                # key is already set: would be non-unique
                return 1
                ;;
            D)
                __farr_sptr=$((__farr_sptr_last + 1))
                setvar "${__farr_bskeyname}_${__farr_bsidx}" "${__farr_sptr};V@${__farr_key}"

                if [ "${__farr_sptr_first}" -eq 0 ]; then
                    __farr_sptr_first="${__farr_sptr}"
                fi
                __farr_prev_sptr="${__farr_sptr_last}"   # may be 0
                __farr_sptr_last="${__farr_sptr}"
                # append key at the end of storage
                setvar "${__farr_keyname}_${__farr_sptr}" "${__farr_prev_sptr};0@${__farr_key}"
                # store the value
                _farr_acquire_object "${__farr_value}"
                setvar "${__farr_valname}_${__farr_sptr}" "${__farr_value}"
                # increase logical length
                __farr_llen=$((__farr_llen + 1))
                setvar "${__farr_objname}__" "${__farr_llen}"
                setvar "${__farr_objname}_P" "${__farr_sptr_first};${__farr_sptr_last}"
                # no change of bs search list length

                # adjust "next ptr" of previous last item -- if any
                if [ "${__farr_prev_sptr}" -ne 0 ]; then
                    eval __farr_prev_key=\"\$\{"${__farr_keyname}"_"${__farr_prev_sptr}"\}\"
                    __farr_tmp_key="${__farr_prev_key#*@}"
                    __farr_tmp_prev_sptr="${__farr_prev_key%%@*}"
                    __farr_tmp_prev_sptr="${__farr_tmp_prev_sptr%;*}"
                    setvar "${__farr_keyname}_${__farr_prev_sptr}" "${__farr_tmp_prev_sptr};${__farr_sptr}@${__farr_tmp_key}"
                fi
                ;;
            i)
                __farr_sptr=$((__farr_sptr_last + 1))
                if [ "${__farr_sptr_first}" -eq 0 ]; then
                    __farr_sptr_first="${__farr_sptr}"
                fi
                __farr_prev_sptr="${__farr_sptr_last}"   # may be 0
                __farr_sptr_last="${__farr_sptr}"
                #
                # Make room and move existing binsearch list entries and
                # insert the key into the binary search list
                #
                __farr_tmp_bsidx="${__farr_bslen}"
                while [ "${__farr_tmp_bsidx}" -ge "${__farr_bsidx}" ]; do
                    eval "${__farr_bskeyname}"_$((__farr_tmp_bsidx + 1))=\"\$\{"${__farr_bskeyname}"_"${__farr_tmp_bsidx}"\}\"
                    __farr_tmp_bsidx=$((__farr_tmp_bsidx - 1))
                done
                setvar "${__farr_bskeyname}_${__farr_bsidx}" "${__farr_sptr};V@${__farr_key}"
                # append key at the end of storage
                setvar "${__farr_keyname}_${__farr_sptr}" "${__farr_prev_sptr};0@${__farr_key}"
                # store the value
                _farr_acquire_object "${__farr_value}"
                setvar "${__farr_valname}_${__farr_sptr}" "${__farr_value}"
                # increase logical length
                __farr_llen=$((__farr_llen + 1))
                setvar "${__farr_objname}__" "${__farr_llen}"
                __farr_bslen=$((__farr_bslen + 1))
                setvar "${__farr_objname}_B" "${__farr_bslen}"
                setvar "${__farr_objname}_P" "${__farr_sptr_first};${__farr_sptr_last}"
                # adjust "next ptr" of previous last item -- if any
                if [ "${__farr_prev_sptr}" -ne 0 ]; then
                    eval __farr_prev_key=\"\$\{"${__farr_keyname}"_"${__farr_prev_sptr}"\}\"
                    __farr_tmp_key="${__farr_prev_key#*@}"
                    __farr_tmp_prev_sptr="${__farr_prev_key%%@*}"
                    __farr_tmp_prev_sptr="${__farr_tmp_prev_sptr%;*}"
                    setvar "${__farr_keyname}_${__farr_prev_sptr}" "${__farr_tmp_prev_sptr};${__farr_sptr}@${__farr_tmp_key}"
                fi
                ;;
            a)
                __farr_sptr=$((__farr_sptr_last + 1))
                setvar "${__farr_bskeyname}_$((__farr_bslen + 1))" "${__farr_sptr};V@${__farr_key}"

                if [ "${__farr_sptr_first}" -eq 0 ]; then
                    __farr_sptr_first="${__farr_sptr}"
                fi
                __farr_prev_sptr="${__farr_sptr_last}"   # may be 0
                __farr_sptr_last="${__farr_sptr}"
                # append key at the end of storage
                setvar "${__farr_keyname}_${__farr_sptr}" "${__farr_prev_sptr};0@${__farr_key}"
                # store the value
                _farr_acquire_object "${__farr_value}"
                setvar "${__farr_valname}_${__farr_sptr}" "${__farr_value}"
                # increase logical length
                __farr_llen=$((__farr_llen + 1))
                setvar "${__farr_objname}__" "${__farr_llen}"
                __farr_bslen=$((__farr_bslen + 1))
                setvar "${__farr_objname}_B" "${__farr_bslen}"
                setvar "${__farr_objname}_P" "${__farr_sptr_first};${__farr_sptr_last}"
                # adjust "next ptr" of previous last item -- if any
                if [ "${__farr_prev_sptr}" -ne 0 ]; then
                    eval __farr_prev_key=\"\$\{"${__farr_keyname}"_"${__farr_prev_sptr}"\}\"
                    __farr_tmp_key="${__farr_prev_key#*@}"
                    __farr_tmp_prev_sptr="${__farr_prev_key%%@*}"
                    __farr_tmp_prev_sptr="${__farr_tmp_prev_sptr%;*}"
                   setvar "${__farr_keyname}_${__farr_prev_sptr}" "${__farr_tmp_prev_sptr};${__farr_sptr}@${__farr_tmp_key}"
                fi
                ;;
            *)
                _farr_fatal "unexpected storage type: ${__farr_stype}"
                ;;
        esac
        shift 2
    done
    return 0
}


#:
#: Update an alist from another alist.
#:
#: Key-values from the right alist are given precedence and may overwrite
#: existing items on the left. But the left array has precedence with regard
#: to insertion order.
#:
#: Args:
#:   $1 (str): The ("left") alist that is to be updated from `$2`.
#:   $2 (str): The ("right") alist
#:
falist_update() {
    local __farr_name __farr_r_name

    local __farr_token __farr_objname __farr_bskeyname __farr_keyname \
          __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_r_token __farr_r_objname __farr_r_bskeyname __farr_r_keyname \
          __farr_r_valname __farr_r_llen __farr_r_bslen \
          __farr_r_sptr_first __farr_r_sptr_last \
          __farr_bsidx __farr_stype __farr_sptr __farr_tmp_bsidx \
          __farr_key __farr_value \
          __farr_r_key __farr_r_sptr __farr_r_sptr_next __farr_r_value \
          __farr_prev_sptr __farr_prev_key \
          __farr_tmp_prev_sptr

    [ $# -ne 2 ] && _farr_fatal "exactly two arrays must be given"
    _farr_alist_get_meta "$2"
    __farr_r_name="${__farr_name}"
    __farr_r_token="${__farr_token}"
    __farr_r_objname="${__farr_objname}"
    __farr_r_bskeyname="${__farr_bskeyname}"
    __farr_r_keyname="${__farr_keyname}"
    __farr_r_valname="${__farr_valname}"
    __farr_r_llen="${__farr_llen}"
    __farr_r_bslen="${__farr_bslen}"
    __farr_r_sptr_first="${__farr_sptr_first}"
    __farr_r_sptr_last="${__farr_sptr_last}"
    _farr_alist_get_meta "$1"

    __farr_r_sptr="${__farr_r_sptr_first}"
    while [ "${__farr_r_sptr}" -ne 0 ] ; do
        eval __farr_r_key=\"\$\{"${__farr_r_keyname}"_"${__farr_r_sptr}"\}\"
        eval __farr_r_value=\"\$\{"${__farr_r_valname}"_"${__farr_r_sptr}"\}\"
        __farr_r_sptr_next="${__farr_r_key%%@*}"
        __farr_r_key="${__farr_r_key#*@}"
        __farr_r_sptr_next="${__farr_r_sptr_next#*;}"

        _farr_alist_bsearch_lm __farr_bsidx __farr_stype __farr_sptr "${__farr_r_key}"
        case "${__farr_stype}" in
            V)
                #
                # Just replace the value at the found position.
                # Key needs no replacement/change.
                #
                eval __farr_value=\"\$\{"${__farr_valname}"_"${__farr_sptr}"\}\"
                _farr_release_object "${__farr_value}"
                _farr_acquire_object "${__farr_r_value}"
                setvar "${__farr_valname}_${__farr_sptr}" "${__farr_r_value}"
                ;;
            D)
                __farr_sptr=$((__farr_sptr_last + 1))
                setvar "${__farr_bskeyname}_${__farr_bsidx}" "${__farr_sptr};V@${__farr_r_key}"

                if [ "${__farr_sptr_first}" -eq 0 ]; then
                    __farr_sptr_first="${__farr_sptr}"
                fi
                __farr_prev_sptr="${__farr_sptr_last}"   # may be 0
                __farr_sptr_last="${__farr_sptr}"
                # append key at the end of storage
                setvar "${__farr_keyname}_${__farr_sptr}" "${__farr_prev_sptr};0@${__farr_r_key}"
                # store the value
                _farr_acquire_object "${__farr_r_value}"
                setvar "${__farr_valname}_${__farr_sptr}" "${__farr_r_value}"
                # increase logical length
                __farr_llen=$((__farr_llen + 1))
                setvar "${__farr_objname}__" "${__farr_llen}"
                setvar "${__farr_objname}_P" "${__farr_sptr_first};${__farr_sptr_last}"
                # no change of bs search list length

                # adjust "next ptr" of previous last item -- if any
                if [ "${__farr_prev_sptr}" -ne 0 ]; then
                    eval __farr_prev_key=\"\$\{"${__farr_keyname}"_"${__farr_prev_sptr}"\}\"
                    __farr_tmp_prev_sptr="${__farr_prev_key%%@*}"
                    __farr_tmp_prev_sptr="${__farr_tmp_prev_sptr%;*}"
                    setvar "${__farr_keyname}_${__farr_prev_sptr}" "${__farr_tmp_prev_sptr};${__farr_sptr}@${__farr_prev_key#*@}"
                fi
                ;;
            i)
                __farr_sptr=$((__farr_sptr_last + 1))
                if [ "${__farr_sptr_first}" -eq 0 ]; then
                    __farr_sptr_first="${__farr_sptr}"
                fi
                __farr_prev_sptr="${__farr_sptr_last}"   # may be 0
                __farr_sptr_last="${__farr_sptr}"
                #
                # Make room and move existing binsearch list entries and
                # insert the key into the binary search list
                #
                __farr_tmp_bsidx="${__farr_bslen}"
                while [ "${__farr_tmp_bsidx}" -ge "${__farr_bsidx}" ]; do
                    eval __farr_key=\"\$\{"${__farr_bskeyname}"_"${__farr_tmp_bsidx}"\}\"
                    setvar "${__farr_bskeyname}_$((__farr_tmp_bsidx + 1))" "${__farr_key}"
                    __farr_tmp_bsidx=$((__farr_tmp_bsidx - 1))
                done
                setvar "${__farr_bskeyname}_${__farr_bsidx}" "${__farr_sptr};V@${__farr_r_key}"
                # append key at the end of storage
                setvar "${__farr_keyname}_${__farr_sptr}" "${__farr_prev_sptr};0@${__farr_r_key}"
                # store the value
                _farr_acquire_object "${__farr_r_value}"
                setvar "${__farr_valname}_${__farr_sptr}" "${__farr_r_value}"
                # increase logical length
                __farr_llen=$((__farr_llen + 1))
                setvar "${__farr_objname}__" "${__farr_llen}"
                __farr_bslen=$((__farr_bslen + 1))
                setvar "${__farr_objname}_B" "${__farr_bslen}"
                setvar "${__farr_objname}_P" "${__farr_sptr_first};${__farr_sptr_last}"
                # adjust "next ptr" of previous last item -- if any
                if [ "${__farr_prev_sptr}" -ne 0 ]; then
                    eval __farr_prev_key=\"\$\{"${__farr_keyname}"_"${__farr_prev_sptr}"\}\"
                    __farr_tmp_prev_sptr="${__farr_prev_key%%@*}"
                    __farr_tmp_prev_sptr="${__farr_tmp_prev_sptr%;*}"
                    setvar "${__farr_keyname}_${__farr_prev_sptr}" "${__farr_tmp_prev_sptr};${__farr_sptr}@${__farr_prev_key#*@}"
                fi
                ;;
            a)
                __farr_sptr=$((__farr_sptr_last + 1))
                setvar "${__farr_bskeyname}_$((__farr_bslen + 1))" "${__farr_sptr};V@${__farr_r_key}"

                if [ "${__farr_sptr_first}" -eq 0 ]; then
                    __farr_sptr_first="${__farr_sptr}"
                fi
                __farr_prev_sptr="${__farr_sptr_last}"   # may be 0
                __farr_sptr_last="${__farr_sptr}"
                # append key at the end of storage
                setvar "${__farr_keyname}_${__farr_sptr}" "${__farr_prev_sptr};0@${__farr_r_key}"
                # store the value
                _farr_acquire_object "${__farr_r_value}"
                setvar "${__farr_valname}_${__farr_sptr}" "${__farr_r_value}"
                # increase logical length
                __farr_llen=$((__farr_llen + 1))
                setvar "${__farr_objname}__" "${__farr_llen}"
                __farr_bslen=$((__farr_bslen + 1))
                setvar "${__farr_objname}_B" "${__farr_bslen}"
                setvar "${__farr_objname}_P" "${__farr_sptr_first};${__farr_sptr_last}"
                # adjust "next ptr" of previous last item -- if any
                if [ "${__farr_prev_sptr}" -ne 0 ]; then
                    eval __farr_prev_key=\"\$\{"${__farr_keyname}"_"${__farr_prev_sptr}"\}\"
                    __farr_tmp_prev_sptr="${__farr_prev_key%%@*}"
                    __farr_tmp_prev_sptr="${__farr_tmp_prev_sptr%;*}"
                   setvar "${__farr_keyname}_${__farr_prev_sptr}" "${__farr_tmp_prev_sptr};${__farr_sptr}@${__farr_prev_key#*@}"
                fi
                ;;
            *)
                _farr_fatal "unexpected storage type: ${__farr_stype}"
                ;;
        esac

        # Loop: move forward
        __farr_r_sptr="${__farr_r_sptr_next}"
    done
    return 0
}


#:
#: Get the value that is associated with a key and put it into a variable.
#:
#: Args:
#:   $1 (str): The name of the variable to put the value into.
#:   $2 (str): The name of an existing alist.
#:   $3: The key.
#:   $4 (str, optional): The name of a variable where to store a storage
#:                       cookie (an extended form of a storage pointer) into.
#:
#: Exit:
#:   - If the key is not found.
#:   - If one of the underlying arrays that implement the alist does not exist.
#:     or if an internal inconsistency will be detected.
#:
falist_get() {
    local __farr_varname __farr_name __farr_key __farr_varname_scookie

    local __farr_token __farr_objname __farr_bskeyname __farr_keyname \
          __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_sptr __farr_get_key __farr_get_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    _farr_alist_get_meta "${2-}"
    [ $# -lt 3 ] && _farr_fatal "missing key"
    __farr_key="$3"
    __farr_varname_scookie="${4-}"

    if _farr_alist_bsearch '' __farr_sptr "${__farr_key}" ; then
        eval __farr_get_value=\"\$\{"${__farr_valname}"_"${__farr_sptr}"\}\"
        _farr_acquire_object "${__farr_get_value}"
        setvar "${__farr_varname}" "${__farr_get_value}"
        if [ -n "${__farr_varname_scookie}" ] ; then
            # need more infos for the cookie from the corresponding key entry
            eval __farr_get_key=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
            # storage cookie is <storage-ptr>/<storage-prev-ptr>;<storage-next-ptr>@<object-token>
            setvar "${__farr_varname_scookie}" "${__farr_sptr}/${__farr_get_key%%@*}@${__farr_token}"
        fi
    else
        _farr_fatal "alist \`${__farr_name:-"${2}"}': key \`${__farr_key}' not found"
    fi
}


#:
#: Try to get the value that is associated with a key and store it in a
#: variable.
#:
#: Args:
#:   $1 (str): The name of the variable where to put the value into.
#:   $2 (str): The name of an existing alist.
#:   $3: The key.
#:   $4 (str, optional): The name of a variable where to store  a storage
#:                       cookie (an extended form of a storage pointer) into.
#:
#: Returns:
#:   0 (truthy) on success,
#:   1 (falsy) if the given key is not found.
#:
falist_tryget() {
    local __farr_varname __farr_name __farr_key __farr_varname_scookie

    local __farr_token __farr_objname __farr_bskeyname __farr_keyname \
          __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_sptr __farr_get_key __farr_get_value

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    _farr_alist_get_meta "${2-}"
    [ $# -lt 3 ] && _farr_fatal "missing key"
    __farr_key="$3"
    __farr_varname_scookie="${4-}"

    if _farr_alist_bsearch '' __farr_sptr "${__farr_key}" ; then
        eval __farr_get_value=\"\$\{"${__farr_valname}"_"${__farr_sptr}"\}\"
        _farr_acquire_object "${__farr_get_value}"
        setvar "${__farr_varname}" "${__farr_get_value}"
        if [ -n "${__farr_varname_scookie}" ] ; then
            # need more infos for the cookie from the corresponding key entry
            eval __farr_get_key=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
            # storage cookie is <storage-ptr>/<storage-prev-ptr>;<storage-next-ptr>@<object-token>
            setvar "${__farr_varname_scookie}" "${__farr_sptr}/${__farr_get_key%%@*}@${__farr_token}"
        fi
        return 0
    fi
    return 1
}


#:
#: Get the cookie to the first item
#:
#: Args:
#:   $1 (str): An existing alist.
#:
#: Output (stdout):
#:   The cookie. Can be used in `falist_tryget_item_at` and friends.
#:
falist_cookie_first() {
    local __farr_name

    local __farr_token __farr_objname __farr_bskeyname __farr_keyname \
          __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_sptr __farr_sptr_next __farr_sptr_prev __farr_cf_key

    _farr_alist_get_meta "$@"

    __farr_sptr="${__farr_sptr_first}"
    if [ "${__farr_sptr}" -eq 0 ]; then
        printf '%s' "0/0;0@${__farr_token}"
    else
        eval __farr_cf_key=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
        __farr_sptr_next="${__farr_cf_key%%@*}"
        __farr_sptr_prev="${__farr_sptr_next%;*}"
        __farr_sptr_next="${__farr_sptr_next#*;}"
        printf '%s/%s;%s@%s' "${__farr_sptr}" "${__farr_sptr_prev}" "${__farr_sptr_next}" "${__farr_token}"
    fi
}


#:
#: Get the cookie to the last item
#:
#: Args:
#:   $1 (str): An existing alist.
#:
#: Output (stdout):
#:   The cookie. Can be used in `falist_tryget_item_at` and friends.
#:
falist_cookie_last() {
    local __farr_name

    local __farr_token __farr_objname __farr_bskeyname __farr_keyname \
          __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_sptr __farr_sptr_next __farr_sptr_prev __farr_cf_key

    _farr_alist_get_meta "$@"

    __farr_sptr="${__farr_sptr_last}"
    if [ "${__farr_sptr}" -eq 0 ]; then
        printf '%s' "0/0;0@${__farr_token}"
    else
        eval __farr_cf_key=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
        __farr_sptr_next="${__farr_cf_key%%@*}"
        __farr_sptr_prev="${__farr_sptr_next%;*}"
        __farr_sptr_next="${__farr_sptr_next#*;}"
        printf '%s/%s;%s@%s' "${__farr_sptr}" "${__farr_sptr_prev}" "${__farr_sptr_next}" "${__farr_token}"
    fi
}


#:
#: Get the next cookie from a given cookie
#:
#: Args:
#:   $1 (str): The cookie value.
#:
#: Output (stdout):
#:   The next cookie.
#:
falist_cookie_next() {
    # __farr_scookie $1

    local __farr_token __farr_objname __farr_keyname __farr_valname \
          __farr_sptr __farr_sptr_prev __farr_sptr_next \
          __farr_cn_key

    _farr_alist_tryparse_cookie "${1-}" || return 1

    if [ "${__farr_sptr}" -eq 0 ] || [ "${__farr_sptr_next}" -eq 0 ] ; then
        printf '%s' "0/0;0@${__farr_token}"
    else
        __farr_sptr="${__farr_sptr_next}"
        eval __farr_cn_key=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
        __farr_sptr_next="${__farr_cn_key%%@*}"
        __farr_sptr_prev="${__farr_sptr_next%;*}"
        __farr_sptr_next="${__farr_sptr_next#*;}"
        printf '%s/%s;%s@%s' "${__farr_sptr}" "${__farr_sptr_prev}" "${__farr_sptr_next}" "${__farr_token}"
    fi
}


#:
#: Get the previous cookie from a given cookie
#:
#: Args:
#:   $1 (str): The cookie value.
#:
#: Output (stdout):
#:   The previous cookie.
#:
falist_cookie_prev() {
    # __farr_scookie $1

    local __farr_token __farr_objname __farr_keyname __farr_valname \
          __farr_sptr __farr_sptr_prev __farr_sptr_next \
          __farr_cn_key

    _farr_alist_tryparse_cookie "${1-}" || return 1

    if [ "${__farr_sptr}" -eq 0 ] || [ "${__farr_sptr_prev}" -eq 0 ] ; then
        printf '%s' "0/0;0@${__farr_token}"
    else
        __farr_sptr="${__farr_sptr_prev}"
        eval __farr_cn_key=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
        __farr_sptr_next="${__farr_cn_key%%@*}"
        __farr_sptr_prev="${__farr_sptr_next%;*}"
        __farr_sptr_next="${__farr_sptr_next#*;}"
        printf '%s/%s;%s@%s' "${__farr_sptr}" "${__farr_sptr_prev}" "${__farr_sptr_next}" "${__farr_token}"
    fi
}


#:
#: Try to get the key that is associated with a storage cookie and
#: store it into a variable,
#:
#: Use this for iteration over keys.
#:
#: Args:
#:   $1 (str): The name of the variable where to put the key into.
#:   $2 (str): The storage cookie.
#:
#: Returns:
#:   0 (truthy) on success,
#:   1 (falsy) if the given index is out of bounds.
#:
#: Exit:
#:   Other errors (missing array name, missing index value) are considered
#:   fatal and call `_farr_fatal` (i.e. `exit`).
#:
falist_tryget_key_at() {
    local __farr_key_varname __farr_scookie

    local __farr_token __farr_objname __farr_keyname __farr_valname \
          __farr_sptr __farr_sptr_prev __farr_sptr_next \
          __farr_getikey __farr_getival

    __farr_key_varname=${1-}
    [ -z "${__farr_key_varname}" ] && _farr_fatal "missing variable name for key"
    _farr_alist_tryparse_cookie "${2-}" || return 1

    if [ "${__farr_sptr}" -ne 0 ] ; then
        eval __farr_getikey=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"+SET\}\"
        if [ -n "${__farr_getikey}" ]; then
            eval __farr_getikey=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
            setvar "${__farr_key_varname}" "${__farr_getikey#*@}"
            return 0
        else
            _farr_fatal "key unexpectedly unset (cookie ${__farr_scookie})"
        fi
    else
        return 1
    fi
}


#:
#: Try to get the value that is associated with a storage cookie and
#: store it into a variable,
#:
#: Use this for iteration over values.
#:
#: Comples values need to be released when they are not used any more
#: (`farray_release`, `falist_release`).
#:
#: Args:
#:   $1 (str): The name of the variable where to put the value into.
#:   $2 (str): The storage cookie.
#:
#: Returns:
#:   0 (truthy) on success,
#:   1 (falsy) if the given index is out of bounds.
#:
#: Exit:
#:   Other errors (missing array name, missing index value) are considered
#:   fatal and call `_farr_fatal` (i.e. `exit`).
#:
falist_tryget_value_at() {
    local __farr_value_varname __farr_scookie

    local __farr_token __farr_objname __farr_keyname __farr_valname \
          __farr_sptr __farr_sptr_prev __farr_sptr_next \
          __farr_getival

    __farr_value_varname=${1-}
    [ -z "${__farr_value_varname}" ] && _farr_fatal "missing variable name for value"
    _farr_alist_tryparse_cookie "${2-}" || return 1

    if [ "${__farr_sptr}" -ne 0 ] ; then
        eval __farr_getival=\"\$\{"${__farr_valname}"_"${__farr_sptr}"+SET\}\"
        if [ -n "${__farr_getival}" ]; then
            eval __farr_getival=\"\$\{"${__farr_valname}"_"${__farr_sptr}"\}\"
            _farr_acquire_object "${__farr_getival}"
            setvar "${__farr_value_varname}" "${__farr_getival}"
            return 0
        else
            _farr_fatal "value unexpectedly unset (cookie ${__farr_scookie})"
        fi
    else
        return 1
    fi
}


#:
#: Try to get the key-value item that is associated with a storage cookie and
#: store it into variables.
#:
#: Use this when iterating over key-value items.
#:
#: Comples values need to be released when they are not used any more
#: (`farray_release`, `falist_release`).
#:
#: Args:
#:   $1 (str): The name of the variable where to put the key into.
#:   $2 (str): The name of the variable where to put the value into.
#:   $3 (str): The storage cookie.
#:
#: Returns:
#:   0 (truthy) on success,
#:   1 (falsy) if the given cookie is out of bounds.
#:
#: Exit:
#:   Other errors (missing array name, missing index value) are considered
#:   fatal and call `_farr_fatal` (i.e. `exit`).
#:
falist_tryget_item_at() {
    local __farr_key_varname __farr_value_varname __farr_scookie

    local __farr_token __farr_objname __farr_keyname __farr_valname \
          __farr_sptr __farr_sptr_prev __farr_sptr_next \
          __farr_getikey __farr_getival

    __farr_key_varname=${1-}
    [ -z "${__farr_key_varname}" ] && _farr_fatal "missing variable name for key"
    __farr_value_varname=${2-}
    [ -z "${__farr_value_varname}" ] && _farr_fatal "missing variable name for value"
    _farr_alist_tryparse_cookie "${3-}" || return 1

    if [ "${__farr_sptr}" -ne 0 ] ; then
        eval __farr_getikey=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"+SET\}\"
        if [ -n "${__farr_getikey}" ]; then
            eval __farr_getival=\"\$\{"${__farr_valname}"_"${__farr_sptr}"+SET\}\"
            if [ -n "${__farr_getival}" ]; then
                eval __farr_getikey=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
                setvar "${__farr_key_varname}" "${__farr_getikey#*@}"
                eval __farr_getival=\"\$\{"${__farr_valname}"_"${__farr_sptr}"\}\"
                _farr_acquire_object "${__farr_getival}"
                setvar "${__farr_value_varname}" "${__farr_getival}"
                return 0
            else
                _farr_fatal "value unexpectedly unset (cookie ${__farr_scookie})"
            fi
        else
            _farr_fatal "key unexpectedly unset (cookie ${__farr_scookie})"
        fi
    else
        return 1
    fi
}


#:
#: Determine whether a key is found within the alist.
#:
#: Args:
#:   $1 (str): The name of an existing alist.
#:   $2: The key.
#:
#: Returns:
#:   0 (truthy) on success if the key is found,
#:   1 (falsy) if the given key is not found.
#:
falist_contains() {
    # __farr_name $1
    # __farr_key $2

    local __farr_name __farr_token __farr_objname __farr_bskeyname \
          __farr_keyname __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last

    _farr_alist_get_meta "${1-}"
    [ $# -lt 2 ] && _farr_fatal "missing key"

    _farr_alist_bsearch '' '' "${2}"
}


#:
#: Try to find the storage cookie of a given key in an alist.
#:
#: Args:
#:   $1 (str): The name of a variable where to put the found storage cookie
#:             into.
#:   $2 (str): The existing alist.
#:   $3: The key.
#:
#: Returns:
#:   0 (truthy) on success if the key is found,
#:   1 (falsy) if the given key is not found.
#:
falist_find() {
    local __farr_varname __farr_name __farr_key

    local __farr_token __farr_objname __farr_bskeyname __farr_keyname \
          __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_sptr __farr_find_key

    __farr_varname="${1-}"
    [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name"
    _farr_alist_get_meta "${2-}"
    [ $# -lt 3 ] && _farr_fatal "missing key"
    __farr_key="$3"


    if _farr_alist_bsearch '' __farr_sptr "${__farr_key}" ; then
        eval __farr_find_key=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
        setvar "${__farr_varname}" "${__farr_sptr}/${__farr_find_key%%@*}@${__farr_token}"
        return 0
    fi
    return 1     # not found
}


#:
#: Try to delete an item with a given key from the alist.
#:
#: Args:
#:   $1 (str): The name of the alist.
#:   $2: The key of the key-value pair to delete to
#:
#: Returns:
#:   int: 0 if the key has been found and is deleted,
#:        1 if the key has not been found.
#:
falist_trydel() {
    local __farr_name __farr_delkey

    local __farr_token __farr_objname __farr_bskeyname __farr_keyname \
          __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_sptr __farr_bsidx __farr_cur_value \
          __farr_cur_key __farr_cur_stype __farr_cur_prev __farr_cur_next \
          __farr_next_key __farr_next_prev __farr_next_next \
          __farr_prev_key __farr_prev_prev __farr_prev_next

    _farr_alist_get_meta "$@"
    [ $# -lt 2 ] && _farr_fatal "missing key"
    __farr_delkey="$2"

    _farr_alist_bsearch __farr_bsidx __farr_sptr "${__farr_delkey}" || return 1

    #
    # Remove from storage
    #

    #
    # Can release the value directly
    #
    eval __farr_cur_value=\"\$\{"${__farr_valname}"_"${__farr_sptr}"\}\"
    _farr_release_object "${__farr_cur_value}"
    eval unset "${__farr_valname}_${__farr_sptr}"

    #
    # Double-linked list: update all pointers (next, prev, first, last)
    # and at last remove the entry.
    #
    eval __farr_cur_key=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
    __farr_cur_prev="${__farr_cur_key%%@*}"
    __farr_cur_next="${__farr_cur_prev#*;}"
    __farr_cur_prev="${__farr_cur_prev%;*}"
    #__farr_cur_key="${__farr_cur_key#*@}"

    if [ "${__farr_cur_prev}" -ne 0 ]; then
        eval __farr_prev_key=\"\$\{"${__farr_keyname}"_"${__farr_cur_prev}"\}\"
        __farr_prev_prev="${__farr_prev_key%%@*}"
        #__farr_prev_next="${__farr_prev_prev#*;}"
        __farr_prev_prev="${__farr_prev_prev%;*}"
        __farr_prev_key="${__farr_prev_key#*@}"
        setvar "${__farr_keyname}_${__farr_cur_prev}" "${__farr_prev_prev};${__farr_cur_next}@${__farr_prev_key}"
    else
        # it is the first key
        __farr_sptr_first="${__farr_cur_next}"
    fi
    if [ "${__farr_cur_next}" -ne 0 ]; then
        eval __farr_next_key=\"\$\{"${__farr_keyname}"_"${__farr_cur_next}"\}\"
        __farr_next_prev="${__farr_next_key%%@*}"
        __farr_next_next="${__farr_next_prev#*;}"
        #__farr_next_prev="${__farr_next_prev%;*}"
        __farr_next_key="${__farr_next_key#*@}"
        setvar "${__farr_keyname}_${__farr_cur_next}" "${__farr_cur_prev};${__farr_next_next}@${__farr_next_key}"
    else
        # it is the last key
        __farr_sptr_last="${__farr_cur_prev}"
    fi

    eval unset "${__farr_keyname}_${__farr_sptr}"
    if [ "${__farr_cur_prev}" -eq 0 ] || [ "${__farr_cur_next}" -eq 0 ] ; then
        setvar "${__farr_objname}_P" "${__farr_sptr_first};${__farr_sptr_last}"
    fi

    #
    # Remove from binary search list
    #

    if [ "${__farr_bsidx}" -eq "${__farr_bslen}" ]; then
        # Can unset directly: no tombstone needed
        eval unset "${__farr_bskeyname}_${__farr_bslen}"
        # Decrement the physical length  --  persist it below
        __farr_bslen=$((__farr_bslen - 1))
        #
        # Because __farr_bsidx is the last item we clean up all
        # trailing tombstoned entries because `falist_add` relies on
        # this for proper key order checks: the last item may never be
        # a tombstone.
        #
        __farr_bsidx="${__farr_bslen}"
        while [ "${__farr_bsidx}" -ge 1 ]; do
            eval __farr_cur_key=\"\$\{"${__farr_bskeyname}"_"${__farr_bsidx}"\}\"
            __farr_cur_stype="${__farr_cur_key%%@*}"
            __farr_cur_stype="${__farr_cur_stype#*;}"
            [ "${__farr_cur_stype}" = 'V' ] && break
            # Just as above
            eval unset "${__farr_bskeyname}_${__farr_bsidx}"
            __farr_bslen=$((__farr_bslen - 1))
            __farr_bsidx=$((__farr_bsidx - 1))
        done
        # Persist the new reduced physical length
        setvar "${__farr_objname}_B" "${__farr_bslen}"
    else
        #
        # Can tombstone the binsearch list entry directly:
        # The storage pointer is not relevant any more and the key value
        # is exactly the one we have searched for.
        #
        setvar "${__farr_bskeyname}_${__farr_bsidx}" "0;D@${__farr_delkey}"
        # XXX TBD: compacting (criterion: difference between bslen and llen)
    fi

    # Decrement the logical length
    __farr_llen=$((__farr_llen - 1))
    setvar "${__farr_objname}__" "${__farr_llen}"
}


#:
#: Test the boolean truth of an alist.
#:
#: Args:
#:   $1 (str): The name of the alist.
#:
#: Returns:
#:   int: 0 (truthy) if the alist contains items,
#:        1 (falsy) otherwise (empty or not created/destroyed properly).
#:
falist_istrue() {
    # name $1

    local __farr_name __farr_token __farr_objname __farr_bskeyname \
          __farr_keyname __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last

    _farr_alist_tryget_meta "$@" || return 1
    if [ "${__farr_llen}" -gt 0 ]; then
        return 0
    else
        return 1
    fi
}


#:
#: Test whether two alists are equal.
#:
#: Two alists compare equal if and only if they have the same (key, value)
#: pairs (regardless of insertion order). Comparison is done using the shell's
#: builtin ``=`` test operator for both keys and values (i.e. lexicographic).
#:
#: Args:
#:   $1 (str): The name of the first alist
#:   $2 (str): The name of the second alist
#:
#: Returns:
#:   int: 0 if both input alists are equal, 1 otherwise
#:
falist_are_equal() {
    local __farr_name __farr_r_name

    local __farr_token __farr_objname __farr_bskeyname __farr_keyname \
          __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_r_token __farr_r_objname __farr_r_bskeyname __farr_r_keyname \
          __farr_r_valname __farr_r_llen __farr_r_bslen \
          __farr_r_sptr_first __farr_r_sptr_last \
          __farr_sptr __farr_r_sptr __farr_r_bsidx \
          __farr_value __farr_r_key __farr_r_value __farr_r_stype

    [ $# -ne 2 ] && _farr_fatal "missing alist parameter"

    _farr_alist_get_meta "$2"
    __farr_r_name="${__farr_name}"
    __farr_r_token="${__farr_token}"
    __farr_r_objname="${__farr_objname}"
    __farr_r_bskeyname="${__farr_bskeyname}"
    __farr_r_keyname="${__farr_keyname}"
    __farr_r_valname="${__farr_valname}"
    __farr_r_llen="${__farr_llen}"
    __farr_r_bslen="${__farr_bslen}"
    __farr_r_sptr_first="${__farr_sptr_first}"
    __farr_r_sptr_last="${__farr_sptr_last}"
    _farr_alist_get_meta "$1"

    [ "${__farr_llen}" -ne "${__farr_r_llen}" ] && return 1

    __farr_r_bsidx=1
    while [ "${__farr_r_bsidx}" -le "${__farr_r_bslen}" ]; do
        eval __farr_r_key=\"\$\{"${__farr_r_bskeyname}"_"${__farr_r_bsidx}"\}\"
        __farr_r_stype="${__farr_r_key%%@*}"
        __farr_r_sptr="${__farr_r_stype%;*}"
        __farr_r_stype="${__farr_r_stype#*;}"
        # Skip tombstones
        if [ "${__farr_r_stype}" = 'V' ]; then
            _farr_alist_bsearch '' __farr_sptr "${__farr_r_key#*@}" || return 1
            # Key comparison is already done by `_farr_alist_bsearch`
            # Just compare the values
            eval __farr_value=\"\$\{"${__farr_valname}"_"${__farr_sptr}"\}\"
            eval __farr_r_value=\"\$\{"${__farr_r_valname}"_"${__farr_r_sptr}"\}\"
            [ "${__farr_value}" != "${__farr_r_value}" ] && return 1
        fi
        __farr_r_bsidx=$((__farr_r_bsidx + 1))
    done
    return 0
}


#:
#: Test whether two alists are equal respecting the (insertion) order.
#:
#: Two alists compare equal if and only if they have the same (key, value)
#: pairs **with** regard of insertion ordering. Comparison is done using the
#: shell's builtin ``=`` test operator for both keys and values
#: (i.e. lexicographic).
#:
#: Args:
#:   $1 (str): The first alist.
#:   $2 (str): The second alist.
#:
#: Returns:
#:   int: 0 if both input alists are equal, 1 otherwise
#:
falist_are_equal_with_order() {
    local __farr_name __farr_r_name

    local __farr_token __farr_objname __farr_bskeyname __farr_keyname \
          __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_r_token __farr_r_objname __farr_r_bskeyname __farr_r_keyname \
          __farr_r_valname __farr_r_llen __farr_r_bslen \
          __farr_r_sptr_first __farr_r_sptr_last \
          __farr_sptr __farr_sptr_next __farr_r_sptr __farr_r_sptr_next \
          __farr_key __farr_value \
          __farr_r_key __farr_r_value

    [ $# -ne 2 ] && _farr_fatal "missing alist parameter"

    _farr_alist_get_meta "$2"
    __farr_r_name="${__farr_name}"
    __farr_r_token="${__farr_token}"
    __farr_r_objname="${__farr_objname}"
    __farr_r_bskeyname="${__farr_bskeyname}"
    __farr_r_keyname="${__farr_keyname}"
    __farr_r_valname="${__farr_valname}"
    __farr_r_llen="${__farr_llen}"
    __farr_r_bslen="${__farr_bslen}"
    __farr_r_sptr_first="${__farr_sptr_first}"
    __farr_r_sptr_last="${__farr_sptr_last}"
    _farr_alist_get_meta "$1"

    [ "${__farr_llen}" -ne "${__farr_r_llen}" ] && return 1

    __farr_sptr="${__farr_sptr_first}"
    __farr_r_sptr="${__farr_r_sptr_first}"
    while [ "${__farr_sptr}" -ne 0 ] && [ "${__farr_r_sptr}" -ne 0 ] ; do
        # Compare the keys ...
        eval __farr_key=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
        eval __farr_r_key=\"\$\{"${__farr_r_keyname}"_"${__farr_r_sptr}"\}\"
        [ "${__farr_key#*@}" != "${__farr_r_key#*@}" ] && return 1
        # ... and the values
        eval __farr_value=\"\$\{"${__farr_valname}"_"${__farr_sptr}"\}\"
        eval __farr_r_value=\"\$\{"${__farr_r_valname}"_"${__farr_r_sptr}"\}\"
        [ "${__farr_value}" != "${__farr_r_value}" ] && return 1

        # Now prepare for moving to next items
        __farr_sptr_next="${__farr_key%%@*}"
        __farr_sptr_next="${__farr_sptr_next#*;}"
        __farr_r_sptr_next="${__farr_r_key%%@*}"
        __farr_r_sptr_next="${__farr_r_sptr_next#*;}"

        __farr_sptr="${__farr_sptr_next}"
        __farr_r_sptr="${__farr_r_sptr_next}"
    done
    # Check consistency with llen
    if [ "${__farr_sptr}" -ne 0 ] || [ "${__farr_r_sptr}" -ne 0 ] ; then
        _farr_fatal "inconsistency of storage with logical length detected"
    fi
    return 0
}


#:
#: Get all keys from the alist and put it into an array.
#:
#: Args:
#:   $1 (str): The name of the target array where the keys are appended to.
#:   $2 (str): The name of the alist from where to get the keys.
#:
#: The keys are appended to `$1` in insertion order.
#:
falist_keys() {
    local __farr_l_result __farr_name

    local __farr_l_name __farr_l_token __farr_l_gvrname __farr_l_len \
          __farr_token __farr_gvrname __farr_objname \
          __farr_bskeyname __farr_keyname __farr_valname \
          __farr_len __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_sptr __farr_key __farr_sptr_next

    # Try to get the array metadata here to provide an early error message
    [ $# -lt 1 ] && _ferr_fatal "missing target array"
    _farr_array_get_meta "$1"
    __farr_l_result="$1"
    __farr_l_name="${__farr_name}"
    __farr_l_token="${__farr_token}"
    __farr_l_gvrname="${__farr_gvrname}"
    __farr_l_len="${__farr_len}"
    [ $# -lt 2 ] && _farr_fatal "missing alist"
    _farr_alist_get_meta "$2"    # and use the standard names here

    __farr_sptr="${__farr_sptr_first}"
    while [ "${__farr_sptr}" -ne 0 ]; do
        eval __farr_key=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
        __farr_sptr_next="${__farr_key%%@*}"
        __farr_sptr_next="${__farr_sptr_next#*;}"
        farray_append "${__farr_l_result}" "${__farr_key#*@}"
        __farr_sptr="${__farr_sptr_next}"
    done
    return 0
}


#:
#: Get all values from the alist and put it into an array.
#:
#: Args:
#:   $1 (str): The name of the target array where values are appended to.
#:   $2 (str): The name of the alist from where to get the values.
#:
#: The values are appended to `$1` in insertion order.
#:
falist_values() {
    local __farr_l_result __farr_name

    local __farr_l_name __farr_l_token __farr_l_gvrname __farr_l_len \
          __farr_token __farr_gvrname __farr_objname \
          __farr_bskeyname __farr_keyname __farr_valname \
          __farr_len __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_sptr __farr_key __farr_val __farr_sptr_next

    # Try to get the array metadata here to provide an early error message
    [ $# -lt 1 ] && _ferr_fatal "missing target array"
    _farr_array_get_meta "$1"
    __farr_l_result="$1"
    __farr_l_name="${__farr_name}"
    __farr_l_token="${__farr_token}"
    __farr_l_gvrname="${__farr_gvrname}"
    __farr_l_len="${__farr_len}"
    [ $# -lt 2 ] && _farr_fatal "missing alist"
    _farr_alist_get_meta "$2"    # and use the standard names here

    __farr_sptr="${__farr_sptr_first}"
    while [ "${__farr_sptr}" -ne 0 ]; do
        eval __farr_key=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
        __farr_sptr_next="${__farr_key%%@*}"
        __farr_sptr_next="${__farr_sptr_next#*;}"
        eval __farr_val=\"\$\{"${__farr_valname}"_"${__farr_sptr}"\}\"
        farray_append "${__farr_l_result}" "${__farr_val}"
        __farr_sptr="${__farr_sptr_next}"
    done
    return 0
}


#:
#: Get all items (key-value pairs) from the alist and put it into an array.
#:
#: Args:
#:   $1 (str): The name of the target array where the sequence of
#:             key-value pairs are to be appended to.
#:   $2 (str): The name of the alist from where to get the items.
#:
#: The items are appended to `$1` in insertion order.
#:
falist_items() {
    local __farr_l_result __farr_name

    local __farr_l_name __farr_l_token __farr_l_gvrname __farr_l_len \
          __farr_token __farr_gvrname __farr_objname \
          __farr_bskeyname __farr_keyname __farr_valname \
          __farr_len __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_sptr __farr_key __farr_val __farr_sptr_next

    # Try to get the array metadata here to provide an early error message
    [ $# -lt 1 ] && _ferr_fatal "missing target array"
    _farr_array_get_meta "$1"
    __farr_l_result="$1"
    __farr_l_name="${__farr_name}"
    __farr_l_token="${__farr_token}"
    __farr_l_gvrname="${__farr_gvrname}"
    __farr_l_len="${__farr_len}"
    [ $# -lt 2 ] && _farr_fatal "missing alist"
    _farr_alist_get_meta "$2"    # and use the standard names here

    __farr_sptr="${__farr_sptr_first}"
    while [ "${__farr_sptr}" -ne 0 ]; do
        eval __farr_key=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
        __farr_sptr_next="${__farr_key%%@*}"
        __farr_sptr_next="${__farr_sptr_next#*;}"
        eval __farr_val=\"\$\{"${__farr_valname}"_"${__farr_sptr}"\}\"
        farray_append "${__farr_l_result}" "${__farr_key#*@}" "${__farr_val}"
        __farr_sptr="${__farr_sptr_next}"
    done
    return 0
}


#:
#: Call a function for every key-value pair in an alist in insertion order.
#:
#: The given callback function will called with at least four arguments:
#:
#: - the alist name
#: - the element key at the current position (storage cookie)
#: - the element value at the current position (storage cookie)
#: - the corresponding storage cookie
#: - all the extra arguments (`$3`, `$4`, ...) given as arguments are
#:   forwarded also
#:
#: The iteration stops if the called function returns a falsy value.
#:
#: Args:
#:   $1 (str): The name of an existing array.
#:   $2 (str): The name of a function to be called with four arguments.
#:   $3... (optional): Extra arguments forwared to `$2` also
#:
#: Warning:
#:   If the number of elements changes while being in `falist_for_each` then
#:   the behaviour is undefined.
#:   The current implementation determines the length of the alist once
#:   at the start of execution.
#:
falist_for_each() {
    local __farr_name __farr_callback

    local __farr_token __farr_objname __farr_bskeyname __farr_keyname \
          __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_fesptr __farr_fesptr_next __farr_fescookie \
          __farr_fekey __farr_feval __farr_rv \
          __farr_gm_name_or_value

    __farr_gm_name_or_value="${1-}"
    _farr_alist_get_meta "${__farr_gm_name_or_value}"
    __farr_callback="${2-}"
    [ -z "${__farr_callback}" ] && _farr_fatal "missing callback function name"

    shift 2

    __farr_fesptr="${__farr_sptr_first}"
    while [ "${__farr_fesptr}" -ne 0 ]; do
        eval __farr_fekey=\"\$\{"${__farr_keyname}"_"${__farr_fesptr}"\}\"
        __farr_fesptr_next="${__farr_fekey%%@*}"
        # Note that __farr_fesptr_next contains <pref>;<next> here
        __farr_fescookie="${__farr_fesptr}/${__farr_fesptr_next}@${__farr_token}"
        __farr_fesptr_next="${__farr_fesptr_next#*;}"
        __farr_fekey="${__farr_fekey#*@}"
        eval __farr_feval=\"\$\{"${__farr_valname}"_"${__farr_fesptr}"\}\"
        _farr_acquire_object "${__farr_feval}"
        eval "${__farr_callback} \"\${__farr_name:-\"\${__farr_gm_name_or_value}\"}\" \"\${__farr_fekey}\" \"\${__farr_feval}\" \"\${__farr_fescookie}\" \"\$@\""
        __farr_rv=$?
        _farr_release_object "${__farr_feval}"
        [ ${__farr_rv} -ne 0 ] && return ${__farr_rv}
        __farr_fesptr="${__farr_fesptr_next}"
    done
    return 0
}


#:
#: Print the contents of an alist to stderr.
#:
#: Args:
#:   $1 (str): The name of an alist. The array may exist or not.
#:
#: Returns:
#:   0
#:
falist_debug() {
    _farr_alist_debug '' "$@"
}


#:
#: Internal implementation of `falist_debug`.
#:
#: Args:
#:   $1 (str): The indent
#:   $2 (str): The name or the complete prefixed token of an alist.
#:
#: Returns:
#:   0
#:
_farr_alist_debug() {
    local __farr_debug_indent
    # __farr_name $1

    local __farr_name __farr_token __farr_objname __farr_bskeyname \
          __farr_keyname __farr_valname __farr_llen __farr_bslen \
          __farr_sptr_first __farr_sptr_last \
          __farr_sptr __farr_el_key __farr_el_val \
          __farr_sptr_next \
          __farr_debug_bsidx __farr_debug_sptr

    __farr_debug_indent="${1}"
    shift
    if ! _farr_alist_tryget_meta "$@"; then
        printf "%sDEBUG: no (meta-)data for falist \`%s'\\n" "${__farr_debug_indent}" "${1-}" 1>&2
        return 0
    fi

    if [ -n "${__farr_name}" ]; then
        printf "%sDEBUG: alist \`%s' has length %s\\n" "${__farr_debug_indent}" "${__farr_name}" "${__farr_llen}" 1>&2
    else
        printf "%sDEBUG: alist with token \`%s' has length %s\\n" "${__farr_debug_indent}" "${__farr_token}" "${__farr_llen}" 1>&2
    fi
    if [ "${__farr_llen}" -gt 0 ]; then
        printf '%sDEBUG:   the items:\n' "${__farr_debug_indent}" 1>&2
    fi
    __farr_sptr="${__farr_sptr_first}"
    while [ "${__farr_sptr}" -ne 0 ]; do
        eval __farr_el_key=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\"
        __farr_sptr_next="${__farr_el_key%%@*}"
        __farr_sptr_next="${__farr_sptr_next#*;}"
        __farr_el_key="${__farr_el_key#*@}"
        # Some internal consistency checks with respect to the sptr values
        if _farr_alist_bsearch __farr_debug_bsidx __farr_debug_sptr "${__farr_el_key}" ; then
            if [ "${__farr_sptr}" != "${__farr_debug_sptr}" ]; then
                printf "%sDEBUG:     WARNING: SPTR INCONSISTENCY FOR KEY \`%s': STOR: %s - BS: %s - BSIDX: %s\\n" "${__farr_debug_indent}" "${__farr_el_key}" "${__farr_sptr}" "${__farr_debug_sptr}" "${__farr_debug_bsidx}" 1>&2
            fi
        else
            printf "%sDEBUG:     WARNING: KEY \`%s' NOT FOUND IN BINARY SEARCH LIST\\n" "${__farr_debug_indent}" "${__farr_el_key}" 1>&2
        fi
        eval __farr_el_val=\"\$\{"${__farr_valname}"_"${__farr_sptr}"\}\"
        case "${__farr_el_val}" in
            "${_farr_array_token_prefix}"*)
                printf "%sDEBUG:     \`%s' -> >>>\\n" "${__farr_debug_indent}" "${__farr_el_key}" 1>&2
                _farr_array_debug "${__farr_debug_indent}    " "${__farr_el_val}"
                ;;
            "${_farr_alist_token_prefix}"*)
                printf "%sDEBUG:     \`%s' -> >>>\\n" "${__farr_debug_indent}" "${__farr_el_key}" 1>&2
                _farr_alist_debug "${__farr_debug_indent}    " "${__farr_el_val}"
                ;;
            *)
                printf "%sDEBUG:     \`%s' -> \`%s'\\n" "${__farr_debug_indent}" "${__farr_el_key}" "${__farr_el_val}" 1>&2
                ;;
        esac
        __farr_sptr="${__farr_sptr_next}"
    done
    return 0
}


#:
#: Acquire any object.
#:
#: If an object represents an array or alist its reference count will be
#: increased.
#:
#: Args:
#:   $1: The object's value
#:
#: Returns:
#:   int: 0 if the incrementation went properly, 1 otherwise
#:
_farr_acquire_object() {
    # $1

    local __farr_tmp_refcount __farr_tmp_token

    case "$1" in
        '')
            return 0
            ;;
        "${_farr_array_token_prefix}"*)
            __farr_tmp_token="${1#"${_farr_array_token_prefix}"}"
            eval __farr_tmp_refcount=\"\$\{"${_farr_array_prefix}""${__farr_tmp_token}"_C:+SET\}\"
            [ -z "${__farr_tmp_refcount}" ] && return 1
            eval __farr_tmp_refcount=\"\$\{"${_farr_array_prefix}""${__farr_tmp_token}"_C\}\"
            __farr_tmp_refcount=$((__farr_tmp_refcount + 1))
            setvar "${_farr_array_prefix}${__farr_tmp_token}_C" "${__farr_tmp_refcount}"
            return 0
            ;;
        "${_farr_alist_token_prefix}"*)
            __farr_tmp_token="${1#"${_farr_alist_token_prefix}"}"
            eval __farr_tmp_refcount=\"\$\{"${_farr_alist_prefix}""${__farr_tmp_token}"_C:+SET\}\"
            [ -z "${__farr_tmp_refcount}" ] && return 1
            eval __farr_tmp_refcount=\"\$\{"${_farr_alist_prefix}""${__farr_tmp_token}"_C\}\"
            __farr_tmp_refcount=$((__farr_tmp_refcount + 1))
            setvar "${_farr_alist_prefix}${__farr_tmp_token}_C" "${__farr_tmp_refcount}"
            return 0
            ;;
        *)
            return 0
            ;;
    esac
}


#:
#: Release any object.
#:
#: If an object represents an array or alist its reference count will be
#: decreased properly.
#:
#: Args:
#:   $1: The object's value
#:
#: Returns:
#:   int: 0 if the destruction went properly without errors, 1 otherwise
#:
_farr_release_object() {
    # $1

    case "$1" in
        '')
            return 0
            ;;
        "${_farr_array_token_prefix}"*)
            farray_release "$1"
            # let the return value pass through
            ;;
        "${_farr_alist_token_prefix}"*)
            falist_release "$1"
            # let the return value pass through
            ;;
        *)
            return 0
            ;;
    esac
}