特殊的键值结构

发表于
本文字数： 6.4k

平时开发中，大部分使用NSDictionary和NSMutableDictionary。下面介绍个特殊的。

  • NSMapTable
  • NXMapTable（objc源码）

NSMapTable

NSMapTable是更广泛意义的NSMutableDictionary，区别于NSMutableDictionary，NSMapTable有如下特性：

  • NSMapTable 是可变的；
  • NSMapTable 可以持有 weak 类型的key和value变量；
  • NSMapTable 可以在添加成员变量的时候复制成员；
  • NSMapTable 可以随意的存储指针并且利用指针的唯一性来进行 hash 同一性检查（检查成员变量是否有重复）和对比操作（equal）；

使用方法

1
2
3
4
NSObject *object = [[NSObject alloc] init];
NSMapTable *map = [[NSMapTable alloc] initWithKeyOptions:NSPointerFunctionsWeakMemory valueOptions:NSPointerFunctionsWeakMemory capacity:10];
[map setObject:object forKey:@"key"];
[map removeObjectForKey:@"key"];

NSMapTableOptions介绍（源码中是使用静态常量做关联）

1
2
3
4
5
6
7
8
9
10
11
12
enum {
    // 默认行为，强引用集合中的对象，等同于NSMutableSet
    NSMapTableStrongMemory             = 0,
    // 在将对象添加到集合之前，会拷贝对象
    NSMapTableCopyIn                   = NSPointerFunctionsCopyIn,
    // 使用移位指针(shifted pointer)来做hash检测和确定两个对象是否相等；
    // 同时使用description方法来做描述字符串
    NSMapTableObjectPointerPersonality = NSPointerFunctionsObjectPointerPersonality,
    // 弱引用集合中的对象，且在对象被释放后，会被正确的移除。
    NSMapTableWeakMemory               = NSPointerFunctionsWeakMemory
};
typedef NSUInteger NSMapTableOptions;

NXMapTable

在objc源码中，找到了关于NSMapTable的类似实现。可以参考下

Hash冲突解决方案：开放地址法

NXMapTable存储结构（精简过）

1
2
3
4
5
6
7
8
9
10
typedef struct _NXMapTable {
    // 附属实体
    const struct _NXMapTablePrototype	* prototype;
    // 真实的长度（存储了多少有效数据）
    unsigned	count;
    // buckets实际所占用的空间大小-1；如果count * 4 > numBuckets * 3 就扩容buckets
    unsigned	nbBucketsMinusOne;
    // 数据[MapPair?]
    void	* buckets;
} NXMapTable;

NXMapTablePrototype存储结构（精简过）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct _NXMapTablePrototype {
    // hash的函数指针
    unsigned	(* hash)(NXMapTable *,
                                  const void * key);
    // 相等的函数指针
    int		(* isEqual)(NXMapTable *,
                                     const void * key1,
                                     const void * key2);
    // 释放函数指针
    void	(* free)(NXMapTable *,
                                  void * key,
                                  void * value);
    // 预留字段
    int		style;
} NXMapTablePrototype;

MapPair存储结构

1
2
3
4
typedef struct _MapPair {
    const void	*key;
    const void	*value;
} MapPair;

NXMapTable的构造器NXCreateMapTable和NXCreateMapTableFromZone

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
NXMapTable *NXCreateMapTable(NXMapTablePrototype prototype, unsigned capacity) {
    return NXCreateMapTableFromZone(prototype, capacity, malloc_default_zone());
}

NXMapTable *NXCreateMapTableFromZone(NXMapTablePrototype prototype, unsigned capacity, void *z) {
    NXMapTable			*table = (NXMapTable *)malloc_zone_malloc((malloc_zone_t *)z, sizeof(NXMapTable));
    NXMapTablePrototype		*proto;
    if (! prototypes) prototypes = NXCreateHashTable(protoPrototype, 0, NULL);
    if (! prototype.hash || ! prototype.isEqual || ! prototype.free || prototype.style) {
	_objc_inform("*** NXCreateMapTable: invalid creation parameters\n");
	return NULL;
    }
    proto = (NXMapTablePrototype *)NXHashGet(prototypes, &prototype); 
    if (! proto) {
	proto = (NXMapTablePrototype *)malloc(sizeof(NXMapTablePrototype));
	*proto = prototype;
    	(void)NXHashInsert(prototypes, proto);
    }
    table->prototype = proto; table->count = 0;
    table->nbBucketsMinusOne = exp2u(log2u(capacity)+1) - 1;
    table->buckets = allocBuckets(z, table->nbBucketsMinusOne + 1);
    return table;
}

