Srilm 阅读文档2
取自 自然语言处理百科
SArray.cc SArray.h
文档作者：rickjin
创立时间：08.08.24
1、基本类
SArray.cc SArray.h 两个文件主要是以模板方式实现了一个排序数组 SArray, 一共包含三个类 : SArrayBody, SArray, SArrayIter
1) SArray<KeyT, DataT> 是一个从 KeyT 映射到 DataT 的 Map 类型, 使用数组存放其中的数据, 但进行排序
2) SArrayBody<KeyT, DataT> 用于维护 SArray 中的数据
3) SArrayIter 用于遍历 SArray 中数据的迭代器, 用户可以指定自己键值排序函数，然后按照排序的顺序访问数据
2、类接口说明
2.1) SArray 主要接口
<src>
template <class KeyT, class DataT>
class SArray : public Map<KeyT,DataT> //从父类 Map 继承
{
friend class SArrayIter<KeyT,DataT>;
public:
//赋值操作
SArray<KeyT,DataT> &operator= (const SArray<KeyT,DataT> &source);
//查找操作
DataT *find(KeyT key, Boolean &foundP) ;
//插入操作
DataT *insert(KeyT key, Boolean &foundP);
//删除操作
DataT *remove(KeyT key, Boolean &foundP);
//返回内部存放的键值， 当 KeyT 为指针类型的时候很有用
KeyT getInternalKey(KeyT key, Boolean &foundP);
//释放分配的内存, 在析构函数中调用
void clear(unsigned size = 0);
//数组中存入的数据项数目
unsigned numEntries();
protected:
// 内存分配函数
void alloc(unsigned size);
// 键值查找定位函数
Boolean locate(KeyT key, unsigned &index);
void *body; // 数据内存块
static DataT *removedData; // 用于暂存删除的数据
};
</src>
说明：
a. 在数据初始化的过程中， body 指针将指向一个 SArrayBody 对象，
然后数据存放在这个 SArrayBody 中， 而实际的数据访问操作都通过 body
指针进行。 在初始化过程中， 所有分配的内存中的数据项的键值会被初始化为 KeyT
的空值，( 空值由 Map_noKey(KeyT) 函数给出, 参见 Map.h 文件)
b. SArray 中没有存放已经存放的数据项数目的成员变量， 该数值可以通过调用
numEntries() 函数定位到最后一个存放数据项的位置而获取到， 文档作者认为
存放这样一个成员变量会比较方便。
c. 在删除操作 (remove) 中, 被删除的数据暂时存放在 removedData 所指向的内存中，
删除操作完成后返回这个指针，从而用户可以通过指针访问被删除的数据项
2.2) SArrayBody 接口
<src>
template <class KeyT, class DataT>
class SArrayBody
{
friend class SArray<KeyT,DataT>;
friend class SArrayIter<KeyT,DataT>;
unsigned deleted:1; // 布尔型变量， 指示是否有删除操作发生
unsigned maxEntries:31; // 最大可存放的数据项
MapEntry<KeyT,DataT> data[1]; //存放排好序的 (key,value) 数据项
};
</src>
说明：SArrayBody 用于存储 SArray 需要的数据，因而SArray 和 SArrayIter
被声明其友 元 类， 可以直接访问其中的数据。 data[] 数组虽然在声明中的大小为1，
但是在初始化的过 程中， data 指针将指向 size 个数据项大小的内存。
2.3) SArrayIter 主要接口
<src>
template <class KeyT, class DataT>
class SArrayIter
{
//用于键值比较的函数
typedef int (*compFnType)(KeyT, KeyT);
public:
//构造函数, sort 将用于键值排序
SArrayIter(const SArray<KeyT,DataT> &sarray, int (*sort)(KeyT, KeyT) = 0);
//初始化函数， 在构造函数中调用
void init();
//数据迭代基本操作
DataT *next(KeyT &key);
private:
//键值排序函数
void sortKeys();
//下标索引比较函数, 基于下标索引所在的键值进行比较
//调用 sortFunction 指向的比较函数进行键值比较
static int compareIndex(const void *idx1, const void *idx2);
SArrayBody<KeyT,DataT> *mySArrayBody; // 数据内存块 unsigned current; //当前数据项的下标索引 unsigned numEntries; //数组中的数据项数目 int (*sortFunction)(KeyT, KeyT); //用于键值比较的函数 KeyT *sortedKeys; //排好序的键值 }; </src> SArray 的迭代器, 通过排序函数 sortFunction 对 SArray 的键值排序之后存放 在 sortedKeys 中， 然后通过依次扫描 sortedKeys 的键值进行迭代操作
3、主要函数功能说明
3.1) SArray 类主要函数
a) 内存分配函数
参数说明：
@param size 需要分配的数据项目数目
<src>
#define BODY(b) ((SArrayBody<KeyT,DataT> *)b) //指针转换的宏
void SArray<KeyT,DataT>::alloc(unsigned size)
{
body = (SArrayBody<KeyT,DataT> *)
malloc( sizeof(*BODY(body)) + (size - 1) * sizeof(BODY(body)->data[0]) );
BODY(body)->deleted = 0;
BODY(body)->maxEntries = size; //最大可存放的数据项
for (unsigned i = 0; i < size; i ++)
Map_noKey(BODY(body)->data[i].key); //初始化所有的键值
}
</src>
body 指针指向 SArrayBody 对象， 但是对 body 分配的内存不是 SArrayBody
对象的大小， 而是 一个 SArrayBody 对象加上 (size-1) 个 MapEntry
对象。这样就使得 SArrayBody::data[] 数组 实际的大小为size, 而不是声明中的 1。
内存分配结束后， 所有的数据项未被使用， 键值全部 初始化为空值。
b) 内存释放函数
<src>
// 释放当前的内存， 如果 size > 0, 则重新分配相应大小的内存
//@param size 需要重新分配的数据项目数目
void SArray<KeyT,DataT>::clear(unsigned size)
{
if (body)
{
unsigned maxEntries = BODY(body)->maxEntries;
for (unsigned i = 0; i < maxEntries; i++)
{
KeyT thisKey = BODY(body)->data[i].key;
if (Map_noKeyP(thisKey)) //此位置极其之后的数据项没有使用过, 键值为空
break;
Map_freeKey(thisKey); //释放当前键值
}
free(body); //释放所有数据项内存
}
....
}
</src>
此处调用 Map_freeKey(thisKey) 释放内存是必要的, 阅读 Map.h 的 Map_copyKey() 和
Map_freeKey() 的代码了解其背景. 在SArray 中赋值操作 (operator =) 和插入操作
(insert) 是通过 Map_copyKey(key) 把原有的 key 值拷贝一份后进行的,
虽然普通情况下 key 值是 passed by value, 并没有进行内存分配. 但是当 KeyT 为
char* 的时候, Map_copyKey() 有一个特化, 调用 strdup() 把 key 拷贝了一份, 所以
相应的 Map_freeKey() 对于 char* 有一个特化, 调用 free() 函数释放内存.
c) 键值查找定位函数
参数说明：
@param key 要查找的键值
@param index 找到的键值在SArrayBody::data[] 数组中的位置
@return 键值查找是否成功
<src>
Boolean SArray<KeyT,DataT>::locate(KeyT key, unsigned &index) const
{
lower = 0;
upper = BODY(body)->maxEntries;
//二分查找键值
while (lower < upper)
{
...
//查找成功，设置index, 并返回 true
}
//查找失败， 此时 lower == upper
if (lower == BODY(body)->maxEntries || //数组已满, key 大于数组中的所有键值
Map_noKeyP(BODY(body)->data[lower].key) || //lower 指示一空数据项
SArray_compareKey(key, BODY(body)->data[lower].key) < 0) //当前键值 key 小于 lower 指示的键值
{
index = lower;
} else {
index = lower + 1;
}
return false;
}
</src>
locate 函数对键值 key 进行定位， 如果该 key 值已经存在于 SArrayBody::data[] 中，
index 设置为它所在位置，函数返回true; 否则 index 设置为该键值应该被插入的位置,
返回 false. 查找过程中使用 SArray_compareKey() 函数进行键值比较.
二分查找失败的时候， key 值应该被插入的位置可能为 lower 或 lower + 1, 分三种情况
a. lower == BODY(body)->maxEntries
表示数组已满, 已经存在的最大下标为 (maxEntries - 1), 而 key 值大于所有数组中
所有的键值，所以应该插到最后， 即 maxEntries 位置。 此时 maxEntries 位置并没有
分配好内存， 在插入操作 insert 中会进行内存分配。
b. Map_noKeyP(BODY(body)->data[lower].key)
表示当前 lower 指示一空数据项, 当前键值可以插入该位置
c. SArray_compareKey(key, BODY(body)->data[lower].key) < 0)
当前键值 key 小于 lower 指示的键值, 表式 key 应该插入的位置为 lower 指示的位置，
而 lower 处原有的键值, 以及 lower 位置后面的所有数据都应该往后移一个位置。
locate 函数在 find, insert, remove 函数中都将被调用。
d) 数组大小函数
template <class KeyT, class DataT>
unsigned SArray<KeyT,DataT>::numEntries() const
{
//二分查找第一个空值
}
通过二分查找定位到第一个空值所在的下标， 该下标值即为数组的大小。 SArray 中没有
存放已经存放的数据项数目的成员变量， 必须通过调用 numEntries() 函数得到， 文档
作者认为存放这样一个成员变量会比较方便。
e) 键值查找定位函数
参数说明：
@param key 要插入的键值
@param foundP 指示键值是否已经存在数组中
@return 键值所对应的数据指针
<src>
DataT * SArray<KeyT,DataT>::insert(KeyT key, Boolean &foundP)
{
unsigned index;
if (foundP = locate(key, index)) { //键值已经存在， 直接返回数据位置
return &(BODY(body)->data[index].value);
} else {
unsigned nEntries = numEntries();
unsigned maxEntries = BODY(body)->maxEntries;
//键值不存在， 而数组已满， 需要扩充数组为新的键值分配内存
if (nEntries == maxEntries) {
maxEntries = (int)(maxEntries * growSize);
...
body = (SArrayBody<KeyT,DataT> *)realloc(body,
sizeof(*BODY(body)) + (maxEntries - 1) * sizeof(BODY(body)->data[0]));
//初始化所有键值为空
for (unsigned i = BODY(body)->maxEntries; i < maxEntries; i ++)
Map_noKey(BODY(body)->data[i].key);
BODY(body)->maxEntries = maxEntries;
}
//index 此时指示 key 应该插入的位置, 移动数据为该位置腾出空间
memmove(&(BODY(body)->data[index + 1]),
&(BODY(body)->data[index]),
(nEntries - index) * sizeof(BODY(body)->data[0]));
//插入键值
BODY(body)->data[index].key = Map_copyKey(key);
//通过 placement new 调用构造函数对数据做初始化
new (&(BODY(body)->data[index].value)) DataT;
//返回数据指针
return &(BODY(body)->data[index].value);
}
}
</src>
该插入操作中参数只有 key 值， 而不是 (key, value)，所以插入函数返回的是数据
value 的指针， 用户可以通过该指针设置数据 value 的值
f) 删除函数
参数说明：
@param key 要删除的键值
@param foundP 指示键值是否已经存在数组中
@return 指向被删除的数据的指针
<src>
DataT * SArray<KeyT,DataT>::remove(KeyT key, Boolean &foundP)
{
unsigned index;
if (foundP = locate(key, index)) { //找到键值， 开始做删除
unsigned nEntries = numEntries();
//释放键值内存(在 KeyT 为指针类型的时候很有必要
Map_freeKey(BODY(body)->data[index].key);
//把待删除数据存放到暂存空间
memcpy(removedData, &BODY(body)->data[index].value, sizeof(DataT));
//删除之后, 移动数组数据项，保持数据连续
memmove(&(BODY(body)->data[index]),
&(BODY(body)->data[index + 1]),
(nEntries - index - 1) * sizeof(BODY(body)->data[0]));
//键值被删除后置空
Map_noKey(BODY(body)->data[nEntries-1].key);
//指示发生了删除操作
BODY(body)->deleted = 1;
//返回暂存数据指针
return removedData;
}
...
}
</src>
3.2) SArrayIter 类主要函数
a) 键值排序函数
<src>
void SArrayIter<KeyT,DataT>::sortKeys()
{ }
</src>
调用快排对数组只用数据项的键值排序, 排完序的键值存放在 SArrayIter::sortedKeys
中, 排序的键值比较函数 SArrayIter::sortFunction 由用户在构造函数中指定， 如果
sortFunction 为 NULL, 则不进行排序操作， sortedKeys 设置为 NULL
a) 迭代函数
参数说明：
@param key 下一个(key, value)数据项的键值
@return 键值所对应的数据指针
<src>
DataT * SArrayIter<KeyT,DataT>::next(KeyT &key)
{
if (sortedKeys == 0) {// 用户没有指定排序， 按数据存放顺序迭代
// 在迭代过程中发生了一次删除操作
if (mySArrayBody->deleted)
{
numEntries --;
current --;
}
...
index = current++;
} else { // 用户指定排序函数， 按照 sortedKey 顺序进行迭代
SArray<KeyT,DataT> mySArray(0);
mySArray.body = mySArrayBody;
(void)mySArray.locate(sortedKeys[current++], index);
mySArray.body = 0;
}
//复位 deleted 指示变量
mySArrayBody->deleted = 0;
key = mySArrayBody->data[index].key; //设置键值
return &(mySArrayBody->data[index].value); //返回数据指针
}
该函数中是唯一是用 deleted 的地方, 主要是用于监视在迭代过程中是否发生了一次删除
操作.
/* vi: set ts=4 sw=4 et: */
