163 blogs的博客：[转] (3) OpenSSL 之堆栈

堆栈是一种先进后出的数据结构。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中定义如下：

typedef struct stack_st

int (*comp)(const char * const *, const char * const *);

各项意义如下：

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目录下。下面分析了部分函数。

此函数用于设置堆栈存放数据的比较函数。由于堆栈不知道用户存放的是什么数据，所以，比较函数必须由用户自己实现。

根据数据地址来查找它在堆栈中的位置。当堆栈设置了比较函数时，它首先对堆栈进行排序，然后通过二分法进行查找。如果堆栈没有设置比较函数，它只是简单的比较数据地址来查找.

本函数对堆栈数据排序。它首先根据sorted来判断是否已经排序，如果未排序则调用了标准C函数qsort进行快速排序。

本函数用于释放堆栈内存放的数据以及堆栈本身，它需要一个由用户指定的针对具体数据的释放函数。如果用户仅调用sk_free函数，则只会释放堆栈本身所用的内存，而不会释放数据内存。

定义用户自己的堆栈函数

用户直接调用最底层的堆栈操作函数是一个麻烦的事情，对此openssl提供了用宏来帮助用户实现接口。用户可以参考safestack.h来定义自己的上层堆栈操作函数，举例如下，safestack.h定义了如下关于GENERAL_NAME数据结构的堆栈操作：

#define sk_GENERAL_NAME_new(st) SKM_sk_new(GENERAL_NAME, (st))

#define sk_GENERAL_NAME_new_null() SKM_sk_new_null(GENERAL_NAME)

#define sk_GENERAL_NAME_free(st) SKM_sk_free(GENERAL_NAME, (st))

#define sk_GENERAL_NAME_num(st) SKM_sk_num(GENERAL_NAME, (st))

#define sk_GENERAL_NAME_value(st, i) SKM_sk_value(GENERAL_NAME, (st), (i))

#define sk_GENERAL_NAME_set(st, i, val) SKM_sk_set(GENERAL_NAME, (st), (i), (val))

#define sk_GENERAL_NAME_zero(st) SKM_sk_zero(GENERAL_NAME, (st))

#define sk_GENERAL_NAME_push(st, val) SKM_sk_push(GENERAL_NAME, (st), (val))

#define sk_GENERAL_NAME_unshift(st, val) SKM_sk_unshift(GENERAL_NAME, (st), (val))

#define sk_GENERAL_NAME_find(st, val) SKM_sk_find(GENERAL_NAME, (st), (val))

#define sk_GENERAL_NAME_find_ex(st, val) SKM_sk_find_ex(GENERAL_NAME, (st), (val))

#define sk_GENERAL_NAME_delete(st, i) SKM_sk_delete(GENERAL_NAME, (st), (i))

#define sk_GENERAL_NAME_delete_ptr(st, ptr) SKM_sk_delete_ptr(GENERAL_NAME, (st), (ptr))

#define sk_GENERAL_NAME_insert(st, val, i) SKM_sk_insert(GENERAL_NAME, (st), (val), (i))

#define sk_GENERAL_NAME_set_cmp_func(st, cmp) SKM_sk_set_cmp_func(GENERAL_NAME, (st), (cmp))

#define sk_GENERAL_NAME_dup(st) SKM_sk_dup(GENERAL_NAME, st)

#define sk_GENERAL_NAME_pop_free(st, free_func) SKM_sk_pop_free(GENERAL_NAME, (st), (free_func))

#define sk_GENERAL_NAME_shift(st) SKM_sk_shift(GENERAL_NAME, (st))

#define sk_GENERAL_NAME_pop(st) SKM_sk_pop(GENERAL_NAME, (st))

#define sk_GENERAL_NAME_sort(st) SKM_sk_sort(GENERAL_NAME, (st))

#define sk_GENERAL_NAME_is_sorted(st) SKM_sk_is_sorted(GENERAL_NAME, (st))

当用户想对GENERAL_NAME数据进行堆栈操作时，调用上面由宏定义的函数即可，即直观又方便。比如用户想设置堆栈数据的比较函数和对堆栈排序时，他分别调用：sk_GENERAL_NAME_set_cmp_func和sk_GENERAL_NAME_sort。

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <openssl/safestack.h>

#define sk_Student_new(st) SKM_sk_new(Student, (st))

#define sk_Student_new_null() SKM_sk_new_null(Student)

#define sk_Student_free(st) SKM_sk_free(Student, (st))

#define sk_Student_num(st) SKM_sk_num(Student, (st))

#define sk_Student_value(st, i) SKM_sk_value(Student, (st), (i))

#define sk_Student_set(st, i, val) SKM_sk_set(Student, (st), (i), (val))

#define sk_Student_zero(st) SKM_sk_zero(Student, (st))

#define sk_Student_push(st, val) SKM_sk_push(Student, (st), (val))

#define sk_Student_unshift(st, val) SKM_sk_unshift(Student, (st), (val))

#define sk_Student_find(st, val) SKM_sk_find(Student, (st), (val))

#define sk_Student_delete(st, i) SKM_sk_delete(Student, (st), (i))

#define sk_Student_delete_ptr(st, ptr) SKM_sk_delete_ptr(Student, (st), (ptr))

#define sk_Student_insert(st, val, i) SKM_sk_insert(Student, (st), (val), (i))

#define sk_Student_set_cmp_func(st, cmp) SKM_sk_set_cmp_func(Student, (st), (cmp))

#define sk_Student_dup(st) SKM_sk_dup(Student, st)

#define sk_Student_pop_free(st, free_func) SKM_sk_pop_free(Student, (st), (free_func))

#define sk_Student_shift(st) SKM_sk_shift(Student, (st))

#define sk_Student_pop(st) SKM_sk_pop(Student, (st))

#define sk_Student_sort(st) SKM_sk_sort(Student, (st))

typedef struct Student_st

{

char *name;

int age;

char *otherInfo;

}Student;

typedef STACK_OF(Student) Students;

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(Student *a,Student *b)

{

int ret;

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(Student_cmp);

s2=Student_Malloc();

sk_Student_push(snew,s2);

i=sk_Student_find(snew,s2);

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\n",one->otherInfo);

}

sk_Student_pop_free(s,Student_Free);

sk_Student_pop_free(snew,Student_Free);

return 0;

}