Как перебрать таблицу, измененную с помощью luaL_ref и luaL_unref?

Функции luaL_ref и luaL_unref определены в lauxlib.c. Они работают, отслеживая свободный список ссылок, который они хранят в таблице, с которой они работают. Эти функции относительно короткие, поэтому я включу их здесь.

LUALIB_API int luaL_ref (lua_State *L, int t) {
  int ref;
  t = abs_index(L, t);
  if (lua_isnil(L, -1)) {
    lua_pop(L, 1);  /* remove from stack */
    return LUA_REFNIL;  /* 'nil' has a unique fixed reference */
  }
  lua_rawgeti(L, t, FREELIST_REF);  /* get first free element */
  ref = (int)lua_tointeger(L, -1);  /* ref = t[FREELIST_REF] */
  lua_pop(L, 1);  /* remove it from stack */
  if (ref != 0) {  /* any free element? */
    lua_rawgeti(L, t, ref);  /* remove it from list */
    lua_rawseti(L, t, FREELIST_REF);  /* (t[FREELIST_REF] = t[ref]) */
  }
  else {  /* no free elements */
    ref = (int)lua_objlen(L, t);
    ref++;  /* create new reference */
  }
  lua_rawseti(L, t, ref);
  return ref;
}

LUALIB_API void luaL_unref (lua_State *L, int t, int ref) {
  if (ref >= 0) {
    t = abs_index(L, t);
    lua_rawgeti(L, t, FREELIST_REF);
    lua_rawseti(L, t, ref);  /* t[ref] = t[FREELIST_REF] */
    lua_pushinteger(L, ref);
    lua_rawseti(L, t, FREELIST_REF);  /* t[FREELIST_REF] = ref */
  }
}

Эти функции действительно умны, потому что они не требуют дополнительной памяти (кроме таблицы, с которой они работают). Однако иногда нежелательно хранить список свободных ссылок в той же таблице, что и значения, на которые ссылаются, например, когда необходимо выполнить итерацию по значениям, на которые ссылаются.

Я написал luaX_ref и luaX_unref, чтобы решить эту проблему. Они работают почти так же, как luaL_ref и luaL_unref, за исключением того, что они хранят список бесплатных ссылок в отдельной таблице, l для списка. (Для моего проекта я поместил их в отдельный исходный файл и включил при необходимости. Я не рекомендую изменять lauxlib.c.)

static int abs_index(lua_State * L, int i){
  return i > 0 || i <= LUA_REGISTRYINDEX ? i : lua_gettop(L) + i + 1;
}

LUALIB_API int luaX_ref(lua_State *L, int t, int l){
  int ref;
  t = abs_index(L, t);
  l = abs_index(L, l);
  if(lua_isnil(L, -1)){
    lua_pop(L, 1); /* remove from stack */
    return LUA_REFNIL; /* 'nil' has a unique fixed reference */
  }
  lua_rawgeti(L, l, FREELIST_REF); /* get first free element */
  ref = (int) lua_tointeger(L, -1); /* ref = l[FREELIST_REF] */
  lua_pop(L, 1); /* remove it from stack */
  if(ref != 0){ /* any free element? */
    lua_rawgeti(L, l, ref); /* remove it from list */
    lua_rawseti(L, l, FREELIST_REF); /* (l[FREELIST_REF] = l[ref]) */
  }else{ /* no free elements */
    ref = (int)lua_objlen(L, l);
    ref++; /* create new reference */
  }
  lua_pushboolean(L, 1);
  lua_rawseti(L, l, ref); /* l[ref] = true */
  lua_rawseti(L, t, ref); /* t[ref] = value */
  return ref;
}

LUALIB_API void luaX_unref(lua_State *L, int t, int l, int ref){
  if(ref >= 0){
    t = abs_index(L, t);
    l = abs_index(L, l);
    lua_rawgeti(L, l, FREELIST_REF);
    lua_rawseti(L, l, ref);  /* l[ref] = l[FREELIST_REF] */
    lua_pushinteger(L, ref);
    lua_rawseti(L, l, FREELIST_REF);  /* l[FREELIST_REF] = ref */
    lua_pushnil(L);
    lua_rawseti(L, t, ref); /* t[ref] = nil */
  }
}

Теперь посмотрите на использование:

lua_newtable(L); /* 1 */
lua_newtable(L); /* 2 */

lua_pushboolean(L, 0);
int ref1 = luaX_ref(L, 1, 2);

lua_pushinteger(L, 7);
int ref2 = luaX_ref(L, 1, 2);

lua_pushstring(L, "test");
int ref3 = luaX_ref(L, 1, 2);

tableDump(L, 1);
tableDump(L, 2);

luaX_unref(L, 1, 2, ref1);
tableDump(L, 1);
tableDump(L, 2);

luaX_unref(L, 1, 2, ref3);
tableDump(L, 1);
tableDump(L, 2);

luaX_unref(L, 1, 2, ref2);
tableDump(L, 1);
tableDump(L, 2);

printf("done.\n");

Выход:

1:  false,  2:  7,  3:  `test',
1:  true,  2:  true,  3:  true,
2:  7,  3:  `test',
3:  true,  2:  true,  0:  1,
2:  7,
3:  1,  2:  true,  0:  3,

3:  1,  2:  3,  0:  2,
done.

Чтобы «обеспечить уникальность возвращаемого ключа», luaL_ref должен вести список используемых и впоследствии luaL_unref удаленных ключей. Похоже, что этот список начинается с t[0] и продолжается до тех пор, пока цепочка индексов не приведет к nil. Этот список хранится в той же таблице, что и активные ссылки.

Если вы хотите продолжать «злоупотреблять API», как заметил Никол, и зависеть от поведения, определенного реализацией, вы можете следовать этому связанному списку, чтобы увидеть, является ли ключ удаленной ссылкой при повторении таблицы. Или, чтобы избежать зависимости от поведения, определяемого реализацией, и повысить производительность, вы можете сохранить отдельную таблицу удаленных ссылок и пропускать их при повторении таблицы, хотя вам нужно будет игнорировать заголовок списка в t[0].

Если вам действительно нужно повторять ссылки, возможно, вам лучше использовать другой механизм. Вы можете просто поместить все свои пары ссылка/значение в отдельную таблицу и установить значение в отдельной таблице на nil при удалении ссылки. Затем вы можете просто перебрать отдельную таблицу.