TC官方文档翻译05----Hash Map对象API(Tokyo Cabinet/Tokyo Tyarnt 文档系列)

wsql

浏览: 11793848 次
性别:
来自: 深圳

最近访客更多访客>>

GDGZWQZ

IT_way

qq_33632159

mhx1535

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (14573)

社区版块

存档分类

2013-03 ( 19)
2013-02 ( 15)
2013-01 ( 268)
更多存档...

/**
* 转载请注明出处, 由于个人技术能力有限, 英语水平欠缺,
* 有翻译不合适或错误的地方, 请纠正,
* 希望不要因为我的错误误导您, 希望您的智慧可以加入.
* @translator: selfimpr
* @mail: lgg860911@yahoo.com.cn
* @blog: http://blog.csdn.net/lgg201
*/

Hash Map 的 API

typedef struct _TCMAPREC { //HASH MAP 元素结构定义

int32_t ksiz; //key 的大小

int32_t vsiz; //value 的大小

struct _TCMAPREC *left; // 左子节点用来维护二叉搜索树

struct _TCMAPREC *right; // 右子节点

struct _TCMAPREC *pref; // 前一个元素用来维护链表

struct _TCMAPREC *next; // 后一个元素

} TCMAPREC;

typedef struct { //HASH MAP 结构定义

TCMAPREC **buckets; // 桶数组

TCMAPREC *first; // 第一个元素

TCMAPREC *last; // 最后一个元素

TCMAPREC *cur; // 当前元素

uint32_t bnum; // 桶大小

uint64_t rnum; // 记录个数

uint64_t msiz; // 总大小 ( 字节数 )

} TCMAP;

TCMAP *tcmapnew(void);

创建 4093( 默认值 ) 个桶的 map

TCMAP *tcmapnew2(uint32_t bnum);

创建指定数量桶的 map.

MAP 有一个预定义的最小内存使用量 131072, 如果 bnum 指定的数量个桶占用空间小于该值 , 则按该值分配 , 否则按实际量来分配内存 . MAP 对象的其实属性都设置为空或 0 等默认值 .

TCMAP *tcmapnew3(const char *str, …);

接受不定个字符串 , 以每两个为一对 key-value 的方式初始化一个 MAP 对象 , 该 MAP 对象实际上是调用 tcmapnew2 创建的 , 初始元素个数是 31.

TCMAP *tcmapdup(const TCMAP *map);

取传入的 map 的 bnum, rnum 以及 TCMAPDEFBNUM(4093) 中最大的值作为桶数量调用 tcmapnew2 创建一个 map, 把参数 map 中的记录拷贝到新的 map 中并返回

void tcmapdel(TCMAP *map);

完全释放一个 map 对象 .

void tcmapput(TCMAP *map, const void *kbuf, int ksiz, const void *vbuf, int vsiz);

map: 要插入数据的 map 对象

kbuf: key 字符串指针

ksiz: key 的大小 , 如果 ksiz 超过 TCMAPKMAXSIZ(0XFFFFFF), 区 0XFFFFFF.

vbuf: 值的字符串指针

vsiz: 值的大小

1. 用 TCMAPHASH1 算法对 key 求一个 hash 值 , 并通过这个值得到 key 对应的桶数组索引 .

2. 分别获取到桶和桶的地址

3. 用 TCMAPHASH2 对 key 再次求 hash, 将 hash 值与 ~TCMAPKMAXSIZ 做与运算 ( 求反 )

4. 接下来就是二叉搜索树插入算法中的循环 ( 寻找插入节点位置 ), 但是这里有两种策略 , 首先会按照 hash 值来处理查找 , 当 hash 值相同时则比较实际值 .

5. 找到了把新的值插入 , 如果有重复的 key( 指真实 key 而不是 hash 后的 ) 则覆盖值

void tcmapput2(TCMAP *map, const char *kstr, const char *vstr);

是调用 tcmapput 实现的 , 不过这里是对字符串的处理做了封装 .

bool tcmapputkeep(TCMAP *map, const void *kbuf, int ksiz, const void *vbuf, int vsiz);

与 tcmapput 算法相同 , 不过在这里碰到 key 完全相同的时候是不会覆盖的 , 而是返回 false, 对应的 , 当插入成功时 , 返回 true

