pure bash 3 associative array with constant time fetch

Question

Here is a bash3 associative array hack which satisfies:

• pure bash (no fork/exec)
• no subshell
• constant time fetch (in terms of number of keys)
• any metachars allowed in keys

The basic idea is to encode keys by substituting non-identifier chars with their hex value, and then use the sanitized key (with a name prefix) as a bash local var, leveraging the constant time bash name lookup.

enc-key()
{
    local key="${1}"  varname="${2:-_rval}"  prefix="${3:-_ENCKEY_}"
    local i  converted
    local -a enc_parts  convert
    local re='^([[:alnum:]]*)([^[:alnum:]]+)(.*)'
    local nonalnum
    enc_parts+=( "${prefix}" )
    while [[ $key =~ $re ]]; do
        enc_parts+=( "${BASH_REMATCH[1]}" )
        nonalnum="${BASH_REMATCH[2]}"
        key="${BASH_REMATCH[3]}"
        convert=()
        for (( i = 0; i < ${#nonalnum}; i++ )); do
            # leading ' in string signals printf to covert char to ascii
            convert+=( "'${nonalnum:$i:1}" )
        done
        printf -v converted "_%x" "${convert[@]}"
        enc_parts+=( "${converted}" )
    done
    enc_parts+=( "${key}" )
    printf -v $varname "%s" "${enc_parts[@]}"
    echo "DEBUG: final key: ${!varname}"
    return 0
}

To store:

    local key
    enc-key 'my-fine-key!' key
    local "${key}=value"

Fetch (before exiting function scope of the store):

    enc-key 'some other key' key
    fetched="${!key}"

Note that the second arg of enc-key is the name of the var into which enc-key will store the sanitized key.

The question: is there a way to do the encoding that does not involve character based traversal with many re matches along the way? Either some printf magic or var sub voodoo?

Answer 1

On surface, the bash3 constraint implied legacy platform. The no-fork constraint prevent using one of the other scripting solution (awk, Perl or python, ...) that have much better support for character level transformations.

One simple alternative is to process all characters in a loop. On surface, this is faster than using RE to identify sequences non-alpha numeric which need to be manipulated.

On my (bash4) machine, this is running 2X

enc-key()
{
    local key="${1}"  varname="${2:-_rval}"  prefix="${3:-_ENCKEY_}"
    local i  converted
    local -a enc_parts  convert
    local re='^([[:alnum:]]*)([^[:alnum:]]+)(.*)'
    local nonalnum
    enc_parts+=( "${prefix}" )
    local key_len=${#key}
    for ((i=0 ; i<key_len ; i++)) do 
        local ch=${key:i:1}
        case "$ch" in
            [a-zA-Z0-9]) ;;
            *)  printf -v ch '_%02x' "'$ch'" ;;
        esac
        enc_parts+=($ch)
    done
    printf -v $varname "%s" "${enc_parts[@]}"
    #echo "DEBUG: final key: ${!varname}"
    return 0
}

Answer 2

As an alternative, fast solution for both bash3 and bash4, using the "global replace" operator, available in bash3.2 and above. It looks for characters to escape, and uses global replace to encode all instances with one go.

On my machine: - 1000 calls to enc-key

• Original solution: 0.39 sec
• Using patterns: 0.19 sec - 52% speed up
• Using global replace: 0.09 sec - 78% speedup

The interesting thing about the global replace is that performance is (almost) linear to the number of distinct character to escape, vs the pattern solution (linear to the length of the string), and the regex solution (linear to the number of characters to escape).

enc-key()
{
        local key="${1}" varname="${2:-_rval}" prefix="${3:-_ENCKEY_}"
        local unsafe=${key//[a-zA-Z0-9]/}
        local -i key_len=${#unsafe}
        local ch ch1

        while [ "$unsafe" ] ;do
                ch=${unsafe:0:1}
                printf -v ch1 '_%02x' "'$ch'"
                key=${key//"$ch"/"$ch1"}
                unsafe=${unsafe/"$ch"}
        done

        printf -v $varname "%s" "$prefix" "$key"
        #echo "DEBUG: final key: ${!varname}"
        return 0
}