Lua 의 시계 -- 'Lua 디자인 과 실현' 노트 읽 기

8037 단어 Lua
개술
1. Lua 언어 는 표 로 모든 데이터 구 조 를 나타 낸다.
2. Lua 표 는 배열 과 해시 표 부분 으로 나 뉜 다.
    배열 부분 색인 은 1 부터 시작 합 니 다.
    산열 표 부분 은 배열 부분 에 저장 할 수 없 는 모든 데 이 터 를 저장 할 수 있 습 니 다. 유일한 요 구 는 키 값 이 nil 이 될 수 없다 는 것 입 니 다.
데이터 구조
값 유형 정의
（lobject.h）
typedef struct Table {
  CommonHeader;
  lu_byte flags;  /* 1<

lu_byte flags;是一个byte类型的数据，用于表示这个表中提供了哪些元方法。

lu_byte lsizenode;以2为底的散列表大小的对数值。由此可见散列表的大小一定是2的幂，即如果散列桶数组要扩展的话，也是每次在原大小的基础上乘以2的形式扩展。

unsigned int sizearray;表示数组部分的大小

TValue *array; 指向数组部分的指针

Node *node;指向该表的散列桶数组起始位置的指针

Node *lastfree;指向该表散列桶数组的最后位置的指针。

struct Table *metatable;存放该表的元表

GCObject *gclist;GC相关的链表


Node类型定义

typedef struct Node {
  TValue i_val;
  TKey i_key;
} Node;

TKey 형식 정의
typedef struct lua_TValue {
  TValuefields;
} TValue;

이 를 통 해 알 수 있 듯 이 Lua 표 는 두 가지 유형의 데이터 구조 에 데 이 터 를 저장 하고 하 나 는 배열 이 며 하 나 는 산 목록 이다.
조작 알고리즘
    표 에는 산 목록 과 배열 의 두 부분 데이터 가 포함 되 어 있 기 때문에 정수 로 키 를 입력 한 데이터 가 Lua 표 에 기록 되 었 을 때 배열 을 기록 하 는 지 산 목록 을 기록 하 는 지 확실 하지 않 습 니 다.
1. 찾기
의사 코드 는 다음 과 같 습 니 다:
입력 한 key 가 정수 이 고 값 > 0 & & < = 배열 크기
    배열 부분 에서 찾 아 보기
그렇지 않 으 면 산 목록 에서 찾 아 보 세 요:
    이 key 의 해시 값 을 계산 합 니 다. 이 해시 값 에 따라 Node 배열 에 접근 하여 해시 통 이 있 는 위 치 를 얻 습 니 다.
    이 해시 통 아래 의 모든 링크 요 소 를 옮 겨 다 니 며 이 key 를 찾 을 때 까지
4. 567913. 1 만 배열 부분 으로 저장 되 었 고 100 은 해시 표 부분 에 저장 되 었 다.
2. 요소 추가
새로운 요 소 를 추가 하 는 절 차 는 비교적 복잡 하 며 재배 치 표 의 배열 과 해시 표 부분 과 관련 된 절차 입 니 다.
해시 표 부분의 데이터 조직 은 먼저 데이터 의 key 가 있 는 통 배열 위 치 를 계산 하고 이 위 치 를 mainposition 이 라 고 합 니 다.같은 mainposition 의 데 이 터 는 링크 형식 으로 구성 되 어 있 습 니 다.
API luaH 포함set、luaH_setnum、luaH_setstr 라 는 세 가지 함수 의 실제 행 위 는 그 함수 내부 에서 key 에 대응 하 는 데 이 터 를 추가 하거나 수정 하 는 것 이 아니 라 이 key 에서 찾 은 Tvalue 지침 에 따라 외부 사용자 가 실제 교체 작업 을 하 는 것 입 니 다.대응 하 는 키 를 찾 을 수 없 을 때, 이 API 들 은 결국 내부 의 뉴 키 함 수 를 호출 하여 새로운 키 를 분배 하여 되 돌려 줍 니 다.
typedef union TKey {
  struct {
    TValuefields;
    int next;  /* for chaining (offset for next node) */
  } nk;
  TValue tvk;
} TKey;