bool tcmapputkeep2(TCMAP *map, const char *kstr, const char *vstr);

同 tcmapputkeep, 不过是对字符串的处理

void tcmapputcat(TCMAP *map, const void *kbuf, int ksiz, const void *vbuf, int vsiz);

同上面的 tcmapput 方法算法 , 不过在 key 完全相同时 , 是通过内存拷贝将值进行了连接

void tcmapputcat2(TCMAP *map, const char *kstr, const char *vstr);

同 tcmapputcat, 是对字符串的处理

bool tcmapout(TCMAP *map, const void *kbuf, int ksiz);

使用的是与 tcmapput 的二叉搜索树插入算法对应的移除算法 ( 二叉搜索树的移除主要问题在于查找后即节点 , 当然在这里可以会有更多细节处理 , 没有细看 ), 移除指定元素 , 如果没有找到 , 返回 false, 找到并移除了返回 true.

bool tcmapout2(TCMAP *map, const char *kstr);

tcmapout 的字符串版本

const void *tcmapget(const TCMAP *map, const void *kbuf, int ksiz, int *sp);

从数据库检索指定 key 对应的记录 , 如果查找成功 , 返回改记录的指针 , 否则 , 返回 NULL

const char *tcmapget2(const TCMAP *map, const char *kstr);

从数据库检索指定字符串 key 存储的字符串记录 .

bool tcmapmove(TCMAP *map, const void *kbuf, int ksiz, bool head);

对于那些 hash 值相同的 key-value 数据 , 实际上是在树的同一个节点上存储为一个链表的 , 该方法是将指定 key 的值移动到链表的两端 , 如果 head 是 true, 移动到第一个元素 , 如果是 false, 移动到末尾 . 如果没有查找到 key 对应的记录 , 返回 false, 否则 , 返回 true

bool tcmapmove2(TCMAP *map, const char *kstr, bool head);

tcmapmove 的字符串版本 .

void tcmapiterinit(TCMAP *map);

MAP 迭代的初始化 , 实际上就是把 map 的 cur 指针移动到桶数组第一个元素

cosnt void *tcmapiternext(TCMAP *map, int *sp);

迭代器的 next 方法 , 获取当前迭代点的元素 , 并将迭代位置向前推一个 , 如果没有元素可迭代了 , 就返回 NULL. 返回时同时向 sp 中记录了返回值的大小

const char *tcmapiternext2(TCMAP *map);

tcmapiternext 的字符串版本

uint64_t tcmaprnum(const TCMAP *map);

返回当前 map 对象中存储的记录条数

uint64_t tcmapmsiz(const TCMAP *map);

返回当前 map 对象占用内存大小 ( 不仅仅是存储的记录的大小 , 也包括了 map 对象保留的一些数据比如 rnum, msiz 等 )

TCLIST *tcmapkeys(const TCMAP *map);

以链表的方式遍历 map 返回内部保存的所有的 key 的列表对象

TCLIST *tcmapvals(const TCMAP *map);

以链表的方式遍历 map 返回内部保存的所有值的列表对象 .

int tcmapaddint(TCMAP *map, const void *kbuf, int ksiz, int num);

对指定 key 的值以 int 数据增加 num 值 , 如果该 key 对应的记录大小和 int 不相等 , 会返回 INT_MIN, 否则返回相加后的值

double tcmapadddouble(TCMAP *map, const void *kbuf, int ksiz, double num);

同 tcmapaddint, 不过这里增加的是 double 值

void tcmapclear(TCMAP *map);

清空 map 中的所有记录

void tcmapcutfront(TCMAP *map, int num);

移除 map 中的前 num 个元素 , 内部是调用了 map 的迭代接口和 out 接口处理的 .

void *tcmapdump(const TCMAP *map, int *sp);

将 map 进行序列化并返回 , sp 将记录序列化结果的长度

TCMAP *tcmapload(const void *ptr, int size);

从 ptr 的前 size 长度的内容加载一个 map 对象并返回 . 由于这里 load 到的 MAP 是通过 tcmapnew 创建的 , 因此可以通过 tcmapdel 来释放 .

分享到：

整合SVN与APACHE | TC官方文档翻译04----列表对象API(Tokyo Ca ...

2010-06-26 01:22
浏览 843
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论