OpenCV源码解析之动态内存管理CvMemStorage与CvSeq

末蓝、 2022-08-26 12:27 272阅读 0赞

# 1. CvMemStorage #

一个对象性不强的结构体，它的作用还是在和CvSeq、文件读取等配合中体现出的。

## 1.1 CvMemStorage结构图 ##

![Center][]

## 1.2CvMemStorage ##

定义于core模块下的types\_c.h：

typedef struct CvMemStorage

int signature;

CvMemBlock\* bottom;  /\* First allocatedblock. \*/

CvMemBlock\* top;  /\* Current memory block -top of the stack. \*/

struct CvMemStorage\* parent;  /\* We get new blocks from parent as needed. \*/

int block\_size;   /\* Block size. \*/

int free\_space;   /\* Remaining free space in current block. \*/

CvMemStorage;

**内存存储器是一个可用来存储诸如序列，轮廓，图形,子划分等动态增长数据结构的底层结构。它是由一系列以同等大小的内存块构成，呈列表型\---bottom 域指的是列首，top域指的是当前指向的块但未必是列尾.在bottom和top之间所有的块(包括bottom,不包括top）被完全占据了空间；在top和列尾之间所有的块（包括块尾，不包括top)则是空的；而top块本身则被占据了部分空间\--free\_space指的是top块剩余的空字节数。新分配的内存缓冲区（或显示的通过cvMemStorageAlloc 函数分配，或隐示的通过cvSeqPush,cvGraphAddEdge等高级函数分配）总是起始于当前块（即top块)的剩余那部分，如果剩余那部分能满足要求（够分配的大小）。分配后，free\_space就减少了新分配的那部分内存大小，外加一些用来保存适当列型的附加大小。当top块的剩余空间无法满足被分配的块（缓冲区）大小时，top块的下一个存储块被置为当前块（新的top块）\-- free\_space被置为先前分配的整个块的大小。如果已经不存在空的存储块（即：top块已是列尾），则必须再分配一个新的块（或从parent那继承,见cvCreateChildMemStorage)并将该块加到列尾上去。于是，存储器（memorystorage)就如同栈（Stack)那样,bottom指向栈底，(top,free\_space)对指向栈顶。栈顶可通过cvSaveMemStoragePos保存，通过cvRestoreMemStoragePos恢复指向，通过 cvClearStorage重置。**

## **1.3 CvMemBlock** ##

**内存存储块结构**

typedef  struct CvMemBlock

struct  CvMemBlock\* prev;

struct  CvMemBlock\* next;