절 차 는 다음 과 같다.
(1) 산열 통 에 있 는 mainposition 을 찾 을 수 있 습 니 다. 되 돌아 온 결과 이 Node 의 값 이 nil 이면 key 를 직접 할당 하고 Node 의 Tvalue 지침 으로 되 돌려 주면 됩 니 다.
(2) 그렇지 않 으 면 이 mainposition 에 다른 데이터 가 있 음 을 설명 합 니 다. 이 새로운 key 에 공간 을 재배 치 한 다음 에 이 새로운 Node 를 해당 하 는 산열 통 에 연결 해 야 합 니 다.
이 를 통 해 알 수 있 듯 이 전체 과정 은 해시 통 부분 에서 진행 되 었 습 니 다. 이 유 는 key 가 숫자 라 도 new key 함 수 를 호출 하기 전에 찾 았 으 나 결 과 를 찾 지 못 했 기 때문에 이 key 는 해시 같은 부분 에 들 어가 서 찾 습 니 다.
상기 조작 디자인 이 표 공간 을 다시 분배 하 는 상황:
function print_ipairs(t)
  for k,v in ipairs(t) do
    print(k)
  end
end
local t = {}
t[1] = 0
t[100] = 0

(1) 비트 맵 nums 를 할당 하여 모든 위치 0. 이 옥토 액 의 미 는 nums 배열 에서 i 번 째 요 소 는 key 가 2 (i - 1) 차 멱 과 2 의 i 차 멱 사이 에 저장 하 는 요소 의 수량 입 니 다.
(2) Lua 표 의 배열 부분 을 옮 겨 다 니 며 그 중의 요소 수 를 계산 하고 해당 하 는 nums 배열 의 요소 수 를 업데이트 합 니 다 (numsearray 함수)
(3) Lua 표 의 산열 통 부분 을 옮 겨 다 니 며 정수 가 저 장 될 수도 있다 고 생각 합 니 다. 이 정수 수량 에 따라 해당 하 는 nums 배열 요소 수량 (numusehash 함수) 을 업데이트 해 야 합 니 다.
(4) 이때 nums 배열 은 현재 이 Table 의 모든 정수 에 대한 배분 통 계 를 가지 고 있 습 니 다. 각각 nums 배열 을 옮 겨 다 니 며 범위 구간 에 포 함 된 정수 수량 이 50% 이상 의 최대 색인 을 얻 었 습 니 다. 재 산열 후의 배열 크기 로 서 이 범위 의 정 수 를 초과 하면 산열 통 부분 (coptute sizes 함수) 에 분 배 됩 니 다.
(5) 위 에서 계산 한 조 정 된 배열 과 산열 통 크기 조정 표 (resize 함수)
이상 의 과정 을 통 해 알 수 있 듯 이 하나의 정수 키 는 같은 표 에서 서로 다른 단계 에서 배열 이나 산열 통 부분 에 분 배 될 수 있다.
Lua 의 디자인 사상 은 간단 하고 효율 적 이 며 메모리 자원 을 최대한 절약 해 야 한 다 는 것 이다.
성능 최적화: 아주 작은 시 계 를 만들어 야 할 때 미리 채 워 서 다시 해시 작업 을 피 할 수 있 습 니 다.
3. 교체
표 의 구 조 는 배열 과 산열 통 부분 을 포함 하기 때문에 교체 위조 코드 는 다음 과 같다.
배열 부분 에서 데이터 찾기:
    검색 에 성공 하면 이 key 의 다음 데 이 터 를 되 돌려 줍 니 다.
그렇지 않 으 면 산열 통 부분 에서 데 이 터 를 찾 습 니 다:
    검색 에 성공 하면 이 key 의 다음 데 이 터 를 되 돌려 줍 니 다.
