堆棧介紹

• 堆棧是一種先進后出的數據結構
• openssl 大量采用堆棧來存放數據。它實現了一 個通用的堆棧，可以方便的存儲任意數據
• 它實現了許多基本的堆棧操作，主要有：堆棧拷貝(sk_dup)、構建新堆棧（sk_new_null，sk_new）、插入數據（sk_insert）、刪除數據（sk_delete）、查找數據（sk_find，sk_find_ex）、入棧（sk_push）、出棧（sk_pop）、獲取堆棧元素個數（sk_num）、獲取堆棧值（sk_value）、設置堆棧值（sk_set）和堆棧排序（sk_sort）

數據結構

• openssl 堆棧數據結構在 stack.h 中
• stack.h 位于 include/openssl文件夾下
• 定義位于crypto/stack文件夾下的stack.c文件內，具體內容如下：

stack.h

/** Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.** Licensed under the OpenSSL license (the "License").  You may not use* this file except in compliance with the License.  You can obtain a copy* in the file LICENSE in the source distribution or at* https://www.openssl.org/source/license.html*/#ifndef HEADER_STACK_H
# define HEADER_STACK_H#ifdef  __cplusplus
extern "C" {
#endiftypedef struct stack_st OPENSSL_STACK; /* Use STACK_OF(...) instead */typedef int (*OPENSSL_sk_compfunc)(const void *, const void *);
typedef void (*OPENSSL_sk_freefunc)(void *);
typedef void *(*OPENSSL_sk_copyfunc)(const void *);int OPENSSL_sk_num(const OPENSSL_STACK *);
void *OPENSSL_sk_value(const OPENSSL_STACK *, int);void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data);OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc cmp);
OPENSSL_STACK *OPENSSL_sk_new_null(void);
void OPENSSL_sk_free(OPENSSL_STACK *);
void OPENSSL_sk_pop_free(OPENSSL_STACK *st, void (*func) (void *));
OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *, OPENSSL_sk_copyfunc c, OPENSSL_sk_freefunc f);
int OPENSSL_sk_insert(OPENSSL_STACK *sk, const void *data, int where);
void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc);
void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p);
int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data);
int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data);
int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data);
int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data);
void *OPENSSL_sk_shift(OPENSSL_STACK *st);
void *OPENSSL_sk_pop(OPENSSL_STACK *st);
void OPENSSL_sk_zero(OPENSSL_STACK *st);
OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk, OPENSSL_sk_compfunc cmp);
OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *st);
void OPENSSL_sk_sort(OPENSSL_STACK *st);
int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st);# if OPENSSL_API_COMPAT < 0x10100000L
#  define _STACK OPENSSL_STACK
#  define sk_num OPENSSL_sk_num
#  define sk_value OPENSSL_sk_value
#  define sk_set OPENSSL_sk_set
#  define sk_new OPENSSL_sk_new
#  define sk_new_null OPENSSL_sk_new_null
#  define sk_free OPENSSL_sk_free
#  define sk_pop_free OPENSSL_sk_pop_free
#  define sk_deep_copy OPENSSL_sk_deep_copy
#  define sk_insert OPENSSL_sk_insert
#  define sk_delete OPENSSL_sk_delete
#  define sk_delete_ptr OPENSSL_sk_delete_ptr
#  define sk_find OPENSSL_sk_find
#  define sk_find_ex OPENSSL_sk_find_ex
#  define sk_push OPENSSL_sk_push
#  define sk_unshift OPENSSL_sk_unshift
#  define sk_shift OPENSSL_sk_shift
#  define sk_pop OPENSSL_sk_pop
#  define sk_zero OPENSSL_sk_zero
#  define sk_set_cmp_func OPENSSL_sk_set_cmp_func
#  define sk_dup OPENSSL_sk_dup
#  define sk_sort OPENSSL_sk_sort
#  define sk_is_sorted OPENSSL_sk_is_sorted
# endif#ifdef  __cplusplus
}
#endif#endif