CvMemBlock;**CvMemBlock 代表一个单独的内存存储块结构。内存存储块中的实际数据存储在header块之后(即：存在一个头指针 head指向的块 header ，该块不存储数据）,于是，内存块的第i 个字节可以通过表达式 ((char\*)(mem\_block\_ptr+1))\[i\]获得。然而，通常没必要直接去获得存储结构的域。**

## **1.4 CvMemStoragePos** ##

**内存存储块地址**

typedef struct CvMemStoragePos

CvMemBlock\* top;

int free\_space;

CvMemStoragePos;

**该结构（如以下所说）保存栈顶的地址，栈顶可以通过 cvSaveMemStoragePos保存，也可以通过 cvRestoreMemStoragePos 恢复。**

CvMemStorage的相关函数定义在core模块下的datastructs.cpp中。接下来一一分析。

## 1.5 cvCreateMemStorage ##

这里仅仅生成一个CvMemStorage类指针并初始化。

/\* Initialize allocated storage: \*/

static void

icvInitMemStorage(  CvMemStorage\* storage,  int block\_size )

if( !storage )

CV\_Error(CV\_StsNullPtr, "");

if(  block\_size <= 0 )

block\_size=  CV\_STORAGE\_BLOCK\_SIZE; // (1 << 16) – 128 = 65408

block\_size =  cvAlign(block\_size,  CV\_STRUCT\_ALIGN); // CV\_STRUCT\_ALIGN = //sizeof(double) = 8

//  此处cvAlign以(align & (align-1)) == 0检验align，并以(size + align -1)&-align返回对齐//后的size，值得学习的是size&-align为对align的左对齐

assert(  sizeof(CvMemBlock)%  CV\_STRUCT\_ALIGN == 0 );

memset(  storage, 0, sizeof(\*storage )); // core初始化为0

storage\->signature = CV\_STORAGE\_MAGIC\_VAL;

storage\->block\_size= block\_size;

但在这里要着重分析下cvAlloc，这和下面cvReleaseMemStorage中的cvFree是相呼应的。

CV\_IMPL void\* cvAlloc( size\_t size )

returncv::fastMalloc( size );

void\*  fastMalloc(size\_t  size)

uchar\*  udata = (uchar\*)malloc(size \+ sizeof(void\*) +  CV\_MALLOC\_ALIGN);

// 此处多分配了sizeof(void\*)+CV\_MALLOC\_ALIGN的空间，毫无疑问后者//是为了对齐而预留的部分空间（在后面也证实了）；前者的用意是为了保存一//个指向这片内存空间的地址

if(!udata)

return  OutOfMemoryError(size);

uchar\*\*  adata = alignPtr((uchar\*\*)udata \+1, CV\_MALLOC\_ALIGN);

adata\[-1\]=  udata;// 分配的空间地址被保存在这段内存的起始位置

return  adata;// 返回的是可用的空间地址

## 1.6 cvReleaseMemStorage ##

代码如下：

/\*Release memory storage: \*/

CV\_IMPL  void

cvReleaseMemStorage(  CvMemStorage\*\*storage )

if( !storage )

CV\_Error(CV\_StsNullPtr, "");

CvMemStorage\*st = \*storage;

\*storage= 0;

if(  st )

icvDestroyMemStorage(st );

cvFree(&st );

/\*Release all blocks of the storage (or return them to parent, if any): \*/

static void

icvDestroyMemStorage(  CvMemStorage\*storage )

int  k = 0;

CvMemBlock\*block;

CvMemBlock\*dst\_top = 0;

if( !storage )

CV\_Error(CV\_StsNullPtr, "");

if(  storage\->parent)

dst\_top=  storage\->parent\->top;

for(  block = storage\->bottom; block!= 0; k\++ )

CvMemBlock \*temp= block;

block=  block\->next;

if(  storage\->parent)

if(dst\_top )

temp\->prev = dst\_top;

temp\->next = dst\_top\->next;

if(temp\->next)

temp\->next\->prev =temp;

dst\_top=  dst\_top\->next=  temp;// 以上部分将block插入到parent的top之后

else

dst\_top=  storage\->parent\->bottom = storage\->parent\->top= temp;

temp\->prev = temp\->next = 0;

storage\->free\_space = storage\->block\_size \- sizeof(\*temp );// 上面没有修正free\_space的原因是这个值没有变

else

cvFree(&temp );

storage\->top = storage\->bottom = 0;

storage\->free\_space = 0;

最终都调用到cvFree宏函数。其中的关系是cvFree->cvFree\_->cv::fastFree：

void  fastFree(void\*  ptr) // 与fastAlloc对应

if(ptr)

uchar\*udata = ((uchar\*\*)ptr)\[-1\]; // 取出在fastAlloc中多分配的存储内存地址的指针

CV\_DbgAssert(udata< (uchar\*)ptr&&

((uchar\*)ptr \- udata)<= (ptrdiff\_t)(sizeof(void\*)+CV\_MALLOC\_ALIGN));

free(udata); // 调用free释放这段分配的内存

没有直接使用ptr，而是用ptr\[-1\]来存储分配内存的地址，这样的机制使得通过cvAlloc分配的空间只能使用cvFree来释放，如果直接free就会造成内存泄露；而如果malloc之后使用cvFree，ptr与ptr-1不连续，调用就会失败，抛出警告。

## 1.7 cvClearMemStorage ##

修改top和free\_space指向bottom

## 1.8 cvMemStorageAlloc ##

/\*Allocate continuous buffer of the specified size in the storage: \*/

CV\_IMPL  void\*

cvMemStorageAlloc(  CvMemStorage\*storage,  size\_tsize )

schar \*ptr = 0;

if( !storage )

CV\_Error(CV\_StsNullPtr, "NULLstorage pointer" );

if(  size > INT\_MAX)

CV\_Error(CV\_StsOutOfRange, "Toolarge memory block is requested" );

assert(  storage\->free\_space%  CV\_STRUCT\_ALIGN == 0 );

if( (size\_t)storage\->free\_space < size) //当前topMemBlock中的自由空间不足时

size\_tmax\_free\_space = cvAlignLeft(storage\->block\_size\- sizeof(CvMemBlock),CV\_STRUCT\_ALIGN);// 计算对齐后的剩余空间最多能够有多大

if(  max\_free\_space < size)  // 如果要分配的空间很大或者参数错误是个负数

CV\_Error(CV\_StsOutOfRange, "requestedsize is negative or too big" );

icvGoNextMemBlock(storage ); // 创建一个新的MemBlock

ptr =  ICV\_FREE\_PTR(storage);// 宏函数找到当前free space的首地址

assert((size\_t)ptr% CV\_STRUCT\_ALIGN == 0 );

storage\->free\_space = cvAlignLeft(storage\->free\_space\- (int)size,CV\_STRUCT\_ALIGN );//不需要再做内存分配，只要更新free\_space即可

return  ptr;

其中的icvGoNextMemBlock是在top之后添加一个MemBlock，并更新top至新添加的MemBlock，更新free\_space，维护一个MemBlock的双向链表

## 1.9 cvMemStorageAllocString ##

调用cvMemStorageAlloc分配存储字符串的空间(len+1)，\+1是为了储存字符串结束符，然后将字符串copy进该段空间

## 1.10 cvSaveMemStoragePos ##

将top和free\_space保存至CvMemStoragePos结构中

## 1.11 cvRestoreMemStoragePos ##

将CvMemStoragePos中的信息恢复进MemStorage，如果Pos中保存的是top地址为空，相当于将MemStorage进行clear操作

# 2. CvSeq #

### 2.1 CvSeq结构图 ###

![Center 1][]

CvSeq的定义同样出现在types\_c.h中：

typedef  struct CvSeqBlock

struct  CvSeqBlock\* prev;  /\*Previous sequence block. \*/

struct  CvSeqBlock\* next;  /\*Next sequence block. \*/

int  start\_index; /\* Index ofthe first element in the block + \*/

/\* sequence->first->start\_index.\*/

int  count; /\*Number of elements in the block. \*/

schar\* data; /\* Pointer to the first element of the block.\*/

CvSeqBlock;

\#define  CV\_TREE\_NODE\_FIELDS(node\_type) \\

int  flags; /\*Miscellaneous flags. \*/ \\

int  header\_size; /\* Size ofsequence header. \*/ \\

struct  node\_type\*h\_prev;  /\*Previous sequence. \*/ \\

struct  node\_type\*h\_next;  /\* Nextsequence. \*/ \\

struct  node\_type\*v\_prev;  /\* 2ndprevious sequence. \*/ \\

struct  node\_type\*v\_next /\* 2nd next sequence. \*/

/\*

Read/Write sequence.

Elements can be dynamically inserted to ordeleted from the sequence.

\*/

\#define  CV\_SEQUENCE\_FIELDS() \\

CV\_TREE\_NODE\_FIELDS(CvSeq); \\

int  total; /\* Totalnumber of elements. \*/ \\

int  elem\_size; /\* Size ofsequence element in bytes. \*/ \\

schar\*  block\_max; /\* Maximalbound of the last block. \*/ \\

schar\*  ptr; /\*Current write pointer. \*/ \\

int  delta\_elems; /\* Grow seq thismany at a time. \*/ \\

CvMemStorage\*storage; /\* Where the seq is stored. \*/ \\

CvSeqBlock\*free\_blocks; /\* Free blocks list. \*/ \\

CvSeqBlock\*first; /\* Pointer to the first sequence block. \*/

typedef  struct CvSeq

CV\_SEQUENCE\_FIELDS()

\}CvSeq;

