stack.h

All headers

A stack, in OpenSSL, is an array of pointers. They are the most commonly used collection object.

This file defines macros for type safe use of the stack functions. A stack of a specific type of object has type STACK_OF(type). This can be defined (once) with DEFINE_STACK_OF(type) and declared where needed with DECLARE_STACK_OF(type). For example:

typedef struct foo_st { int bar; } FOO;

DEFINE_STACK_OF(FOO)

Although note that the stack will contain /pointers/ to FOO.

A macro will be defined for each of the sk_* functions below. For STACK_OF(FOO), the macros would be sk_FOO_new, sk_FOO_pop etc.

  1. STACK_OF
  2. DECLARE_STACK_OF
  3. sk_new
  4. sk_new_null
  5. sk_num
  6. sk_zero
  7. sk_value
  8. sk_set
  9. sk_free
  10. sk_pop_free_ex
  11. sk_insert
  12. sk_delete
  13. sk_delete_ptr
  14. sk_find
  15. sk_shift
  16. sk_push
  17. sk_pop
  18. sk_dup
  19. sk_sort
  20. sk_is_sorted
  21. sk_set_cmp_func
  22. sk_deep_copy
  23. Deprecated functions
  24. sk_pop_free
  25. Defining stack types
  26. BORINGSSL_DEFINE_STACK_TRAITS
  27. BORINGSSL_DEFINE_STACK_TRAITS
  28. BORINGSSL_DEFINE_STACK_OF_IMPL
  29. DEFINE_NAMED_STACK_OF
  30. DEFINE_STACK_OF
  31. DEFINE_CONST_STACK_OF
  32. DEFINE_SPECIAL_STACK_OF

stack_free_func is a function that frees an element in a stack. Note its actual type is void (*)(T *) for some T. Low-level sk_* functions will be passed a type-specific wrapper to call it correctly.

typedef void (*stack_free_func)(void *ptr);

stack_copy_func is a function that copies an element in a stack. Note its actual type is T *(*)(T *) for some T. Low-level sk_* functions will be passed a type-specific wrapper to call it correctly.

typedef void *(*stack_copy_func)(void *ptr);

stack_cmp_func is a comparison function that returns a value < 0, 0 or > 0 if *a is less than, equal to or greater than *b, respectively. Note the extra indirection - the function is given a pointer to a pointer to the element. This differs from the usual qsort/bsearch comparison function.

Note its actual type is int (*)(const T **, const T **). Low-level sk_* functions will be passed a type-specific wrapper to call it correctly.

typedef int (*stack_cmp_func)(const void **a, const void **b);

stack_st contains an array of pointers. It is not designed to be used directly, rather the wrapper macros should be used.

typedef struct stack_st {
  // num contains the number of valid pointers in |data|.
  size_t num;
  void **data;
  // sorted is non-zero if the values pointed to by |data| are in ascending
  // order, based on |comp|.
  int sorted;
  // num_alloc contains the number of pointers allocated in the buffer pointed
  // to by |data|, which may be larger than |num|.
  size_t num_alloc;
  // comp is an optional comparison function.
  stack_cmp_func comp;
} _STACK;
#define STACK_OF(type) struct stack_st_##type
#define DECLARE_STACK_OF(type) STACK_OF(type);

These are the raw stack functions, you shouldn't be using them. Rather you should be using the type stack macros implemented above.


          

sk_new creates a new, empty stack with the given comparison function, which may be zero. It returns the new stack or NULL on allocation failure.

OPENSSL_EXPORT _STACK *sk_new(stack_cmp_func comp);

sk_new_null creates a new, empty stack. It returns the new stack or NULL on allocation failure.

OPENSSL_EXPORT _STACK *sk_new_null(void);

sk_num returns the number of elements in s.

OPENSSL_EXPORT size_t sk_num(const _STACK *sk);

sk_zero resets sk to the empty state but does nothing to free the individual elements themselves.

OPENSSL_EXPORT void sk_zero(_STACK *sk);

sk_value returns the ith pointer in sk, or NULL if i is out of range.

