3 堆栈¶
man DEFINE_STACK_OF
- https://www.openssl.org/docs/man1.1.1/man3/sk_TYPE_num.html
- https://blog.csdn.net/as3luyuan123/article/details/17081581
3.1 openssl堆栈¶
堆栈是一种先进后出的数据结构。 openssl大量采用堆栈来存放数据。
它实现了一个通用的堆栈，可以方便的存储任意数据。
它实现了许多基本的堆栈操作，主要有：
构建新堆栈（sk_new_null，sk_new）、
堆栈拷贝(sk_dup)、
插入数据（sk_insert）、 删除数据（sk_delete）、
查找数据（sk_find，sk_find_ex）、
入栈（sk_push）、 出栈（sk_pop）、
获取堆栈元素个数（sk_num）、 获取堆栈值（sk_value）、
设置堆栈值（sk_set）和堆栈排序（sk_sort）。
// 通用堆栈
//创建一个空栈，参数可指定排序方法，因为openssl不知道里面存放的是什么类型的数据，
// 所以排序方法需要用户实现，当参数为NULL，同下方法
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 *));
//栈深copy,
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);
//在栈位置0次添加一个元素，类似 insert(st,0);
int OPENSSL_sk_unshift(OPENSSL_STACK *st, const void *data);
//移出栈位置0处的元素，类似pop
void *OPENSSL_sk_shift(OPENSSL_STACK *st);
//在栈顶移出一个元素，并释放该元素内存，
void *OPENSSL_sk_pop(OPENSSL_STACK *st);
//设置栈元素为0，不释放栈
void OPENSSL_sk_zero(OPENSSL_STACK *st);
//设置栈的排序方法
OPENSSL_sk_compfunc OPENSSL_sk_set_cmp_func( OPENSSL_STACK *sk,
OPENSSL_sk_compfunc cmp);
//copy 栈
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);
3.2 数据结构¶
openssl堆栈数据结构在stack.h中定义如下：
typedef struct stack_st
{
int num;
char **data;
int sorted;
int num_alloc;
int (*comp)(const char * const *, const char * const *);
} STACK;
各项意义如下：
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等)，而是调用他通过宏实现的各个函数。
3.3 源码¶
openssl堆栈实现源码位于crypto/stack目录下。下面分析了部分函数。
1) sk_set_cmp_func
此函数用于设置堆栈存放数据的比较函数。
由于堆栈不知道用户存放的是什么数据，
所以，比较函数必须由用户自己实现。
2) sk_find
根据数据地址来查找它在堆栈中的位置。
当堆栈设置了比较函数时，它首先对堆栈进行排序，然后通过二分法进行查找。
如果堆栈没有设置比较函数，它只是简单的比较数据地址来查找.
3）sk_sort
本函数对堆栈数据排序。
它首先根据sorted来判断是否已经排序，
如果未排序则调用了标准C函数qsort进行快速排序。
4）sk_pop_free
本函数用于释放堆栈内存放的数据以及堆栈本身，
它需要一个由用户指定的针对具体数据的释放函数。
如果用户仅调用sk_free函数，则只会释放堆栈本身所用的内存，而不会释放数据内存。
3.4 定义用户自己的堆栈¶
STACK_OF(TYPE)
DEFINE_STACK_OF(TYPE)
DEFINE_STACK_OF_CONST(TYPE)
DEFINE_SPECIAL_STACK_OF(FUNCTYPE, TYPE)
DEFINE_SPECIAL_STACK_OF_CONST(FUNCTYPE, TYPE)
/*
test/stack_test.c
*/
3.5 编程示例¶
3.5.1 通用堆栈¶
#include <stdio.h>
#include <openssl/safestack.h>
void popfreeCallBack(void *arg)
{
printf("pop and free %d \n",*(int*)arg);
}
/* ****************
* 通用链表
***************** */
int test_stack()
{
//创建一个空的栈
OPENSSL_STACK *st = OPENSSL_sk_new_null();
int a = 10;
OPENSSL_sk_push(st, &a);
int b = 100;
OPENSSL_sk_push(st, &b);
char *c = "hello";
OPENSSL_sk_push(st, c);
char d[10] = {0};
OPENSSL_sk_push(st, d);
char e = 'A';
OPENSSL_sk_push(st, &e);
//返回栈内数据个数
if (OPENSSL_sk_num(st) == 5) {
printf("sk_num PASS\n");
}
//获取指定index数据
int *getb = OPENSSL_sk_value(st, 1);
if (*getb==b) {
printf("sk_value PASS\n");
}
//获取指定数据，返回index
if (OPENSSL_sk_find(st,"hello") == 2) {
printf("sk_find PASS \n");
}
//在位置2插入一个 数据 TAOBAO,返回总数
if (OPENSSL_sk_insert(st, "TAOBAO", 2) == 6) {
printf("sk_insert PASS\n");
}
int ff = 88;
OPENSSL_sk_push(st, &ff);
//在栈顶移出一个数据, 返回删除的元素
char *popDT = OPENSSL_sk_pop(st);
if (*popDT==ff) {
printf("sk_pop PASS\n");
}
//从栈中移出所有的元素，并释放内存，并且释放st;
//每删除一个元素，回调一次popfreeCallBack回调函数
OPENSSL_sk_pop_free(st, popfreeCallBack);
return 0;
}
int main()
{
test_stack(); // 通用链表
return 0;
}
3.5.2 自定义堆栈¶
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <openssl/safestack.h>
//#define sk_Student_new(st) OPENSSL_sk_new(st)
//#define sk_Student_new_null() OPENSSL_sk_new_null()
//#define sk_Student_free(st) OPENSSL_sk_free(st)
//#define sk_Student_num(st) OPENSSL_sk_num(st)
//#define sk_Student_value(st, i) OPENSSL_sk_value((st), i)
//#define sk_Student_set(st, i, val) OPENSSL_sk_set((st), (i), (val))
//#define sk_Student_zero(st) OPENSSL_sk_zero(Student, (st))
//#define sk_Student_push(st, val) OPENSSL_sk_push((st),(val))
//#define sk_Student_unshift(st, val) OPENSSL_sk_unshift((st), (val))
//#define sk_Student_find(st, val) OPENSSL_sk_find((st), (val))
//#define sk_Student_delete(st, i) OPENSSL_sk_delete((st), (i))
//#define sk_Student_delete_ptr(st, ptr) OPENSSL_sk_delete_ptr((st), (ptr))
//#define sk_Student_insert(st, val, i) OPENSSL_sk_insert((st), (val), (i))
//#define sk_Student_set_cmp_func(st, cmp) OPENSSL_sk_set_cmp_func((st), (cmp))
//#define sk_Student_dup(st) OPENSSL_sk_dup(Student, st)
//#define sk_Student_pop_free(st, free_func) OPENSSL_sk_pop_free((st), (free_func))
//#define sk_Student_shift(st) OPENSSL_sk_shift(st)
//#define sk_Student_pop(st) OPENSSL_sk_pop(st)
//#define sk_Student_sort(st) OPENSSL_sk_sort(st)
typedef struct Student_st {
char *name;
int age;
char *otherInfo;
}Student;
typedef STACK_OF(Student) Students;
DEFINE_STACK_OF(Student) // 重点
Student *Student_Malloc()
{
Student *a=malloc(sizeof(Student));
a->name=malloc(20);
strcpy(a->name,"zcp");
a->otherInfo=malloc(20);
strcpy(a->otherInfo,"no info");
return a;
}
void Student_Free(Student *a)
{
free(a->name);
free(a->otherInfo);
free(a);
}
static int Student_cmp(const Student * const *a, const Student *const *b)
{
int ret;
printf("%s cpmp %s \n",(*a)->name,(*b)->name);
ret=strcmp((*a)->name,(*b)->name);
return ret;
}
int main()
{
Students *s, *snew;
Student *s1, *one, *s2;
int i, num;
s = sk_Student_new_null();
//snew = sk_Student_new((sk_Student_compfunc)Student_cmp);
snew = sk_Student_new(Student_cmp);
s2=Student_Malloc();
sk_Student_push(snew,s2);
i=sk_Student_find(snew,s2);
printf("at : %d \n" ,i );
s1=Student_Malloc();
sk_Student_push(s,s1);
num=sk_Student_num(s);
for(i=0;i<num;i++) {
one=sk_Student_value(s,i);
printf("student name : %s\n",one->name);
printf("sutdent age : %d\n",one->age);
printf("student otherinfo : %s\n\n",one->otherInfo);
}
sk_Student_pop_free(s,Student_Free);
sk_Student_pop_free(snew,Student_Free);
return 0;
}