仅仅从结构上理解这个struct是不准确的，因为主要是CvSeq在使用中的内存管理才是关键。以下方法多定义在datastructs.cpp内。

### 2.2 cvCreateSeq ###

/\*Create empty sequence: \*/

CV\_IMPL  CvSeq\*

cvCreateSeq(  int seq\_flags,  size\_theader\_size,  size\_telem\_size,  CvMemStorage\*storage )

CvSeq \*seq = 0;

if( !storage )

CV\_Error(CV\_StsNullPtr, "");

if(  header\_size < sizeof(CvSeq ) || elem\_size<= 0 )

CV\_Error(CV\_StsBadSize, "");

/\* allocatesequence header \*/

seq = (CvSeq\*)cvMemStorageAlloc(storage, header\_size);

memset(  seq, 0, header\_size);

seq\->header\_size = (int)header\_size;

seq\->flags = (seq\_flags& ~CV\_MAGIC\_MASK) | CV\_SEQ\_MAGIC\_VAL;

int  elemtype = CV\_MAT\_TYPE(seq\_flags);

int  typesize = CV\_ELEM\_SIZE(elemtype);

if(  elemtype != CV\_SEQ\_ELTYPE\_GENERIC&&  elemtype != CV\_USRTYPE1 &&

typesize!= 0 &&  typesize != (int)elem\_size )

CV\_Error(CV\_StsBadSize,

"Specifiedelement size doesn't match to the size of the specified element type "

"(tryto use 0 for element type)" );

seq\->elem\_size = (int)elem\_size;

seq\->storage = storage;

cvSetSeqBlockSize(seq, (int)((1<< 10)/elem\_size) );// 设定delta\_elems，表示当Seq中的空间不足时，增加多大空间，这里设定的delta\_elems是((1<< 10)/elem\_size)和cvAlignLeft(seq->storage->block\_size- sizeof(CvMemBlock) -sizeof(CvSeqBlock), CV\_STRUCT\_ALIGN)的最小值，此处保留一个疑问：难道CvSeq在CvMemStorage中的保存位置是在每一个CvMemBlock的MemBlock之外？

