OpenSSL---stack_of堆栈

矫情吗；* 2023-07-04 12:47 11阅读 0赞

堆栈是一种先进后出的数据结构。是一种只允许在其一端进行插入或者删除的线性表。允许插入或删除操作的一端为栈顶，另一端称为栈底。对堆栈的插入和删除操作称为入栈和出栈。

**1.1     概述**  
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）。

**1.2     堆栈相关结构描述**  
OpenSSL堆栈数据结构在crypto/stack/stack.h中定义，其详细定义如下：

typedef struct stack\_st  
\{  
int num;  
char \*\*data;  
int sorted;  
   
int num\_alloc;  
int (\*comp)(const void \*, const void \*);  
\} \_STACK;  /\* Use STACK\_OF(...) instead \*/

主要项意义如下：

num：int数据类型，堆栈中存放数据的个数。

data：char \*\*数据类型，用于存放数据地址，每个数据地址存放在data\[0\]到data\[num-1\]中。

sorted：int数据类型，该堆栈是否排序，若已经排序，则为1，否则为0。堆栈数据一般是无序的，只有当用户调用了sk\_sort操作，其值才为1。

num\_alloc：int数据类型，分配内存的次数。

comp：回调函数，堆栈内存放数据的比较函数地址，此函数用于排序和查找操作；当用户生成一个新堆栈时，可以指定comp为用户实现的一个比较函数；或当堆栈已经存在时通过调用sk\_set\_cmp\_func函数来重新指定比较函数。

1.3     堆栈相关函数  
用户直接调用最底层的堆栈操作函数是一个麻烦的事情，对此openssl提供了用宏来帮助用户实现接口。用户可以参考safestack.h来定义自己的上层堆栈操作函数。openssl堆栈实现源码位于crypto/stack目录下。

1.3.1    新建一个堆栈对象函数sk\_new\_null  
函数功能：新建一个堆栈对象\_STACK。该函数直接调用sk\_new函数，参数直接传的是(int (\*)(const void \*, const void \*))0。

函数定义：

\_STACK \*sk\_new\_null(void);  
参数说明：

无。

返回值：若堆栈对象\_STACK新建成功，则直接返回堆栈对象\_STACK的指针。否则返回NULL。

1.3.2    根据对象比较函数来创建一个堆栈对象函数sk\_new  
函数功能：根据对象比较函数来创建一个堆栈对象\_STACK。该函数首先调用OPENSSL\_malloc函数给对象分配内存，然后给每个对象分配相对应的内存。注意：数据地址首先分配的是4个。

函数定义：

\_STACK \*sk\_new(int (\*cmp)(constvoid \*, const void \*));

参数说明：

cmp：\[in\]回调函数，对象的比较函数。

返回值：若堆栈对象\_STACK新建成功，则直接返回堆栈对象\_STACK的指针。否则返回NULL。

1.3.3    释放堆栈自己的内存空间函数sk\_free  
函数功能：释放堆栈自己的内存空间函数。该函数首先调用OPENSSL\_free函数释放掉数据地址，然后再调用OPENSSL\_free函数释放掉堆栈对象本身。

函数定义：

void sk\_free(\_STACK \*st);

参数说明：

st：\[in\] \_STACK \*数据类型，需要释放的堆栈对象。

返回值：无。

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

函数定义：

void sk\_pop\_free(\_STACK \*st,void (\*func)(void \*));

参数说明：

st：\[in\] \_STACK \*数据类型，需要释放的堆栈对象。

func：\[in\]对象的释放函数。

返回值：无。

1.3.5    向堆栈中插入数据函数sk\_insert  
函数功能：根据指定的位置往堆栈对象中插入数据。该函数首先判断堆栈对象是否需要分配内存空间，若需要，则分配内存空间。然后将数据添加到指定的位置。

函数定义：

int sk\_insert(\_STACK \*sk, void \*data, int where);

参数说明：

sk：\[in\] \_STACK \*数据类型，需要添加数据的堆栈对象。

data：\[in\] void \*数据类型，需要添加的数据。

where：\[in\] int数据类型，需要插入的位置。

返回值：返回堆栈对象中数据的个数。