stack.cpp

/** Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.** Licensed under the OpenSSL license (the "License").  You may not use* this file except in compliance with the License.  You can obtain a copy* in the file LICENSE in the source distribution or at* https://www.openssl.org/source/license.html*/#include <stdio.h>
#include "internal/cryptlib.h"
#include "internal/numbers.h"
#include <openssl/stack.h>
#include <openssl/objects.h>struct stack_st {int num;const char **data;int sorted;size_t num_alloc;OPENSSL_sk_compfunc comp;
};#undef MIN_NODES
#define MIN_NODES       4#include <errno.h>OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk, OPENSSL_sk_compfunc c)
{OPENSSL_sk_compfunc old = sk->comp;if (sk->comp != c)sk->sorted = 0;sk->comp = c;return old;
}OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk)
{OPENSSL_STACK *ret;if (sk->num < 0)return NULL;if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)return NULL;/* direct structure assignment */*ret = *sk;if ((ret->data = OPENSSL_malloc(sizeof(*ret->data) * sk->num_alloc)) == NULL)goto err;memcpy(ret->data, sk->data, sizeof(char *) * sk->num);return ret;err:OPENSSL_sk_free(ret);return NULL;
}OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk,OPENSSL_sk_copyfunc copy_func,OPENSSL_sk_freefunc free_func)
{OPENSSL_STACK *ret;int i;if (sk->num < 0)return NULL;if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)return NULL;/* direct structure assignment */*ret = *sk;ret->num_alloc = sk->num > MIN_NODES ? (size_t)sk->num : MIN_NODES;ret->data = OPENSSL_zalloc(sizeof(*ret->data) * ret->num_alloc);if (ret->data == NULL) {OPENSSL_free(ret);return NULL;}for (i = 0; i < ret->num; ++i) {if (sk->data[i] == NULL)continue;if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {while (--i >= 0)if (ret->data[i] != NULL)free_func((void *)ret->data[i]);OPENSSL_sk_free(ret);return NULL;}}return ret;
}OPENSSL_STACK *OPENSSL_sk_new_null(void)
{return OPENSSL_sk_new((OPENSSL_sk_compfunc)NULL);
}OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c)
{OPENSSL_STACK *ret;if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL)goto err;if ((ret->data = OPENSSL_zalloc(sizeof(*ret->data) * MIN_NODES)) == NULL)goto err;ret->comp = c;ret->num_alloc = MIN_NODES;return (ret);err:OPENSSL_free(ret);return (NULL);
}int OPENSSL_sk_insert(OPENSSL_STACK *st, const void *data, int loc)
{if (st == NULL || st->num < 0 || st->num == INT_MAX) {return 0;}if (st->num_alloc <= (size_t)(st->num + 1)) {size_t doub_num_alloc = st->num_alloc * 2;const char **tmpdata;/* Overflow checks */if (doub_num_alloc < st->num_alloc)return 0;/* Avoid overflow due to multiplication by sizeof(char *) */if (doub_num_alloc > SIZE_MAX / sizeof(char *))return 0;tmpdata = OPENSSL_realloc((char *)st->data,sizeof(char *) * doub_num_alloc);if (tmpdata == NULL)return 0;st->data = tmpdata;st->num_alloc = doub_num_alloc;}if ((loc >= st->num) || (loc < 0)) {st->data[st->num] = data;} else {memmove(&st->data[loc + 1], &st->data[loc],sizeof(st->data[0]) * (st->num - loc));st->data[loc] = data;}st->num++;st->sorted = 0;return st->num;
}void *OPENSSL_sk_delete_ptr(OPENSSL_STACK *st, const void *p)
{int i;for (i = 0; i < st->num; i++)if (st->data[i] == p)return OPENSSL_sk_delete(st, i);return NULL;
}void *OPENSSL_sk_delete(OPENSSL_STACK *st, int loc)
{const char *ret;if (st == NULL || loc < 0 || loc >= st->num)return NULL;ret = st->data[loc];if (loc != st->num - 1)memmove(&st->data[loc], &st->data[loc + 1],sizeof(st->data[0]) * (st->num - loc - 1));st->num--;return (void *)ret;
}static int internal_find(OPENSSL_STACK *st, const void *data,int ret_val_options)
{const void *r;int i;if (st == NULL)return -1;if (st->comp == NULL) {for (i = 0; i < st->num; i++)if (st->data[i] == data)return (i);return (-1);}OPENSSL_sk_sort(st);if (data == NULL)return (-1);r = OBJ_bsearch_ex_(&data, st->data, st->num, sizeof(void *), st->comp,ret_val_options);if (r == NULL)return (-1);return (int)((const char **)r - st->data);
}int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data)
{return internal_find(st, data, OBJ_BSEARCH_FIRST_VALUE_ON_MATCH);
}int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data)
{return internal_find(st, data, OBJ_BSEARCH_VALUE_ON_NOMATCH);
}int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data)
{return (OPENSSL_sk_insert(st, data, st->num));
}int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data)
{return (OPENSSL_sk_insert(st, data, 0));
}void *OPENSSL_sk_shift(OPENSSL_STACK *st)
{if (st == NULL)return (NULL);if (st->num <= 0)return (NULL);return (OPENSSL_sk_delete(st, 0));
}void *OPENSSL_sk_pop(OPENSSL_STACK *st)
{if (st == NULL)return (NULL);if (st->num <= 0)return (NULL);return (OPENSSL_sk_delete(st, st->num - 1));
}void OPENSSL_sk_zero(OPENSSL_STACK *st)
{if (st == NULL)return;if (st->num <= 0)return;memset(st->data, 0, sizeof(*st->data) * st->num);st->num = 0;
}void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
{int i;if (st == NULL)return;for (i = 0; i < st->num; i++)if (st->data[i] != NULL)func((char *)st->data[i]);OPENSSL_sk_free(st);
}void OPENSSL_sk_free(OPENSSL_STACK *st)
{if (st == NULL)return;OPENSSL_free(st->data);OPENSSL_free(st);
}int OPENSSL_sk_num(const OPENSSL_STACK *st)
{if (st == NULL)return -1;return st->num;
}void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i)
{if (st == NULL || i < 0 || i >= st->num)return NULL;return (void *)st->data[i];
}void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data)
{if (st == NULL || i < 0 || i >= st->num)return NULL;st->data[i] = data;return (void *)st->data[i];
}void OPENSSL_sk_sort(OPENSSL_STACK *st)
{if (st && !st->sorted && st->comp != NULL) {qsort(st->data, st->num, sizeof(char *), st->comp);st->sorted = 1;}
}int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
{if (st == NULL)return 1;return st->sorted;
}