return  seq;

### 2.3 cvCloneSeq ###

clone函数调用cvSeqSlice函数，该函数是根据CvSlice中给出的起始index以及是否copy数据，取出CvSeq的一部分作为CvSeq结构返回。而clone在调用时将结束位置设置到最大，将起始位置设置为0，并且永远进行数据copy。

CV\_INLINE  CvSeq\*cvCloneSeq(  constCvSeq\*  seq,CvMemStorage\*  storageCV\_DEFAULT(NULL))

return  cvSeqSlice( seq,  CV\_WHOLE\_SEQ,storage, 1 );

通过cvSeqSlice的代码梳理，可以看出CvSeq中的CvSeqBlock所形成的双向链表是一个封闭的环形，也就是说first->prev保存的是最后一个CvSeqBlock的地址

CV\_IMPL  CvSeq\*

cvSeqSlice(  const CvSeq\*  seq, CvSlice  slice, CvMemStorage\*  storage,int copy\_data)

CvSeq\*  subseq = 0;

int  elem\_size, count,length;

CvSeqReaderreader;

CvSeqBlock\*block, \*first\_block= 0, \*last\_block = 0;

if( !CV\_IS\_SEQ(seq))

CV\_Error(CV\_StsBadArg, "Invalidsequence header" );

if( !storage )

storage=  seq\->storage;

if( !storage )

CV\_Error(CV\_StsNullPtr, "NULLstorage pointer" );

elem\_size=  seq\->elem\_size;

length =cvSliceLength( slice,seq );// 此处在length的计算中同样可以看出cvseq内部的环形结构，因为index=index+cvSeq->total

if(  slice.start\_index< 0 )

slice.start\_index \+= seq\->total;

else  if( slice.start\_index >= seq\->total )

slice.start\_index \-= seq\->total;

if( (unsigned)length> (unsigned)seq\->total ||

((unsigned)slice.start\_index>= (unsigned)seq\->total && length!= 0) )

CV\_Error(CV\_StsOutOfRange, "Badsequence slice" );

subseq =cvCreateSeq( seq\->flags, seq\->header\_size, elem\_size,storage );//创建一个新的CvSeq

if(  length > 0 )

cvStartReadSeq(seq, &reader,0 );//初始化CvSeqReader

cvSetSeqReaderPos(&reader, slice.start\_index, 0 );//根据给出的起始index将CvSeqReader更新到当前的index下

count= (int)((reader.block\_max \- reader.ptr)/elem\_size);//当前block中剩余的元素数

intbl = MIN(count,  length);

if(!copy\_data )