4. 길이 조작
Lua 에 서 는 \ # 시 계 를 사용 하여 길 이 를 가 져 올 수 있 습 니 다.
(ltable.c)
/*
** inserts a new key into a hash table; first, check whether key's main
** position is free. If not, check whether colliding node is in its main
** position or not: if it is not, move colliding node to an empty place and
** put new key in its main position; otherwise (colliding node is in its main
** position), new key goes to an empty position.
*/
TValue *luaH_newkey (lua_State *L, Table *t, const TValue *key) {
  Node *mp;
  TValue aux;
  if (ttisnil(key)) luaG_runerror(L, "table index is nil");
  else if (ttisfloat(key)) {
    lua_Integer k;
    if (luaV_tointeger(key, &k, 0)) {  /* does index fit in an integer? */
      setivalue(&aux, k);
      key = &aux;  /* insert it as an integer */
    }
    else if (luai_numisnan(fltvalue(key)))
      luaG_runerror(L, "table index is NaN");
  }
  mp = mainposition(t, key);
  if (!ttisnil(gval(mp)) || isdummy(t)) {  /* main position is taken? */
    Node *othern;
    Node *f = getfreepos(t);  /* get a free place */
    if (f == NULL) {  /* cannot find a free place? */
      rehash(L, t, key);  /* grow table */
      /* whatever called 'newkey' takes care of TM cache */
      return luaH_set(L, t, key);  /* insert key into grown table */
    }
    lua_assert(!isdummy(t));
    othern = mainposition(t, gkey(mp));
    if (othern != mp) {  /* is colliding node out of its main position? */
      /* yes; move colliding node into free position */
      while (othern + gnext(othern) != mp)  /* find previous */
        othern += gnext(othern);
      gnext(othern) = cast_int(f - othern);  /* rechain to point to 'f' */
      *f = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
      if (gnext(mp) != 0) {
        gnext(f) += cast_int(mp - f);  /* correct 'next' */
        gnext(mp) = 0;  /* now 'mp' is free */
      }
      setnilvalue(gval(mp));
    }
    else {  /* colliding node is in its own main position */
      /* new node will go into free position */
      if (gnext(mp) != 0)
        gnext(f) = cast_int((mp + gnext(mp)) - f);  /* chain new position */
      else lua_assert(gnext(f) == 0);
      gnext(mp) = cast_int(f - mp);
      mp = f;
    }
  }
  setnodekey(L, &mp->i_key, key);
  luaC_barrierback(L, t, key);
  lua_assert(ttisnil(gval(mp)));
  return gval(mp);
}

표 에 배열 이 없어 서 산열 통 이 존재 할 때 도 키 값 이 정수 인 부분 에 대해 길 이 를 취 하 는 작업 을 합 니 다.
/*
** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
*/
static void rehash (lua_State *L, Table *t, const TValue *ek) {
  unsigned int asize;  /* optimal size for array part */
  unsigned int na;  /* number of keys in the array part */
  unsigned int nums[MAXABITS + 1];
  int i;
  int totaluse;
  for (i = 0; i <= MAXABITS; i++) nums[i] = 0;  /* reset counts */
  na = numusearray(t, nums);  /* count keys in array part */
  totaluse = na;  /* all those keys are integer keys */
  totaluse += numusehash(t, nums, &na);  /* count keys in hash part */
  /* count extra key */
  na += countint(ek, nums);
  totaluse++;
  /* compute new size for array part */
  asize = computesizes(nums, &na);
  /* resize the table to new computed sizes */
  luaH_resize(L, t, asize, totaluse - na);
}
print(#{10,20,nil,40}) --   2

，

：

：

    i， i t[i] ！= nil t[i+1] = nil

， ：

    i, i t[i] != nil t[i+1] = nil

데이터 구조 - 2 단일 체인 테이블 삽입 및 삭제 노드
springboot에서rest 인터페이스 404500 json 형식으로 되돌아오기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage