整体上说，OpenCV的内存管理比较复杂。他不象其他很多库文件，把内在管理交给操作系统，而是通过大量的类，函数，和结构，自己实现对内存的动态管理。
1. 内存存储器CvMemStorage一个对象性不强的结构体，它的作用还是在和CvSeq、文件读取等配合中体现出的。
1.1 CvMemStorage结构图结构图如下所示，每个block内存块的头部，都是一个CvMemBlock的结构，然后才是供使用的内存空间，
通常情况下，block中的内容，都是CvSeq或CvSet结构或其派生结构，如序列，轮廓，图形,子划分等动态增长数据结构，这一点非常重要，我们在后面会详细讲到。
1.2 CvMemStorage
定义于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;（1） 内存存储器是一个可用来存储诸如序列，轮廓，图形,子划分等动态增长数据结构的底层结构。它是由一系列以同等大小的内存块构成，呈列表型
---bottom 域指的是列首，
---top域指的是当前指向的块但未必是列尾.
在bottom和top之间所有的块(包括bottom,不包括top）被完全占据了空间；在top和列尾之间所有的块（包括块尾，不包括top)则是空的；
（2）top块本身则被占据了部分空间,
参数free_space指的是top块剩余的空字节数。新分配的内存缓冲区（或显式地通过cvMemStorageAlloc 函数分配，或隐式的通过cvSeqPush, cvGraphAddEdge等高级函数分配）总是起始于当前块（即top块）的剩余那部分，如果剩余那部分能满足要求（够分配的大小）。分配后，free_space就减少了新分配的那部分内存大小，外加一些用来保存适当列型的附加大小。
当top块的剩余（小部分）空间无法满足被分配的块（缓冲区）大小时，top块的下一个存储块被置为当前块（新的top块）， free_space被置为该top块的整个块的大小（所以上一个块那个小部分空间被浪费掉了）。如果已经不存在空的存储块（即：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。内存存储块中的实际数据存储在header块之后（即：存在一个头指针 head指向的块 header ，该块不存储数据），于是，内存块的第i 个字节可以通过表达式 ((char *)(mem_block_ptr+1))[i]获得。然而，通常没必要直接去获得存储结构的域。
1.4 CvMemStoragePos内存存储块地址，定义在core/datastructs.cpp
typedef struct CvMemStoragePos
{
CvMemBlock* top;
int free_space;
}
CvMemStoragePos;该结构保存栈顶的地址，他通常和cvSaveMemStoragePos及cvRestoreMemStoragePos一起配合使用：栈顶可以通过 cvSaveMemStoragePos保存，也可以通过 cvRestoreMemStoragePos 恢复。
cvSaveMemStoragePos将top和free_space保存至CvMemStoragePos结构中，
/* Remember memory storage position: */
CV_IMPL void
cvSaveMemStoragePos( const CvMemStorage * storage, CvMemStoragePos * pos )
{
if( !storage || !pos )
CV_Error( CV_StsNullPtr, "" );
pos->top = storage->top;
pos->free_space = storage->free_space;
}将CvMemStoragePos中的信息恢复进MemStorage，如果Pos中保存的top地址为空，相当于将MemStorage进行clear操作,
/* Restore memory storage position: */
CV_IMPL void
cvRestoreMemStoragePos( CvMemStorage * storage, CvMemStoragePos * pos )
{
if( !storage || !pos )
CV_Error( CV_StsNullPtr, "" );
if( pos->free_space > storage->block_size )
CV_Error( CV_StsBadSize, "" );
storage->top = pos->top;
storage->free_space = pos->free_space;
if( !storage->top )
{
storage->top = storage->bottom;
storage->free_space = storage->top ?
storage->block_size - sizeof(CvMemBlock) : 0;
}
}函数功能：生成一个CvMemStorage类指针并初始化。
/* Initialize allocated storage: */
static void
icvInitMemStorage( CvMemStorage* storage, int block_size )
{
if( !storage )
CV_Error( CV_StsNullPtr, "" );
if( block_size block_size = block_size;
}这里要说明一下OpenCv中的节对齐
cvAlignLeft vs. cvAlign我们看一下cvAlign和cvAlignLeft函数，cvAlign采用“入”的方式对齐，保证空间不比size小；cvAlignLeft采用“舍”的方式对齐，保证空间不比size大，也称为左对齐；这里参数align是指对齐的位数，比如8位或32位，源码的区别如下
static inline int cvAlign( int size, int align )
{
CV_DbgAssert( (align & (align-1)) == 0 && size < INT_MAX );
return (size + align - 1) & -align;
}
CV_INLINE int
cvAlignLeft( int size, int align )
{
return size & -align;
}另外我们要特别注意这个cvAlloc，他和cvReleaseMemStorage中的cvFree是相呼应的。也就是说，cvAlloc和cvFree必须成对使用。
cvAlloc这里要注意，下面udata多分配了sizeof(void*)+CV_MALLOC_ALIGN的空间，前者是为了保存一个指向这片内存空间的地址；后者是为了对齐而预留的部分空间，对齐的目的是为了加快计算（比如在对齐的情况下才能运行的SIMD指令，一次能运行4个int的加法，共计128位）；
// 在64位机中，CV_MALLOC_ALIGN的宏定义是：
// #define CV_MALLOC_ALIGN 64
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);
if(!udata)
return OutOfMemoryError(size);
uchar** adata = alignPtr((uchar**)udata +1, CV_MALLOC_ALIGN);
// 分配的sizeof(void*)空间,用来保存这段内存的起始地址位置（释放时要用到）
adata[-1]= udata;
// 返回的是对齐后可用空间的首地址
return adata;
}代码如下：
/*Release memory storage: */
CV_IMPL void
cvReleaseMemStorage( CvMemStorage**storage )
{
if( !storage )
CV_Error(CV_StsNullPtr, "");
CvMemStorage* st = *storage;
*storage= 0;
if( st )
{
icvDestroyMemStorage(st); //释放storage中的block内存块
cvFree(&st); // 释放storage结构体,
}
}
/*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;
// 循环处理storage的block内存块,如果不能挂载到parent节点，就直接释放该block的内存。
for( block = storage->bottom; block!= 0; k++ )
{
CvMemBlock *temp= block; // storage中的block内存块
block= block->next; // 下一个block内存块(从此，temp->next=block）
// 如果storage有parent节点，则直接插入到parent节点内存块的链表上
// 如果storage没有parent节点，则直接释放内存
if( storage->parent)
{
if(dst_top )
{
//将block插入到parent的top之后
temp->prev = dst_top;
temp->next = dst_top->next;
if(temp->next)
temp->next->prev =temp;
dst_top= dst_top->next= temp;
}
else
{
// 如果parent没有block块，则直接把temp当成parent的bottom/top块
dst_top= storage->parent->bottom = storage->parent->top= temp;
temp->prev = temp->next = 0;
// sizeof(*temp) 是CvMemBlock结构的大小
storage->free_space = storage->block_size - sizeof(*temp );
}
}
else
{
cvFree(&temp );
}
}
storage->top = storage->bottom = 0;
storage->free_space = 0;
}其中在链表的dst_top之后插入temp的操作示意图如下（一般情况下after是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)parent )
icvDestroyMemStorage( storage );
else
{
storage->top = storage->bottom;
storage->free_space = storage->bottom ?
storage->block_size - sizeof(CvMemBlock) : 0;
}
}该函数在OpenCV中调用非常频繁，其功能是分配一个size大小的可使用空间，并返回该空间的指针。这个空间往往是分配给CvSeq，CvSet或其派生结构使用。
/*Allocate continuous buffer of the specified size in the storage: */
CV_IMPL void*
cvMemStorageAlloc( CvMemStorage* storage, size_t size )
{
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) //当前top所指的block内存块中的自由空间不足时
{
size_t max_free_space = cvAlignLeft(storage->block_size - sizeof(CvMemBlock),
CV_STRUCT_ALIGN);// 对齐后的剩余空间最多有多大
if( max_free_space < size) // 如果要分配的空间比block最大可用空间还大，或者参数为负
CV_Error(CV_StsOutOfRange, "requestedsize is negative or too big" );
icvGoNextMemBlock(storage ); // 创建一个新的MemBlock
}
ptr = ICV_FREE_PTR(storage); // 宏函数: 找到当前free space的首地址
/*
#define ICV_FREE_PTR(storage)
((schar*)(storage)->top + (storage)->block_size - (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对齐空间，cvAlignLeft是避免越界。不需要再做内存分配，只要更新free_space即可,
return ptr;
}在上面的函数中，当剩余空间不足以分配所需（max_free_space < size）时，就会调用icvGoNextMemBlock是在CvMemStorage的top之后添加一个block内存块，并更新free_space，维护一个CvMemBlock的双向链表。
/* Moves stack pointer to next block.
If no blocks, allocate new one and link it to the storage: */
static void
icvGoNextMemBlock( CvMemStorage * storage )
{
if( !storage )
CV_Error( CV_StsNullPtr, "" );
if( !storage->top || !storage->top->next )
{
CvMemBlock *block;
if( !(storage->parent) )
{
// 如果没有parent节点，就直接创建一个block内存块
block = (CvMemBlock *)cvAlloc( storage->block_size );
}
else
{
// 如果有parent节点，就插入一个新节点到parent的top后面
// 目的是新建block时，需要用到parent的参数，所以就直接放到了parent的top
CvMemStorage *parent = storage->parent;
CvMemStoragePos parent_pos;
cvSaveMemStoragePos( parent, &parent_pos );
icvGoNextMemBlock( parent ); // 添加一个block到parent节点的top
block = parent->top;
cvRestoreMemStoragePos( parent, &parent_pos );
// 下面这个if-else语句，可以简单理解为断绝block与parent的关系
// 因为上面这个block是放在parent的末尾(即top）的
if( block == parent->top ) /* the single allocated block */
{
// 如果parent节点只有一个block, 也就是上面创建的那个
assert( parent->bottom == block );
parent->top = parent->bottom = 0; // parent节点清零，不再关联block
parent->free_space = 0;
}
else
{
/* cut the block from the parent's list of blocks */
parent->top->next = block->next;
if( block->next)
block->next->prev = parent->top;
}
}
/* link block to the current storage structure */
// 此时block必然已经断绝与parent的关系
block->next = 0;
block->prev = storage->top;
if( storage->top )
storage->top->next = block;
else
storage->top = storage->bottom = block;
}
/* make the last block to top */
if( storage->top->next )
storage->top = storage->top->next;
storage->free_space = storage->block_size - sizeof(CvMemBlock);
assert( storage->free_space % CV_STRUCT_ALIGN == 0 );
}调用cvMemStorageAlloc分配存储字符串的空间(len+1)，+1是为了储存字符串结束符，然后将字符串copy进该段空间，
CV_IMPL CvString
cvMemStorageAllocString( CvMemStorage* storage, const char* ptr, int len )
{
CvString str;
memset(&str, 0, sizeof(CvString));
str.len = len >= 0 ? len : (int)strlen(ptr);
str.ptr = (char*)cvMemStorageAlloc( storage, str.len + 1 );
memcpy( str.ptr, ptr, str.len );
str.ptr[str.len] = '\0';
return str;
}2. CvSeq
OpenCV中最重要的动态内存管理序列是CvSeq，他以链表的形式存在，也是所有OpenCV动态数据结构的基础。OpenCV中，CvSeq序列及其派生序列可以存储多种不同的结构。可以将序列想象为许多编程语言中都存在的容器类或容器类模版(如C++中的vector或list)。序列在内存被实现为一个双端队列(deque)，从而可以实现快速的随机访问。
2.1 数据结构 CvSeqCvSeq的定义同样出现在types_c.h中，他通过建立一个block内存块链表来管理内存，定义如下
#define CV_TREE_NODE_FIELDS(node_type) \
int flags; /* 标识. */ \
int header_size; /* 序列头的大小 */ \
struct node_type* h_prev; /* 水平方向上的前一个序列 */ \
struct node_type* h_next; /* 水平方向上的下一个序列 */ \
struct node_type* v_prev; /*垂直方向上的上一个序列 */ \
struct node_type* v_next /* 垂直方向上的下一个序列 */
/*
Read/Write sequence.
Elements can be dynamically inserted to or deleted from the sequence.
*/
#define CV_SEQUENCE_FIELDS() \
CV_TREE_NODE_FIELDS(CvSeq); \
int total; /* 元素总和 */ \
int elem_size; /* 序列元素的大小,用字节表示. */ \
schar* block_max; /* 最后块的最大区间 */ \
schar* ptr; /* 写指针的当前位置 */ \
int delta_elems; /* 当序列增长时有多少元素需要重新分配(序列的粒度). */ \
CvMemStorage* storage; /* Where the seq is stored. */ \
CvSeqBlock* free_blocks; /* 自由块列表 */ \
CvSeqBlock* first; /* 指向第一个块的指针 */
typedef struct CvSeq
{
CV_SEQUENCE_FIELDS()
}
CvSeq;可以看出，他通过宏定义 简化了带有附加参数的结构，使得CvSeq的扩展极为容易，在CvSeq的基础上，用户可以自己定义一个新的数据结构，也可以使用宏CV_SEQUENCE_FIELDS()包括CvSeq域后再放入用户自定义的域。OpenCV的很多其他结构，如CvSet，CvChain, CvContour等就是通过包括宏CV_SEQUENCE_FIELDS()然后再添加一些其他参数而组成。
值得说明的是，此处这个count的注释，严格地来说是不准确的，在实际应用中，他的意思是可能是（1）对于free blocks：count表示CvSeq序列的free blocks中还有多少个字节可供使用（往往是在计算中作为临时变量使用）；（2） 对于已经使用的blocks: 该blocks中已经分配有多少个数据元素，比如有多少个FileNode节点。
各个参数的解释如下：
域header_size含有序列头部节点的实际大小,此值大于或等于sizeof(CvSeq)
域h_prev,h_next,v_prev,v_next可用来创建不同序列的层次结构。域h_prev和h_next指向同意层次结构的前一个和后一个序列，域v_prev和v_next指向垂直方向结构上的前一个和后一个序列，很多情况下你只需要用到其中的一对即可。
域first指向第一个序列块
域total包含稠密序列的总元素数和稀疏序列被分配的节点数
域flags的高16位描述(包含)特定的动态结构类型(CV_SEQ_MAGIC_VAL表示稠密序列，CV_SET_MAGIC_VAL表示稀疏序列)，flags本身同事还包含形形色色的其他信息：
(1)标准的序列元素类型
#define CV_SEQ_ELTYPE_POINT CV_32SC2 /* (x,y) */
#define CV_SEQ_ELTYPE_CODE CV_8UC1 /* freeman code: 0..7 */
#define CV_SEQ_ELTYPE_GENERIC 0
#define CV_SEQ_ELTYPE_PTR CV_USRTYPE1
#define CV_SEQ_ELTYPE_PPOINT CV_SEQ_ELTYPE_PTR /* &(x,y) */
#define CV_SEQ_ELTYPE_INDEX CV_32SC1 /* #(x,y) */
#define CV_SEQ_ELTYPE_GRAPH_EDGE 0 /* &next_o, &next_d, &vtx_o, &vtx_d */
#define CV_SEQ_ELTYPE_GRAPH_VERTEX 0 /* first_edge, &(x,y) */
#define CV_SEQ_ELTYPE_TRIAN_ATR 0 /* vertex of the binary tree */
#define CV_SEQ_ELTYPE_CONNECTED_COMP 0 /* connected component */
#define CV_SEQ_ELTYPE_POINT3D CV_32FC3 /* (x,y,z) */(2)通用序列类型
#define CV_SEQ_KIND_GENERIC (0 key = key(rect)。
当返回到icvXMLParseValue后，只需要继续填充elem节点的内容（左上角x,y,右下角x,y），即可完成该子节点的操作。
// persistance_c.cpp
CV_IMPL CvFileNode*
cvGetFileNode( CvFileStorage* fs, CvFileNode* _map_node,
const CvStringHashNode* key,
int create_missing )
{
CvFileNode* value = 0;
int k = 0, attempts = 1;
if( !fs )
return 0;
CV_CHECK_FILE_STORAGE(fs);
if( !key )
CV_Error( CV_StsNullPtr, "Null key element" );
if( _map_node )
{
if( !fs->roots )
return 0;
attempts = fs->roots->total;
}
for( k = 0; k < attempts; k++ )
{
int i, tab_size;
CvFileNode* map_node = _map_node;
CvFileMapNode* another;
CvFileNodeHash* map;
if( !map_node )
map_node = (CvFileNode*)cvGetSeqElem( fs->roots, k );
CV_Assert(map_node != NULL);
if( !CV_NODE_IS_MAP(map_node->tag) )
{
if( (!CV_NODE_IS_SEQ(map_node->tag) || map_node->data.seq->total != 0) &&
CV_NODE_TYPE(map_node->tag) != CV_NODE_NONE )
CV_Error( CV_StsError, "The node is neither a map nor an empty collection" );
return 0;
}
map = map_node->data.map;
tab_size = map->tab_size;
if( (tab_size & (tab_size - 1)) == 0 )
i = (int)(key->hashval & (tab_size - 1));
else
i = (int)(key->hashval % tab_size);
for( another = (CvFileMapNode*)(map->table[i]); another != 0; another = another->next )
if( another->key == key )
{
if( !create_missing )
{
value = &another->value;
return value;
}
CV_PARSE_ERROR( "Duplicated key" );
}
if( k == attempts - 1 && create_missing )
{
// 从map生成一个新的node(获取node空间)
CvFileMapNode* node = (CvFileMapNode*)cvSetNew( (CvSet*)map );
node->key = key;
node->next = (CvFileMapNode*)(map->table[i]);
map->table[i] = node;
value = (CvFileNode*)node;
}
}
return value;
}
2.3 读取节点信息cvGetFileNodeByName
从各节点中读取节点信息的函数是cvGetFileNodeByName，它采用Hash快速排序的方法，快速地从fs中读取CvFileNode。
CV_IMPL CvFileNode*
cvGetFileNodeByName( const CvFileStorage* fs, const CvFileNode* _map_node, const char* str )
{
CvFileNode* value = 0;
int i, len, tab_size;
unsigned hashval = 0;
int k = 0, attempts = 1;
if( !fs )
return 0;
CV_CHECK_FILE_STORAGE(fs);
if( !str )
CV_Error( CV_StsNullPtr, "Null element name" );
// 计算Hash值及表的序号i.
for( i = 0; str[i] != '\0'; i++ )
hashval = hashval*CV_HASHVAL_SCALE + (unsigned char)str[i];
hashval &= INT_MAX;
len = i; // 字符串长度
if( !_map_node )
{
if( !fs->roots )
return 0;
attempts = fs->roots->total;
}
for( k = 0; k < attempts; k++ )
{
CvFileNodeHash* map;
const CvFileNode* map_node = _map_node;
CvFileMapNode* another;
if( !map_node )
map_node = (CvFileNode*)cvGetSeqElem( fs->roots, k );
if( !CV_NODE_IS_MAP(map_node->tag) )
{
if( (!CV_NODE_IS_SEQ(map_node->tag) || map_node->data.seq->total != 0) &&
CV_NODE_TYPE(map_node->tag) != CV_NODE_NONE )
CV_Error( CV_StsError, "The node is neither a map nor an empty collection" );
return 0;
}
map = map_node->data.map;
tab_size = map->tab_size;
// 从Hash值hashval得到表的序号i
if( (tab_size & (tab_size - 1)) == 0 )
i = (int)(hashval & (tab_size - 1));
else
i = (int)(hashval % tab_size);
for( another = (CvFileMapNode*)(map->table[i]); another != 0; another = another->next )
{
const CvStringHashNode* key = another->key;
// 如果Hash值，序号等都匹配的话，就返回读取的节点
if( key->hashval == hashval &&
key->str.len == len &&
memcmp( key->str.ptr, str, len ) == 0 )
{
value = &another->value;
return value;
}
}
}
return value;
}
2.4 常用节点的结构定义
为了方便，我这里列出常用节点的结构定义，
hash & node
// ref. types_c.h
typedef struct CvString
{
int len;
char* ptr;
}
CvString;
/** All the keys (names) of elements in the readed file storage
are stored in the hash to speed up the lookup operations: */
typedef struct CvStringHashNode
{
unsigned hashval;
CvString str;
struct CvStringHashNode* next;
}
CvStringHashNode;
/** Basic element of the file storage - scalar or collection: */
typedef struct CvFileNode
{
int tag;
struct CvTypeInfo* info; /**< type information
(only for user-defined object, for others it is 0) */
union
{
double f; /**< scalar floating-point number */
int i; /**< scalar integer number */
CvString str; /**< text string */
CvSeq* seq; /**< sequence (ordered collection of file nodes) */
CvFileNodeHash* map; /**< map (collection of named file nodes) */
} data;
}
CvFileNode;
// ref. persistance.cpp
typedef struct CvFileMapNode
{
CvFileNode value;
const CvStringHashNode* key;
struct CvFileMapNode* next;
}
CvFileMapNode;
// 一些常的Hash定义
typedef struct CvGenericHash
{
CV_SET_FIELDS()
int tab_size;
void** table;
}
CvGenericHash;
typedef CvGenericHash CvStringHash;
typedef struct CvGenericHash CvFileNodeHash;
2.5 CvSeq操作函数
2.5.1 cvCreateSeq
功能：创建一序列
参数：seq_flags为序列的符号标志。如果序列不会被传递给任何使用特定序列的函数，那么将它设为0，否则从预定义的序列类型中选择一合适的类型。 Header_size为序列头部的大小；必须大于或等于sizeof(CvSeq)。如果制定了类型或它的扩展名，则此类型必须适合基类的头部大小。 Elem_size为元素的大小，以字节计。这个大小必须与序列类型（由seq_flags指定）相一致。例如，对于一个点的序列，元素类型 CV_SEQ_ELTYPE_POINT应当被指定，参数elem_size必须等同于sizeof(CvPoint)。 Storage为指向前面定义的内存存储器
值得说明的是，不论是CvSet，CvSeq，还是其派生结构如CvMap, CvGenericHash, CvStringHash，最后都会调用cvCreateSeq来生成链表，并设置元素大小等初始化函数。
/*Create empty sequence: */
CV_IMPL CvSeq*
cvCreateSeq( int seq_flags, size_t header_size, size_t elem_size, CvMemStorage*storage )
{
CvSeq *seq = 0;
if( !storage )
CV_Error(CV_StsNullPtr, "");
if( header_size < sizeof(CvSeq ) || elem_sizeheader_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)((1storage )
CV_Error( CV_StsNullPtr, "" );
if( delta_elements < 0 )
CV_Error( CV_StsOutOfRange, "" );
useful_block_size = cvAlignLeft(seq->storage->block_size - sizeof(CvMemBlock) -
sizeof(CvSeqBlock), CV_STRUCT_ALIGN);
elem_size = seq->elem_size;
if( delta_elements == 0 )
{
delta_elements = (1 useful_block_size )
{
delta_elements = useful_block_size / elem_size;
if( delta_elements == 0 )
CV_Error( CV_StsOutOfRange, "Storage block size is too small "
"to fit the sequence elements" );
}
seq->delta_elems = delta_elements; // 修改分配粒度
}
2.5.3 icvGrowSeq
这个函数往往用来分配新的元素空间，他对理解OpenCV的block内存分配非常重要，所以源码中给出了非常详细的注释。
可以自出，当添加block时，seq的block链表是往前面生长的；值得说明的是，在使用block中的空间，往里面填数据时，是往后添加数据的，这一点可以参考cvSeqPush函数。
参考宏定义：
#define ICV_ALIGNED_SEQ_BLOCK_SIZE
(int)cvAlign(sizeof(CvSeqBlock), ((int)sizeof(double)))
/* The function allocates space for at least one more sequence element.
If there are free sequence blocks (seq->free_blocks != 0)
they are reused, otherwise the space is allocated in the storage: */
static void
icvGrowSeq( CvSeq *seq, int in_front_of )
{
CvSeqBlock *block;
if( !seq )
CV_Error( CV_StsNullPtr, "" );
block = seq->free_blocks;
if( !block ) // 如果还没有自由的block空间
{
// 每个element的大小（举例：这个element,有可能是一个FileNode）
int elem_size = seq->elem_size;
// 每次最少分配的elements个数
int delta_elems = seq->delta_elems;
// 放数据的地方
CvMemStorage *storage = seq->storage;
// （最多只能是4倍delta_elems）如果total已经超过4倍的步长delta_elems,说明步长太小
if( seq->total >= delta_elems*4 )
// 扩大步长（seq->delta_elems = delta_elements;）
cvSetSeqBlockSize( seq, delta_elems*2 );
if( !storage )
CV_Error( CV_StsNullPtr, "The sequence has NULL storage pointer" );
/* If there is a free space just after last allocated block
and it is big enough then enlarge the last block.
This can happen only if the new block is added to the end of sequence: */
if( (size_t)(ICV_FREE_PTR(storage) - seq->block_max) < CV_STRUCT_ALIGN &&
storage->free_space >= seq->elem_size && !in_front_of )
{
int delta = storage->free_space / elem_size;
delta = MIN( delta, delta_elems ) * elem_size;
seq->block_max += delta;
storage->free_space = cvAlignLeft((int)(((schar*)storage->top
+ storage->block_size) - seq->block_max), CV_STRUCT_ALIGN );
return;
}
else
{
// 扩充data_elements个元素所需要的字节数
int delta = elem_size * delta_elems + ICV_ALIGNED_SEQ_BLOCK_SIZE;
/* Try to allocate elements: */
// 如果自由空间大小不够扩充所需
if( storage->free_space < delta )
{
// 那就看delta_elems/3个元素的小空间small_block_size
int small_block_size = MAX(1, delta_elems/3)*elem_size +
ICV_ALIGNED_SEQ_BLOCK_SIZE;
/* try to allocate smaller part */
if( storage->free_space >= small_block_size + CV_STRUCT_ALIGN )
{
// to ensure delta bytes of space can be allocated
// within free_space
delta = (storage->free_space - ICV_ALIGNED_SEQ_BLOCK_SIZE)
/seq->elem_size;
delta = delta*seq->elem_size + ICV_ALIGNED_SEQ_BLOCK_SIZE;
}
else
{
// 如果delta_emems/3个元素都容纳不下，那就在storage中开辟新的空间吧
icvGoNextMemBlock( storage );
assert( storage->free_space >= delta );
}
}
// 从storage中分配delta个字节的内存空间
block = (CvSeqBlock*)cvMemStorageAlloc( storage, delta );
// 对齐所需要的使用空间
block->data = (schar*)cvAlignPtr( block + 1, CV_STRUCT_ALIGN );
// 对齐后的总空间
block->count = delta - ICV_ALIGNED_SEQ_BLOCK_SIZE;
block->prev = block->next = 0;
}
}
else
{
seq->free_blocks = block->next;
}
// 把新建的CvSeqBlock block插入到first之前
// 如果seq->first为空，则该block是第0个
if( !(seq->first) )
{
seq->first = block; // seq序列的第0个block地址
block->prev = block->next = block;
}
// 如果seq->first非空，则block插入到set->first的前面
// （可见seq的block链表是往前面生长的）
else
{
block->prev = seq->first->prev;
block->next = seq->first;
block->prev->next = block->next->prev = block;
}
/* For free blocks the field means
* total number of bytes in the block.
*
* For used blocks it means current number
* of sequence elements in the block:
*/
assert( block->count % seq->elem_size == 0 && block->count > 0 );
if( !in_front_of )
{
// 本block的数据起始位置
seq->ptr = block->data;
// 本block的最大位置
seq->block_max = block->data + block->count;
// 本block的起始元素序号
block->start_index = block == block->prev ? 0 :
block->prev->start_index + block->prev->count;
}
else
{
int delta = block->count / seq->elem_size;
block->data += block->count;
if( block != block->prev )
{
assert( seq->first->start_index == 0 );
seq->first = block;
}
else
{
seq->block_max = seq->ptr = block->data;
}
block->start_index = 0;
for( ;; )
{
block->start_index += delta;
block = block->next;
if( block == seq->first )
break;
}
}
block->count = 0;
}
2.5.4 icvFreeSeqBlock
/* 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 */
{
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;
}
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;
}
else
{
int delta = block->start_index;
block->count = delta * seq->elem_size;
block->data -= block->count;
/* Update start 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;
}
assert( block->count > 0 && block->count % seq->elem_size == 0 );
block->next = seq->free_blocks;
seq->free_blocks = block;
}
2.5.5 cvSetNew
从cvSeq中分配内存给CvSetElem或其派生元素
/** Fast variant of cvSetAdd */
CV_INLINE CvSetElem* cvSetNew( CvSet* set_header )
{
CvSetElem* elem = set_header->free_elems;
if( elem )
{
set_header->free_elems = elem->next_free;
elem->flags = elem->flags & CV_SET_ELEM_IDX_MASK;
set_header->active_count++;
}
else
cvSetAdd( set_header, NULL, &elem );
return elem;
}
2.5.6 cvSetAdd
这个重点是理解cvSetAdd。他为inserted_element分配内存空间，返回时inserted_element是当前可以使用的有效内存的指针。当内在空间set->free_elems尚不存在时，cvSetAdd会用icvGrowSeq去申请一个新的block。
/* Add new element to the set: */
CV_IMPL int
cvSetAdd( CvSet* set, CvSetElem* element, CvSetElem** inserted_element )
{
int id = -1;
CvSetElem *free_elem;
if( !set )
CV_Error( CV_StsNullPtr, "" );
if( !(set->free_elems) )
{
int count = set->total;
int elem_size = set->elem_size;
schar *ptr;
icvGrowSeq( (CvSeq *) set, 0 );
// ref. icvGrowSeq, seq->free_blocks的起始地址
set->free_elems = (CvSetElem*) (ptr = set->ptr);
// 从ptr开始，把block的内存空间分配给尽可能多的CvSetElem
for( ; ptr + elem_size block_max; ptr += elem_size, count++ )
{
((CvSetElem*)ptr)->flags = count | CV_SET_ELEM_FREE_FLAG;
((CvSetElem*)ptr)->next_free = (CvSetElem*)(ptr + elem_size);
}
assert( count next_free = 0;
//一个block内形成一个环形链表，头指向尾
set->first->prev->count += count - set->total;
set->total = count;
set->ptr = set->block_max;
}
// 把free_elem这个元素空出来使用，free_elems指向下一个空元素
free_elem = set->free_elems;
set->free_elems = free_elem->next_free;
id = free_elem->flags & CV_SET_ELEM_IDX_MASK;
if( element )
memcpy( free_elem, element, set->elem_size );
free_elem->flags = id;
set->active_count++; // 更新当前活跃元素的序号
if( inserted_element )
*inserted_element = free_elem;
return id;
}
2.5.7 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的计算中同样可以看出cvseq内部的环形结构，因为index=index+cvSeq->total
length =cvSliceLength( slice,seq );
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" );
//创建一个新的CvSeq
subseq =cvCreateSeq( seq->flags, seq->header_size, elem_size,storage );
if( length > 0 )
{
cvStartReadSeq(seq, &reader,0 );//初始化CvSeqReader
//根据给出的起始index将CvSeqReader更新到当前的index下
cvSetSeqReaderPos(&reader, slice.start_index, 0 );
//当前block中剩余的元素数
count= (int)((reader.block_max - reader.ptr)/elem_size);
do
{
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;
//在最后加入新建的seqBlock并更新指针构成新的环路
block->start_index = last_block->start_index + last_block->count;
}
last_block= block;
block->data = reader.ptr;
block->count = bl;
subseq->total += bl;
}
else
//需要copy数据时，用reader在CvSeq中读取并附加到subseq队尾
cvSeqPushMulti(subseq, reader.ptr, bl, 0 );
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 next;
index-= count;
}
while( index >= (count= block->count));
}
else// 如果index处于所有element的后半部分，block向前移动
{
do
{
block= block->prev;
total-= block->count;
}
while( index < total);
index -= total;
}
2.5.8 cvSeqInvert
顾名思义，将CvSeq中的元素倒置，本质就是一个循环双向链表的倒置
在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;
//如果在当前写入点向后移动一个元素位置后会超出seq的边界，就要增加一个block并且写入点后移
if(ptr > seq->block_max )
{
icvGrowSeq(seq, 0 );
ptr= seq->ptr+ elem_size;
assert(ptr 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;
// 将当前block中before_index本身及之后的元素向后移动
memmove(block->data+ before_index + elem_size,block->data+ before_index,
block_size- before_index - elem_size);
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.9 cvSeqSort
该函数通过传递的比较函数指针，对其中的元素进行排序
2.5.10 cvSeqSearch
在序列中查找特定元素：如果给出了cmp_func，将按照cmp_func将元素与elem对比，如果没有给出对比函数，则在序列中查找完全等于elem内容的元素。idx中存储的是元素id，userdata是为了协助cmp_func作为传入参数，is_sorted指明当前的序列是否已经经过排序，如果已经排序，使用二分查找；如果没有排序，则通过遍历查找。
2.5.11 cvClearSeq
这里仅仅调用了cvSeqPopMulti将所有元素弹出，具体的内存空间仍存在于seq的storage中，并没有被释放。当cvClearMemStorage和cvRestoreMemStoragePos均没有被调用时，这段空间仍可以被当前名称的CvSeq使用。
2.5.12 cvSeqPush
功能 函数cvSeqPush添加元素到序列的尾部
说明: 函数cvSeqPush在序列块的尾部添加一元素并返回指向该元素的指针. 如果输入参数为NULL, 则函数仅分配一空间, 留给下一个元素使用.
该部分代码比较简单，可以直接看下面的代码，唯一注意的是它会返回一个指向已经插入了的元素的指针
/* 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 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.5.13 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 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.5.14 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.5.15 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 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.5.16 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 )
{
// 当前sequence block还能存储多少element
intdelta = (int)((seq->block_max- seq->ptr)/ elem_size);
delta= MIN( delta,count );
if(delta > 0 )
{
// 最后一个block内的count增加delta
seq->first->prev->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 )
// 在队尾的自由空间中新增一个sequence block，如果不足就分配新的空间
icvGrowSeq(seq, 0 );
}
}
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.5.17 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的count和seq的ptr/block_max
block->prev->count* seq->elem_size;
}
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;
// 在循环列表中去掉first block
block->next->prev =block->prev;
}
assert( block->count> 0 && block->count % seq->elem_size == 0 );
block->next = seq->free_blocks;
// 将回收的block添加到seq下free_blocks的队首
seq->free_blocks = block;
}
通过以上回收一个CvSeqBlock可以看出，CvSeq虽然做了很多内存管理的工作，但究其根本，仍然是在CvMemStorage分配的空间里维护着自己的一个CvSeqBlock的双向循环列表。它只是在内存不足时会要求CvMemStorage为他继续分配内存，而其他时候内存空间既不会释放也不会再增加。
2.5.18 cvSeqRemove
此处与cvSeqInsert只是一个逆过程，并在最后做是否需要CvSeq释放空block的检查
2.5.19 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= (count= block->count))
{
block= block->next;
index-= count;
}
}
else
{
do
{
block= block->prev;
total-= block->count;
}
while( index < total);
index-= total;
}
return block->data+ index * seq->elem_size;
}
2.5.20 cvSeqElemIdx
该函数给出元素的指针element然后返回其在CvSeq中的id以及所在block的指针。
2.5.21 cvStartAppendToSeq、cvStartWriteSeq、cvEndWirteSeq
cvStartWriteSeq将调用cvStartAppendToSeq，就是先初始化创建一个CvSeq结构，然后将writer初始化。之后可以通过宏CV_WRITE_SEQ_ELEM来将数据写入序列。cvEndWriteSeq则作为这一写入过程的结束操作。
CvMemStorage* storage = cvCreateMemStorage(0);
CvSeq* seq = cvCreateSeq(CV_32SC1,**sizeof**(CvSeq),**sizeof**(**int**),storage);
CvSeqWriter writer;
CvSeqReader reader;
**int** i;
cvStartAppendToSeq(seq,&writer);
**for** (i=0;ifirst->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;
// reverse被置为非0时，当前元素指针ptr与前一个元素指针prev_elem交换，
// 当前block成为上一个block，即last_block
if( reverse )
{
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的首
// 指向当前block的尾
reader->block_max = reader->block_min + reader->block->count* seq->elem_size;
}
else
{
reader->delta_index = 0;
reader->block = 0;
reader->ptr = reader->prev_elem = reader->block_min = reader->block_max = 0;
}
}