\{ //仅copy了CvSeq中的结构，而没有数据

block= (CvSeqBlock\*)cvMemStorageAlloc(storage, sizeof(\*block) );

if(!first\_block )

first\_block= subseq\->first= block\->prev= block\->next= block;

block\->start\_index = 0;//构建仅有一个seqBlock的环

else

block\->prev = last\_block;

block\->next = first\_block;

last\_block\->next = first\_block\->prev = block;

block\->start\_index = last\_block\->start\_index \+ last\_block\->count;//在最后加入新建的seqBlock并更新指针构成新的环路

last\_block=  block;

block\->data = reader.ptr;

block\->count = bl;

subseq\->total \+= bl;

else

cvSeqPushMulti(subseq, reader.ptr, bl, 0 );//需要copy数据时，用reader在CvSeq中读取并附加到subseq队尾

length\-=  bl;

reader.block = reader.block\->next;

reader.ptr = reader.block\->data;

count=  reader.block\->count;//更新reader的位置

while(  length > 0 );

return  subseq;

为了进一步理解CvSeq中的CvSeqBlock的环形结构，可以看到cvSetSeqReaderPos函数中有这样一段：

if( index\+ index <= total)// 如果index处于所有element的前半部分，block向后移动

block=  block\->next;

index\-=  count;

while(  index >= (count=  block\->count));

else// 如果index处于所有element的后半部分，block向前移动

block=  block\->prev;

total\-=  block\->count;

while(  index < total);

index \-=  total;

### 2.4 cvSeqInvert ###

在CvSeq中在before\_index之前插入一个元素，当before\_index处于序列后半部分时，如果空间不足在队尾增加一个block，并移动befor\_index之后的元素后移；如果处于序列的前半部分，遇到空间不足时，在队首增加一个block，更新所有block的start\_index，并将before\_index的前面的元素前移来保持队形。

/\*Insert new element in middle of sequence: \*/

CV\_IMPL  schar\*

cvSeqInsert(  CvSeq\*seq, int before\_index, constvoid \*element)

int  elem\_size;

int  block\_size;

CvSeqBlock\*block;

int  delta\_index;

int  total;

schar\*  ret\_ptr = 0;

if( !seq )

CV\_Error(CV\_StsNullPtr, "");

total =  seq\->total;

before\_index\+=  before\_index < 0 ? total : 0;

before\_index\-=  before\_index > total ?  total : 0;// 以total为周期纠正befor\_index

if( (unsigned)before\_index> (unsigned)total)

CV\_Error(CV\_StsOutOfRange, "");

if(  before\_index == total)

ret\_ptr=  cvSeqPush( seq,element );

else  if( before\_index== 0 )

ret\_ptr=  cvSeqPushFront( seq,element );

else // 在序列中间插入一个元素

elem\_size=  seq\->elem\_size;

if(  before\_index >= total>> 1 )  // 要插入的元素位置在序列后半部分时

schar\*ptr = seq\->ptr \+  elem\_size;

if(ptr > seq\->block\_max )//如果在当前写入点向后移动一个元素位置后会超出seq的边界，就要增加一个block并且写入点后移

icvGrowSeq(seq, 0 );

ptr=  seq\->ptr\+ elem\_size;

assert(ptr <= seq\->block\_max );

delta\_index=  seq\->first\->start\_index;

block=  seq\->first\->prev;

block\->count\++;

block\_size= (int)(ptr\- block\->data);

while(before\_index < block\->start\_index \- delta\_index)

\{ // 由block从后向前，每一个写入位置之后的block中，将自己的前n-1个元素向后移动一个元素位置，并从前一个block中取出最后一个元素copy至自己的第一个元素位置

CvSeqBlock\*prev\_block = block\->prev;

memmove(block\->data\+ elem\_size, block\->data, block\_size\- elem\_size );

block\_size=  prev\_block\->count\*  elem\_size;

memcpy(block\->data,prev\_block\->data\+ block\_size \- elem\_size,elem\_size );

block=  prev\_block;

/\*Check that we don't fall into an infinite loop: \*/

assert(block != seq\->first\->prev);

before\_index= (before\_index \- block\->start\_index \+ delta\_index)\* elem\_size;

memmove(block\->data\+ before\_index \+ elem\_size,block\->data\+ before\_index,

block\_size\- before\_index \- elem\_size); // 将当前block中before\_index本身及之后的元素向后移动

ret\_ptr=  block\->data\+  before\_index;

if(element )

memcpy(ret\_ptr, element,elem\_size );// 将要插入的元素放入更新后的当前位置，并且更新写入点

seq\->ptr = ptr;

else

block=  seq\->first;

if(block\->start\_index== 0 )

icvGrowSeq(seq, 1 );

block=  seq\->first;

//当要插入元素位于序列前半部分时，直接先在队首增加一个block，增加之后first->start\_index为这个新增block能够保存的元素数

delta\_index=  block\->start\_index;

block\->count\++;

block\->start\_index\--;

block\->data \-= elem\_size;//  移出保存新元素的空间

while(before\_index > block\->start\_index \- delta\_index\+ block\->count)

\{ // 此处与前面向后移动是相似的

CvSeqBlock\*next\_block = block\->next;

block\_size=  block\->count\*  elem\_size;

memmove(block\->data,block\->data\+ elem\_size, block\_size\- elem\_size );

memcpy(block\->data\+ block\_size \- elem\_size,next\_block\->data,elem\_size );

block=  next\_block;

/\*Check that we don't fall into an infinite loop: \*/

assert(block != seq\->first );

before\_index= (before\_index \- block\->start\_index \+ delta\_index)\* elem\_size;

memmove(block\->data,block\->data\+ elem\_size, before\_index\- elem\_size );

ret\_ptr=  block\->data\+  before\_index \- elem\_size;

if(element )

memcpy(ret\_ptr, element,elem\_size );

seq\->total = total \+1;

return  ret\_ptr;

### 2.5 cvSeqSort ###

该函数通过传递的比较函数指针，对其中的元素进行排序

### 2.6 cvSeqSearch ###

在序列中查找特定元素：如果给出了cmp\_func，将按照cmp\_func将元素与elem对比，如果没有给出对比函数，则在序列中查找完全等于elem内容的元素。idx中存储的是元素id，userdata是为了协助cmp\_func作为传入参数，is\_sorted指明当前的序列是否已经经过排序，如果已经排序，使用二分查找；如果没有排序，则通过遍历查找。

### 2.7 cvSeqInvert ###

顾名思义，将CvSeq中的元素倒置，本质就是一个循环双向链表的倒置

### 2.8 cvClearSeq ###

这里仅仅调用了cvSeqPopMulti将所有元素弹出，具体的内存空间仍存在于seq的storage中，并没有被释放。当cvClearMemStorage和cvRestoreMemStoragePos均没有被调用时，这段空间仍可以被当前名称的CvSeq使用。

### 2.9 cvSeqPush ###

该部分代码比较简单，可以直接看下面的代码，唯一注意的是它会返回一个指向已经插入了的元素的指针

/\*Push element onto the sequence: \*/

CV\_IMPL  schar\*

cvSeqPush(  CvSeq\*seq, const void \*element )

schar \*ptr = 0;

size\_t  elem\_size;

if( !seq )

CV\_Error(CV\_StsNullPtr, "");

elem\_size=  seq\->elem\_size;

ptr =  seq\->ptr;

if(  ptr >= seq\->block\_max )

icvGrowSeq(seq, 0 );

ptr=  seq\->ptr;

assert(ptr \+ elem\_size<= seq\->block\_max/\*&& ptr == seq->block\_min \*/ );

if(  element )

memcpy(ptr, element,elem\_size );

seq\->first\->prev\->count\++;

seq\->total\++;

seq\->ptr = ptr \+ elem\_size;

return  ptr;

### 2.10 cvSeqPop ###

弹出一个序列尾部的元素至element中，弹出后如果最后一个block中不包含元素时将被CvSeq释放，但该空间仍在storage中，并没有真正释放

/\*Pop last element off of the sequence: \*/

CV\_IMPL  void

cvSeqPop(  CvSeq\*seq, void \*element )

schar \*ptr;

int  elem\_size;

if( !seq )

CV\_Error(CV\_StsNullPtr, "");

if(  seq\->total<= 0 )

CV\_Error(CV\_StsBadSize, "");

elem\_size=  seq\->elem\_size;

seq\->ptr = ptr = seq\->ptr \- elem\_size;

if(  element )

memcpy(element, ptr,elem\_size );

seq\->ptr = ptr;

seq\->total\--;

if( --(seq\->first\->prev\->count)== 0 )

icvFreeSeqBlock(seq, 0 );

assert(seq\->ptr== seq\->block\_max);

### 2.11 cvSeqPushFront ###

在序列首增加一个元素，这里的处理上与cvSeqInsert有很大相似，主要的关注点是在队首的start\_index的维护上

/\*Push element onto the front of the sequence: \*/

CV\_IMPL  schar\*

cvSeqPushFront(  CvSeq\*seq, const void \*element )

schar\*  ptr = 0;

int  elem\_size;

CvSeqBlock\*block;

if( !seq )

CV\_Error(CV\_StsNullPtr, "");

elem\_size=  seq\->elem\_size;

block =  seq\->first;

if( !block || block\->start\_index == 0 )

icvGrowSeq(seq, 1 );

block=  seq\->first;

assert(block\->start\_index> 0 );

ptr =  block\->data\-=  elem\_size;

if(  element )

memcpy(ptr, element,elem\_size );

block\->count\++;

block\->start\_index\--;

seq\->total\++;

return  ptr;

### 2.12 cvSeqPopFront ###

这里与cvSeqPop的区别是两个地方：一是通过first->start\_index来pop第一个元素；二是pop后检查的是第一个block是否不再包含元素，是否需要被CvSeq释放

/\*Shift out first element of the sequence: \*/

CV\_IMPL  void

cvSeqPopFront(  CvSeq\*seq, void \*element )

int  elem\_size;

CvSeqBlock\*block;

if( !seq )

CV\_Error(CV\_StsNullPtr, "");

if(  seq\->total<= 0 )

CV\_Error(CV\_StsBadSize, "");

elem\_size=  seq\->elem\_size;

block =  seq\->first;

if(  element )

memcpy(element, block\->data, elem\_size);

block\->data \+= elem\_size;

block\->start\_index\++;

seq\->total\--;

if( --(block\->count)== 0 )

icvFreeSeqBlock(seq, 1 );

### 2.13 cvSeqPushMulti ###

/\*Add several elements to the beginning or end of a sequence: \*/

//front 表示累加的元素是在sequence的队首还是队尾

CV\_IMPL  void

cvSeqPushMulti(  CvSeq\*seq, const void \*\_elements, int count,  int front )

char \*elements = (char\*) \_elements;

if( !seq )

CV\_Error(CV\_StsNullPtr, "NULLsequence pointer" );

if(  count < 0 )

CV\_Error(CV\_StsBadSize, "numberof removed elements is negative" );

int  elem\_size = seq\->elem\_size;

if( !front )

\{ // 叠加到队尾

while(  count > 0 )

intdelta = (int)((seq\->block\_max\- seq\->ptr)/  elem\_size);// 当前sequence block还能存储多少element

delta=  MIN( delta,count );

if(delta > 0 )

seq\->first\->prev\->count \+= delta;// 最后一个block内的count增加delta

seq\->total \+= delta;// 整体增加delta个元素

count\-=  delta;

delta\*=  elem\_size;

if(elements )

memcpy(seq\->ptr,elements, delta);// 将数据copy进新增元素内

elements\+= delta;

seq\->ptr \+= delta;

if(count > 0 )

icvGrowSeq(seq, 0 );// 在队尾的自由空间中新增一个sequence block，如果不足就分配新的空间

else

CvSeqBlock\*block = seq\->first;

while(  count > 0 )

intdelta;

if(!block || block\->start\_index == 0 )

icvGrowSeq(seq, 1 );

block=  seq\->first;

assert(block\->start\_index> 0 );

delta=  MIN( block\->start\_index, count);

count\-=  delta;

block\->start\_index \-= delta;

block\->count \+= delta;

seq\->total \+= delta;

delta\*=  elem\_size;

block\->data \-= delta;

if(elements )

memcpy(block\->data,elements \+ count\*elem\_size, delta);

###     ###

### 2.14 cvSeqPopMulti ###

### 该部分不做讨论，作用就是在CvSeq的末尾弹出需要的n个元素至传入的地址空间内。需要展开的是其中的icvFreeSeqBlock函数，因为这其中涉及到CvSeq的内存是如何被回收的。回收过程分为三种情况：只有一个CvSeqBlock/有多个block回收最后一个/有多个block回收第一个。 ###

/\* Recycle a sequence block: \*/

static void

icvFreeSeqBlock(  CvSeq \*seq, int in\_front\_of )

CvSeqBlock\*block = seq\->first;

assert((in\_front\_of ? block: block\->prev)->count == 0 );

if(  block == block\->prev ) /\* single block case 仅包含一个CvSeqBlock\*/

block\->count = (int)(seq\->block\_max\- block\->data)+ block\->start\_index\* seq\->elem\_size;

block\->data = seq\->block\_max \- block\->count;

seq\->first = 0;

seq\->ptr = seq\->block\_max = 0;

seq\->total = 0;// 更新一个block的data/count以及seq的first/ptr/total

else

if( !in\_front\_of )

block=  block\->prev;

assert(seq\->ptr== block\->data);

block\->count = (int)(seq\->block\_max\- seq\->ptr);

seq\->block\_max = seq\->ptr =  block\->prev\->data \+

block\->prev\->count\* seq\->elem\_size;// 仅更新末尾block的count和seq的ptr/block\_max

else

intdelta = block\->start\_index;

block\->count = delta \*seq\->elem\_size;

block\->data \-= block\->count;// first block的data置为其首地址

/\* Updatestart indices of sequence blocks: \*/

for(;; )

block\->start\_index \-= delta;

block=  block\->next;

if(block == seq\->first )

break;

seq\->first = block\->next;

block\->prev\->next =block\->next;

block\->next\->prev =block\->prev;// 在循环列表中去掉first block

assert(  block\->count> 0 &&  block\->count %  seq\->elem\_size == 0 );

block\->next = seq\->free\_blocks;

seq\->free\_blocks = block;// 将回收的block添加到seq下free\_blocks的队首

通过以上回收一个CvSeqBlock可以看出，CvSeq虽然做了很多内存管理的工作，但究其根本，仍然是在CvMemStorage分配的空间里维护着自己的一个CvSeqBlock的双向循环列表。它只是在内存不足时会要求CvMemStorage为他继续分配内存，而其他时候内存空间既不会释放也不会再增加。

### 2.15 cvSeqRemove ###

此处与cvSeqInsert只是一个逆过程，并在最后做是否需要CvSeq需要释放空block的检查

### 2.16 cvGetSeqElem ###

这个函数对于理解CvSeq的结构有所帮助，所以也将代码拿来：

/\*Find a sequence element by its index: \*/

CV\_IMPL  schar\*

cvGetSeqElem(  const CvSeq \*seq, int index )

CvSeqBlock\*block;

int  count, total =  seq\->total;

if( (unsigned)index>= (unsigned)total)

index\+=  index < 0 ? total: 0;

index\-=  index >= total?  total : 0;

if( (unsigned)index>= (unsigned)total)

return0;

block =  seq\->first;

if(  index \+ index<=  total )

while(  index >= (count=  block\->count))

block=  block\->next;

index\-=  count;

else

block=  block\->prev;

total\-=  block\->count;

while(  index < total);

index\-=  total;

return  block\->data\+  index \* seq\->elem\_size;

### 2.17 cvSeqElemIdx ###

该函数给出元素的指针element然后返回其在CvSeq中的id以及所在block的指针。

### 2.18 cvStartAppendToSeq、cvStartWriteSeq、cvEndWirteSeq ###

cvStartWriteSeq将调用cvStartAppendToSeq，就是先初始化创建一个CvSeq结构，然后将writer初始化。之后可以通过宏CV\_WRITE\_SEQ\_ELEM来将数据写入序列。cvEndWriteSeq则作为这一写入过程的结束操作。

1. CvMemStorage\* storage = cvCreateMemStorage(0);

2.  CvSeq\* seq = cvCreateSeq(CV\_32SC1,**sizeof**(CvSeq),**sizeof**(**int**),storage);

3.  CvSeqWriter writer;

4.  CvSeqReader reader;

5.  **int** i;

6.  cvStartAppendToSeq(seq,&writer);

7.  **for** (i=0;i<10;i++)

8.  \{

9.  **int** val = rand() % 100;

10.  CV\_WRITE\_SEQ\_ELEM(val,writer);

11.  printf("%d is written\\n",val);

12.  \}

13.  cvEndWriteSeq(&writer);

cvStartWriteSeq相当于其中的先cvCreateSeq然后再cvStartAppendToSeq。

### 2.19 cvStartReadSeq ###

首先来看CvSeqReader的定义：

\#define  CV\_SEQ\_READER\_FIELDS() \\

int  header\_size; \\

CvSeq\*  seq; /\* sequence,beign read \*/ \\

CvSeqBlock\*  block; /\* currentblock \*/ \\

schar\*  ptr; /\* pointer toelement be read next \*/ \\

schar\*  block\_min; /\* pointer to thebeginning of block \*/\\

schar\*  block\_max; /\* pointer to theend of block \*/ \\

int  delta\_index;/\* = seq->first->start\_index \*/ \\

schar\*  prev\_elem; /\* pointer toprevious element \*/

typedef  struct CvSeqReader

CV\_SEQ\_READER\_FIELDS()

CvSeqReader;

而cvStartReadSeq仅仅是对CvSeqReader结构的初始化而已，参数reverse表示是从后往前读（!=0），还是从前往后读(==0)

/\*Initialize sequence reader: \*/

CV\_IMPL  void

cvStartReadSeq(  const CvSeq \*seq, CvSeqReader \* reader,int reverse)

CvSeqBlock\*first\_block;

CvSeqBlock\*last\_block;

if(  reader )

reader\->seq = 0;

reader\->block = 0;

reader\->ptr = reader\->block\_max = reader\->block\_min = 0;

if( !seq || !reader)

CV\_Error(CV\_StsNullPtr, "");// 以上均为检验

reader\->header\_size = sizeof(CvSeqReader );

reader\->seq = (CvSeq\*)seq;

first\_block=  seq\->first;

if(  first\_block )

last\_block=  first\_block\->prev;

reader\->ptr = first\_block\->data;

reader\->prev\_elem = CV\_GET\_LAST\_ELEM(seq, last\_block);

reader\->delta\_index = seq\->first\->start\_index;

if(  reverse )// reverse被置为非0时，当前元素指针ptr与前一个元素指针prev\_elem交换，当前block成为上一个block，即last\_block

schar\*temp = reader\->ptr;

reader\->ptr = reader\->prev\_elem;

reader\->prev\_elem = temp;

reader\->block = last\_block;

else

reader\->block = first\_block;

reader\->block\_min = reader\->block\->data;// 指向当前block的首

reader\->block\_max = reader\->block\_min \+ reader\->block\->count\* seq\->elem\_size;// 指向当前block的尾

else

reader\->delta\_index = 0;

reader\->block = 0;

reader\->ptr = reader\->prev\_elem = reader\->block\_min = reader\->block\_max = 0;

[Center]: /images/20220824/90959ebe967d4fe7a5bfdfbf7d73b4e4.png
[Center 1]: /images/20220824/139811ae8ec2461d916b35b99e8a0b91.png

OpenCV源码解析之动态内存管理CvMemStorage与CvSeq

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 Nginx源码剖析之内存池，与内存管理

相关 OpenCV源码解析之CascadeClassifier多尺度检测

相关 OpenCV源码解析之动态内存管理CvMemStorage与CvSeq

相关 OpenCV源码解析之CascadeClassifier多尺度检测

相关 nginx源码解析(二)-内存池与内存管理ngx_pool_t

相关 OpenCV源码解析之Mat类理解及内存管理

相关 OpenCV源码解析之基本数据类型操作与概念

相关 OpenCV源码解析：动态内存管理（CvMemStorage与CvSeq）

相关 OpenCV源码解析之findContours

相关 Memcached源码分析之内存管理