1.3.6    删除指定位置的堆栈对象函数sk\_delete  
函数功能：删除指定位置的堆栈对象。该函数首先判断需要删除数据的位置是否合法，若不合法，则返回。然后循环移位赋值。

函数定义：

void \*sk\_delete(\_STACK \*st,int loc);

参数说明：

sk：\[in\] \_STACK \*数据类型，需要删除数据的堆栈对象。

loc：\[in\] int数据类型，需要删除的位置。

返回值：若删除成功，则直接返回删除的堆栈数据。否则返回NULL。

1.3.7    从堆栈对象中删除指定的对象值函数sk\_delete\_ptr  
函数功能：从堆栈对象中删除指定的对象值。该函数首先遍历整个堆栈对象中的对象值，判断每个堆栈对象值是否与需要删除的对象值相等，若相等，则删除，并返回值。

函数定义：

void \*sk\_delete\_ptr(\_STACK \*st,void \*p);

参数说明：

sk：\[in\] \_STACK \*数据类型，需要删除数据的堆栈对象。

p：\[in\] void \*数据类型，需要删除的对象值。

返回值：若堆栈对象中有需要删除的值，则返回删除成功后的值；若没有，则直接返回NULL。

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

函数定义：

int sk\_find(\_STACK \*st,void \*data);

参数说明：

sk：\[in\] \_STACK \*数据类型，需要查找数据的堆栈对象。

p：\[in\] void \*数据类型，需要查找的对象值。

返回值：若堆栈中有该对象，则返回它的位置，否则返回-1。

1.3.9    根据对象值从堆栈中查找它的位置函数sk\_find\_ex  
函数功能：根据数据地址来查找它在堆栈中的位置。当堆栈设置了比较函数时，它首先对堆栈进行排序，然后通过二分法进行查找。如果堆栈没有设置比较函数，它只是简单的比较数据地址来查找。

函数定义：

int sk\_find\_ex(\_STACK \*st,void \*data);

参数说明：

sk：\[in\] \_STACK \*数据类型，需要查找数据的堆栈对象。

p：\[in\] void \*数据类型，需要查找的对象值。

返回值：若堆栈中有该对象，则返回它的位置，否则返回-1。

1.3.10 向堆栈栈顶插入数据函数sk\_push  
函数功能：向堆栈栈顶插入数据。该函数实际上调用的是sk\_insert函数，最后一个参数传的是st->num。

函数定义：

int sk\_push(\_STACK \*st,void \*data);

参数说明：

sk：\[in\] \_STACK \*数据类型，需要添加数据的堆栈对象。

data：\[in\] void \*数据类型，需要添加的数据。

返回值：返回堆栈对象中数据的个数。

1.3.11 往堆栈栈底插入数据函数sk\_unshift  
函数功能：往堆栈栈底插入一条数据。该函数实际上调用的是sk\_insert函数，最后一个参数传的是0。

函数定义：

int sk\_unshift(\_STACK \*st,void \*data);

参数说明：

sk：\[in\] \_STACK \*数据类型，需要添加数据的堆栈对象。

data：\[in\] void \*数据类型，需要添加的数据。

返回值：返回堆栈对象中数据的个数。

1.3.12 删除栈底的数据函数sk\_shift  
函数功能：删除栈底的数据。该函数实际上调用的是sk\_delete函数，第二个参数传的是0。

函数定义：

void \*sk\_shift(\_STACK \*st);

参数说明：

sk：\[in\] \_STACK \*数据类型，需要删除数据的堆栈对象。

返回值：若删除成功，则直接返回删除的堆栈数据。否则返回NULL。

1.3.13 删除栈顶的数据函数sk\_pop  
函数功能：删除栈顶的数据。该函数实际上调用的是sk\_delete函数，第二个参数传的是st->num - 1。

函数定义：

void \*sk\_shift(\_STACK \*st);

参数说明：

sk：\[in\] \_STACK \*数据类型，需要删除数据的堆栈对象。

返回值：若删除成功，则直接返回删除的堆栈数据。否则返回NULL。

1.3.14 初始化堆栈对象的数据值的函数sk\_zero  
函数功能：初始化堆栈对象的数据值。该函数直接调用memset函数来初始化堆栈对象的数据值。

函数定义：

void sk\_zero(\_STACK \*st);

参数说明：