取数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void *NXMapGet(NXMapTable *table, const void *key) {
    void	*value;
    return (_NXMapMember(table, key, &value) != NX_MAPNOTAKEY) ? value : NULL;
}
static inline void *_NXMapMember(NXMapTable *table, const void *key, void **value) {
    MapPair	*pairs = (MapPair *)table->buckets;
    unsigned	index = bucketOf(table, key);
    MapPair	*pair = pairs + index;
    if (pair->key == NX_MAPNOTAKEY) return NX_MAPNOTAKEY;
    validateKey(table, pair, index, index);

    if (isEqual(table, pair->key, key)) {
	*value = (void *)pair->value;
	return (void *)pair->key;
    } else {
	unsigned	index2 = index;
	while ((index2 = nextIndex(table, index2)) != index) {
	    pair = pairs + index2;
	    if (pair->key == NX_MAPNOTAKEY) return NX_MAPNOTAKEY;
	    validateKey(table, pair, index, index2);
	    if (isEqual(table, pair->key, key)) {
	    	*value = (void *)pair->value;
		return (void *)pair->key;
	    }
	}
	return NX_MAPNOTAKEY;
    }
}

插入数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
void *NXMapInsert(NXMapTable *table, const void *key, const void *value) {
    MapPair	*pairs = (MapPair *)table->buckets;
    unsigned	index = bucketOf(table, key);
    MapPair	*pair = pairs + index;
    if (key == NX_MAPNOTAKEY) {
	_objc_inform("*** NXMapInsert: invalid key: -1\n");
	return NULL;
    }

    unsigned numBuckets = table->nbBucketsMinusOne + 1;

    if (pair->key == NX_MAPNOTAKEY) {
	pair->key = key; pair->value = value;
	table->count++;
	if (table->count * 4 > numBuckets * 3) _NXMapRehash(table);
	return NULL;
    }
    
    if (isEqual(table, pair->key, key)) {
	const void	*old = pair->value;
	if (old != value) pair->value = value;/* avoid writing unless needed! */
	return (void *)old;
    } else if (table->count == numBuckets) {
	/* no room: rehash and retry */
	_NXMapRehash(table);
	return NXMapInsert(table, key, value);
    } else {
	unsigned	index2 = index;
	while ((index2 = nextIndex(table, index2)) != index) {
	    pair = pairs + index2;
	    if (pair->key == NX_MAPNOTAKEY) {
		pair->key = key; pair->value = value;
		table->count++;
		if (table->count * 4 > numBuckets * 3) _NXMapRehash(table);
		return NULL;
	    }
	    if (isEqual(table, pair->key, key)) {
		const void	*old = pair->value;
		if (old != value) pair->value = value;/* avoid writing unless needed! */
		return (void *)old;
	    }
	}
	/* no room: can't happen! */
	_objc_inform("**** NXMapInsert: bug\n");
	return NULL;
    }
}

删除数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
void *NXMapRemove(NXMapTable *table, const void *key) {
    MapPair	*pairs = (MapPair *)table->buckets;
    unsigned	index = bucketOf(table, key);
    MapPair	*pair = pairs + index;
    unsigned	chain = 1; /* number of non-nil pairs in a row */
    int		found = 0;
    const void	*old = NULL;
    if (pair->key == NX_MAPNOTAKEY) return NULL;
    /* compute chain */
    {
	unsigned	index2 = index;
	if (isEqual(table, pair->key, key)) {found ++; old = pair->value; }
	while ((index2 = nextIndex(table, index2)) != index) {
	    pair = pairs + index2;
	    if (pair->key == NX_MAPNOTAKEY) break;
	    if (isEqual(table, pair->key, key)) {found ++; old = pair->value; }
	    chain++;
	}
    }
    if (! found) return NULL;
    if (found != 1) _objc_inform("**** NXMapRemove: incorrect table\n");
    /* remove then reinsert */
    {
	MapPair	buffer[16];
	MapPair	*aux = (chain > 16) ? (MapPair *)malloc(sizeof(MapPair)*(chain-1)) : buffer;
	unsigned	auxnb = 0;
	int	nb = chain;
	unsigned	index2 = index;
	while (nb--) {
	    pair = pairs + index2;
	    if (! isEqual(table, pair->key, key)) aux[auxnb++] = *pair;
	    pair->key = NX_MAPNOTAKEY; pair->value = NULL;
	    index2 = nextIndex(table, index2);
	}
	table->count -= chain;
	if (auxnb != chain-1) _objc_inform("**** NXMapRemove: bug\n");
	while (auxnb--) NXMapInsert(table, aux[auxnb].key, aux[auxnb].value);
	if (chain > 16) free(aux);
    }
    return (void *)old;
}