zipmap
??Zipmap是為了實(shí)現(xiàn)保存Pair(String,String)數(shù)據(jù)的結(jié)構(gòu)，是存儲(chǔ)效率非常高的一種結(jié)構(gòu)
zipmap結(jié)構(gòu)
對(duì)于map :
"foo" => "bar", "hello" => "world":
<zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"<end>
zmlen 1字節(jié) 鍵值對(duì)的個(gè)數(shù)
len 1字節(jié)表示key or value長(zhǎng)度(0-253) 如果超過(guò)253 則使用5字節(jié) 第一個(gè)字節(jié)設(shè)為254 后面四個(gè)字節(jié)表示長(zhǎng)度.
free 1字節(jié) value長(zhǎng)度中未使用的長(zhǎng)度，主要考慮到value改變的情況.
end 0xFF 結(jié)束標(biāo)志
此map的在內(nèi)存中的結(jié)構(gòu)為
0x02,0x03,foo,0x03,0x00,bar,0x05,hello,0x05,0x00,world,0xFF
2個(gè)鍵值對(duì):len=3:foo:len=3:len=3:free=0:bar:len=5:hello:len=5:free=0:world:結(jié)束標(biāo)志
主要api
unsigned char *zipmapNew(void);//創(chuàng)建一個(gè)空的map 只需要兩個(gè)字節(jié)
unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update);//插入或者跟新一個(gè)鍵值對(duì)
unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted);//刪除一個(gè)鍵值對(duì)
unsigned char *zipmapRewind(unsigned char *zm);// 返回第一個(gè)元素的地址
unsigned char *zipmapNext(unsigned char *p, unsigned char **key, unsigned int *klen, unsigned char **value, unsigned int *vlen);//得到p所指向的鍵值對(duì)的數(shù)據(jù)，并且返回下一個(gè)鍵值對(duì)的起始位置
int zipmapGet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char **value, unsigned int *vlen);//尋找key相等的鍵值對(duì)起始位置
int zipmapExists(unsigned char *zm, unsigned char *key, unsigned int klen);//key是否存在 調(diào)用了zipmapGet函數(shù)
unsigned int zipmapLen(unsigned char *zm);//如果長(zhǎng)度小于254直接返回，否則需要遍歷map得到其大小
size_t zipmapBlobLen(unsigned char *zm);//得到這個(gè)zipmap所占內(nèi)存
zipmap插入or更新鍵值對(duì)
//不存在則插入否則更新
unsigned char *zipmapSet(unsigned char *zm, unsigned char *key, unsigned int klen, unsigned char *val, unsigned int vlen, int *update) {
unsigned int zmlen, offset;
unsigned int freelen, reqlen = zipmapRequiredLength(klen,vlen);
unsigned int empty, vempty;
unsigned char *p;
freelen = reqlen;
if (update) *update = 0;
p = zipmapLookupRaw(zm,key,klen,&zmlen);//得到總長(zhǎng)度 并且找到有沒(méi)有這個(gè)key
if (p == NULL) {//沒(méi)有找到 插入新的pair
zm = zipmapResize(zm, zmlen+reqlen);//重新申請(qǐng)內(nèi)存
p = zm+zmlen-1;//要被填充鍵值對(duì)數(shù)據(jù)的起始位置
zmlen = zmlen+reqlen;//更新zipmap所占字節(jié)數(shù)
if (zm[0] < ZIPMAP_BIGLEN) zm[0]++;//更新pair個(gè)數(shù)
} else {
//找到了key 更新 value
if (update) *update = 1;
freelen = zipmapRawEntryLength(p);//返回p所代表的鍵值對(duì)所占有的空間
if (freelen < reqlen) {//如果更新的這個(gè)鍵值對(duì)所需空間大于 此鍵值對(duì)目前所占有的空間 更新
offset = p-zm;//記錄下p的偏移量
zm = zipmapResize(zm, zmlen-freelen+reqlen);//realloc
p = zm+offset;//重新得到p的地址
memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));//后移數(shù)據(jù)，騰出空間放置更新的value
zmlen = zmlen-freelen+reqlen;//更新zipmap所占內(nèi)存大小
freelen = reqlen;//freelen == reqlen
}
}
empty = freelen-reqlen;//如果此鍵值對(duì)目前所占有的空間 大于 更新的這個(gè)鍵值對(duì)所需空間
if (empty >= ZIPMAP_VALUE_MAX_FREE) {//empty>4的話(huà)就要重新分配內(nèi)存
/* First, move the tail <empty> bytes to the front, then resize
* the zipmap to be <empty> bytes smaller. */
offset = p-zm;
memmove(p+reqlen, p+freelen, zmlen-(offset+freelen+1));//數(shù)據(jù)前移
zmlen -= empty;//減去需要需要減少的字節(jié)個(gè)數(shù)
zm = zipmapResize(zm, zmlen);//重新分配內(nèi)存
p = zm+offset;
vempty = 0;//free 的值
} else {//設(shè)置free的值
vempty = empty;//free 的值
}
//把數(shù)據(jù)填充一下即可
p += zipmapEncodeLength(p,klen);
memcpy(p,key,klen);
p += klen;
p += zipmapEncodeLength(p,vlen);
*p++ = vempty;
memcpy(p,val,vlen);
return zm;
}
zipmap刪除鍵
unsigned char *zipmapDel(unsigned char *zm, unsigned char *key, unsigned int klen, int *deleted) {
unsigned int zmlen, freelen;
unsigned char *p = zipmapLookupRaw(zm,key,klen,&zmlen);//有這個(gè)key嗎
if (p) {//存在
freelen = zipmapRawEntryLength(p);//這個(gè)鍵值對(duì)所占內(nèi)存字節(jié)數(shù)
memmove(p, p+freelen, zmlen-((p-zm)+freelen+1));//前移數(shù)據(jù)
zm = zipmapResize(zm, zmlen-freelen);//realloc內(nèi)存
if (zm[0] < ZIPMAP_BIGLEN) zm[0]--;//如果可以 更新 鍵值對(duì)個(gè)數(shù)
if (deleted) *deleted = 1;//刪除了
} else {
if (deleted) *deleted = 0;//沒(méi)有這個(gè)鍵
}
return zm;
}