OPENSSL_EXPORT void *sk_value(const _STACK *sk, size_t i);

sk_set sets the ith pointer in sk to p and returns p. If i is out of range, it returns NULL.

OPENSSL_EXPORT void *sk_set(_STACK *sk, size_t i, void *p);

sk_free frees the given stack and array of pointers, but does nothing to free the individual elements. Also see sk_pop_free_ex.

OPENSSL_EXPORT void sk_free(_STACK *sk);

sk_pop_free_ex calls free_func on each element in the stack and then frees the stack itself. Note this corresponds to sk_FOO_pop_free. It is named sk_pop_free_ex as a workaround for existing code calling an older version of sk_pop_free.

OPENSSL_EXPORT void sk_pop_free_ex(_STACK *sk,
                                   void (*call_free_func)(stack_free_func,
                                                          void *),
                                   stack_free_func free_func);

sk_insert inserts p into the stack at index where, moving existing elements if needed. It returns the length of the new stack, or zero on error.

OPENSSL_EXPORT size_t sk_insert(_STACK *sk, void *p, size_t where);

sk_delete removes the pointer at index where, moving other elements down if needed. It returns the removed pointer, or NULL if where is out of range.

OPENSSL_EXPORT void *sk_delete(_STACK *sk, size_t where);

sk_delete_ptr removes, at most, one instance of p from the stack based on pointer equality. If an instance of p is found then p is returned, otherwise it returns NULL.

OPENSSL_EXPORT void *sk_delete_ptr(_STACK *sk, const void *p);

sk_find returns the first value in the stack equal to p. If a comparison function has been set on the stack, equality is defined by it, otherwise pointer equality is used. If the stack is sorted, then a binary search is used, otherwise a linear search is performed. If a matching element is found, its index is written to *out_index (if out_index is not NULL) and one is returned. Otherwise zero is returned.

Note this differs from OpenSSL. The type signature is slightly different, and OpenSSL's sk_find will implicitly sort sk if it has a comparison function defined.

OPENSSL_EXPORT int sk_find(const _STACK *sk, size_t *out_index, const void *p,
                           int (*call_cmp_func)(stack_cmp_func, const void **,
                                                const void **));

sk_shift removes and returns the first element in the stack, or returns NULL if the stack is empty.

OPENSSL_EXPORT void *sk_shift(_STACK *sk);

sk_push appends p to the stack and returns the length of the new stack, or 0 on allocation failure.

OPENSSL_EXPORT size_t sk_push(_STACK *sk, void *p);

sk_pop returns and removes the last element on the stack, or NULL if the stack is empty.

OPENSSL_EXPORT void *sk_pop(_STACK *sk);

sk_dup performs a shallow copy of a stack and returns the new stack, or NULL on error.

OPENSSL_EXPORT _STACK *sk_dup(const _STACK *sk);

sk_sort sorts the elements of sk into ascending order based on the comparison function. The stack maintains a sorted flag and sorting an already sorted stack is a no-op.

OPENSSL_EXPORT void sk_sort(_STACK *sk);

sk_is_sorted returns one if sk is known to be sorted and zero otherwise.

OPENSSL_EXPORT int sk_is_sorted(const _STACK *sk);

sk_set_cmp_func sets the comparison function to be used by sk and returns the previous one.

OPENSSL_EXPORT stack_cmp_func sk_set_cmp_func(_STACK *sk, stack_cmp_func comp);

sk_deep_copy performs a copy of sk and of each of the non-NULL elements in sk by using copy_func. If an error occurs, free_func is used to free any copies already made and NULL is returned.

OPENSSL_EXPORT _STACK *sk_deep_copy(
    const _STACK *sk, void *(*call_copy_func)(stack_copy_func, void *),
    stack_copy_func copy_func, void (*call_free_func)(stack_free_func, void *),
    stack_free_func free_func);

Deprecated functions.

sk_pop_free behaves like sk_pop_free_ex but performs an invalid function pointer cast. It exists because some existing callers called sk_pop_free directly.