數據結構

struct stack_st {int num;const char **data;int sorted;size_t num_alloc;OPENSSL_sk_compfunc comp;
};

• 各項意義如下：
  • num: 堆棧中存放數據的個數。
  • data: ?用于存放數據地址，每個數據地址存放在 data[0]到 data[num-1]中。
  • sorted: 堆棧是否已排序，如果排序則值為 1，否則為 0，堆棧數據一般是無序的，只有當用戶調用了 sk_sort 操作，其值才為 1。
  • comp: 堆棧內存放數據的比較函數地址，此函數用于排序和查找操作；當用戶生成一 個新堆棧時，可以指定comp為用戶實現的一個比較函數；或當堆棧已經存在 時通過調用 sk_set_cmp_func 函數來重新指定比較函數。
• 注意，用戶不需要調用底層的堆棧函數(sk_sort、sk_set_cmp_func 等)，而是調用他通過 宏實現的各個函數。

函數介紹

• openssl 堆棧實現源碼位于 crypto/stack 目錄下。下面分析了部分函數。
• ?sk_set_cmp_func
• 此函數用于設置堆棧存放數據的比較函數。由于堆棧不知道用戶存放的是什么數據，所以，比較函數必須由用戶自己實現。

OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func(OPENSSL_STACK *sk, OPENSSL_sk_compfunc c)
{OPENSSL_sk_compfunc old = sk->comp;if (sk->comp != c)sk->sorted = 0;sk->comp = c;return old;
}