sk：\[in\] \_STACK \*数据类型，需要初始化的堆栈对象。

返回值：无。

1.3.15 设置堆栈存放数据的比较函数sk\_set\_cmp\_func  
函数功能：设置堆栈存放数据的比较函数。由于堆栈不知道用户存放的是什么数据，所以，比较函数必须由用户自己实现。

函数定义：

int (\*sk\_set\_cmp\_func(\_STACK \*sk,int (\*c)(const void \*, const void \*)))  
(const void \*, const void \*);  
参数说明：

sk：\[in\] \_STACK \*数据类型，需要设置比较函数的堆栈对象。

c：比较函数。

返回值：若设置成功，则返回比较函数。否则返回原来的比较函数。

1.3.16 堆栈对象的复制函数sk\_dup  
函数功能：复制一个堆栈对象。该函数首先声明一个堆栈对象，然后将需要复制的堆栈对象逐个赋值。

函数定义：

\_STACK \*sk\_dup(\_STACK \*st);

参数说明：

sk：\[in\] \_STACK \*数据类型，需要复制的堆栈对象。

返回值：若复制成功，则返回堆栈对象指针，否则返回NULL。

1.3.17 对堆栈数据排序函数sk\_sort  
函数功能：对堆栈中的数据进行排序。它首先根据sorted来判断是否已经排序，如果未排序则调用了标准C函数qsort进行快速排序。

函数定义：

void sk\_sort(\_STACK \*st);

参数说明：

sk：\[in\] \_STACK \*数据类型，需要排序的堆栈对象。

返回值：无。

1.3.18 获取堆栈对象中的排序标识函数sk\_is\_sorted  
函数功能：获取堆栈对象中的排序标识。

函数定义：

int sk\_is\_sorted(const \_STACK \*st);

参数说明：

sk：\[in\] const \_STACK \*数据类型，需要获取值的堆栈对象。

返回值：堆栈对象排序标识。

1.3.19 获取堆栈对象中的数据的总数函数sk\_num  
函数功能：获取堆栈对象中的数据的总数。

函数定义：

int sk\_num(const \_STACK \*st );

参数说明：

sk：\[in\] const \_STACK \*数据类型，需要获取值的堆栈对象。

返回值：堆栈对象中的数据的总数。

1.3.20 获取指定位置的堆栈对象中的数据函数sk\_value  
函数功能：获取指定位置的堆栈对象中的数据。

函数定义：

void \*sk\_value(const \_STACK \*st,int i);

参数说明：

sk：\[in\] const \_STACK \*数据类型，需要获取值的堆栈对象。

i：\[in\] int数据类型，指定位置。

返回值：堆栈对象中的数据值指针。

