A stack? In bash?

For reasons I won’t go into here, I needed a simple stack implementation. In bash.

Now, stack implementations aren’t difficult, and bash does have arrays. But bash does not have classes or objects, and I wanted a general-purpose solution, not a quick-and-dirty, one-use hack.

The specification

The specification for my stack implementation is simple and straightforward. I wanted the following functions:

stack_new name: Create a stack with the specified name. The name is akin to variable name and follows the same naming conventions.
stack_push name value ...: Push one or more values onto the stack called name.
stack_pop name variable: Pop the top value from the stack called name, storing the result in the named variable.
stack_destroy name: Destroy the stack called name
stack_size name variable: Store the size of the stack called name in the specified variable.
stack_print name: Display the contents of the stack called name on stdout.

I didn’t bother with stack_clear, since stack_destroy followed by stack_create is good enough. It’d be simple enough to add a stack_clear function, though.

Example

stack_new foo
stack_push foo 10 20 30
stack_print foo          # prints: ( 30 20 10 )
stack_pop foo i          # i is now 30. Stack is now ( 30 20 )

The implementation

The implementation is, to put it bluntly, rather ugly. But, as my first boss (many years ago) was fond of saying, “If the solution has to be ugly, at least hide the ugly.” The ugly is hidden in the implementation, where I don’t have to look at it.

So, without further ado, here’s the code:

# A stack, using bash arrays. # --------------------------------------------------------------------------- # Create a new stack. # # Usage: stack_new name # # Example: stack_new x function stack_new { : ${1?'Missing stack name'} if stack_exists $1 then echo "Stack already exists -- $1" >&2 return 1 fi eval "declare -ag _stack_$1" eval "declare -ig _stack_$1_i" eval "let _stack_$1_i=0" return 0 } # Destroy a stack # # Usage: stack_destroy name function stack_destroy { : ${1?'Missing stack name'} eval "unset _stack_$1 _stack_$1_i" return 0 } # Push one or more items onto a stack. # # Usage: stack_push stack item ... function stack_push { : ${1?'Missing stack name'} : ${2?'Missing item(s) to push'} if no_such_stack $1 then echo "No such stack -- $1" >&2 return 1 fi stack=$1 shift 1 while (( $# > 0 )) do eval '_i=$'"_stack_${stack}_i" eval "_stack_${stack}[$_i]='$1'" eval "let _stack_${stack}_i+=1" shift 1 done unset _i return 0 } # Print a stack to stdout. # # Usage: stack_print name function stack_print { : ${1?'Missing stack name'} if no_such_stack $1 then echo "No such stack -- $1" >&2 return 1 fi tmp="" eval 'let _i=$'_stack_$1_i while (( $_i > 0 )) do let _i=${_i}-1 eval 'e=$'"{_stack_$1[$_i]}" tmp="$tmp $e" done echo "(" $tmp ")" } # Get the size of a stack # # Usage: stack_size name var # # Example: # stack_size mystack n # echo "Size is $n" function stack_size { : ${1?'Missing stack name'} : ${2?'Missing name of variable for stack size result'} if no_such_stack $1 then echo "No such stack -- $1" >&2 return 1 fi eval "$2"='$'"{#_stack_$1[*]}" } # Pop the top element from the stack. # # Usage: stack_pop name var # # Example: # stack_pop mystack top # echo "Got $top" function stack_pop { : ${1?'Missing stack name'} : ${2?'Missing name of variable for popped result'} eval 'let _i=$'"_stack_$1_i" if no_such_stack $1 then echo "No such stack -- $1" >&2 return 1 fi if [[ "$_i" -eq 0 ]] then echo "Empty stack -- $1" >&2 return 1 fi let _i-=1 eval "$2"='$'"{_stack_$1[$_i]}" eval "unset _stack_$1[$_i]" eval "_stack_$1_i=$_i" unset _i return 0 } function no_such_stack { : ${1?'Missing stack name'} stack_exists $1 ret=$? declare -i x let x="1-$ret" return $x } function stack_exists { : ${1?'Missing stack name'} eval '_i=$'"_stack_$1_i" if [[ -z "$_i" ]] then return 1 else return 0 fi }

The code is also checked into my GitHub lib-sh repository, as stack.sh.

Brizzled

... wherein I bloviate discursively

A bash stack

A stack? In bash?

The specification

Example

The implementation

Comments