Python 2.7的字典实现简化版(C语言)

这是一个能自动调整大小的哈希字典,外部接口实现了下列功能.

1.字典级别:

创建字典 dict_new

归零字典 dict_clear

2.键值级别:

查找 dict_search

强制查找 dict_force_search

更新 dict_update

添加 dict_add

删除 dict_del

所谓强制查找就是假如key不存在,那么它将先在字典中添加这个key,值设置为默认值,再返回这个值的指针.

由于键值都是以空指针定义的,所以在处理一些简单的值类型时(如int),显得繁琐了些(比如valcmp),但好处是更加灵活了,比如稍作修改(valdup和get_default_val)就可以处理值为字符串的情况.

C确实很快,但繁重的内存管理果然名不虚传.这个简单的字典要求:

1.键(me_key)和值(me_value)的指针所指向的堆内存区域能够直接用free释放,如果这些区域还包含另一些堆指针,那么可能会出问题.

2.只需传递缓冲数据(main中的keybuf和valbuf)给键值函数,函数内部会根据情况申请或释放内存,或不做任何处理.

为方便处理,words文本格式要求每行一个词语.

/* Pure C simple version of python 2.7.8 hash table */
/* Sample usage: see main() */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#define PyDict_MINSIZE 8
#define PERTURB_SHIFT 5
#define NEED_RESIZE(mp) ((mp)->ma_fill * 3 >= ((mp)->ma_mask + 1) * 2)

typedef void PyObject;

typedef struct {
    size_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictEntry;

typedef struct _dictobject PyDictObject;
struct _dictobject {
    size_t ma_fill;  /* # Active + # Dummy */
    size_t ma_used;  /* # Active */
    size_t ma_mask;
    PyDictEntry *ma_table;
    size_t(*ma_keyhash)(PyObject *key);
    int(*ma_keycmp)(PyObject *key1, PyObject *key2);
    PyObject *(*ma_keydup)(PyObject *key);
    PyObject *(*ma_valuedup)(PyObject *value);
    PyObject *(*ma_default)(void);
};

/* Object used as dummy key to fill deleted entries */
static PyDictEntry _dummy_struct;
#define dummy (&_dummy_struct)

static size_t
keyhash(PyObject *_key)
{
    char *key = (char *)_key;
    size_t hash = 5381;
    for (; *key; key++)
        hash = ((hash << 5) + hash) + *key; /* hash * 33 + c */
    return hash;
}

static int
keycmp(PyObject *_key1, PyObject *_key2)
{
    char *key1 = (char *)_key1;
    char *key2 = (char *)_key2;
    for (; *key1 == *key2; key1++, key2++)
        if (*key1 == '

Python 2.7的字典实现简化版(C语言)

相关推荐