**1.4     应用实例**  
本实例中，首先声明一个people\_info\_st对象，然后利用宏定义来操作底层的堆栈处理函数。

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <openssl/safestack.h>
    #include <openssl/crypto.h>
     
    #define sk_PEOPLE_INFO_new(cmp)                                                     SKM_sk_new(PEOPLE_INFO, (cmp))
    #define sk_PEOPLE_INFO_new_null()                                           SKM_sk_new_null(PEOPLE_INFO)
    #define sk_PEOPLE_INFO_free(st)                                                SKM_sk_free(PEOPLE_INFO, (st))
    #define sk_PEOPLE_INFO_num(st)                                                SKM_sk_num(PEOPLE_INFO, (st))
    #define sk_PEOPLE_INFO_value(st, i)                                           SKM_sk_value(PEOPLE_INFO, (st), (i))
    #define sk_PEOPLE_INFO_set(st, i, val)                               SKM_sk_set(PEOPLE_INFO, (st), (i), (val))
    #define sk_PEOPLE_INFO_zero(st)                                                SKM_sk_zero(PEOPLE_INFO, (st))
    #define sk_PEOPLE_INFO_push(st, val)                               SKM_sk_push(PEOPLE_INFO, (st), (val))
    #define sk_PEOPLE_INFO_unshift(st, val)                                     SKM_sk_unshift(PEOPLE_INFO, (st), (val))
    #define sk_PEOPLE_INFO_find(st, val)                                 SKM_sk_find(PEOPLE_INFO, (st), (val))
    #define sk_PEOPLE_INFO_delete(st, i)                                SKM_sk_delete(PEOPLE_INFO, (st), (i))
    #define sk_PEOPLE_INFO_delete_ptr(st, ptr)                      SKM_sk_delete_ptr(PEOPLE_INFO, (st), (ptr))
    #define sk_PEOPLE_INFO_insert(st, val, i)                           SKM_sk_insert(PEOPLE_INFO, (st), (val), (i))
    #define sk_PEOPLE_INFO_set_cmp_func(st, cmp)              SKM_sk_set_cmp_func(PEOPLE_INFO, (st), (cmp))
    #define sk_PEOPLE_INFO_dup(st)                                                 SKM_sk_dup(PEOPLE_INFO, st)
    #define sk_PEOPLE_INFO_pop_free(st, free_func)             SKM_sk_pop_free(PEOPLE_INFO, (st), (free_func))
    #define sk_PEOPLE_INFO_shift(st)                                      SKM_sk_shift(PEOPLE_INFO, (st))
    #define sk_PEOPLE_INFO_pop(st)                                                 SKM_sk_pop(PEOPLE_INFO, (st))
    #define sk_PEOPLE_INFO_sort(st)                                                 SKM_sk_sort(PEOPLE_INFO, (st))
     
    typedef struct people_info_st
    {
    char       *name, *otherInfo;
    int        age;
    }PEOPLE_INFO;
     
    PEOPLE_INFO *PEOPLE_INFO_Malloc()
    {
    PEOPLE_INFO *a= ( PEOPLE_INFO * )OPENSSL_malloc(sizeof(PEOPLE_INFO));
     
    a->name = ( char * )OPENSSL_malloc(20);
    strcpy( a->name, "zcp" );
    a->otherInfo = ( char * )OPENSSL_malloc(20);
    strcpy( a->otherInfo, "no info" );
    a->age = 20;
     
    return a;
    }
     
    void PEOPLE_INFO_Free( PEOPLE_INFO *a )
    {
    OPENSSL_free( a->name );
    OPENSSL_free( a->otherInfo );
    OPENSSL_free( a );
    }
     
    static int PEOPLE_INFO_cmp( const PEOPLE_INFO *const *a, const PEOPLE_INFO *const *b )
    {
    int ret;
    /* 只比较关键字 */
    ret = strcmp(  (*a)->name, (*b)->name );
     
    return ret;
    }
     
    int main( int argc, char *argv[] )
    {
    STACK_OF(PEOPLE_INFO)      *s,*snew;
    PEOPLE_INFO          *s1,*one,*s2;
    int                  i, num;
     
    /* 新建一个堆栈对象 */
    s = sk_PEOPLE_INFO_new_null();
     
    /* 新建一个堆栈对象 */
    snew = sk_PEOPLE_INFO_new( PEOPLE_INFO_cmp );
     
    s2 = PEOPLE_INFO_Malloc();
     
    sk_PEOPLE_INFO_push( snew, s2 );
    i=sk_PEOPLE_INFO_find( snew, s2 );
    s1 = PEOPLE_INFO_Malloc();
    sk_PEOPLE_INFO_push( s, s1 );
     
    num = sk_PEOPLE_INFO_num( s );
     
    for( i = 0;i< num; i++ )
    {
              printf("堆栈s中的数据有：\n" );
               one = sk_PEOPLE_INFO_value( s, i );
               printf("PEOPLE_INFO name :    %s\n",one->name );
               printf("PEOPLE_INFO age  :     %d\n",one->age );
              printf("PEOPLE_INFO otherinfo :      %s\n\n\n",one->otherInfo );
               printf("\n\n");
    }
     
    for( i = 0;i< num; i++ )
    {
               printf("堆栈snew中的数据有：\n" );
               one = sk_PEOPLE_INFO_value( snew, i );
               printf("PEOPLE_INFO name :    %s\n",one->name );
               printf("PEOPLE_INFO age  :     %d\n",one->age );
               printf("PEOPLE_INFO otherinfo :      %s\n\n\n",one->otherInfo );
               printf("\n\n");
    }
    sk_PEOPLE_INFO_pop_free( s, PEOPLE_INFO_Free );
    sk_PEOPLE_INFO_pop_free( snew, PEOPLE_INFO_Free );
     
    return 0;
    
    }