• OPENSSL_sk_dup 堆棧拷貝
• 使用OPSNSSL_malloc進行內存的分配，其實質是調用CRYPTO_malloc進行內存的分配

OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk)
{OPENSSL_STACK *ret;if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)goto err;if (sk == NULL) {ret->num = 0;ret->sorted = 0;ret->comp = NULL;} else {/* direct structure assignment */*ret = *sk;}if (sk == NULL || sk->num == 0) {/* postpone |ret->data| allocation */ret->data = NULL;ret->num_alloc = 0;return ret;}/* duplicate |sk->data| content */if ((ret->data = OPENSSL_malloc(sizeof(*ret->data) * sk->num_alloc)) == NULL)goto err;memcpy(ret->data, sk->data, sizeof(void *) * sk->num);return ret;err:ERR_raise(ERR_LIB_CRYPTO, ERR_R_MALLOC_FAILURE);OPENSSL_sk_free(ret);return NULL;
}

• C++版本?

OPENSSL_STACK *OPENSSL_sk_dup(const OPENSSL_STACK *sk){OPENSSL_STACK *ret;if((ret = reinterpret_cast<OPENSSL_STACK *>(OPENSSL_malloc(sizeof (*ret)))) == nullptr){goto err;}if (sk == nullptr){ret->num = 0;ret->sorted = 0;ret->comp = nullptr;} else{//直接結構賦值*ret = *sk;}if (sk == nullptr || sk->num == 0){//推遲|ret->data|分配ret->data = nullptr;ret->num_alloc = 0;return ret;}// 重復|sk->data|內容if ((ret->data = static_cast<const void **>(OPENSSL_malloc(sizeof((*ret).data) * sk->num_alloc))) == nullptr)goto err;memcpy(ret->data,sk->data,sizeof (void*)*sk->num);return ret;err:ERR_raise(ERR_LIB_CRYPTO,ERR_R_MALLOC_FAILURE);OPENSSL_sk_free(ret);return nullptr;
}

# define OPENSSL_malloc(num) \CRYPTO_malloc(num, OPENSSL_FILE, OPENSSL_LINE)

• *根據配置制作我們自己的__FILE__和__LINE__變體

/** Make our own variants of __FILE__ and __LINE__, depending on configuration*/# ifndef OPENSSL_FILE
#  ifdef OPENSSL_NO_FILENAMES
#   define OPENSSL_FILE ""
#   define OPENSSL_LINE 0
#  else
#   define OPENSSL_FILE __FILE__
#   define OPENSSL_LINE __LINE__
#  endif
# endif

• ?CRYPTO_malloc
• # define INCREMENT(x) /* empty */

void *CRYPTO_malloc(size_t num, const char *file, int line)
{INCREMENT(malloc_count);if (malloc_impl != CRYPTO_malloc)return malloc_impl(num, file, line);if (num == 0)return NULL;FAILTEST();if (allow_customize) {/** Disallow customization after the first allocation. We only set this* if necessary to avoid a store to the same cache line on every* allocation.*/allow_customize = 0;}return malloc(num);
}

• malloc_count 全局靜態變量，在openssl里面出現了三次
• 定義位于 mem.c 文件中?

• ?只要設置了“allow_customize”，就可以更改以下指針

/** the following pointers may be changed as long as 'allow_customize' is set*/static CRYPTO_malloc_fn malloc_impl = CRYPTO_malloc;

• ?INCREMENT? 和? FAILTEST

# define FAILTEST() if (shouldfail()) return NULL#else# define INCREMENT(x) /* empty */
# define FAILTEST() /* empty */
#endif

• *allow_customize? 禁止在第一次分配后進行自定義。我們僅在必要時設置此值，以避免在每次分配時將存儲存儲到相同的緩存行。?

?

OPENSSL_sk_deep_copy? 深拷貝

OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk,OPENSSL_sk_copyfunc copy_func,OPENSSL_sk_freefunc free_func)
{OPENSSL_STACK *ret;int i;if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL)goto err;if (sk == NULL) {ret->num = 0;ret->sorted = 0;ret->comp = NULL;} else {/* direct structure assignment */*ret = *sk;}if (sk == NULL || sk->num == 0) {/* postpone |ret| data allocation */ret->data = NULL;ret->num_alloc = 0;return ret;}ret->num_alloc = sk->num > min_nodes ? sk->num : min_nodes;ret->data = OPENSSL_zalloc(sizeof(*ret->data) * ret->num_alloc);if (ret->data == NULL)goto err;for (i = 0; i < ret->num; ++i) {if (sk->data[i] == NULL)continue;if ((ret->data[i] = copy_func(sk->data[i])) == NULL) {while (--i >= 0)if (ret->data[i] != NULL)free_func((void *)ret->data[i]);goto err;}}return ret;err:ERR_raise(ERR_LIB_CRYPTO, ERR_R_MALLOC_FAILURE);OPENSSL_sk_free(ret);return NULL;
}

