.\" $OpenBSD: OPENSSL_sk_new.3,v 1.10 2018/08/08 18:21:02 tb Exp $
.\"
.\" Copyright (c) 2018 Ingo Schwarze <schwarze@openbsd.org>
.\"
.\" Permission to use, copy, modify, and distribute this software for any
.\" purpose with or without fee is hereby granted, provided that the above
.\" copyright notice and this permission notice appear in all copies.
.\"
.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
.\"
.Dd $Mdocdate: August 8 2018 $
.Dt OPENSSL_SK_NEW 3
.Os
.Sh NAME
.Nm sk_new_null ,
.Nm sk_new ,
.Nm sk_set_cmp_func ,
.Nm sk_dup ,
.Nm sk_free ,
.Nm sk_pop_free ,
.Nm sk_num ,
.Nm sk_value ,
.Nm sk_find ,
.Nm sk_find_ex ,
.Nm sk_sort ,
.Nm sk_is_sorted ,
.Nm sk_push ,
.Nm sk_unshift ,
.Nm sk_insert ,
.Nm sk_set ,
.Nm sk_pop ,
.Nm sk_shift ,
.Nm sk_delete ,
.Nm sk_delete_ptr ,
.Nm sk_zero
.Nd variable-sized arrays of void pointers, called OpenSSL stacks
.Sh SYNOPSIS
.In openssl/stack.h
.Ft _STACK *
.Fn sk_new_null void
.Ft _STACK *
.Fo sk_new
.Fa "int (*compfunc)(const void *, const void *)"
.Fc
.Ft old_function_pointer
.Fo sk_set_cmp_func
.Fa "_STACK *stack"
.Fa "int (*compfunc)(const void *, const void *)"
.Fc
.Ft _STACK *
.Fo sk_dup
.Fa "_STACK *stack"
.Fc
.Ft void
.Fo sk_free
.Fa "_STACK *stack"
.Fc
.Ft void
.Fo sk_pop_free
.Fa "_STACK *stack"
.Fa "void (*freefunc)(void *)"
.Fc
.Ft int
.Fo sk_num
.Fa "const _STACK *stack"
.Fc
.Ft void *
.Fo sk_value
.Fa "const _STACK *stack"
.Fa "int index"
.Fc
.Ft int
.Fo sk_find
.Fa "_STACK *stack"
.Fa "void *wanted"
.Fc
.Ft int
.Fo sk_find_ex
.Fa "_STACK *stack"
.Fa "void *wanted"
.Fc
.Ft void
.Fo sk_sort
.Fa "_STACK *stack"
.Fc
.Ft int
.Fo sk_is_sorted
.Fa "const _STACK *stack"
.Fc
.Ft int
.Fo sk_push
.Fa "_STACK *stack"
.Fa "void *new_item"
.Fc
.Ft int
.Fo sk_unshift
.Fa "_STACK *stack"
.Fa "void *new_item"
.Fc
.Ft int
.Fo sk_insert
.Fa "_STACK *stack"
.Fa "void *new_item"
.Fa "int index"
.Fc
.Ft void *
.Fo sk_set
.Fa "_STACK *stack"
.Fa "int index"
.Fa "void *new_item"
.Fc
.Ft void *
.Fo sk_pop
.Fa "_STACK *stack"
.Fc
.Ft void *
.Fo sk_shift
.Fa "_STACK *stack"
.Fc
.Ft void *
.Fo sk_delete
.Fa "_STACK *stack"
.Fa "int index"
.Fc
.Ft void *
.Fo sk_delete_ptr
.Fa "_STACK *stack"
.Fa "void *wanted"
.Fc
.Ft void
.Fo sk_zero
.Fa "_STACK *stack"
.Fc
.Sh DESCRIPTION
OpenSSL introduced an idiosyncratic concept of variable sized arrays
of pointers and somewhat misleadingly called such an array a
.Dq stack .
Intrinsically, and as documented in this manual page, OpenSSL stacks
are not type safe but only handle
.Vt void *
function arguments and return values.
.Pp
OpenSSL also provides a fragile, unusually complicated system of
macro-generated wrappers that offers superficial type safety at the
expense of extensive obfuscation, implemented using large amounts
of autogenerated code involving exceedingly ugly, nested
.Xr cpp 1
macros; see the
.Xr STACK_OF 3
manual page for details.
.Pp
The fundamental data type is the
.Vt _STACK
structure.
It stores a variable number of void pointers
and remembers the number of pointers currently stored.
It can optionally hold a pointer to a comparison function.
As long as no comparison function is installed, the order of pointers
is meaningful; as soon as a comparison function is installed, it
becomes ill-defined.
.Pp
.Fn sk_new_null
allocates and initializes a new, empty stack.
.Fn sk_new
is identical except that it also installs
.Fa compfunc
as the comparison function for the new stack object.
.Fn sk_set_cmp_func
installs
.Fa compfunc
for the existing
.Fa stack .
The
.Fa compfunc
is allowed to be
.Dv NULL ,
but the
.Fa stack
is not.
.Pp
.Fn sk_dup
creates a shallow copy of the given
.Fa stack ,
which must not be a
.Dv NULL
pointer.
It neither copies the objects pointed to from the stack nor
increases their reference counts, but merely copies the pointers.
Extreme care must be taken in order to avoid freeing the memory twice,
for example by calling
.Fn sk_free
on one copy and only calling
.Fn sk_pop_free
on the other.
.Pp
.Fn sk_free
frees the given
.Fa stack .
It does not free any of the pointers stored on the stack.
Unless these pointers are merely copies of pointers owned by
other objects, they must be freed before calling
.Fn sk_free ,
in order to avoid leaking memory.
If
.Fa stack
is a
.Dv NULL
pointer, no action occurs.
.Pp
.Fn sk_pop_free
is severely misnamed.
It does not at all do what one would expect from a function called
.Dq pop .
Instead, it does the same as
.Fn sk_free ,
except that it also calls the function
.Fa freefunc
on each of the pointers contained in the
.Fa stack .
If the calls to
.Fa freefunc
are intended to free the memory in use by the objects on the stack,
ensure that no other pointers to the same objects remain elsewhere.
.Pp
.Fn sk_find
searches the
.Fa stack
for the
.Fa wanted
pointer.
If the
.Fa stack
contains more than one copy of the
.Fa wanted
pointer, only the first match is found.
If a comparison function is installed for the stack, the stack is
first sorted with
.Fn sk_sort ,
and instead of comparing pointers, two pointers are considered to match
if the comparison function returns 0.
.Pp
.Fn sk_find_ex
is identical to
.Fn sk_find
except that if the
.Fa stack
is not empty but no match is found,
the index of some pointer considered closest to
.Fa wanted
is returned.
.Pp
.Fn sk_sort
sorts the
.Fa stack
using
.Xr qsort 3
and the installed comparison function.
If
.Fa stack
is a
.Dv NULL
pointer or already considered sorted, no action occurs.
This function can only be called if a comparison function is installed.
.Pp
.Fn sk_is_sorted
reports whether the
.Fa stack
is considered sorted.
Calling
.Fn sk_new_null
or
.Fn sk_new ,
successfuly calling
.Fn sk_push ,
.Fn sk_unshift ,
.Fn sk_insert ,
or
.Fn sk_set ,
or changing the comparison function sets the state to unsorted.
If a comparison function is installed, calling
.Fn sk_sort ,
.Fn sk_find ,
or
.Fn sk_find_ex
sets the state to sorted.
.Pp
.Fn sk_push
pushes
.Fa new_item
onto the end of the
.Fa stack ,
increasing the number of pointers by 1.
If
.Fa stack
is a
.Dv NULL
pointer, no action occurs.
.Pp
.Fn sk_unshift
inserts
.Fa new_item
at the beginning of the
.Fa stack ,
such that it gets the index 0.
The number of pointers increases by 1.
If
.Fa stack
is a
.Dv NULL
pointer, no action occurs.
.Pp
.Fn sk_insert
inserts the
.Fa new_item
into the
.Fa stack
such that it gets the given
.Fa index .
If
.Fa index
is less than 0 or greater than or equal to
.Fn sk_num stack ,
the effect is the same as for
.Fn sk_push .
If
.Fa stack
is a
.Dv NULL
pointer, no action occurs.
.Pp
.Fn sk_set
replaces the pointer with the given
.Fa index
on the
.Fa stack
with the
.Fa new_item .
The old pointer is not freed,
which may leak memory if no copy of it exists elsewhere.
If
.Fa stack
is a
.Dv NULL
pointer or if
.Fa index
is less than 0 or greater than or equal to
.Fn sk_num stack ,
no action occurs.
.Pp
.Fn sk_pop
and
.Fn sk_shift
remove the pointer with the highest or lowest index from the
.Fa stack ,
respectively, reducing the number of pointers by 1.
If
.Fa stack
is a
.Dv NULL
pointer or if it is empty, no action occurs.
.Pp
.Fn sk_delete
removes the pointer with the given
.Fa index
from the
.Fa stack ,
reducing the number of pointers by 1.
If
.Fa stack
is a
.Dv NULL
pointer or the
.Fa index
is less than 0 or greater than or equal to
.Fn sk_num stack ,
no action occurs.
.Pp
.Fn sk_delete_ptr
removes the
.Fa wanted
pointer from the
.Fa stack ,
reducing the number of pointers by 1 if it is found.
It never uses a comparison function
but only compares pointers themselves.
The
.Fa stack
pointer must not be
.Dv NULL .
.Pp
.Fn sk_zero
removes all pointers from the
.Fa stack .
It does not free any of the pointers.
Unless these pointers are merely copies of pointers owned by other
objects, they must be freed before calling
.Fn sk_zero ,
in order to avoid leaking memory.
If
.Fa stack
is a
.Dv NULL
pointer, no action occurs.
.Sh RETURN VALUES
.Fn sk_new_null ,
.Fn sk_new ,
and
.Fn sk_dup
return a pointer to the newly allocated stack object or
.Dv NULL
if insufficient memory is available.
.Pp
.Fn sk_set_cmp_func
returns a pointer to the comparison function
that was previously installed for the
.Fa stack
or
.Dv NULL
if none was installed.
.Pp
.Fn sk_num
returns the number of pointers currently stored on the
.Fa stack ,
or \-1 if
.Fa stack
is a
.Dv NULL
pointer.
.Pp
.Fn sk_value
returns the pointer with the given
.Fa index
from the
.Fa stack ,
or
.Dv NULL
if
.Fa stack
is a
.Dv NULL
pointer or if the
.Fa index
is less than 0 or greater than or equal to
.Fn sk_num stack .
.Pp
.Fn sk_find
returns the lowest index considered to match or \-1 if
.Fa stack
is a
.Dv NULL
pointer or if no match is found.
.Pp
.Fn sk_find_ex
returns some index or \-1 if
.Fa stack
is a
.Dv NULL
pointer or empty.
.Pp
.Fn sk_is_sorted
returns 1 if the
.Fa stack
is considered sorted or if it is a
.Dv NULL
pointer, or 0 otherwise.
.Pp
.Fn sk_push ,
.Fn sk_unshift ,
and
.Fn sk_insert
return the new number of pointers on the
.Fa stack
or 0 if
.Fa stack
is a
.Dv NULL
pointer or if memory allocation fails.
.Pp
.Fn sk_set
returns
.Fa new_item
or
.Dv NULL
if
.Fa stack
is a
.Dv NULL
pointer or if the
.Fa index
is less than 0 or greater than or equal to
.Fn sk_num stack .
.Pp
.Fn sk_pop
and
.Fn sk_shift
return the deleted pointer or
.Dv NULL
if
.Fa stack
is a
.Dv NULL
pointer or if it is empty.
.Pp
.Fn sk_delete
returns the deleted pointer or
.Dv NULL
if
.Fa stack
is a
.Dv NULL
pointer or if the
.Fa index
is less than 0 or greater than or equal to
.Fn sk_num stack .
.Pp
.Fn sk_delete_ptr
returns
.Fa wanted
or
.Dv NULL
if it is not found.
.Sh HISTORY
.Fn sk_new_null ,
.Fn sk_new ,
.Fn sk_free ,
.Fn sk_pop_free ,
.Fn sk_num ,
.Fn sk_value ,
.Fn sk_find ,
.Fn sk_push ,
.Fn sk_unshift ,
.Fn sk_insert ,
.Fn sk_pop ,
.Fn sk_shift ,
.Fn sk_delete ,
and
.Fn sk_delete_ptr
first appeared in SSLeay 0.5.1.
.Fn sk_set_cmp_func ,
.Fn sk_dup ,
and
.Fn sk_zero
first appeared in SSLeay 0.8.0.
These functions have been available since
.Ox 2.4 .
.Pp
.Fn sk_set
first appeared in OpenSSL 0.9.3.
.Fn sk_sort
first appeared in OpenSSL 0.9.4.
Both functions have been available since
.Ox 2.6 .
.Pp
.Fn sk_is_sorted
first appeared in OpenSSL 0.9.7e and has been available since
.Ox 3.8 .
.Pp
.Fn sk_find_ex
first appeared in OpenSSL 0.9.8 and has been available since
.Ox 4.5 .
.Sh BUGS
Even if a comparison function is installed, empty stacks and
stacks containing a single pointer are sometimes considered
sorted and sometimes considered unsorted.
.Pp
If a comparison function is installed, the concept of
.Dq first match
in
.Fn sk_find
and
.Fn sk_find_ex
is ill-defined because
.Xr qsort 3
is not a stable sorting function.
It is probably best to only assume that they return an arbitrary match.
.Pp
The concept of
.Dq closest
for
.Fn sk_find_ex
is even less clearly defined.
The match may sometimes be smaller and sometimes larger than
.Fa wanted ,
even if both smaller and larger pointers exist in the
.Fa stack .
Besides, it is again ill-defined
which of several pointers that compare equal is selected.
It is probably best to not assume anything about the selection
for cases where there is no match.