快速略读了一下源码，记了一些东西。
先看看mapping
mapping其实就是C++中的multimap，但是支持更多。
array values(mapping)。这个方法可以返回所有mapping中的value，那么values()究竟作了什么呢？源码中是这样定义的：
PMOD_EXPORT struct array *mapping_values(struct mapping *m)
{
INT32 e;
struct keypair *k;
struct array *a;
struct svalue *s; #ifdef PIKE_DEBUG
if(m->data->refs <=)
Pike_fatal("Zero refs in mapping->data\n");
#endif check_mapping_for_destruct(m); a=allocate_array(m->data->size);
s=ITEM(a); /* no locking required */
NEW_MAPPING_LOOP(m->data) assign_svalue(s++, & k->val); a->type_field = m->data->val_types; #ifdef PIKE_DEBUG
if(d_flag > ) check_mapping_type_fields(m);
#endif return a;
}
可以看到，在第15行直接申请了足够存储所有value的内存大小，第19行是一个宏，其循环了所有的可能的value，然后assign_svalue就会将每个k->value给拷贝到返回值array中，并且在27行返回a。
mapping也可以将字符串作为key的，但是它是如何依靠一个ke=string来迅速地找到对应的value的呢？其实mapping使用的siphash（*， 原著论文）来哈希字符串的，也就是先将字符串哈希成一个值，再跟其他的key的哈希值来匹配，这样就容易找到了。如果有兴趣可以看pike中的实现：
static size_t low_hashmem_siphash24( const void *s, size_t len, size_t nbytes, size_t key )
{
const unsigned char * in = (const unsigned char*)s;
unsigned long long inlen = MINIMUM(len, nbytes); /* "some pseudo randomly generated bytes" 伪随机产生的字节 */
unsigned INT64 v0 = 0x736f6d6570736575ULL;
unsigned INT64 v1 = 0x646f72616e646f6dULL;
unsigned INT64 v2 = 0x6c7967656e657261ULL;
unsigned INT64 v3 = 0x7465646279746573ULL;
unsigned INT64 b;
unsigned INT64 k0 = (unsigned INT64)key;
unsigned INT64 k1 = (unsigned INT64)key;
unsigned INT64 m;
const unsigned char *end = in + inlen - ( inlen % sizeof( unsigned INT64 ) );
const int left = inlen & ;
b = ( ( unsigned INT64 )inlen ) << ;
v3 ^= k1;
v2 ^= k0;
v1 ^= k1;
v0 ^= k0; for ( ; in != end; in += )
{
m = U8TO64_LE( in );
v3 ^= m;
SIPROUND;
SIPROUND;
v0 ^= m;
} switch( left )
{
case : b |= ( ( unsigned INT64 )in[ ] ) << ; case : b |= ( ( unsigned INT64 )in[ ] ) << ; case : b |= ( ( unsigned INT64 )in[ ] ) << ; case : b |= ( ( unsigned INT64 )in[ ] ) << ; case : b |= ( ( unsigned INT64 )in[ ] ) << ; case : b |= ( ( unsigned INT64 )in[ ] ) << ; case : b |= ( ( unsigned INT64 )in[ ] ); break; case : break;
} v3 ^= b;
SIPROUND;
SIPROUND;
v0 ^= b;
v2 ^= 0xff;
SIPROUND;
SIPROUND;
SIPROUND;
SIPROUND;
b = v0 ^ v1 ^ v2 ^ v3;
return (size_t)b;
}
low_hashmen_siphash24
将字符串哈希成一个值后，pike是以一个表来管理字符串的（不知是否为所有），定义在stralloc.c中的原型如下：
static struct pike_string **base_table=;
shared string table。当字符串被哈希成一个值后，就在这个table中寻找（这是简化了的说法，其实在找之前还与htable_mask做了位与）。但是哈希值是不能保证唯一的，所以需要一个二级指针，每个桶中存放着所有的哈希值相同的字符串呢。那如果重叠率太高了呢？pike还定义了一个全局变量：
static unsigned int need_new_hashkey_depth=;
这个变量在每次找不到的时候就可以会有变化，这跟“字符串哈希”所取的前缀长短有关（如果每次都将整个字符串用于哈希的话，也太长了吧？其实不知道是否是整个字符串哈希），可能是会根据这个变量值作哈希的调整。函数原型如下：
static struct pike_string *internal_findstring(const char *s,
ptrdiff_t len,
enum size_shift size_shift,
size_t hval) /* hval是用siphash计算出来的结果 */
每对key-value的信息是以一个struct keypair来记录的，其中仅记录了一些信息，以及一个指针（应该是指向真正数据的），初始mapping时需要申请一些内存来存放keypair。
#define MD_KEYPAIRS(MD, HSIZE)
( (struct keypair *)
DO_ALIGN( PTR_TO_INT(MD) + OFFSETOF(mapping_data, hash) + HSIZE * sizeof(struct keypair *),
ALIGNOF(struct keypair)) )
DO_ALIGN的定义：
#define DO_ALIGN(X,Y) (((size_t)(X)+((Y)-1)) & ~((Y)-1))
ALIGNIOF是内置函数，用于计算对齐内存所占的大小。
mapping中提用了几个操作，很是方便，比如 &与操作，|或操作，xor异或操作等等。
先拿xor开刀，就是将两个mapping中的具有相同key的key-value都给删除掉，留下唯一的key的那种。实现起来也没有多大的优化技巧，就是先将小的mapping先拷贝出来，然后再将大的mapping中的key-value逐个往里面插，如果key已经存在了，就一块删掉，如果不存在，就插进去。仍然需要考虑特殊情况的，比如相同mapping作异或操作等。源码：
static struct mapping *xor_mappings(struct mapping *a, struct mapping *b)
{
struct mapping *res;
struct keypair *k;
struct mapping_data *a_md = a->data;
struct mapping_data *b_md = b->data;
INT32 e;
ONERROR err; /* First some special cases. */
if (!a_md->size) return destructive_copy_mapping(b); /* 只是有可能会删除真数据 */
if (!b_md->size) return destructive_copy_mapping(a);
if (a_md == b_md) return allocate_mapping(); /* 数据一样，返回空mapping */ /* Copy the largest mapping. 保持a<=b */
if (a_md->size > b_md->size) {
struct mapping *tmp = a;
a = b;
b = tmp;
a_md = b_md;
b_md = b->data;
}
res = destructive_copy_mapping(b); /* 先拷贝个小的进去 */
SET_ONERROR(err, do_free_mapping, res); /* Add elements in a that aren't in b, and remove those that are. */
NEW_MAPPING_LOOP(a_md) {
size_t h = k->hval & (b_md->hashsize - );
struct keypair *k2;
for (k2 = b_md->hash[h]; k2; k2 = k2->next)
{
if ((k2->hval == k->hval) && is_eq(&k2->ind, &k->ind)) /* 先比对哈希值，再比对真实数据 */
{
break;
}
}
if (!k2) /* k2=0表示没有找到相同的 */
{
mapping_insert(res, &k->ind, &k->val);
}
else
{
map_delete(res, &k2->ind);
}
b_md = b->data;
}
UNSET_ONERROR(err);
return res;
}
看看逻辑或运算，c=a|b 。这也是很普通的操作而已，实现起来也没有什么优化。思路是，1，若b比较大，那么先拷贝b到c，而对于a，逐个key判断是否存在于c，若在则不操作，否则插入。2，若a比较大，直接将a拷贝到c，再将b逐个插入到c，若key已存在，直接覆盖。
static struct mapping *or_mappings(struct mapping *a, struct mapping *b)
{
struct mapping *res;
struct keypair *k;
struct mapping_data *a_md = a->data;
struct mapping_data *b_md = b->data;
INT32 e;
ONERROR err; /* First some special cases. */
if (!a_md->size) return destructive_copy_mapping(b);
if (!b_md->size) return destructive_copy_mapping(a);
if (a_md == b_md) return destructive_copy_mapping(a); if (a_md->size <= b_md->size) { /* a的数据比较少 */
/* Copy the second mapping. */
res = destructive_copy_mapping(b);
SET_ONERROR(err, do_free_mapping, res); if (!b_md->hashsize) {
Pike_fatal("Invalid hashsize.\n");
} /* Add elements in a that aren't in b. */
NEW_MAPPING_LOOP(a_md) {
size_t h = k->hval & (b_md->hashsize - );
struct keypair *k2;
for (k2 = b_md->hash[h]; k2; k2 = k2->next) { /* 如果b中已经存在的，a就不能再插进去了 */
if ((k2->hval == k->hval) && is_eq(&k2->ind, &k->ind)) {
break;
}
}
if (!k2) {
mapping_insert(res, &k->ind, &k->val);
b_md = b->data;
}
}
UNSET_ONERROR(err);
} else {
/* Copy the first mapping. */
res = destructive_copy_mapping(a);
SET_ONERROR(err, do_free_mapping, res); /* Add all elements in b. */
NEW_MAPPING_LOOP(b_md) { /* 直接将b插进去，如果a中已经存在key，则value会自动覆盖 */
mapping_insert(res, &k->ind, &k->val);
}
UNSET_ONERROR(err);
}
return res;
}
and操作，即c=a+b，对于那些“key在a和b中皆存在，key-value属于b”的key-value于c中。源码的实现思路是，先将b拷贝到c，再将a中每个元素判断key是否存在于c中，若存在，则不操作，否则，删除。
static struct mapping *and_mappings(struct mapping *a, struct mapping *b)
{
struct mapping *res;
struct keypair *k;
struct mapping_data *a_md = a->data;
struct mapping_data *b_md = b->data;
INT32 e;
ONERROR err; /* First some special cases. */
if (!a_md->size || !b_md->size) return allocate_mapping();
if (a_md == b_md) return destructive_copy_mapping(a); /* Copy the second mapping. */
res = copy_mapping(b); /* 先拷贝了b */
SET_ONERROR(err, do_free_mapping, res); /* Remove elements in res that aren't in a. */
NEW_MAPPING_LOOP(b_md) { /* 如果已经存在key，则不操作；否则删除已存在的key-value */
size_t h = k->hval & (a_md->hashsize - );
struct keypair *k2;
for (k2 = a_md->hash[h]; k2; k2 = k2->next) {
if ((k2->hval == k->hval) && is_eq(&k2->ind, &k->ind)) {
break;
}
}
if (!k2) {
map_delete(res, &k->ind);
}
}
UNSET_ONERROR(err);
return res;
}
and_mappings
substract操作，即c=a-b，对于所有在b中出现的key，如果a中也存在，则删除，否则不操作。
static struct mapping *subtract_mappings(struct mapping *a, struct mapping *b)
{
struct mapping *res;
struct keypair *k;
struct mapping_data *a_md = a->data;
struct mapping_data *b_md = b->data;
INT32 e;
ONERROR err; /* First some special cases. */
if (!a_md->size || !b_md->size || !a_md->hashsize || !b_md->hashsize) {
return destructive_copy_mapping(a);
}
if (a_md == b_md) {
return allocate_mapping();
}
/* FIXME: The break-even point should probably be researched. */
if (a_md->size < b_md->size) {
/* Add the elements in a that aren't in b. */
res = allocate_mapping(a_md->size);
SET_ONERROR(err, do_free_mapping, res);
NEW_MAPPING_LOOP(a_md) {
size_t h = k->hval & (b_md->hashsize - );
struct keypair *k2;
for (k2 = b_md->hash[h]; k2; k2 = k2->next) {
if ((k2->hval == k->hval) && is_eq(&k2->ind, &k->ind)) {
break;
}
}
if (!k2) {
mapping_insert(res, &k->ind, &k->val);
}
}
} else {
/* Remove the elements in a that are in b. */
res = destructive_copy_mapping(a);
SET_ONERROR(err, do_free_mapping, res);
NEW_MAPPING_LOOP(b_md) {
map_delete(res, &k->ind);
}
}
UNSET_ONERROR(err);
return res;
}
subtract_mappings
replace(mapping,old,new)函数，将mapping中所有value=old的替换成value=new。由于pike中使用了索引的概念，替换之后可能会有value需要清除了，如果它的引用次数=1的话。
PMOD_EXPORT void mapping_replace(struct mapping *m, struct svalue *from, struct svalue *to)
{
INT32 e;
struct keypair *k;
struct mapping_data *md; #ifdef PIKE_DEBUG
if (m->data->refs <= )
Pike_fatal("Zero refs in mapping->data\n");
#endif md = m->data;
if (md->size) {
add_ref(md); /* 增加md的引用一次 */
NEW_MAPPING_LOOP(md) { /* 扫描所有键值对 */
if (is_eq(& k->val, from)) { /* 如果与from相同的话就申请内存并替换成to */
PREPARE_FOR_DATA_CHANGE(); /* 为k申请新内存 */
assign_svalue(& k->val, to);
md->val_types |= << TYPEOF(*to);
}
}
free_mapping_data(md); /* 释放掉引用次数=1的value，不一定是真的释放 */
} #ifdef PIKE_DEBUG
if (d_flag > ) check_mapping_type_fields(m);
#endif
}
mkmapping(array ind,array val)函数，创建一个mapping对象，并且以ind作为索引，val作为值来组成key-value初始化该对象。这里的实现是以ind的元素个数作为mapping的元素个数的，所以如果val的元素个数比ind要大的话，是会自动忽略后面的多余部分。还有一个点，就是初始化时，hashsize（也称之为桶的数量）应该是多少的问题，这里依靠MAP_SLOTS这个宏来计算的，这样的计算方式的优劣性未明～
#define MAP_SLOTS(X) ((X)?((X)+((X)>>4)+8):0)
PMOD_EXPORT struct mapping *mkmapping(struct array *ind, struct array *val)
{
struct mapping *m;
struct svalue *i, *v;
INT32 e; #ifdef PIKE_DEBUG
if (ind->size != val->size)
Pike_fatal("mkmapping on different sized arrays.\n");
#endif m = allocate_mapping(MAP_SLOTS(ind->size)); /* 申请一个mapping，这里关系到hashsize的大小 */
i = ITEM(ind);
v = ITEM(val);
for (e = ; e < ind->size; e++) /* 逐个插入*/
low_mapping_insert(m, i++, v++, ); return m;
}