OPENSSL_STACK *OPENSSL_sk_deep_copy(const OPENSSL_STACK *sk,OPENSSL_sk_copyfunc copy_func,OPENSSL_sk_freefunc free_func)
{OPENSSL_STACK *ret;int j;if ((ret = reinterpret_cast<OPENSSL_STACK *>(OPENSSL_malloc(sizeof (*ret))))== nullptr)goto err;if (sk == nullptr){ret->num = 0;ret->sorted = 0;ret->comp = nullptr;} else{//直接結構賦值*ret = *sk;}if (sk == nullptr || sk->num == 0){//推遲|ret->data|分配ret->data = nullptr;ret->num_alloc = 0;return ret;}ret->num_alloc = sk->num > min_nodes ? sk->num : min_nodes;ret->data = static_cast<const void **>(OPENSSL_zalloc(sizeof(*ret->data) * ret->num_alloc));if (ret->data == nullptr)goto err;for (j = 0; j < ret->num; ++j) {if (sk->data[j] == nullptr)continue;if ((ret->data[j] = copy_func(sk->data[j]))== nullptr){while (--j >= 0)if (ret->data[j]!= nullptr)free_func((void *)ret->data[j]);goto err;}}return ret;err:ERR_raise(ERR_LIB_CRYPTO,ERR_R_MALLOC_FAILURE);OPENSSL_sk_free(ret);return nullptr;
}

# define OPENSSL_zalloc(num) \CRYPTO_zalloc(num, OPENSSL_FILE, OPENSSL_LINE)

• ?CRYPTO_zalloc 內存分配，內部調用 CRYPTO_malloc

void *CRYPTO_zalloc(size_t num, const char *file, int line)
{void *ret;ret = CRYPTO_malloc(num, file, line);FAILTEST();if (ret != NULL)memset(ret, 0, num);return ret;
}

typedef void *(*OPENSSL_sk_copyfunc)(const void *);
typedef void (*OPENSSL_sk_freefunc)(void *);

/* Main error raising functions */
# define ERR_raise(lib, reason) ERR_raise_data((lib),(reason),NULL)
# define ERR_raise_data                                         \(ERR_new(),                                                 \ERR_set_debug(OPENSSL_FILE,OPENSSL_LINE,OPENSSL_FUNC),     \ERR_set_error)

void ERR_new(void)
{c_new_error(NULL);
}void ERR_set_debug(const char *file, int line, const char *func)
{c_set_error_debug(NULL, file, line, func);
}void ERR_set_error(int lib, int reason, const char *fmt, ...)
{va_list args;va_start(args, fmt);c_vset_error(NULL, ERR_PACK(lib, 0, reason), fmt, args);va_end(args);
}

void OPENSSL_sk_free(OPENSSL_STACK *st)
{if (st == NULL)return;OPENSSL_free(st->data);OPENSSL_free(st);
}

?OPENSSL_sk_new_reserve

OPENSSL_STACK *OPENSSL_sk_new_null(void)
{return OPENSSL_sk_new_reserve(NULL, 0);
}

??OPENSSL_sk_new

OPENSSL_STACK *OPENSSL_sk_new(OPENSSL_sk_compfunc c)
{return OPENSSL_sk_new_reserve(c, 0);
}

?OPENSSL_sk_new_reserve

OPENSSL_STACK *OPENSSL_sk_new_reserve(OPENSSL_sk_compfunc c, int n)
{OPENSSL_STACK *st = reinterpret_cast<OPENSSL_STACK *>(OPENSSL_zalloc(sizeof(OPENSSL_STACK)));if (st == NULL)return NULL;st->comp = c;if (n <= 0)return st;if (!sk_reserve(st, n, 1)) {OPENSSL_sk_free(st);return NULL;}return st;
}

?sk_reserve

/* internal STACK storage allocation */
static int sk_reserve(OPENSSL_STACK *st, int n, int exact)
{const void **tmpdata;int num_alloc;//檢查預訂是否超過硬限制if (n > max_nodes - st->num){return 0;}//指出新的大小num_alloc = st->num + n;if (num_alloc < min_nodes){num_alloc = min_nodes;}//如果 |st->data| 分配被推遲if (st->data == nullptr){//此時，|st->num_alloc| 和 |st->num| 是 0//所以 |num_alloc| 值為 |n| 或 |min_nodes| 如果大于 |n|if((st->data = static_cast<const void **>(OPENSSL_zalloc(sizeof (void *)*num_alloc)))== nullptr){ERR_raise(ERR_LIB_CRYPTO,ERR_R_MALLOC_FAILURE);return 0;}st->num_alloc = num_alloc;return 1;}if (!exact){if (num_alloc <= st->num_alloc)return 1;num_alloc = compute_growth(num_alloc,st->num_alloc);if (num_alloc == 0)return 0;} else if (num_alloc == st->num_alloc){return 1;}tmpdata = static_cast<const void **>(OPENSSL_realloc((void *)st->data, sizeof(void *) * num_alloc));if (tmpdata == NULL)return 0;st->data = tmpdata;st->num_alloc = num_alloc;return 1;
}

compute_growth?

/** 根據目標大小計算數組增長。** 增長分數是有理數，由分子和分母定義。 根據 Andrew Koenig 在他的論文“為什么向量是有效的？”中的說法。 從 JOOP 11(5) 1998 開始，這個因子應該小于黃金比例 (1.618...)。** 我們使用 3/2 = 1.5 來簡化計算和溢出檢查。另一個選項 8/5 = 1.6 允許稍微更快的增長，盡管安全計算更加困難。** 避免溢出的限制是正確的。 模三校正項確保限制是在不超過硬限制的情況下可以通過增長因子擴展的最大數。** 不要用 |current| 調用它 小于2，否則會無限循環。*/
static ossl_inline int compute_growth(int target,int current){const int limit = (max_nodes / 3)*2 + (max_nodes % 3 ? 1: 0);while(current < target){//檢查我們是否處于硬限制if (current >= max_nodes)return 0;//如果在范圍內，則將大小擴大 3/2 倍current = current < limit ? current + current / 2 : max_nodes;}return current;
}

OPENSSL_sk_reserve

int OPENSSL_sk_reserve(OPENSSL_STACK *st, int n)
{if (st == NULL)return 0;if (n < 0)return 1;return sk_reserve(st, n, 1);
}

OPENSSL_sk_insert?

• C 庫函數 – memmove() | 菜鳥教程

int OPENSSL_sk_insert(OPENSSL_STACK *st,const void *data,int loc)
{if (st == nullptr || st->num == max_nodes){return 0;}if (!sk_reserve(st,1,0))return 0;if ((loc >= st->num) || (loc < 0)){st->data[st->num] = data;} else{memmove(&st->data[loc+1],&st->data[loc],sizeof(st->data[0]) * (st->num - loc));st->data[loc] = data;}st->num++;st->sorted = 0;return st->num;
}

internal_delete?

static ossl_inline void * internal_delete(OPENSSL_STACK *st,int loc){const void *ret = st->data[loc];if (loc != st->num-1){memmove(&st->data[loc],&st->data[loc+1],sizeof (st->data[0]) * (st->num - loc -1));}st->num--;return (void*)ret;
}

?OPENSSL_sk_delete_ptr

void* OPENSSL_sk_delete_ptr(OPENSSL_STACK *st,const void *p){for (int j = 0; j < st->num; ++j) {if (st->data[j]==p)return internal_delete(st,j);}return nullptr;
}

OPENSSL_sk_delete?

void *OPENSSL_sk_delete(OPENSSL_STACK *st,int loc)
{if (st == nullptr || loc < 0 || loc >= st->num){return nullptr;}return internal_delete(st,loc);
}

?internal_find

• 根據數據地址來查找它在堆棧中的位置。當堆棧設置了比較函數時，它首先對堆棧進行排序，然后通過二分法進行查找。
• 如果堆棧沒有設置比較函數，它只是簡單的比較數據地址來查找

static int internal_find(OPENSSL_STACK *st,const void *data,int ret_val_options,int *pnum)
{const void *r = nullptr;if (st == nullptr || st->num == 0){return -1;}//未排序 采用循環遍歷的方式進行查找if (st->comp == nullptr){for (int i = 0; i < st->num; ++i) {if (st->data[i] == data){if (pnum != nullptr)*pnum = 1;return i;}if (pnum != nullptr){*pnum = 0;}return -1;}}//根據comp比較函數進行快速排序if (!st->sorted){if (st->num > 1)qsort(st->data,st->num,sizeof (void*),st->comp);st->sorted = 1; //空或單元素堆棧被視為已排序}if (data == nullptr)return -1;if (pnum != nullptr)ret_val_options |= OSSL_BSEARCH_FIRST_VALUE_ON_MATCH;r = ossl_bsearch(&data,st->data,st->num,sizeof(void*),st->comp,ret_val_options);if (pnum != nullptr){*pnum = 0;if (r != nullptr){const void **p = (const void **)r;while (p < st->data + st->num){if (st->comp(&data,p) != 0)break;++*pnum;++p;}}}return r == nullptr ? -1 : (int)((const void **)r - st->data);
}

?ossl_bsearch

• C 庫函數 – bsearch() | 菜鳥教程

#include <stddef.h>
#include "internal/cryptlib.h"const void *ossl_bsearch(const void *key, const void *base, int num,int size, int (*cmp) (const void *, const void *),int flags)
{const char *base_ = base;int l, h, i = 0, c = 0;const char *p = NULL;if (num == 0)return NULL;l = 0;h = num;while (l < h) {i = (l + h) / 2;p = &(base_[i * size]);c = (*cmp) (key, p);if (c < 0)h = i;else if (c > 0)l = i + 1;elsebreak;}if (c != 0 && !(flags & OSSL_BSEARCH_VALUE_ON_NOMATCH))p = NULL;else if (c == 0 && (flags & OSSL_BSEARCH_FIRST_VALUE_ON_MATCH)) {while (i > 0 && (*cmp) (key, &(base_[(i - 1) * size])) == 0)i--;p = &(base_[i * size]);}return p;
}

/* Function for simple binary search *//* Flags */
# define OSSL_BSEARCH_VALUE_ON_NOMATCH            0x01
# define OSSL_BSEARCH_FIRST_VALUE_ON_MATCH        0x02

?OPENSSL_sk_find

int OPENSSL_sk_find(OPENSSL_STACK *st, const void *data)
{return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, NULL);
}

OPENSSL_sk_find_ex

int OPENSSL_sk_find_ex(OPENSSL_STACK *st, const void *data)
{return internal_find(st, data, OSSL_BSEARCH_VALUE_ON_NOMATCH, NULL);
}

OPENSSL_sk_find_all?

int OPENSSL_sk_find_all(OPENSSL_STACK *st, const void *data, int *pnum)
{return internal_find(st, data, OSSL_BSEARCH_FIRST_VALUE_ON_MATCH, pnum);
}

OPENSSL_sk_push?

int OPENSSL_sk_push(OPENSSL_STACK *st, const void *data)
{if (st == NULL)return -1;return OPENSSL_sk_insert(st, data, st->num);
}

OPENSSL_sk_unshift?

int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data)
{return OPENSSL_sk_insert(st, data, 0);
}