TODO(davidben): Migrate callers to bssl::UniquePtr and remove this.

OPENSSL_EXPORT void sk_pop_free(_STACK *sk, stack_free_func free_func);

Defining stack types.

This set of macros is used to emit the typed functions that act on a STACK_OF(T).

#if !defined(BORINGSSL_NO_CXX)
extern "C++" {
BSSL_NAMESPACE_BEGIN
namespace internal {
template <typename T>
struct StackTraits {};
}
BSSL_NAMESPACE_END
}
#define BORINGSSL_DEFINE_STACK_TRAITS(name, type, is_const) \
  extern "C++" {                                            \
  BSSL_NAMESPACE_BEGIN                                      \
  namespace internal {                                      \
  template <>                                               \
  struct StackTraits<STACK_OF(name)> {                      \
    static constexpr bool kIsStack = true;                  \
    using Type = type;                                      \
    static constexpr bool kIsConst = is_const;              \
  };                                                        \
  }                                                         \
  BSSL_NAMESPACE_END                                        \
  }
#else
#define BORINGSSL_DEFINE_STACK_TRAITS(name, type, is_const)
#endif
#define BORINGSSL_DEFINE_STACK_OF_IMPL(name, ptrtype, constptrtype)            \
  DECLARE_STACK_OF(name)                                                       \
                                                                               \
  typedef void (*stack_##name##_free_func)(ptrtype);                           \
  typedef ptrtype (*stack_##name##_copy_func)(ptrtype);                        \
  typedef int (*stack_##name##_cmp_func)(constptrtype *a, constptrtype *b);    \
                                                                               \
  OPENSSL_INLINE void sk_##name##_call_free_func(stack_free_func free_func,    \
                                                 void *ptr) {                  \
    ((stack_##name##_free_func)free_func)((ptrtype)ptr);                       \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE void *sk_##name##_call_copy_func(stack_copy_func copy_func,   \
                                                  void *ptr) {                 \
    return (void *)((stack_##name##_copy_func)copy_func)((ptrtype)ptr);        \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE int sk_##name##_call_cmp_func(                                \
      stack_cmp_func cmp_func, const void **a, const void **b) {               \
    constptrtype a_ptr = (constptrtype)*a;                                     \
    constptrtype b_ptr = (constptrtype)*b;                                     \
    return ((stack_##name##_cmp_func)cmp_func)(&a_ptr, &b_ptr);                \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE STACK_OF(name) *                                              \
      sk_##name##_new(stack_##name##_cmp_func comp) {                          \
    return (STACK_OF(name) *)sk_new((stack_cmp_func)comp);                     \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE STACK_OF(name) *sk_##name##_new_null(void) {                  \
    return (STACK_OF(name) *)sk_new_null();                                    \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE size_t sk_##name##_num(const STACK_OF(name) *sk) {            \
    return sk_num((const _STACK *)sk);                                         \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE void sk_##name##_zero(STACK_OF(name) *sk) {                   \
    sk_zero((_STACK *)sk);                                                     \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE ptrtype sk_##name##_value(const STACK_OF(name) *sk,           \
                                           size_t i) {                         \
    return (ptrtype)sk_value((const _STACK *)sk, i);                           \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE ptrtype sk_##name##_set(STACK_OF(name) *sk, size_t i,         \
                                         ptrtype p) {                          \
    return (ptrtype)sk_set((_STACK *)sk, i, (void *)p);                        \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE void sk_##name##_free(STACK_OF(name) * sk) {                  \
    sk_free((_STACK *)sk);                                                     \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE void sk_##name##_pop_free(                                    \
      STACK_OF(name) * sk, stack_##name##_free_func free_func) {               \
    sk_pop_free_ex((_STACK *)sk, sk_##name##_call_free_func,                   \
                   (stack_free_func)free_func);                                \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE size_t sk_##name##_insert(STACK_OF(name) *sk, ptrtype p,      \
                                           size_t where) {                     \
    return sk_insert((_STACK *)sk, (void *)p, where);                          \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE ptrtype sk_##name##_delete(STACK_OF(name) *sk,                \
                                            size_t where) {                    \
    return (ptrtype)sk_delete((_STACK *)sk, where);                            \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE ptrtype sk_##name##_delete_ptr(STACK_OF(name) *sk,            \
                                                constptrtype p) {              \
    return (ptrtype)sk_delete_ptr((_STACK *)sk, (const void *)p);              \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE int sk_##name##_find(const STACK_OF(name) *sk,                \
                                      size_t * out_index, constptrtype p) {    \
    return sk_find((const _STACK *)sk, out_index, (const void *)p,             \
                   sk_##name##_call_cmp_func);                                 \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE ptrtype sk_##name##_shift(STACK_OF(name) *sk) {               \
    return (ptrtype)sk_shift((_STACK *)sk);                                    \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE size_t sk_##name##_push(STACK_OF(name) *sk, ptrtype p) {      \
    return sk_push((_STACK *)sk, (void *)p);                                   \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE ptrtype sk_##name##_pop(STACK_OF(name) *sk) {                 \
    return (ptrtype)sk_pop((_STACK *)sk);                                      \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE STACK_OF(name) * sk_##name##_dup(const STACK_OF(name) *sk) {  \
    return (STACK_OF(name) *)sk_dup((const _STACK *)sk);                       \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE void sk_##name##_sort(STACK_OF(name) *sk) {                   \
    sk_sort((_STACK *)sk);                                                     \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE int sk_##name##_is_sorted(const STACK_OF(name) *sk) {         \
    return sk_is_sorted((const _STACK *)sk);                                   \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE stack_##name##_cmp_func sk_##name##_set_cmp_func(             \
      STACK_OF(name) *sk, stack_##name##_cmp_func comp) {                      \
    return (stack_##name##_cmp_func)sk_set_cmp_func((_STACK *)sk,              \
                                                    (stack_cmp_func)comp);     \
  }                                                                            \
                                                                               \
  OPENSSL_INLINE STACK_OF(name) *                                              \
      sk_##name##_deep_copy(const STACK_OF(name) *sk,                          \
                            ptrtype(*copy_func)(ptrtype),                      \
                            void (*free_func)(ptrtype)) {                      \
    return (STACK_OF(name) *)sk_deep_copy(                                     \
        (const _STACK *)sk, sk_##name##_call_copy_func,                        \
        (stack_copy_func)copy_func, sk_##name##_call_free_func,                \
        (stack_free_func)free_func);                                           \
  }

DEFINE_NAMED_STACK_OF defines STACK_OF(name) to be a stack whose elements are type *.

#define DEFINE_NAMED_STACK_OF(name, type)                    \
  BORINGSSL_DEFINE_STACK_OF_IMPL(name, type *, const type *) \
  BORINGSSL_DEFINE_STACK_TRAITS(name, type, false)

DEFINE_STACK_OF defines STACK_OF(type) to be a stack whose elements are type *.

#define DEFINE_STACK_OF(type) DEFINE_NAMED_STACK_OF(type, type)

DEFINE_CONST_STACK_OF defines STACK_OF(type) to be a stack whose elements are const type *.

#define DEFINE_CONST_STACK_OF(type)                                \
  BORINGSSL_DEFINE_STACK_OF_IMPL(type, const type *, const type *) \
  BORINGSSL_DEFINE_STACK_TRAITS(type, const type, true)

DEFINE_SPECIAL_STACK_OF defines STACK_OF(type) to be a stack whose elements are type, where type must be a typedef for a pointer.

#define DEFINE_SPECIAL_STACK_OF(type)                   \
  OPENSSL_STATIC_ASSERT(sizeof(type) == sizeof(void *), \
                        #type " is not a pointer");     \
  BORINGSSL_DEFINE_STACK_OF_IMPL(type, type, const type)
typedef char *OPENSSL_STRING;
DEFINE_STACK_OF(void)
DEFINE_SPECIAL_STACK_OF(OPENSSL_STRING)