13

Lua和Python：实现一个高效的List对象(3)

 3 years ago
source link: https://zhuanlan.zhihu.com/p/180538010
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Lua和Python：实现一个高效的List对象(3)

这一篇介绍一些列表函数的实现。

取值用法和Table一样，用ls[idx]获得列表的值；并且除了可以用正索引，还可以像Python一样用负索引，如-1表示最后一个元素，-2表示倒数第2个元素等等，C层代码如下：

// 取list指针
#define checklist(L) (list_t*)luaL_checkudata(L, 1, LIST_MT)
// ls[idx]
static int list_index(lua_State *L) {
    list_t *ls = checklist(L);
    int idx = (int)luaL_checkinteger(L, 2);
    if (idx > 0) idx--;                 // 正索引
    else if (idx < 0) idx += ls->size;  // 负索引
    if (idx < 0 || idx >= ls->size) {   // 超出范围的一律返回nil
        lua_pushnil(L);
        return 1;
    }
    int ref = ls->ary[idx].ref;         // 取引用值
    lua_getuservalue(L, 1);             // 将list的关联Table放到栈上
    lua_rawgeti(L, -1, ref);            // 通过引用取Table的值，并返回
    return 1;
}

对列表设值必须限定在长度之内，超出会抛出错误，唯一的例外是在列表最后设值，那样将认为是往后面追加，比如这样写：ls[#ls+1] = "ok"。

不能将nil设置给列表，因为Lua认为设置nil是删除元素，要达到类似的需求，可给列表设置false。

设值和取值一样支持负索引。

// ls[idx] = v
static int list_newindex(lua_State *L) {
    list_t *ls = checklist(L);
    int idx = (int)luaL_checkinteger(L, 2);
    if (idx > 0) idx--;                     // 正索引
    else if (idx < 0) idx += ls->size;      // 负索引
    luaL_argcheck(L, 0 <= idx && idx <= ls->size, 2, "index out of range");     // 范围检查
    if (lua_isnoneornil(L, 3))              // 不允许设置为nil
        luaL_argerror(L, 3, "value can not be nil");

    lua_getuservalue(L, 1);                 // 将list的关联Table放到栈上
    lua_pushvalue(L, 3);                    // 将设置的值压栈
    if (idx == ls->size) {                  // 往后追加
        check_and_grow_size(ls, 1);
        ls->ary[ls->size++].ref = ref_value(L, ls, -2);
    } else {                                // 正常设值
        lua_rawseti(L, -2, ls->ary[idx].ref);
    }
    return 0;
}

check_and_grow_size检查数组的内存是否够用，不够会按2倍来扩展内存：

static void check_and_grow_size(list_t *ls, int n) {
    int newcap = ls->cap;
    while (ls->size + n > newcap)
        newcap <<= 1;
    if (newcap != ls->cap) {
        ls->ary = (refdata_t*)realloc(ls->ary, newcap*sizeof(refdata_t));
        ls->cap = newcap;
    }
}

取值/设值由于用了元表的方法，多了一个间接层，必然比直接访问Table要慢一点。

取列表长度

按Lua的习惯，取长度用#ls，只需将list的size返回即可，效率比Table取长度要快得多：

// #ls
static int list_len(lua_State *L) {
    list_t *ls = checklist(L);
    lua_pushinteger(L, ls->size);
    return 1;
}

清除列表内容

直接将list的size置0即可，对于关联的Table，干脆抛弃它，直接新建一个Table关联：

// list.clear(ls[, shink])
static int list_clear(lua_State *L) {
    list_t *ls = checklist(L);
    int shink = lua_toboolean(L, 2);        // 如果指定shink，会收缩内存
    ls->size = 0;                           // 直接置0
    ls->ref = 0;
    if (shink) {
        ls->cap = 4;
        ls->ary = (refdata_t*)realloc(ls->ary, ls->cap * sizeof(refdata_t));
    }
    lua_createtable(L, ls->cap, 0);         // 重新创建Table，替换掉老的Table，老Table会被Lua自动GC回收掉。
    lua_setuservalue(L, 1);
    return 0;
}

交换两个位置的元素

这同样是一个很高效的操作，不需要涉及到Table的操作，直接将两个引用交换：

// list.exchange(ls, idx1, idx2)
static int list_exchange(lua_State *L) {
    list_t *ls = checklist(L);
    int idx1 = (int)luaL_checkinteger(L, 2) - 1;
    int idx2 = (int)luaL_checkinteger(L, 3) - 1;
    if (idx1 == idx2) return 0; 

    luaL_argcheck(L, 0 <= idx1 && idx1 < ls->size, 2, "index out of range");
    luaL_argcheck(L, 0 <= idx2 && idx2 < ls->size, 3, "index out of range");

    refdata_t ref = ls->ary[idx1];      // 交换引用即可
    ls->ary[idx1] = ls->ary[idx2];
    ls->ary[idx2] = ref;
    return 0;
}

接口和table.insert一样，如果不指定pos则往后插入，如果指定则插入到pos位置：

// list.insert(ls, [pos,] value)
static int list_insert(lua_State *L) {
    list_t *ls = checklist(L);
    int pos, n, vidx;
    if (lua_gettop(L) == 2) {       // 只有两个参数，则认为没有指定pos，pos设置为size
        pos = ls->size;
        vidx = 2;
    } else {                        // 有指定pos
        pos = (int)luaL_checkinteger(L, 2) - 1;
        vidx = 3;
    }
    if (lua_isnoneornil(L, vidx))   // 不允许设置nil
        luaL_argerror(L, vidx, "value can not be nil");
    // 检查pos的合法性
    luaL_argcheck(L, 0 <= pos && pos <= ls->size, 2, "index out of range");
    // 检查和增长内存
    check_and_grow_size(ls, 1);
    // 如果不是往后插入，则要移动内存
    if (pos != ls->size)
        memmove(ls->ary + pos + 1, ls->ary + pos, (ls->size - pos) * sizeof(refdata_t));

    lua_getuservalue(L, 1);                     // 取关联Table
    lua_pushvalue(L, vidx);                     // 将要设置的值入栈
    ls->ary[pos].ref = ref_value(L, ls, -2);    // 将值设为Table，同时返回一个引用，保存到数组。
    ls->size++;
    return 0;
}

我们后面的操作都是对引用的操作，Table只是设值和去除值。

接口和table.remove一样，如果不指定pos则从最后删除，如果指定则删除pos的值，最后返回删除的值

// list.remove(ls[, pos]) -> v
static int list_remove(lua_State *L) {
    list_t *ls = checklist(L);
    int pos = luaL_optinteger(L, 2, ls->size) - 1;
    luaL_argcheck(L, 0 <= pos && pos < ls->size, 2, "index out of range");
    int ref = ls->ary[pos].ref;
    // 如果不是删除最后一个，则要移动内存
    if (pos != ls->size - 1)
        memmove(ls->ary + pos, ls->ary + pos + 1, (ls->size - pos - 1) * sizeof(refdata_t));
    ls->size--;

    lua_getuservalue(L, 1);     // 取关联Table
    lua_rawgeti(L, -1, ref);    // 将要删除的值取出，返回
    unref_value(L, -2, ref);    // 删除值，解除引用
    return 1;
}

除了上面的函数，还有其他的接口，这里就不一一介绍了，我最后会把完整代码共享出来。

下一篇单独把排序拿出来说，并给出一个高效的实现。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK