Mercurial > hgrepos > FreeBSD > ports > sysutils > local-bsdtools
changeset 756:33df05108ba1
farray.sh: New implementation alists: searching is done using a binary search now while preserving insertion order.
The implementation uses two key lists:
The first one is sorted and is used for searching using binary search.
The second is a double-linked list and is used for remembering the
insertion order.
| author | Franz Glasner <fzglas.hg@dom66.de> |
|---|---|
| date | Sat, 19 Oct 2024 22:40:11 +0200 |
| parents | f6d296c5868e |
| children | a339666cb421 |
| files | .shellcheckrc share/local-bsdtools/farray.sh tests/farray-alist.t tests/testsetup.sh |
| diffstat | 4 files changed, 2095 insertions(+), 1127 deletions(-) [+] |
line wrap: on
line diff
--- a/.shellcheckrc Fri Oct 18 14:02:18 2024 +0200 +++ b/.shellcheckrc Sat Oct 19 22:40:11 2024 +0200 @@ -25,5 +25,7 @@ disable=SC3012 # In POSIX sh, local is undefined disable=SC3043 +# ;& is non-standard +disable=SC2127 enable=avoid-nullary-conditions
--- a/share/local-bsdtools/farray.sh Fri Oct 18 14:02:18 2024 +0200 +++ b/share/local-bsdtools/farray.sh Sat Oct 19 22:40:11 2024 +0200 @@ -2,7 +2,7 @@ # -*- indent-tabs-mode: nil; -*- #: #: A simple library to emulate simple arrays (one-dimensional) and alists -#: in a POSIX shell. +#: in FreeBSD's POSIX shell :command:`/bin/sh`. #: #: :Author: Franz Glasner #: :Copyright: (c) 2024 Franz Glasner. @@ -94,16 +94,21 @@ #: 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[?]:' +_farr_array_token_prefix='_farr_A[?]:' # token value prefix _farr_array_prefix=_farr_A_ -_farr_alist_token_prefix='_farr_KV[?,?]:' -_farr_alist_prefix=_farr_KV_ -_farr_alist_key_prefix=_farr_K_ -_farr_alist_value_prefix=_farr_V_ +_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 #: @@ -169,6 +174,60 @@ #: +#: 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;; + *[!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. #: @@ -1926,7 +1985,8 @@ falist_create() { local __farr_name - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len + local __farr_token __farr_objname __farr_bskeyname __farr_keyname __farr_valname + local __farr_llen __farr_name="${1-}" [ -z "${__farr_name}" ] && _farr_fatal "missing falist name" @@ -1936,20 +1996,29 @@ __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_len=\$\{${__farr_objname}__+SET\} - [ -n "${__farr_len}" ] && _farr_fatal "falist \`${__farr_name}' already exists: existing token \`${__farr_token}'" - - # Really create the storage by initializing its length ... - eval ${__farr_objname}__=0 - # ... and its reference count - eval ${__farr_objname}_C=1 - - # And associate the token with the array name - eval "${__farr_name}=\"\${_farr_alist_token_prefix}\${__farr_token}\"" + 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. @@ -1973,31 +2042,35 @@ #: 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_len (int): The length of the alist. +#: __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() { - local __farr_gm_name_or_value - - local __farr_tmp_refcount - - __farr_gm_name_or_value="${1-}" - case "${__farr_gm_name_or_value}" in + # __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="${__farr_gm_name_or_value#"${_farr_alist_token_prefix}"}" + __farr_token="${1#"${_farr_alist_token_prefix}"}" ;; *) # A variable name: go through one indirection - __farr_name="${__farr_gm_name_or_value}" + __farr_name="${1}" eval __farr_token=\"\$\{"${__farr_name}"-\}\" case "${__farr_token}" in '') @@ -2015,14 +2088,21 @@ esac __farr_objname="${_farr_alist_prefix}${__farr_token}" - __farr_keyname=${_farr_alist_key_prefix}${__farr_token} - __farr_valname=${_farr_alist_value_prefix}${__farr_token} - - eval __farr_len=\$\{${__farr_objname}__:+SET\} - [ -z "${__farr_len}" ] && _farr_fatal "falist \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no object for token \`${__farr_token}'" - eval __farr_tmp_refcount=\$\{${__farr_objname}_C:+SET\} - [ -z "${__farr_tmp_refcount}" ] && _farr_fatal "falist \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no refcnt for token \`${__farr_token}'" - eval __farr_len="\${${__farr_objname}__}" + __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 } @@ -2039,20 +2119,24 @@ #: __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_len (int): The length of the alist. +#: __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() { - local __farr_gm_name_or_value - - local __farr_tmp_refcount - - __farr_gm_name_or_value="${1-}" - case "${__farr_gm_name_or_value}" in + # __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 @@ -2060,11 +2144,11 @@ "${_farr_alist_token_prefix}"*) # A prefixed token value __farr_name='' - __farr_token="${__farr_gm_name_or_value#"${_farr_alist_token_prefix}"}" + __farr_token="${1#"${_farr_alist_token_prefix}"}" ;; *) # A variable name: go through one indirection - __farr_name="${__farr_gm_name_or_value}" + __farr_name="${1}" eval __farr_token=\"\$\{"${__farr_name}"-\}\" case "${__farr_token}" in '') @@ -2084,41 +2168,120 @@ esac __farr_objname="${_farr_alist_prefix}${__farr_token}" - __farr_keyname=${_farr_alist_key_prefix}${__farr_token} - __farr_valname=${_farr_alist_value_prefix}${__farr_token} - - eval __farr_len=\$\{${__farr_objname}__:+SET\} - if [ -z "${__farr_len}" ] ; then - _farr_err "falist \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no object for token \`${__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 - eval __farr_tmp_refcount=\$\{${__farr_objname}_C:+SET\} - if [ -z "${__farr_tmp_refcount}" ] ; then - _farr_err "falist \`${__farr_name:-"${__farr_gm_name_or_value}"}' not created properly: no refcnt 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 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 - eval __farr_len="\${${__farr_objname}__}" + __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 length of an alist and put it into a variable. +#: 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() { - local __farr_varname __farr_name - - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - - __farr_varname="${1-}" - [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name" - shift - _farr_alist_get_meta "$@" - eval "${__farr_varname}"=${__farr_len} + # __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}" } @@ -2136,9 +2299,11 @@ #: 0 (truthy) #: falist_print_length() { - local __farr_vn - - ( falist_length __farr_vn "$@" && printf "%s" "${__farr_vn}"; ) \ + # $1 + + local __farr_vn_pl + + ( falist_length __farr_vn_pl "$@" && printf "%s" "${__farr_vn_pl}"; ) \ || printf "%s" "-1" } @@ -2150,28 +2315,40 @@ #: $1 (str): The name of the existing alist. #: falist_clear() { - local __farr_name - - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_idx __farr_del_value + # __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 + local __farr_bsidx __farr_sptr __farr_sptr_next __farr_del_value __farr_del_key _farr_alist_get_meta "$@" - # Remove "storage" - __farr_idx=1 - while [ ${__farr_idx} -le ${__farr_len} ]; do - eval __farr_del_value=\"\$\{${__farr_valname}_${__farr_idx}\}\" + # 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}" - # XXX FIXME: no arrays/alists as keys: should we check this - #eval __farr_del_value=\"\$\{${__farr_keyname}_${__farr_idx}\}\" - #_farr_release_object "${__farr_del_value}" - eval unset ${__farr_valname}_${__farr_idx} - eval unset ${__farr_keyname}_${__farr_idx} - __farr_idx=$((__farr_idx + 1)) + 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 - eval ${__farr_objname}__=0 + 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 } @@ -2192,8 +2369,9 @@ falist_release() { local __farr_name - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_idx __farr_del_value + local __farr_token __farr_objname __farr_bskeyname __farr_keyname __farr_valname __farr_llen __farr_bslen __farr_sptr_first __farr_sptr_last + local __farr_sptr __farr_del_value __farr_del_key + local __farr_sptr_next __farr_bsidx local __farr_refcnt _farr_alist_tryget_meta "$@" || return 1 @@ -2203,34 +2381,202 @@ # Note that the existence of the reference count proper is already # checked by `_farr_alist_tryget_meta`. # - eval __farr_refcnt=\$\{${__farr_objname}_C\} + eval __farr_refcnt=\"\$\{"${__farr_objname}"_C\}\" __farr_refcnt=$((__farr_refcnt - 1)) - eval ${__farr_objname}_C=\$\{__farr_refcnt\} + setvar "${__farr_objname}_C" "${__farr_refcnt}" if [ "${__farr_refcnt}" -ne 0 ] ; then # Clean out the alist name from the token always - [ -n "${__farr_name}" ] && eval "${__farr_name}=''" + [ -n "${__farr_name}" ] && setvar "${__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_valname}_${__farr_idx}\}\" + __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}" - # XXX FIXME: no arrays/alists as keys: should we check this - #eval __farr_del_value=\"\$\{${__farr_keyname}_${__farr_idx}\}\" - #_farr_release_object "${__farr_del_value}" - eval unset ${__farr_valname}_${__farr_idx} - eval unset ${__farr_keyname}_${__farr_idx} - __farr_idx=$((__farr_idx + 1)) + 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}__ + eval unset "${__farr_objname}__" # ... and its reference count - eval unset ${__farr_objname}_C + 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}" ] && eval "${__farr_name}=''" + [ -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 + local __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 + local __farr_searched_value + + local __farr_lo __farr_hi __farr_mid __farr_mid_value + local __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 } @@ -2248,13 +2594,15 @@ #: or if an internal inconsistency will be detected. #: falist_set() { - local __farr_name __farr_key __farr_value - - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_idx __farr_elkey - local __farr_old_value - - _farr_alist_get_meta "$@" + # __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 + local __farr_bsidx __farr_tmp_bsidx + local __farr_tmp_value __farr_tmp_key __farr_prev_key + local __farr_stype __farr_sptr __farr_prev_sptr __farr_tmp_prev_sptr + + _farr_alist_get_meta "${1-}" shift while [ $# -ne 0 ]; do @@ -2263,35 +2611,116 @@ [ $# -lt 2 ] && _farr_fatal "missing value" __farr_value="$2" - __farr_idx=1 - while [ ${__farr_idx} -le ${__farr_len} ]; do - eval __farr_elkey=\"\$\{${__farr_keyname}_${__farr_idx}+SET\}\" - if [ -n "${__farr_elkey}" ]; then - eval __farr_elkey=\"\$\{${__farr_keyname}_${__farr_idx}\}\" - if [ "${__farr_elkey}" = "${__farr_key}" ]; then - eval __farr_old_value=\"\$\{${__farr_valname}_${__farr_idx}\}\" - _farr_release_object "${__farr_old_value}" - _farr_acquire_object "${__farr_value}" - eval ${__farr_valname}_${__farr_idx}=\"\$\{__farr_value\}\" - return 0 + _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 - else - _farr_fatal "key unexpectedly unset (index ${__farr_idx})" - fi - __farr_idx=$((__farr_idx + 1)) - done - # - # Not yet found: "append" ... - # - # NOTE: __farr_idx here already is the new correct length - # - __farr_len=${__farr_idx} - # ... the key/value pairs to storage - eval ${__farr_keyname}_${__farr_len}=\"\$\{__farr_key\}\" - _farr_acquire_object "${__farr_value}" - eval ${__farr_valname}_${__farr_len}=\"\$\{__farr_value\}\" - # ... the new length to the storage - eval ${__farr_objname}__=${__farr_len} + __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_tmp_key=\"\$\{"${__farr_bskeyname}"_"${__farr_tmp_bsidx}"\}\" + setvar "${__farr_bskeyname}_$((__farr_tmp_bsidx + 1))" "${__farr_tmp_key}" + __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 @@ -2312,11 +2741,13 @@ #: or if an internal inconsistency will be detected. #: falist_add() { - local __farr_name __farr_key __farr_value - - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - - _farr_alist_get_meta "$@" + # __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 + local __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 @@ -2328,13 +2759,49 @@ # # We do just append ... # - __farr_len=$((__farr_len + 1)) - # ... the key/value pairs to storage - eval ${__farr_keyname}_${__farr_len}=\"\$\{__farr_key\}\" + + # + # 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}" - eval ${__farr_valname}_${__farr_len}=\"\$\{__farr_value\}\" - # ... the new length to the storage - eval ${__farr_objname}__=${__farr_len} + 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 @@ -2359,12 +2826,15 @@ #: or if an internal inconsistency will be detected. #: falist_set_unique() { - local __farr_name __farr_key __farr_value - - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_idx __farr_elkey - - _farr_alist_get_meta "$@" + # __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 + local __farr_bsidx __farr_tmp_bsidx + local __farr_tmp_value __farr_tmp_key __farr_prev_key + local __farr_stype __farr_sptr __farr_prev_sptr __farr_tmp_prev_sptr + + _farr_alist_get_meta "${1-}" shift while [ $# -ne 0 ]; do @@ -2373,32 +2843,112 @@ [ $# -lt 2 ] && _farr_fatal "missing value" __farr_value="$2" - __farr_idx=1 - while [ ${__farr_idx} -le ${__farr_len} ]; do - eval __farr_elkey=\"\$\{${__farr_keyname}_${__farr_idx}+SET\}\" - if [ -n "${__farr_elkey}" ]; then - eval __farr_elkey=\"\$\{${__farr_keyname}_${__farr_idx}\}\" - if [ "${__farr_elkey}" = "${__farr_key}" ]; then - # key is already set: would be non-unique - return 1 + _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 - else - _farr_fatal "key unexpectedly unset (index ${__farr_idx})" - fi - __farr_idx=$((__farr_idx + 1)) - done - # - # Not yet found: "append" .. - # - # NOTE: __farr_idx here already is the new correct length - # - __farr_len=${__farr_idx} - # ... the key/value pairs to storage - eval ${__farr_keyname}_${__farr_len}=\"\$\{__farr_key\}\" - _farr_acquire_object "${__farr_value}" - eval ${__farr_valname}_${__farr_len}=\"\$\{__farr_value\}\" - # ... the new length - eval ${__farr_objname}__=${__farr_len} + __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_tmp_key=\"\$\{"${__farr_bskeyname}"_"${__farr_tmp_bsidx}"\}\" + setvar "${__farr_bskeyname}_$((__farr_tmp_bsidx + 1))" "${__farr_tmp_key}" + __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 @@ -2408,157 +2958,159 @@ #: #: Update an alist from another alist. #: -#: Key-values from the other alist are given precedence. +#: 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 name of the alist that is to be updated. -#: $2 (str): The name of the other alist. +#: $1 (str): The ("left") alist that is to be updated from `$2`. +#: $2 (str): The ("right") alist #: falist_update() { - - local __farr_l_name __farr_r_name - - local __farr_l_token __farr_l_objname __farr_l_keyname __farr_l_valname __farr_l_len - local __farr_r_token __farr_r_objname __farr_r_keyname __farr_r_valname __farr_r_len - - local __farr_name __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_l_idx __farr_r_idx __farr_r_key __farr_l_key __farr_value + 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 + local __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 + local __farr_bsidx __farr_stype __farr_sptr __farr_tmp_bsidx + local __farr_key __farr_value + local __farr_r_key __farr_r_sptr __farr_r_sptr_next __farr_r_value + local __farr_prev_sptr __farr_prev_key + local __farr_tmp_prev_sptr [ $# -ne 2 ] && _farr_fatal "exactly two arrays must be given" - _farr_alist_get_meta "$1" - __farr_l_name="${__farr_name}" - __farr_l_token="${__farr_token}" - __farr_l_objname="${__farr_objname}" - __farr_l_keyname="${__farr_keyname}" - __farr_l_valname="${__farr_valname}" - __farr_l_len="${__farr_len}" _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_len="${__farr_len}" - - __farr_r_idx=1 - while [ ${__farr_r_idx} -le ${__farr_r_len} ]; do - eval __farr_r_key=\"\$\{${__farr_r_keyname}_${__farr_r_idx}\}\" - - __farr_l_idx=1 - while [ ${__farr_l_idx} -le ${__farr_l_len} ]; do - eval __farr_l_key=\"\$\{${__farr_l_keyname}_${__farr_l_idx}\}\" - if [ "${__farr_l_key}" = "${__farr_r_key}" ]; then - eval __farr_value=\"\$\{${__farr_r_valname}_${__farr_r_idx}\}\" - _farr_acquire_object "${__farr_value}" - eval ${__farr_l_valname}_${__farr_l_idx}=\"\$\{__farr_value\}\" - break - fi - __farr_l_idx=$((__farr_l_idx + 1)) - done - # - # If __farr_l_idx > __farr_l_len: Not yet found: "append" .. - # - # NOTE: __farr_l_idx is here also the new correct length - # - if [ ${__farr_l_idx} -eq $((__farr_l_len + 1)) ]; then - # ... the key/value pairs to storage - eval ${__farr_l_keyname}_${__farr_l_idx}=\"\$\{__farr_r_key\}\" - eval __farr_value=\"\$\{${__farr_r_valname}_${__farr_r_idx}\}\" - _farr_acquire_object "${__farr_value}" - eval ${__farr_l_valname}_${__farr_l_idx}=\"\$\{__farr_value\}\" - # ... the new length in storage - eval ${__farr_l_objname}__=${__farr_l_idx} - # ... and temporary here - __farr_l_len=${__farr_l_idx} - fi - __farr_r_idx=$((__farr_r_idx + 1)) - done - return 0 -} - - -#: -#: Merge two *sorted* alists using the mergesort algorithm. -#: -#: A "sorted" alist is an alist where all the key-value pairs are added -#: in a sorted fashion: `falist_keys()` yields a lexicographcally sorted -#: array. -#: -#: Sources: - https://de.wikipedia.org/wiki/Mergesort -#: - https://en.wikipedia.org/wiki/Merge_sort -#: -#: Args: -#: $1 (str): The result alist where all the sorted items will be added to -#: using `falist_add` -#: $2 (str): The first sorted input alist -#: $3 (str): The second sorted input alist -#: -falist_merge() { - local __farr_result __farr_input_1 __farr_input_2 - - local __farr_name __farr_token __farr_objname __farr_valname __farr_keyname __farr_len - local __farr_name_1 __farr_token_1 __farr_objname_1 __farr_valname_1 __farr_keyname_1 __farr_len_1 - local __farr_name_2 __farr_token_2 __farr_objname_2 __farr_valname_2 __farr_keyname_2 __farr_len_2 - local __farr_idx_1 __farr_key_1 __farr_val_2 - local __farr_idx_2 __farr_key_2 __farr_val_2 - - _farr_alist_get_meta "$2" - __farr_input_1="$2" - __farr_name_1="${__farr_name}" - __farr_token_1="${__farr_token}" - __farr_objname_1="${__farr_objname}" - __farr_keyname_1="${__farr_keyname}" - __farr_valname_1="${__farr_valname}" - __farr_len_1="${__farr_len}" - _farr_alist_get_meta "$3" - __farr_input_2="$3" - __farr_name_2="${__farr_name}" - __farr_token_2="${__farr_token}" - __farr_objname_2="${__farr_objname}" - __farr_keyname_2="${__farr_keyname}" - __farr_valname_2="${__farr_valname}" - __farr_len_2="${__farr_len}" + __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_result="$1" - - __farr_idx_1=1 - if [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; then - eval __farr_key_1=\"\$\{${__farr_keyname_1}_${__farr_idx_1}\}\" - fi - __farr_idx_2=1 - if [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; then - eval __farr_key_2=\"\$\{${__farr_keyname_2}_${__farr_idx_2}\}\" - fi - while [ \( "${__farr_idx_1}" -le "${__farr_len_1}" \) -a \( "${__farr_idx_2}" -le "${__farr_len_2}" \) ]; do - if [ \( "${__farr_key_1}" '<' "${__farr_key_2}" \) -o \( "${__farr_key_1}" '=' "${__farr_key_2}" \) ] ; then - eval __farr_val_1=\"\$\{${__farr_valname_1}_${__farr_idx_1}\}\" - # shellcheck disable=SC2154 # bogus __farr_val_1 is ref but not set - falist_add "${__farr_result}" "${__farr_key_1}" "${__farr_val_1}" - __farr_idx_1=$((__farr_idx_1 + 1)) - if [ "${__farr_idx_1}" -le "${__farr_len_1}" ]; then - eval __farr_key_1=\"\$\{${__farr_keyname_1}_${__farr_idx_1}\}\" - fi - else - eval __farr_val_2=\"\$\{${__farr_valname_2}_${__farr_idx_2}\}\" - falist_add "${__farr_result}" "${__farr_key_2}" "${__farr_val_2}" - __farr_idx_2=$((__farr_idx_2 + 1)) - if [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; then - eval __farr_key_2=\"\$\{${__farr_keyname_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_key_1=\"\$\{${__farr_keyname_1}_${__farr_idx_1}\}\" - eval __farr_val_1=\"\$\{${__farr_valname_1}_${__farr_idx_1}\}\" - falist_add "${__farr_result}" "${__farr_key_1}" "${__farr_val_1}" - __farr_idx_1=$((__farr_idx_1 + 1)) - done - while [ "${__farr_idx_2}" -le "${__farr_len_2}" ]; do - eval __farr_key_2=\"\$\{${__farr_keyname_2}_${__farr_idx_2}\}\" - eval __farr_val_2=\"\$\{${__farr_valname_2}_${__farr_idx_2}\}\" - falist_add "${__farr_result}" "${__farr_key_2}" "${__farr_val_2}" - __farr_idx_2=$((__farr_idx_2 + 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 } @@ -2571,8 +3123,8 @@ #: $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 the index -#: of the found item into. +#: $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. @@ -2580,38 +3132,31 @@ #: or if an internal inconsistency will be detected. #: falist_get() { - local __farr_varname __farr_name __farr_key __farr_idx_varname - - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_idx __farr_getkey - local __farr_get_value + 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 + local __farr_sptr __farr_get_key __farr_get_value __farr_varname="${1-}" [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name" - shift - _farr_alist_get_meta "$@" - [ $# -lt 2 ] && _farr_fatal "missing key" - __farr_key="$2" - __farr_idx_varname="${3-}" - - __farr_idx=1 - while [ ${__farr_idx} -le ${__farr_len} ]; do - eval __farr_getkey=\"\$\{${__farr_keyname}_${__farr_idx}+SET\}\" - if [ -n "${__farr_getkey}" ]; then - eval __farr_getkey=\"\$\{${__farr_keyname}_${__farr_idx}\}\" - if [ "${__farr_getkey}" = "${__farr_key}" ]; then - eval __farr_get_value=\"\$\{${__farr_valname}_${__farr_idx}\}\" - _farr_acquire_object "${__farr_get_value}" - eval "${__farr_varname}"=\"\$\{__farr_get_value\}\" - [ -n "${__farr_idx_varname}" ] && eval "${__farr_idx_varname}"=${__farr_idx} - return 0 - fi - else - _farr_fatal "key unexpectedly unset (index ${__farr_idx})" + _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 - __farr_idx=$((__farr_idx + 1)) - done - _farr_fatal "alist \`${__farr_name:-"${1}"}': key \`${__farr_key}' not found" + else + _farr_fatal "alist \`${__farr_name:-"${2}"}': key \`${__farr_key}' not found" + fi } @@ -2623,58 +3168,173 @@ #: $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 the index -#: of the found item into. +#: $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_idx_varname - - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_idx __farr_getkey - local __farr_get_value + 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 + local __farr_sptr __farr_get_key __farr_get_value __farr_varname="${1-}" [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name" - shift - _farr_alist_get_meta "$@" - [ $# -lt 2 ] && _farr_fatal "missing key" - __farr_key="$2" - __farr_idx_varname="${3-}" - - __farr_idx=1 - while [ ${__farr_idx} -le ${__farr_len} ]; do - eval __farr_getkey=\"\$\{${__farr_keyname}_${__farr_idx}+SET\}\" - if [ -n "${__farr_getkey}" ]; then - eval __farr_getkey=\"\$\{${__farr_keyname}_${__farr_idx}\}\" - if [ "${__farr_getkey}" = "${__farr_key}" ]; then - eval __farr_get_value=\"\$\{${__farr_valname}_${__farr_idx}\}\" - _farr_acquire_object "${__farr_get_value}" - eval "${__farr_varname}"=\"\$\{__farr_get_value\}\" - [ -n "${__farr_idx_varname}" ] && eval "${__farr_idx_varname}"=${__farr_idx} - return 0 - fi - else - _farr_fatal "key unexpectedly unset (index ${__farr_idx})" + _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 - __farr_idx=$((__farr_idx + 1)) - done + return 0 + fi return 1 } #: -#: Try to get the key that is associated with a storage index and store it in a variable. -#: -#: Use this for iteration over values. +#: 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 + local __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 + local __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 + local __farr_sptr __farr_sptr_prev __farr_sptr_next + local __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 + local __farr_sptr __farr_sptr_prev __farr_sptr_next + local __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 name of an existing alist. -#: $3 (int): The index. +#: $2 (str): The storage cookie. #: #: Returns: #: 0 (truthy) on success, @@ -2684,28 +3344,25 @@ #: Other errors (missing array name, missing index value) are considered #: fatal and call `_farr_fatal` (i.e. `exit`). #: -falist_tryget_key_at_index() { - local __farr_varname __farr_name __farr_index - - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_idx __farr_getikey - - __farr_varname=${1-} - [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name" - shift - _farr_alist_get_meta "$@" - __farr_index="${2-}" - [ -z "${__farr_index}" ] && _farr_fatal "missing index" - _farr_make_index __farr_index "${__farr_index}" "${__farr_len}" - - if [ \( ${__farr_index} -ge 1 \) -a \( ${__farr_index} -le ${__farr_len} \) ]; then - eval __farr_getikey=\"\$\{${__farr_keyname}_${__farr_index}+SET\}\" +falist_tryget_key_at() { + local __farr_key_varname __farr_scookie + + local __farr_token __farr_objname __farr_keyname __farr_valname + local __farr_sptr __farr_sptr_prev __farr_sptr_next + local __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 - # no refcount change because no complex values allowed yet - eval "${__farr_varname}"=\"\$\{${__farr_keyname}_${__farr_index}\}\" + eval __farr_getikey=\"\$\{"${__farr_keyname}"_"${__farr_sptr}"\}\" + setvar "${__farr_key_varname}" "${__farr_getikey#*@}" return 0 else - _farr_fatal "key unexpectedly unset (index ${__farr_index})" + _farr_fatal "key unexpectedly unset (cookie ${__farr_scookie})" fi else return 1 @@ -2714,14 +3371,17 @@ #: -#: Try to get the value that is associated with a storage index and store it in a variable. -#: -#: Use this for iteration over keys. +#: 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 name of an existing alist. -#: $3 (int): The index. +#: $2 (str): The storage cookie. #: #: Returns: #: 0 (truthy) on success, @@ -2731,29 +3391,26 @@ #: Other errors (missing array name, missing index value) are considered #: fatal and call `_farr_fatal` (i.e. `exit`). #: -falist_tryget_value_at_index() { - local __farr_varname __farr_name __farr_index - - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_idx __farr_getival - - __farr_varname=${1-} - [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name" - shift - _farr_alist_get_meta "$@" - __farr_index="${2-}" - [ -z "${__farr_index}" ] && _farr_fatal "missing index" - _farr_make_index __farr_index "${__farr_index}" "${__farr_len}" - - if [ \( ${__farr_index} -ge 1 \) -a \( ${__farr_index} -le ${__farr_len} \) ]; then - eval __farr_getival=\"\$\{${__farr_valname}_${__farr_index}+SET\}\" +falist_tryget_value_at() { + local __farr_value_varname __farr_scookie + + local __farr_token __farr_objname __farr_keyname __farr_valname + local __farr_sptr __farr_sptr_prev __farr_sptr_next + local __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_index}\}\" + eval __farr_getival=\"\$\{"${__farr_valname}"_"${__farr_sptr}"\}\" _farr_acquire_object "${__farr_getival}" - eval "${__farr_varname}"=\"\$\{__farr_getival\}\" + setvar "${__farr_value_varname}" "${__farr_getival}" return 0 else - _farr_fatal "value unexpectedly unset (index ${__farr_index})" + _farr_fatal "value unexpectedly unset (cookie ${__farr_scookie})" fi else return 1 @@ -2762,56 +3419,56 @@ #: -#: Try to get the key-value item that is associated with a storage index and +#: Try to get the key-value item that is associated with a storage cookie and #: store it into variables. #: -#: Use this for iteration over key-value items. +#: 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 name of an existing alist. -#: $4 (int): The index. +#: $3 (str): The storage cookie. #: #: Returns: #: 0 (truthy) on success, -#: 1 (falsy) if the given index is out of bounds. +#: 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_index() { - local __farr_key_varname __farr_value_varname __farr_name __farr_index - - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_idx __farr_getikey __farr_getival +falist_tryget_item_at() { + local __farr_key_varname __farr_value_varname __farr_scookie + + local __farr_token __farr_objname __farr_keyname __farr_valname + local __farr_sptr __farr_sptr_prev __farr_sptr_next + local __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" - shift 2 - _farr_alist_get_meta "$@" - __farr_index="${2-}" - [ -z "${__farr_index}" ] && _farr_fatal "missing index" - _farr_make_index __farr_index "${__farr_index}" "${__farr_len}" - - if [ \( ${__farr_index} -ge 1 \) -a \( ${__farr_index} -le ${__farr_len} \) ]; then - eval __farr_getikey=\"\$\{${__farr_keyname}_${__farr_index}+SET\}\" + _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_index}+SET\}\" + eval __farr_getival=\"\$\{"${__farr_valname}"_"${__farr_sptr}"+SET\}\" if [ -n "${__farr_getival}" ]; then - eval "${__farr_key_varname}"=\"\$\{${__farr_keyname}_${__farr_index}\}\" - eval __farr_getival=\"\$\{${__farr_valname}_${__farr_index}\}\" + 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}" - eval "${__farr_value_varname}"=\"\$\{__farr_getival\}\" + setvar "${__farr_value_varname}" "${__farr_getival}" return 0 else - _farr_fatal "value unexpectedly unset (index ${__farr_index})" + _farr_fatal "value unexpectedly unset (cookie ${__farr_scookie})" fi else - _farr_fatal "key unexpectedly unset (index ${__farr_index})" + _farr_fatal "key unexpectedly unset (cookie ${__farr_scookie})" fi else return 1 @@ -2831,44 +3488,26 @@ #: 1 (falsy) if the given key is not found. #: falist_contains() { - local __farr_name __farr_key - - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_idx __farr_cokey - - _farr_alist_get_meta "$@" + # __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_key="$2" - - __farr_idx=1 - while [ ${__farr_idx} -le ${__farr_len} ]; do - eval __farr_cokey=\"\$\{${__farr_keyname}_${__farr_idx}+SET\}\" - if [ -n "${__farr_cokey}" ]; then - eval __farr_cokey=\"\$\{${__farr_keyname}_${__farr_idx}\}\" - if [ "${__farr_cokey}" = "${__farr_key}" ]; then - return 0 - fi - else - _farr_fatal "key unexpectedly unset (index ${__farr_idx})" - fi - __farr_idx=$((__farr_idx + 1)) - done - return 1 + + _farr_alist_bsearch '' '' "${2}" } #: -#: Try to find the index of a given key in an alist. +#: 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 index into +#: $1 (str): The name of a variable where to put the found storage cookie +#: into. #: $2 (str): The existing alist. #: $3: The key. -#: $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 (truthy) on success if the key is found, @@ -2876,95 +3515,23 @@ #: falist_find() { local __farr_varname __farr_name __farr_key - local __farr_start __farr_end - - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_cur_find_idx __farr_fikey + + local __farr_token __farr_objname __farr_bskeyname __farr_keyname __farr_valname __farr_llen __farr_bslen __farr_sptr_first __farr_sptr_last + local __farr_sptr __farr_find_key __farr_varname="${1-}" [ -z "${__farr_varname}" ] && _farr_fatal "missing variable name" - shift - - _farr_alist_get_meta "$@" - [ $# -lt 2 ] && _farr_fatal "missing key" - __farr_key="$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_fikey=\"\$\{${__farr_keyname}_${__farr_cur_find_idx}+SET\}\" - if [ -n "${__farr_fikey}" ]; then - eval __farr_fikey=\"\$\{${__farr_keyname}_${__farr_cur_find_idx}\}\" - if [ "${__farr_fikey}" = "${__farr_key}" ]; then - eval "${__farr_varname}"=${__farr_cur_find_idx} - return 0 - fi - else - _farr_fatal "key unexpectedly unset (index ${__farr_cur_find_idx})" - fi - __farr_cur_find_idx=$((__farr_cur_find_idx + 1)) - done - return 1 -} - - -#: -#: Internal helper to delete an item from an alist storage. -#: -#: Args: -#: $1 (str): The name of the storage object -#: $2 (int): The current length of the storage object (i.e. the current -#: length of the alist) -#: $3 (int): The storage index that will be deleted -#: $4: if no-null use release semantics (used for values) -#: -#: Returns: -#: int: Always 0 -#: -#: Important: -#: This is an internal function. No index and other storage consistency -#: checks are done. -#: -#: Note: -#: The implementation is very similar to `farray_del`. -#: But the new length must be managed by the caller. -#: -_farr_alist_del_storage_at_index() { - local __farr_storage_name __farr_storage_length __farr_storage_index - local __farr_use_release - - local __farr_idx __farr_del_item - - __farr_storage_name="$1" - __farr_storage_length="$2" - __farr_storage_index="$3" - __farr_use_release="$4" - - # Release the item at index -- if requested - if [ -n "${__farr_use_release}" ] ; then - eval __farr_del_item=\"\$\{${__farr_storage_name}_${__farr_idx}\}\" - _farr_release_object "${__farr_del_item}" + _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 - - # Move all other items down by one - __farr_idx=${__farr_storage_index} - while [ ${__farr_idx} -lt ${__farr_storage_length} ] ; do - # copy the following value to the current index - eval ${__farr_storage_name}_${__farr_idx}=\"\$\{${__farr_storage_name}_$((__farr_idx + 1))\}\" - __farr_idx=$((__farr_idx + 1)) - done - # Drop the last item - eval unset ${__farr_storage_name}_${__farr_idx} - return 0 + return 1 # not found } @@ -2982,32 +3549,108 @@ falist_trydel() { local __farr_name __farr_delkey - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_idx __farr_curkey + local __farr_token __farr_objname __farr_bskeyname __farr_keyname __farr_valname __farr_llen __farr_bslen __farr_sptr_first __farr_sptr_last + local __farr_sptr __farr_bsidx __farr_cur_value + local __farr_cur_key __farr_cur_stype __farr_cur_prev __farr_cur_next + local __farr_next_key __farr_next_prev __farr_next_next + local __farr_prev_key __farr_prev_prev __farr_prev_next _farr_alist_get_meta "$@" [ $# -lt 2 ] && _farr_fatal "missing key" __farr_delkey="$2" - __farr_idx=1 - while [ ${__farr_idx} -le ${__farr_len} ] ; do - eval __farr_curkey=\"\$\{${__farr_keyname}_${__farr_idx}+SET\}\" - if [ -n "${__farr_curkey}" ]; then - eval __farr_curkey=\"\$\{${__farr_keyname}_${__farr_idx}\}\" - if [ "${__farr_curkey}" = "${__farr_delkey}" ]; then - _farr_alist_del_storage_at_index "${__farr_valname}" "${__farr_len}" "${__farr_idx}" '1' - _farr_alist_del_storage_at_index "${__farr_keyname}" "${__farr_len}" "${__farr_idx}" "" - # Reduce the length by 1 - eval ${__farr_objname}__=$((__farr_len - 1)) - return 0 - fi - else - _farr_fatal "key unexpectedly unset (index ${__farr_idx})" - fi - __farr_idx=$((__farr_idx + 1)) - done - # Not found - return 1 + _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}" } @@ -3022,12 +3665,12 @@ #: 1 (falsy) otherwise (empty or not created/destroyed properly). #: falist_istrue() { - local __farr_name - - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len + # 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_len}" -gt 0 ]; then + if [ "${__farr_llen}" -gt 0 ]; then return 0 else return 1 @@ -3039,8 +3682,8 @@ #: Test whether two alists are equal. #: #: Two alists compare equal if and only if they have the same (key, value) -#: pairs (regardless of ordering). Comparison is done using the shell's -#: builtin ``=`` operator for both keys and values. +#: 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 @@ -3050,52 +3693,46 @@ #: int: 0 if both input alists are equal, 1 otherwise #: falist_are_equal() { - local __farr_l_name __farr_r_name - - local __farr_l_token __farr_l_objname __farr_l_keyname __farr_l_valname __farr_l_len - local __farr_r_token __farr_r_objname __farr_r_keyname __farr_r_valname __farr_r_len - - local __farr_name __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_l_idx __farr_l_key __farr_l_value - local __farr_r_idx __farr_r_key __farr_r_value + 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 + local __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 + local __farr_sptr __farr_r_sptr __farr_r_bsidx + local __farr_value __farr_r_key __farr_r_value __farr_r_stype [ $# -ne 2 ] && _farr_fatal "missing alist parameter" - _farr_alist_get_meta "$1" - __farr_l_name="${__farr_name}" - __farr_l_token="${__farr_token}" - __farr_l_objname="${__farr_objname}" - __farr_l_keyname="${__farr_keyname}" - __farr_l_valname="${__farr_valname}" - __farr_l_len="${__farr_len}" _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_len="${__farr_len}" - - [ ${__farr_l_len} -ne ${__farr_r_len} ] && return 1 - - __farr_l_idx=1 - while [ ${__farr_l_idx} -le ${__farr_l_len} ]; do - __farr_r_idx=1 - eval __farr_l_key=\"\$\{${__farr_l_keyname}_${__farr_l_idx}\}\" - # Find within the right alist - __farr_r_idx=1 - while [ ${__farr_r_idx} -le ${__farr_r_len} ]; do - eval __farr_r_key=\"\$\{${__farr_r_keyname}_${__farr_r_idx}\}\" - [ "${__farr_l_key}" = "${__farr_r_key}" ] && break - __farr_r_idx=$((__farr_r_idx + 1)) - done - # The index is above the right length if not found - [ ${__farr_r_idx} -gt ${__farr_r_len} ] && return 1 - # Also compare the values - eval __farr_l_value=\"\$\{${__farr_l_valname}_${__farr_l_idx}\}\" - eval __farr_r_value=\"\$\{${__farr_r_valname}_${__farr_r_idx}\}\" - [ "${__farr_l_value}" != "${__farr_r_value}" ] && return 1 - __farr_l_idx=$((__farr_l_idx + 1)) + __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 } @@ -3105,57 +3742,68 @@ #: 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 ordering. Comparison is done using the shell's -#: builtin ``=`` operator for both keys and values. +#: 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 name of the first alist -#: $2 (str): The name of the second alist +#: $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_l_name __farr_r_name - - local __farr_l_token __farr_l_objname __farr_l_keyname __farr_l_valname __farr_l_len - local __farr_r_token __farr_r_objname __farr_r_keyname __farr_r_valname __farr_r_len - - local __farr_name __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_idx - local __farr_l_key __farr_l_value + 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 + local __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 + local __farr_sptr __farr_sptr_next __farr_r_sptr __farr_r_sptr_next + local __farr_key __farr_value local __farr_r_key __farr_r_value [ $# -ne 2 ] && _farr_fatal "missing alist parameter" - _farr_alist_get_meta "$1" - __farr_l_name="${__farr_name}" - __farr_l_token="${__farr_token}" - __farr_l_objname="${__farr_objname}" - __farr_l_keyname="${__farr_keyname}" - __farr_l_valname="${__farr_valname}" - __farr_l_len="${__farr_len}" _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_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_l_key=\"\$\{${__farr_l_keyname}_${__farr_idx}\}\" - eval __farr_r_key=\"\$\{${__farr_r_keyname}_${__farr_idx}\}\" - [ "${__farr_l_key}" != "${__farr_r_key}" ] && return 1 - # Also compare the values - eval __farr_l_value=\"\$\{${__farr_l_valname}_${__farr_idx}\}\" - eval __farr_r_value=\"\$\{${__farr_r_valname}_${__farr_idx}\}\" - [ "${__farr_l_value}" != "${__farr_r_value}" ] && return 1 - __farr_idx=$((__farr_idx + 1)) + __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 } @@ -3167,15 +3815,18 @@ #: $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_r_name - - local __farr_r_token __farr_r_objname __farr_r_keyname __farr_r_valname __farr_r_len + local __farr_l_result __farr_name + local __farr_l_name __farr_l_token __farr_l_gvrname __farr_l_len - local __farr_name __farr_token __farr_gvrname __farr_objname - local __farr_keyname __farr_valname __farr_len - local __farr_idx __farr_key + local __farr_token __farr_gvrname __farr_objname + local __farr_bskeyname __farr_keyname __farr_valname + local __farr_len __farr_llen __farr_bslen + local __farr_sptr_first __farr_sptr_last + local __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" @@ -3186,24 +3837,15 @@ __farr_l_gvrname="${__farr_gvrname}" __farr_l_len="${__farr_len}" [ $# -lt 2 ] && _farr_fatal "missing alist" - _farr_alist_get_meta "$2" - __farr_r_name="${__farr_name}" - __farr_r_token="${__farr_token}" - __farr_r_objname="${__farr_objname}" - __farr_r_keyname="${__farr_keyname}" - __farr_r_valname="${__farr_valname}" - __farr_r_len="${__farr_len}" - - __farr_idx=1 - while [ ${__farr_idx} -le ${__farr_r_len} ]; do - eval __farr_key=\"\$\{${__farr_r_keyname}_${__farr_idx}+SET\}\" - if [ -n "${__farr_key}" ]; then - eval __farr_key=\"\$\{${__farr_r_keyname}_${__farr_idx}\}\" - farray_append "${__farr_l_result}" "${__farr_key}" - else - _farr_fatal "alist \`${__farr_r_name}': missing key index" - fi - __farr_idx=$((__farr_idx + 1)) + _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 } @@ -3216,15 +3858,18 @@ #: $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_r_name - - local __farr_r_token __farr_r_objname __farr_r_keyname __farr_r_valname __farr_r_len + local __farr_l_result __farr_name + local __farr_l_name __farr_l_token __farr_l_gvrname __farr_l_len - local __farr_name __farr_token __farr_gvrname __farr_objname - local __farr_keyname __farr_valname __farr_len - local __farr_idx __farr_value + local __farr_token __farr_gvrname __farr_objname + local __farr_bskeyname __farr_keyname __farr_valname + local __farr_len __farr_llen __farr_bslen + local __farr_sptr_first __farr_sptr_last + local __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" @@ -3235,24 +3880,16 @@ __farr_l_gvrname="${__farr_gvrname}" __farr_l_len="${__farr_len}" [ $# -lt 2 ] && _farr_fatal "missing alist" - _farr_alist_get_meta "$2" - __farr_r_name="${__farr_name}" - __farr_r_token="${__farr_token}" - __farr_r_objname="${__farr_objname}" - __farr_r_keyname="${__farr_keyname}" - __farr_r_valname="${__farr_valname}" - __farr_r_len="${__farr_len}" - - __farr_idx=1 - while [ ${__farr_idx} -le ${__farr_r_len} ]; do - eval __farr_value=\"\$\{${__farr_r_valname}_${__farr_idx}+SET\}\" - if [ -n "${__farr_value}" ]; then - eval __farr_value=\"\$\{${__farr_r_valname}_${__farr_idx}\}\" - farray_append "${__farr_l_result}" "${__farr_value}" - else - _farr_fatal "alist \`${__farr_r_name}': missing value index" - fi - __farr_idx=$((__farr_idx + 1)) + _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 } @@ -3266,15 +3903,18 @@ #: 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_r_name - - local __farr_r_token __farr_r_objname __farr_r_keyname __farr_r_valname __farr_r_len + local __farr_l_result __farr_name + local __farr_l_name __farr_l_token __farr_l_gvrname __farr_l_len - local __farr_name __farr_token __farr_gvrname __farr_objname - local __farr_keyname __farr_valname __farr_len - local __farr_idx __farr_key __farr_value + local __farr_token __farr_gvrname __farr_objname + local __farr_bskeyname __farr_keyname __farr_valname + local __farr_len __farr_llen __farr_bslen + local __farr_sptr_first __farr_sptr_last + local __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" @@ -3285,43 +3925,30 @@ __farr_l_gvrname="${__farr_gvrname}" __farr_l_len="${__farr_len}" [ $# -lt 2 ] && _farr_fatal "missing alist" - _farr_alist_get_meta "$2" - __farr_r_name="${__farr_name}" - __farr_r_token="${__farr_token}" - __farr_r_objname="${__farr_objname}" - __farr_r_keyname="${__farr_keyname}" - __farr_r_valname="${__farr_valname}" - __farr_r_len="${__farr_len}" - - __farr_idx=1 - while [ ${__farr_idx} -le ${__farr_r_len} ]; do - eval __farr_key=\"\$\{${__farr_r_keyname}_${__farr_idx}+SET\}\" - if [ -n "${__farr_key}" ]; then - eval __farr_key=\"\$\{${__farr_r_keyname}_${__farr_idx}\}\" - eval __farr_value=\"\$\{${__farr_r_valname}_${__farr_idx}+SET\}\" - if [ -n "${__farr_value}" ]; then - eval __farr_value=\"\$\{${__farr_r_valname}_${__farr_idx}\}\" - farray_append "${__farr_l_result}" "${__farr_key}" "${__farr_value}" - else - _farr_fatal "alist \`${__farr_r_name}': missing value index" - fi - else - _farr_fatal "alist \`${__farr_r_name}': missing key index" - fi - __farr_idx=$((__farr_idx + 1)) + _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 starting in index order. -#: -#: The function to be called must accept at least three or four arguments: +#: 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 index -#: - the element value at the current index -#: - the current index +#: - 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 #: @@ -3341,37 +3968,33 @@ falist_for_each() { local __farr_name __farr_callback - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_feidx __farr_fekey __farr_feval __farr_rv + local __farr_token __farr_objname __farr_bskeyname __farr_keyname __farr_valname __farr_llen __farr_bslen __farr_sptr_first __farr_sptr_last + local __farr_fesptr __farr_fesptr_next __farr_fescookie + local __farr_fekey __farr_feval __farr_rv local __farr_gm_name_or_value __farr_gm_name_or_value="${1-}" - _farr_alist_get_meta "$@" + _farr_alist_get_meta "${__farr_gm_name_or_value}" __farr_callback="${2-}" [ -z "${__farr_callback}" ] && _farr_fatal "missing callback function name" shift 2 - __farr_feidx=1 - while [ ${__farr_feidx} -le ${__farr_len} ]; do - eval __farr_fekey=\"\$\{${__farr_keyname}_${__farr_feidx}+SET\}\" - if [ -n "${__farr_fekey}" ]; then - eval __farr_fekey=\"\$\{${__farr_keyname}_${__farr_feidx}\}\" - eval __farr_feval=\"\$\{${__farr_valname}_${__farr_feidx}+SET\}\" - if [ -n "${__farr_feval}" ]; then - eval __farr_feval=\"\$\{${__farr_valname}_${__farr_feidx}\}\" - _farr_acquire_object "${__farr_feval}" - eval "${__farr_callback} \"\${__farr_name:-\"\${__farr_gm_name_or_value}\"}\" \"\${__farr_fekey}\" \"\${__farr_feval}\" \"\${__farr_feidx}\" \"\$@\"" - __farr_rv=$? - _farr_release_object "${__farr_feval}" - [ ${__farr_rv} -ne 0 ] && return ${__farr_rv} - else - _farr_fatal "alist \`${__farr_name:-"${__farr_gm_name_or_value}"}': missing value index" - fi - else - _farr_fatal "alist \`${__farr_name:-"${__farr_gm_name_or_value}"}': missing key index" - fi - __farr_feidx=$((__farr_feidx + 1)) + __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 } @@ -3402,10 +4025,13 @@ #: 0 #: _farr_alist_debug() { - local __farr_debug_indent __farr_name - - local __farr_token __farr_objname __farr_keyname __farr_valname __farr_len - local __farr_idx __farr_el_key __farr_el_val + 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 + local __farr_sptr __farr_el_key __farr_el_val + local __farr_sptr_next + local __farr_debug_bsidx __farr_debug_sptr __farr_debug_indent="${1}" shift @@ -3415,41 +4041,42 @@ fi if [ -n "${__farr_name}" ]; then - printf "%sDEBUG: alist \`%s' has length %s\\n" "${__farr_debug_indent}" "${__farr_name}" "${__farr_len}" 1>&2 + 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_len}" 1>&2 + printf "%sDEBUG: alist with token \`%s' has length %s\\n" "${__farr_debug_indent}" "${__farr_token}" "${__farr_llen}" 1>&2 fi - if [ ${__farr_len} -gt 0 ]; then + if [ "${__farr_llen}" -gt 0 ]; then printf '%sDEBUG: the items:\n' "${__farr_debug_indent}" 1>&2 fi - __farr_idx=1 - while [ ${__farr_idx} -le ${__farr_len} ]; do - eval __farr_el_key=\"\$\{${__farr_keyname}_${__farr_idx}+SET\}\" - if [ -z "${__farr_el_key}" ]; then - printf "%sDEBqUG: key unexpectedly unset (index %s)\\n" "${__farr_debug_indent}" "${__farr_idx}" 1>&2 - fi - eval __farr_el_val=\"\$\{${__farr_valname}_${__farr_idx}+SET\}\" - if [ -z "${__farr_el_val}" ]; then - printf "%s DEBUG: value unexpectedly unset (index %s)\\n" "${__farr_debug_indent}" "${__farr_idx}" 1>&2 + __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 - if [ \( -n "${__farr_el_key}" \) -a \( -n "${__farr_el_val}" \) ]; then - eval __farr_el_key=\"\$\{${__farr_keyname}_${__farr_idx}\}\" - eval __farr_el_val=\"\$\{${__farr_valname}_${__farr_idx}\}\" - 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 - fi - __farr_idx=$((__farr_idx + 1)) + 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 } @@ -3477,20 +4104,20 @@ ;; "${_farr_array_token_prefix}"*) __farr_tmp_token="${1#"${_farr_array_token_prefix}"}" - eval __farr_tmp_refcount=\$\{${_farr_array_prefix}${__farr_tmp_token}_C:+SET\} + 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\} + eval __farr_tmp_refcount=\"\$\{"${_farr_array_prefix}""${__farr_tmp_token}"_C\}\" __farr_tmp_refcount=$((__farr_tmp_refcount + 1)) - eval ${_farr_array_prefix}${__farr_tmp_token}_C=\$\{__farr_tmp_refcount\} + 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\} + 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\} + eval __farr_tmp_refcount=\"\$\{"${_farr_alist_prefix}""${__farr_tmp_token}"_C\}\" __farr_tmp_refcount=$((__farr_tmp_refcount + 1)) - eval ${_farr_alist_prefix}${__farr_tmp_token}_C=\$\{__farr_tmp_refcount\} + setvar "${_farr_alist_prefix}${__farr_tmp_token}_C" "${__farr_tmp_refcount}" return 0 ;; *)
--- a/tests/farray-alist.t Fri Oct 18 14:02:18 2024 +0200 +++ b/tests/farray-alist.t Sat Oct 19 22:40:11 2024 +0200 @@ -18,6 +18,14 @@ Create an empty alist $ falist_create LIST +Has some initial global variables set + $ check_no_alist_artifacts + _farr_KV_[a-f0-9]+_B=0 (re) + _farr_KV_[a-f0-9]+_C=1 (re) + _farr_KV_[a-f0-9]+_P='0;0' (re) + _farr_KV_[a-f0-9]+__=0 (re) + [1] + $ falist_length _i LIST $ echo "$_i" 0 @@ -37,6 +45,161 @@ $ check_no_alist_artifacts + $ falist_create LIST + $ falist_clear LIST + $ falist_istrue LIST + [1] + $ falist_debug LIST + DEBUG: alist `LIST' has length 0 + $ falist_release LIST + $ ( falist_release LIST ) + ERROR: object `LIST' not created properly: token empty + [1] + $ check_no_alist_artifacts + + +Creation and Destruction with one Item +====================================== + +Create an alist with one item + + $ falist_create LIST K1 V1 + $ falist_length _i LIST + $ echo "$_i" + 1 + $ test "${_i}" -eq 1 + $ falist_print_length LIST + 1 (no-eol) + + $ falist_istrue LIST + $ falist_debug LIST + DEBUG: alist `LIST' has length 1 + DEBUG: the items: + DEBUG: `K1' -> `V1' + $ falist_release LIST + $ ( falist_release LIST ) + ERROR: object `LIST' not created properly: token empty + [1] + + $ check_no_alist_artifacts + +One Item that replaces the first item + + $ falist_create LIST K1 V1 K1 "V1 1" + $ falist_length _i LIST + $ echo "$_i" + 1 + $ test "${_i}" -eq 1 + $ falist_print_length LIST + 1 (no-eol) + + $ falist_istrue LIST + $ falist_debug LIST + DEBUG: alist `LIST' has length 1 + DEBUG: the items: + DEBUG: `K1' -> `V1 1' + $ falist_release LIST + $ ( falist_release LIST ) + ERROR: object `LIST' not created properly: token empty + [1] + + $ check_no_alist_artifacts + + +Creation and Destruction with more Items +======================================== + +Create an alist with two items + + $ falist_create LIST K1 V1 K2 V2 + $ falist_debug LIST + DEBUG: alist `LIST' has length 2 + DEBUG: the items: + DEBUG: `K1' -> `V1' + DEBUG: `K2' -> `V2' + + $ falist_release LIST + + $ check_no_alist_artifacts + +Create with inverse insertion order + + $ falist_create LIST K2 V2 K1 V1 + $ falist_debug LIST + DEBUG: alist `LIST' has length 2 + DEBUG: the items: + DEBUG: `K2' -> `V2' + DEBUG: `K1' -> `V1' + + $ falist_release LIST + +Insert at the beginning + + + $ falist_create LIST K2 V2 K1 V1 K0 V0 + $ falist_debug LIST + DEBUG: alist `LIST' has length 3 + DEBUG: the items: + DEBUG: `K2' -> `V2' + DEBUG: `K1' -> `V1' + DEBUG: `K0' -> `V0' + +Replace: beginning + + $ falist_set $LIST K2 $'V2 \' \\ "$abc' + $ falist_debug LIST + DEBUG: alist `LIST' has length 3 + DEBUG: the items: + DEBUG: `K2' -> `V2 ' \ "$abc' + DEBUG: `K1' -> `V1' + DEBUG: `K0' -> `V0' + +Replace: mid + + $ falist_set $LIST K1 'V1 1' + $ falist_debug LIST + DEBUG: alist `LIST' has length 3 + DEBUG: the items: + DEBUG: `K2' -> `V2 ' \ "$abc' + DEBUG: `K1' -> `V1 1' + DEBUG: `K0' -> `V0' + +Replace: end + + $ falist_set $LIST K0 'V0 1' + $ falist_debug LIST + DEBUG: alist `LIST' has length 3 + DEBUG: the items: + DEBUG: `K2' -> `V2 ' \ "$abc' + DEBUG: `K1' -> `V1 1' + DEBUG: `K0' -> `V0 1' + +Insert in the midele again + + $ falist_set LIST K1-1 'V1-1' + $ falist_debug LIST + DEBUG: alist `LIST' has length 4 + DEBUG: the items: + DEBUG: `K2' -> `V2 ' \ "$abc' + DEBUG: `K1' -> `V1 1' + DEBUG: `K0' -> `V0 1' + DEBUG: `K1-1' -> `V1-1' + +Clear resets to initial values + + $ falist_clear LIST + $ check_no_alist_artifacts + _farr_KV_[a-f0-9]+_B=0 (re) + _farr_KV_[a-f0-9]+_C=1 (re) + _farr_KV_[a-f0-9]+_P='0;0' (re) + _farr_KV_[a-f0-9]+__=0 (re) + [1] + + $ falist_print_length LIST + 0 (no-eol) + $ falist_release LIST + $ check_no_alist_artifacts + Clear ===== @@ -44,14 +207,14 @@ $ falist_create LIST $ falist_istrue LIST [1] - $ falist_set LIST K1 V1 + $ falist_set LIST K2 V2 $ falist_istrue LIST - $ falist_set LIST K2 V2 + $ falist_set LIST K1 V1 $ falist_debug LIST DEBUG: alist `LIST' has length 2 DEBUG: the items: + DEBUG: `K2' -> `V2' DEBUG: `K1' -> `V1' - DEBUG: `K2' -> `V2' $ falist_length _i LIST $ echo "$_i" 2 @@ -67,6 +230,17 @@ $ falist_print_length LIST 0 (no-eol) +Clear resets to initial values + + $ falist_clear LIST + $ check_no_alist_artifacts + _farr_KV_[a-f0-9]+_B=0 (re) + _farr_KV_[a-f0-9]+_C=1 (re) + _farr_KV_[a-f0-9]+_P='0;0' (re) + _farr_KV_[a-f0-9]+__=0 (re) + [1] + $ falist_istrue LIST + [1] $ falist_release LIST $ falist_istrue LIST ERROR: object `LIST' not created properly: token empty @@ -74,6 +248,359 @@ $ check_no_alist_artifacts +Optimized Adding +================ + + $ falist_create LIST + $ falist_add LIST k1 v1 + $ falist_add LIST k2 v2 +Would violate order requirements + $ ( falist_add LIST k0 v0 ) + ERROR: falist_add() would violate key order + [70] + $ ( falist_add LIST k2 v2-2 ) + ERROR: falist_add() would violate key order + [70] + $ falist_add $LIST k3 $'" 111222333" \\\'444555666 ' # ' + $ falist_debug LIST + DEBUG: alist `LIST' has length 3 + DEBUG: the items: + DEBUG: `k1' -> `v1' + DEBUG: `k2' -> `v2' + DEBUG: `k3' -> `" 111222333" \'444555666 ' + $ falist_add $LIST k4 'v4 1' k5 v5 + $ falist_debug LIST + DEBUG: alist `LIST' has length 5 + DEBUG: the items: + DEBUG: `k1' -> `v1' + DEBUG: `k2' -> `v2' + DEBUG: `k3' -> `" 111222333" \'444555666 ' + DEBUG: `k4' -> `v4 1' + DEBUG: `k5' -> `v5' + $ falist_release LIST + $ check_no_alist_artifacts + + +Iteration +========= + + $ falist_create LIST + $ falist_set LIST K1 V1 + $ falist_set LIST K2 "V2 2" + $ falist_set LIST K3 $'" 111222333" \\\'444555 ' # ' + +Consistency check of storage cookies + + $ _c="$(falist_cookie_first LIST)" + $ echo $_c + 1/0;2@[a-f0-9]+ (re) + $ _cnull="$(falist_cookie_prev "${_c}")" + $ echo "${_cnull}" + 0/0;0@[a-f0-9]+ (re) + $ _c2="$(falist_cookie_next "$_c")" + $ echo "${_c2}" + 2/1;3@[a-f0-9]+ (re) + $ _c3="$(falist_cookie_prev "${_c2}")" + $ test "${_c}" = "${_c3}" + $ _c=$(falist_cookie_last LIST) + $ echo $_c + 3/2;0@[a-f0-9]+ (re) + $ _cnull="$(falist_cookie_next "${_c}")" + $ echo "${_cnull}" + 0/0;0@[a-f0-9]+ (re) + +MANUAL (by cookie, forward in insertion order) + + $ _pos="$(falist_cookie_first LIST)" + > while falist_tryget_item_at _k _v "$_pos"; do + > printf $'%s -> `%s\'\\n' "$_k" "$_v" + > _pos="$(falist_cookie_next "$_pos")" + > done + K1 -> `V1' + K2 -> `V2 2' + K3 -> `" 111222333" \'444555 ' + +MANUAL (by cookie, reversed insertion order) + + $ _pos="$(falist_cookie_last LIST)" + > while falist_tryget_item_at _k _v "$_pos"; do + > printf $'`%s\' <- %s\\n' "$_v" "$_k" + > _pos="$(falist_cookie_prev "$_pos")" + > done + `" 111222333" \'444555 ' <- K3 + `V2 2' <- K2 + `V1' <- K1 + +MANUAL values (by cookie, forward in insertion order) + + $ _pos="$(falist_cookie_first LIST)" + > while falist_tryget_value_at _v "$_pos"; do + > printf $'`%s\'\\n' "$_v" + > _pos="$(falist_cookie_next "$_pos")" + > done + `V1' + `V2 2' + `" 111222333" \'444555 ' + + +MANUAL keys (by cookie, reversed insertion order) + + $ _pos="$(falist_cookie_last LIST)" + > while falist_tryget_key_at _k "$_pos"; do + > printf '%s\n' "$_k" + > _pos="$(falist_cookie_prev "$_pos")" + > done + K3 + K2 + K1 + +ITERATE (for each, by name) + + $ falist_for_each LIST $'printf "EACH: %s key \\`%s\\\', value \\`%s\\\' at cookie %s\\n"' # ` + EACH: LIST key `K1', value `V1' at cookie 1/[0-9]+;[0-9]+@[a-f0-9]+ (re) + EACH: LIST key `K2', value `V2 2' at cookie 2/[0-9]+;[0-9]+@[a-f0-9]+ (re) + EACH: LIST key `K3', value `" 111222333" \\'444555 ' at cookie 3/[0-9]+;[0-9]+@[a-f0-9]+ (re) + +ITERATE (for each, by value) + + $ falist_for_each "$LIST" $'printf "EACH: %s key \\`%s\\\', value \\`%s\\\' at cookie %s\\n"' # ` + EACH: _farr_KV\[\?,\?\]:[a-f0-9]+ key `K1', value `V1' at cookie 1/[0-9]+;[0-9]+@[a-f0-9]+ (re) + EACH: _farr_KV\[\?,\?\]:[a-f0-9]+ key `K2', value `V2 2' at cookie 2/[0-9]+;[0-9]+@[a-f0-9]+ (re) + EACH: _farr_KV\[\?,\?\]:[a-f0-9]+ key `K3', value `" 111222333" \\'444555 ' at cookie 3/[0-9]+;[0-9]+@[a-f0-9]+ (re) + + $ falist_clear LIST + + $ falist_release LIST + $ falist_release LIST + ERROR: object `LIST' not created properly: token empty + [1] + $ check_no_alist_artifacts + + +Deleting +======== + + $ falist_create LIST + $ (falist_trydel LIST foo) + [1] + + $ falist_release LIST + $ check_no_alist_artifacts + + $ falist_create LIST K1 V1 + $ (falist_trydel LIST foo) + [1] + $ falist_debug LIST + DEBUG: alist `LIST' has length 1 + DEBUG: the items: + DEBUG: `K1' -> `V1' + $ falist_istrue LIST + $ falist_trydel LIST K1 + $ falist_debug LIST + DEBUG: alist `LIST' has length 0 + $ check_no_alist_artifacts + _farr_KV_[a-f0-9]+_B=0 (re) + _farr_KV_[a-f0-9]+_C=1 (re) + _farr_KV_[a-f0-9]+_P='0;0' (re) + _farr_KV_[a-f0-9]+__=0 (re) + [1] + $ (falist_istrue LIST) + [1] + $ falist_release LIST + $ check_no_alist_artifacts + + $ falist_create LIST K1 V1 K2 V2 + $ (falist_trydel LIST foo) + [1] + $ falist_trydel LIST K1 + $ falist_debug LIST + DEBUG: alist `LIST' has length 1 + DEBUG: the items: + DEBUG: `K2' -> `V2' + $ falist_trydel LIST K2 + $ falist_debug LIST + DEBUG: alist `LIST' has length 0 + $ falist_release LIST + $ check_no_alist_artifacts + + $ falist_create LIST K1 V1 K2 V2 + $ (falist_trydel LIST foo) + [1] + $ falist_trydel LIST K2 + $ falist_debug LIST + DEBUG: alist `LIST' has length 1 + DEBUG: the items: + DEBUG: `K1' -> `V1' + $ falist_trydel LIST K1 + $ falist_debug LIST + DEBUG: alist `LIST' has length 0 + $ falist_release LIST + $ check_no_alist_artifacts + + $ falist_create LIST K1 V1 K2 V2 K3 V3 + $ (falist_trydel LIST foo) + [1] + $ falist_trydel LIST K1 + $ falist_debug LIST + DEBUG: alist `LIST' has length 2 + DEBUG: the items: + DEBUG: `K2' -> `V2' + DEBUG: `K3' -> `V3' + $ falist_release LIST + $ check_no_alist_artifacts + + $ falist_create LIST K1 V1 K2 V2 K3 V3 + $ (falist_trydel LIST foo) + [1] + $ falist_trydel LIST K2 + $ falist_debug LIST + DEBUG: alist `LIST' has length 2 + DEBUG: the items: + DEBUG: `K1' -> `V1' + DEBUG: `K3' -> `V3' + $ falist_release LIST + $ check_no_alist_artifacts + + $ falist_create LIST K1 V1 K2 V2 K3 V3 + $ (falist_trydel LIST foo) + [1] + $ falist_trydel LIST K3 + $ falist_debug LIST + DEBUG: alist `LIST' has length 2 + DEBUG: the items: + DEBUG: `K1' -> `V1' + DEBUG: `K2' -> `V2' + $ falist_release LIST + $ check_no_alist_artifacts + + $ falist_create LIST K1 V1 K2 V2 K3 V3 + $ (falist_trydel LIST foo) + [1] + $ falist_trydel LIST K2 + $ falist_trydel LIST K1 + $ falist_trydel LIST K3 + $ falist_debug LIST + DEBUG: alist `LIST' has length 0 +Check that the binary search list is cleaned up + $ check_no_alist_artifacts + _farr_KV_[a-f0-9]+_B=0 (re) + _farr_KV_[a-f0-9]+_C=1 (re) + _farr_KV_[a-f0-9]+_P='0;0' (re) + _farr_KV_[a-f0-9]+__=0 (re) + [1] + $ falist_release LIST + $ check_no_alist_artifacts + + $ falist_create LIST K1 V1 K2 V2 K3 V3 + $ (falist_trydel LIST foo) + [1] + $ falist_trydel LIST K2 +Skipping tombstones + $ (falist_trydel LIST K2) + [1] + $ falist_trydel LIST K3 + $ (falist_trydel LIST K3) + [1] + $ falist_debug LIST + DEBUG: alist `LIST' has length 1 + DEBUG: the items: + DEBUG: `K1' -> `V1' +Check that the binary search list is cleaned up properly: just the first +storage entries are left + $ check_no_alist_artifacts + _farr_KV_[a-f0-9]+_B=1 (re) + _farr_KV_[a-f0-9]+_C=1 (re) + _farr_KV_[a-f0-9]+_P='1;1' (re) + _farr_KV_[a-f0-9]+__=1 (re) + _farr_Kb_[a-f0-9]+_1='1;V@K1' (re) + _farr_Ks_[a-f0-9]+_1='0;0@K1' (re) + _farr_Vs_[a-f0-9]+_1=V1 (re) + [1] +Can re-add K2 now again + $ falist_add LIST K2 'V2 2' + $ falist_release LIST + $ check_no_alist_artifacts + +Try this with reversed insertion order also + + $ falist_create LIST K3 V3 K2 V2 K1 V1 + $ falist_find _var LIST K3 +Cookie has structure <storage-ptr>/<storage-prev-ptr>;<storage-next-ptr>@<object-token> + $ echo "$_var" + 1/[0-9]+;[0-9]+@[a-f0-9]+ (re) + $ falist_contains LIST K3 + $ falist_find _var LIST K2 + $ echo "$_var" + 2/[0-9]+;[0-9]+@[a-f0-9]+ (re) + $ falist_contains LIST K2 + $ falist_find _var LIST K1 + $ echo "$_var" + 3/[0-9]+;[0-9]+@[a-f0-9]+ (re) + $ falist_contains LIST K1 + $ (falist_trydel LIST foo) + [1] + $ falist_trydel LIST K2 +Skipping tombstones + $ (falist_trydel LIST K2) + [1] + $ falist_trydel LIST K3 + $ (falist_trydel LIST K3) + [1] + $ falist_debug LIST + DEBUG: alist `LIST' has length 1 + DEBUG: the items: + DEBUG: `K1' -> `V1' +Check that the binary search list is cleaned up properly: just the first +storage entries are left + $ check_no_alist_artifacts + _farr_KV_[a-f0-9]+_B=1 (re) + _farr_KV_[a-f0-9]+_C=1 (re) + _farr_KV_[a-f0-9]+_P='3;3' (re) + _farr_KV_[a-f0-9]+__=1 (re) + _farr_Kb_[a-f0-9]+_1='3;V@K1' (re) + _farr_Ks_[a-f0-9]+_3='0;0@K1' (re) + _farr_Vs_[a-f0-9]+_3=V1 (re) + [1] +Can re-add K2 now again + $ falist_add LIST K2 'V2 2' + $ falist_find _var LIST K2 + $ falist_contains LIST K2 +But K3 is tombstoned/deleted + $ (falist_find _var LIST K3) + [1] + $ (falist_contains LIST K3) + [1] + $ farray_create ARRAY + $ falist_keys ARRAY LIST + $ farray_debug ARRAY + DEBUG: array `ARRAY' has length 2 + DEBUG: the items: + DEBUG: 1: `K1' + DEBUG: 2: `K2' + $ farray_release ARRAY + $ farray_create ARRAY + $ falist_values ARRAY LIST + $ farray_debug ARRAY + DEBUG: array `ARRAY' has length 2 + DEBUG: the items: + DEBUG: 1: `V1' + DEBUG: 2: `V2 2' + $ farray_release ARRAY + $ farray_create ARRAY + $ falist_items ARRAY LIST + $ farray_debug ARRAY + DEBUG: array `ARRAY' has length 4 + DEBUG: the items: + DEBUG: 1: `K1' + DEBUG: 2: `V1' + DEBUG: 3: `K2' + DEBUG: 4: `V2 2' + $ farray_release ARRAY + $ falist_release LIST + $ check_no_alist_artifacts + $ check_no_array_artifacts + + Get / Set / Contains / Find Index ================================= @@ -108,11 +635,12 @@ 3 (no-eol) $ falist_contains LIST K1 - $ falist_find idx LIST K1 - $ test "$idx" -eq 1 + $ falist_find cookie LIST K1 + $ echo "$cookie" + 1/[0-9]+;[0-9]+@[a-f0-9]+ (re) $ falist_contains LIST K [1] - $ falist_find idx LIST K + $ falist_find cookie LIST K [1] $ falist_get _var LIST K2 $ echo "$_var" @@ -123,17 +651,17 @@ $ falist_tryget _i LIST K [1] - $ falist_get _var LIST K2 _idx + $ falist_get _var LIST K2 _cookie $ echo "$_var" V2 2 - $ echo "$_idx" - 2 - $ falist_tryget _var LIST K1 _idx + $ echo "$_cookie" + 2/[0-9]+;[0-9]+@[a-f0-9]+ (re) + $ falist_tryget _var LIST K1 _cookie $ echo "$_var" V1 - $ echo "$_idx" - 1 - $ falist_tryget _i LIST K _idx + $ echo "$_cookie" + 1/[0-9]+;[0-9]+@[a-f0-9]+ (re) + $ falist_tryget _i LIST K _cookie [1] $ _var="$(falist_print_length NON_EXISTING_LIST)" ERROR: object `NON_EXISTING_LIST' not created properly: token empty @@ -150,160 +678,39 @@ $ falist_release LIST $ check_no_alist_artifacts -Special case empty list (because of start/stop extra indexes) - $ falist_create LIST - $ falist_find _var LIST foo - [1] - $ falist_release LIST - $ check_no_alist_artifacts - - -Add -=== - - $ falist_create LIST - $ falist_add LIST K1 'V 1' - $ falist_add LIST K2 'V 2' - $ falist_add LIST K3 $'" 111222333" \\\'444555666 ' # ' - $ falist_debug LIST - DEBUG: alist `LIST' has length 3 - DEBUG: the items: - DEBUG: `K1' -> `V 1' - DEBUG: `K2' -> `V 2' - DEBUG: `K3' -> `" 111222333" \'444555666 ' -Yes: make a duplicate key - $ falist_add LIST K3 $'" 111222333" \\\'444555666 ' # - $ falist_debug LIST - DEBUG: alist `LIST' has length 4 - DEBUG: the items: - DEBUG: `K1' -> `V 1' - DEBUG: `K2' -> `V 2' - DEBUG: `K3' -> `" 111222333" \'444555666 ' - DEBUG: `K3' -> `" 111222333" \'444555666 ' - $ falist_release LIST - $ check_no_alist_artifacts - - -Iteration -========= - -ITERATE (manual indexing) - - $ falist_create LIST - $ falist_set LIST K1 V1 - $ falist_set LIST K2 "V2 2" - $ falist_set LIST K3 $'" 111222333" \\\'444555 ' # ' - -Iteration by indexing key and values separately - - $ _i=1 - > while falist_tryget_key_at_index _k LIST ${_i}; do - > # cannot fail under "normal" circumstances - > falist_tryget_value_at_index _v LIST ${_i} - > printf " KEY: \`%s', VAL: \`%s'\\n" "${_k}" "${_v}" - > _i=$((_i + 1)) - > done - KEY: `K1', VAL: `V1' - KEY: `K2', VAL: `V2 2' - KEY: `K3', VAL: `" 111222333" \'444555 ' - -ITERATE (manual indexing over items) +Items / Keys / Values +===================== - $ _i=1 - > while falist_tryget_item_at_index _k _v LIST ${_i}; do - > printf " KEY: \`%s', VAL: \`%s'\\n" "${_k}" "${_v}" - > _i=$((_i + 1)) - > done - KEY: `K1', VAL: `V1' - KEY: `K2', VAL: `V2 2' - KEY: `K3', VAL: `" 111222333" \'444555 ' - -ITERATE (for each, by name) - - $ falist_for_each LIST $'printf "EACH: %s key \\`%s\\\', value \\`%s\\\' at idx %d\\n"' # ` - EACH: LIST key `K1', value `V1' at idx 1 - EACH: LIST key `K2', value `V2 2' at idx 2 - EACH: LIST key `K3', value `" 111222333" \'444555 ' at idx 3 - -ITERATE (for each, by value) - - $ falist_for_each "$LIST" $'printf "EACH: %s key \\`%s\\\', value \\`%s\\\' at idx %d\\n"' # ` - EACH: _farr_KV\[\?,\?\]:[a-f0-9]+ key `K1', value `V1' at idx 1 (re) - EACH: _farr_KV\[\?,\?\]:[a-f0-9]+ key `K2', value `V2 2' at idx 2 (re) - EACH: _farr_KV\[\?,\?\]:[a-f0-9]+ key `K3', value `" 111222333" \\'444555 ' at idx 3 (re) - - $ falist_clear LIST - $ falist_release LIST - $ falist_release LIST - ERROR: object `LIST' not created properly: token empty - [1] - - $ check_no_alist_artifacts - - -Valid and Invalid Indices - - $ falist_create LIST - $ falist_set LIST 'KEY 1' 'VAL 1' - $ falist_set LIST 'KEY 2' 'VAL 2' - $ falist_set LIST 'KEY 3' 'VAL 3' - - $ (falist_tryget_item_at_index _k _v LIST "") - ERROR: missing index - [70] - - $ (falist_tryget_item_at_index _k _v LIST) - ERROR: missing index - [70] - - $ falist_tryget_item_at_index _k _v LIST 4 - [1] - - $ falist_tryget_item_at_index _k _v LIST 0 - $ printf '%s:%s' "$_k" "$_v" - KEY 3:VAL 3 (no-eol) - - $ falist_tryget_item_at_index _k _v LIST -2 - $ printf '%s:%s' "$_k" "$_v" - KEY 1:VAL 1 (no-eol) - - $ falist_tryget_item_at_index _k _v LIST -3 - [1] + $ farray_create KEYS + $ farray_create VALUES + $ farray_create ITEMS + $ falist_create LIST "Key 1" "Value 1" "Key 2" 'Value 2 '\''' + $ falist_items ITEMS LIST + $ farray_debug ITEMS + DEBUG: array `ITEMS' has length 4 + DEBUG: the items: + DEBUG: 1: `Key 1' + DEBUG: 2: `Value 1' + DEBUG: 3: `Key 2' + DEBUG: 4: `Value 2 '' + $ falist_keys KEYS LIST + $ farray_debug KEYS + DEBUG: array `KEYS' has length 2 + DEBUG: the items: + DEBUG: 1: `Key 1' + DEBUG: 2: `Key 2' + $ falist_values VALUES LIST + $ farray_debug VALUES + DEBUG: array `VALUES' has length 2 + DEBUG: the items: + DEBUG: 1: `Value 1' + DEBUG: 2: `Value 2 '' $ falist_release LIST - $ check_no_alist_artifacts - - -Deletion of keys -================ - - $ falist_create LIST - $ falist_set LIST 'key 1' 'value 1' - $ falist_set LIST 'key 2' 'value 2' - $ falist_set LIST 'key 3' 'value 3' - $ falist_set LIST 'key 4' 'value 4' - $ falist_set LIST 'key 5' 'value 5' - $ falist_trydel LIST 'key 1' - $ falist_trydel LIST 'key 5' - $ falist_trydel LIST 'key 3' - $ falist_debug LIST - DEBUG: alist `LIST' has length 2 - DEBUG: the items: - DEBUG: `key 2' -> `value 2' - DEBUG: `key 4' -> `value 4' - $ falist_trydel LIST "non-existing key" - [1] - $ falist_print_length LIST - 2 (no-eol) - $ falist_get _var LIST 'key 2' - $ printf '%s' "$_var" - value 2 (no-eol) - $ falist_get _var LIST 'key 4' - $ printf '%s' "$_var" - value 4 (no-eol) - - $ falist_release LIST + $ farray_release KEYS + $ farray_release VALUES + $ farray_release ITEMS $ check_no_alist_artifacts @@ -364,191 +771,123 @@ Updating ======== - $ falist_create ARR "Key 1" "Value 1" "Key 2" 'Value 2 '\''' - $ falist_create UPDATE1 "Key 1" "Value 1" "Key 2" 'Value 2 '\''' - $ falist_create UPDATE2 "Key 2" 'Value 2 (Updated) '\''' "Key 3" "Value 3" - $ falist_create EMPTY - - $ falist_are_equal_with_order ARR UPDATE1 - $ falist_are_equal_with_order ARR UPDATE2 - [1] +Just replace existing items - $ falist_update ARR UPDATE1 - $ falist_are_equal_with_order ARR UPDATE1 - - $ falist_update ARR UPDATE2 - $ falist_debug ARR - DEBUG: alist `ARR' has length 3 + $ falist_create LIST k2 v2 k4 v4 k6 v6 k8 v8 + $ falist_debug LIST + DEBUG: alist `LIST' has length 4 DEBUG: the items: - DEBUG: `Key 1' -> `Value 1' - DEBUG: `Key 2' -> `Value 2 (Updated) '' - DEBUG: `Key 3' -> `Value 3' + DEBUG: `k2' -> `v2' + DEBUG: `k4' -> `v4' + DEBUG: `k6' -> `v6' + DEBUG: `k8' -> `v8' -Updating an into an empty alist is just a copy - - $ falist_update EMPTY UPDATE1 - $ falist_debug EMPTY - DEBUG: alist `EMPTY' has length 2 + $ falist_create UPDATE1 k2 v2-2 k4 v4-2 k8 v8-2 + $ falist_update LIST UPDATE1 + $ falist_debug LIST + DEBUG: alist `LIST' has length 4 DEBUG: the items: - DEBUG: `Key 1' -> `Value 1' - DEBUG: `Key 2' -> `Value 2 '' - $ falist_debug UPDATE1 - DEBUG: alist `UPDATE1' has length 2 - DEBUG: the items: - DEBUG: `Key 1' -> `Value 1' - DEBUG: `Key 2' -> `Value 2 '' + DEBUG: `k2' -> `v2-2' + DEBUG: `k4' -> `v4-2' + DEBUG: `k6' -> `v6' + DEBUG: `k8' -> `v8-2' - $ falist_release ARR + $ falist_release LIST $ falist_release UPDATE1 - $ falist_release UPDATE2 - $ falist_release EMPTY - $ check_no_alist_artifacts -Merging -======= - - $ falist_create RES - $ falist_create INPUT1 "K1" "V1" "K2" "V2" "K3" "V3" - $ falist_create INPUT2 - $ falist_merge "$RES" "$INPUT1" "$INPUT2" - $ falist_release INPUT1 - $ falist_release INPUT2 - $ falist_debug RES - DEBUG: alist `RES' has length 3 - DEBUG: the items: - DEBUG: `K1' -> `V1' - DEBUG: `K2' -> `V2' - DEBUG: `K3' -> `V3' - $ falist_release RES - $ check_no_alist_artifacts +Handle previously deleted items also - $ falist_create RES - $ falist_create INPUT1 - $ falist_create INPUT2 "k1" "v1" "k2" "v2" "k3" "v3" - $ falist_merge "$RES" "$INPUT1" "$INPUT2" - $ falist_release INPUT1 - $ falist_release INPUT2 - $ falist_debug RES - DEBUG: alist `RES' has length 3 + $ falist_create LIST k2 v2 k4 v4 k6 v6 k8 v8 + $ falist_trydel LIST k2 + $ falist_create UPDATE1 k2 v2-2 k4 v4-2 k8 v8-2 + $ falist_update LIST UPDATE1 + $ falist_debug LIST + DEBUG: alist `LIST' has length 4 DEBUG: the items: - DEBUG: `k1' -> `v1' - DEBUG: `k2' -> `v2' - DEBUG: `k3' -> `v3' - $ falist_release RES - $ check_no_alist_artifacts + DEBUG: `k4' -> `v4-2' + DEBUG: `k6' -> `v6' + DEBUG: `k8' -> `v8-2' + DEBUG: `k2' -> `v2-2' - $ falist_create RES - $ falist_create INPUT1 "K1" "V1" "K2" "V2" "K3" "V3" - $ falist_create INPUT2 "k1" "v1" "k2" "v2" "k3" "v3" "k4" "v4" - $ falist_merge "$RES" "$INPUT1" "$INPUT2" - $ falist_release INPUT1 - $ falist_release INPUT2 - $ falist_debug RES - DEBUG: alist `RES' has length 7 - DEBUG: the items: - DEBUG: `K1' -> `V1' - DEBUG: `K2' -> `V2' - DEBUG: `K3' -> `V3' - DEBUG: `k1' -> `v1' - DEBUG: `k2' -> `v2' - DEBUG: `k3' -> `v3' - DEBUG: `k4' -> `v4' - $ falist_release RES + $ falist_release LIST + $ falist_release UPDATE1 $ check_no_alist_artifacts - $ falist_create RES - $ falist_create INPUT1 "k1" "v1" "k2" "v2" "k3" "v3" "k4" "v4" - $ falist_create INPUT2 "K1" "V1" "K2" "V2" "K3" "V3" - $ falist_merge "$RES" "$INPUT1" "$INPUT2" - $ falist_release INPUT1 - $ falist_release INPUT2 - $ falist_debug RES - DEBUG: alist `RES' has length 7 - DEBUG: the items: - DEBUG: `K1' -> `V1' - DEBUG: `K2' -> `V2' - DEBUG: `K3' -> `V3' - DEBUG: `k1' -> `v1' - DEBUG: `k2' -> `v2' - DEBUG: `k3' -> `v3' - DEBUG: `k4' -> `v4' - $ falist_release RES - $ check_no_alist_artifacts - - $ falist_create RES - $ falist_create INPUT1 "K1" "V1" "K3" "V3" "k1" "v1" "k4" "v4" - $ falist_create INPUT2 "K2" "V2" "k2" "v2" "k3" "v3" - $ falist_merge "$RES" "$INPUT1" "$INPUT2" - $ falist_release INPUT1 - $ falist_release INPUT2 - $ falist_debug RES - DEBUG: alist `RES' has length 7 + $ falist_create LIST k2 v2 k4 v4 k6 v6 k8 v8 + $ falist_trydel LIST k4 + $ falist_create UPDATE1 k2 v2-2 k4 v4-2 k8 v8-2 + $ falist_update LIST UPDATE1 + $ falist_debug LIST + DEBUG: alist `LIST' has length 4 DEBUG: the items: - DEBUG: `K1' -> `V1' - DEBUG: `K2' -> `V2' - DEBUG: `K3' -> `V3' - DEBUG: `k1' -> `v1' - DEBUG: `k2' -> `v2' - DEBUG: `k3' -> `v3' - DEBUG: `k4' -> `v4' - $ falist_release RES - $ check_no_alist_artifacts + DEBUG: `k2' -> `v2-2' + DEBUG: `k6' -> `v6' + DEBUG: `k8' -> `v8-2' + DEBUG: `k4' -> `v4-2' - $ falist_create RES - $ falist_create INPUT1 "K1" "V1" "K3" "V3" "k1" "v1" "k4" "v4" - $ falist_create INPUT2 "K2" "V2" "k2" "v2" "k3" "v3" - $ falist_merge "$RES" INPUT2 INPUT1 - $ falist_release INPUT1 - $ falist_release INPUT2 - $ falist_debug RES - DEBUG: alist `RES' has length 7 - DEBUG: the items: - DEBUG: `K1' -> `V1' - DEBUG: `K2' -> `V2' - DEBUG: `K3' -> `V3' - DEBUG: `k1' -> `v1' - DEBUG: `k2' -> `v2' - DEBUG: `k3' -> `v3' - DEBUG: `k4' -> `v4' - $ falist_release RES + $ falist_release LIST + $ falist_release UPDATE1 $ check_no_alist_artifacts -Items / Keys / Values -===================== +Just appending - $ farray_create KEYS - $ farray_create VALUES - $ farray_create ITEMS - $ falist_create LIST "Key 1" "Value 1" "Key 2" 'Value 2 '\''' - $ falist_items ITEMS LIST - $ farray_debug ITEMS - DEBUG: array `ITEMS' has length 4 + $ falist_create LIST k2 v2 k4 v4 k6 v6 k8 v8 + $ falist_create UPDATE1 k9 v9 k91 v91 + $ falist_update LIST UPDATE1 + $ falist_debug LIST + DEBUG: alist `LIST' has length 6 DEBUG: the items: - DEBUG: 1: `Key 1' - DEBUG: 2: `Value 1' - DEBUG: 3: `Key 2' - DEBUG: 4: `Value 2 '' - $ falist_keys KEYS LIST - $ farray_debug KEYS - DEBUG: array `KEYS' has length 2 - DEBUG: the items: - DEBUG: 1: `Key 1' - DEBUG: 2: `Key 2' - $ falist_values VALUES LIST - $ farray_debug VALUES - DEBUG: array `VALUES' has length 2 - DEBUG: the items: - DEBUG: 1: `Value 1' - DEBUG: 2: `Value 2 '' + DEBUG: `k2' -> `v2' + DEBUG: `k4' -> `v4' + DEBUG: `k6' -> `v6' + DEBUG: `k8' -> `v8' + DEBUG: `k9' -> `v9' + DEBUG: `k91' -> `v91' $ falist_release LIST - $ farray_release KEYS - $ farray_release VALUES - $ farray_release ITEMS + $ falist_release UPDATE1 + $ check_no_alist_artifacts + + +Append after deletion + + $ falist_create LIST k2 v2 k4 v4 k6 v6 k8 v8 + $ falist_trydel LIST k8 + $ falist_create UPDATE1 k2 v2-2 k4 v4-2 k8 v8-2 + $ falist_update LIST UPDATE1 + $ falist_debug LIST + DEBUG: alist `LIST' has length 4 + DEBUG: the items: + DEBUG: `k2' -> `v2-2' + DEBUG: `k4' -> `v4-2' + DEBUG: `k6' -> `v6' + DEBUG: `k8' -> `v8-2' + $ falist_release LIST + $ falist_release UPDATE1 + $ check_no_alist_artifacts + +Insertions + + $ falist_create LIST k2 v2 k4 v4 k6 v6 k8 v8 + $ falist_create UPDATE1 k1 v1 k3 v3 k7 v7 + $ falist_update LIST UPDATE1 + $ falist_debug LIST + DEBUG: alist `LIST' has length 7 + DEBUG: the items: + DEBUG: `k2' -> `v2' + DEBUG: `k4' -> `v4' + DEBUG: `k6' -> `v6' + DEBUG: `k8' -> `v8' + DEBUG: `k1' -> `v1' + DEBUG: `k3' -> `v3' + DEBUG: `k7' -> `v7' + + $ falist_release LIST + $ falist_release UPDATE1 $ check_no_alist_artifacts
--- a/tests/testsetup.sh Fri Oct 18 14:02:18 2024 +0200 +++ b/tests/testsetup.sh Sat Oct 19 22:40:11 2024 +0200 @@ -27,7 +27,7 @@ #: check_no_alist_artifacts() { # This are all _farr_alist_XXX_prefix variables - if set | grep -E -e '^_farr_KV_.*=' -e '^_farr_K_.*=' -e '^_farr_V_.*='; then + if set | grep -E -e '^_farr_KV_.*=' -e '^_farr_Kb_.*=' -e '^_farr_Ks_.*=' -e '^_farr_Vs_.*='; then return 1 else return 0