OPENSSL_sk_shift?

void *OPENSSL_sk_shift(OPENSSL_STACK *st)
{if (st == NULL || st->num == 0)return NULL;return internal_delete(st, 0);
}

OPENSSL_sk_pop?

void *OPENSSL_sk_pop(OPENSSL_STACK *st)
{if (st == NULL || st->num == 0)return NULL;return internal_delete(st, st->num - 1);
}

OPENSSL_sk_zero?

void OPENSSL_sk_zero(OPENSSL_STACK *st)
{if (st == NULL || st->num == 0)return;memset(st->data, 0, sizeof(*st->data) * st->num);st->num = 0;
}

?OPENSSL_sk_pop_free

• 釋放data和結構體?

void OPENSSL_sk_pop_free(OPENSSL_STACK *st, OPENSSL_sk_freefunc func)
{int i;if (st == NULL)return;for (i = 0; i < st->num; i++)if (st->data[i] != NULL)func((char *)st->data[i]);OPENSSL_sk_free(st);
}

OPENSSL_sk_free?

void OPENSSL_sk_free(OPENSSL_STACK *st)
{if (st == NULL)return;OPENSSL_free(st->data);OPENSSL_free(st);
}

OPENSSL_sk_num?

int OPENSSL_sk_num(const OPENSSL_STACK *st)
{return st == NULL ? -1 : st->num;
}

OPENSSL_sk_value?

void *OPENSSL_sk_value(const OPENSSL_STACK *st, int i)
{if (st == NULL || i < 0 || i >= st->num)return NULL;return (void *)st->data[i];
}

OPENSSL_sk_set?

void *OPENSSL_sk_set(OPENSSL_STACK *st, int i, const void *data)
{if (st == NULL || i < 0 || i >= st->num)return NULL;st->data[i] = data;st->sorted = 0;return (void *)st->data[i];
}

OPENSSL_sk_sort?

• 本函數對堆棧數據排序。它首先根據sorted來判斷是否已經排序，如果未排序 則調用了標準C 函數qsort 進行快速排序。

void OPENSSL_sk_sort(OPENSSL_STACK *st)
{if (st != NULL && !st->sorted && st->comp != NULL) {if (st->num > 1)qsort(st->data, st->num, sizeof(void *), st->comp);st->sorted = 1; /* empty or single-element stack is considered sorted */}
}

OPENSSL_sk_is_sorted?

int OPENSSL_sk_is_sorted(const OPENSSL_STACK *st)
{return st == NULL ? 1 : st->sorted;
}