Lua 원본 읽 기 노트 - string 문자열

18232 단어 Lua
TString 데이터 구조
// lobject.h

/*
** String headers for string table
*/
typedef union TString {
  L_Umaxalign dummy;  /* ensures maximum alignment for strings */
  struct {
    CommonHeader;
    lu_byte reserved;
    unsigned int hash;
    size_t len;
  } tsv;
} TString;

위 는 lua 문자열 의 데이터 구조 입 니 다.이 를 통 해 알 수 있 듯 이 TString 에는 명시 적 char* 변수 가 나타 나 지 않 고 해시 값 과 길이 가 저장 되 어 있다.그래서 이 안에 저장 문자 가 없 나 요?TString 의 생 성 함 수 를 살 펴 보 겠 습 니 다.
TString 만 들 기
먼저 대응 하 는 소스 코드 를 붙 입 니 다.
// lstring.c

TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
  GCObject *o;
  unsigned int h = cast(unsigned int, l);  /* seed */
  size_t step = (l>>5)+1;  /* if string is too long, don't hash all its chars */
  size_t l1;
  for (l1=l; l1>=step; l1-=step)  /* compute hash */
    h = h ^ ((h<<5)+(h>>2)+cast(unsigned char, str[l1-1]));
  for (o = G(L)->strt.hash[lmod(h, G(L)->strt.size)];
       o != NULL;
       o = o->gch.next) {
    TString *ts = rawgco2ts(o);
    if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) {
      /* string may be dead */
      if (isdead(G(L), o)) changewhite(o);
      return ts;
    }
  }
  return newlstr(L, str, l, h);  /* not found */
}

함수 가 문자열 str 과 길이 l 를 입력 합 니 다. 먼저 문자열 의 해시 값 h 을 계산 한 다음 전체 문자열 표 에서 찾 습 니 다. 문자열 의 길이 와 메모 리 를 비교 하고 찾 으 면 만 든 문자열 을 되 돌려 줍 니 다. 그렇지 않 으 면 새로 만 듭 니 다.
전역 문자열 표 strt 의 정 의 를 보십시오.
// lstate.h

/*
** `global state', shared by all threads of this state
*/
typedef struct global_State {
  stringtable strt;  /* hash table for strings */
...

typedef struct stringtable {
  GCObject **hash;
  lu_int32 nuse;  /* number of elements */
  int size;
} stringtable;
strt 정 의 는 전체 상태 에서 hash 모든 TString 을 저장 한 해시 표 입 니 다.이 시 계 를 옮 겨 다 니 면 lua 의 모든 문자열 을 찾 을 수 있 습 니 다.hash 을 찾 는 과정 에서 조건 이 있 습 니 다. if (ts->tsv.len == l && (memcmp(str, getstr(ts), l) == 0)) 여 기 는 길 이 를 비교 한 다음 에 문자열 메모 리 를 비교 해 보 았 습 니 다. getstr
// lobject.h

#define getstr(ts)    cast(const char *, (ts) + 1)

생 성 된 문자열 str 뒤의 메모리 와 비교 하기 때문에 ts 에 도 문자열 이 저장 되 어 있 고 가 까 운 메모리 영역 에 있 을 것 이 라 고 추측 할 수 있 습 니 다.
새 문자열 의 함수 TString 를 살 펴 보 겠 습 니 다.
// lstring.c

static TString *newlstr (lua_State *L, const char *str, size_t l,
                                       unsigned int h) {
  TString *ts;
  stringtable *tb;
  if (l+1 > (MAX_SIZET - sizeof(TString))/sizeof(char))
    luaM_toobig(L);
  ts = cast(TString *, luaM_malloc(L, (l+1)*sizeof(char)+sizeof(TString)));
  ts->tsv.len = l;
  ts->tsv.hash = h;
  ts->tsv.marked = luaC_white(G(L));
  ts->tsv.tt = LUA_TSTRING;
  ts->tsv.reserved = 0;
  memcpy(ts+1, str, l*sizeof(char));
  ((char *)(ts+1))[l] = '\0';  /* ending 0 */
  tb = &G(L)->strt;
  h = lmod(h, tb->size);
  ts->tsv.next = tb->hash[h];  /* chain new entry */
  tb->hash[h] = obj2gco(ts);
  tb->nuse++;
  if (tb->nuse > cast(lu_int32, tb->size) && tb->size <= MAX_INT/2)
    luaS_resize(L, tb->size*2);  /* too crowded */
  return ts;
}

문자열 표 에서 찾 을 수 없 을 때 이 함수 의 새 문자열 에 들 어 갑 니 다.메모 리 를 할당 할 때 TString *newlstr (lua_State *L, const char *str, size_t l, unsigned int h) 공간 외 에 도 TString 바이트 가 더 할당 되 어 들 어 오 는 문자열 을 저장 하 는 데 사용 되 었 으 며, 여기 서도 이전의 추측 을 검증 하 였 다.l+1 새로 만 든 후 문자열 해시 값 에 따라 새로운 해시 값 TString 을 다시 계산 한 다음 전체 문자열 표 h 에 삽입 합 니 다.strt 의 해시 표 는 strt 의 해시 표 와 다르다. table 의 해시 표 는 개방 주소 법 을 사용 하고 table 의 해시 표 는 체인 주소 법 을 사용한다.삽입 후 전역 문자열 표 가 너무 큰 것 을 발견 하면 호출 strt 을 통 해 해시 표 에 메모 리 를 다시 할당 합 니 다. 공간 은 이전의 두 배 이 고 낡은 해시 표 의 데 이 터 를 새 해시 표 에 삽입 한 다음 에 이전의 메모 리 를 방출 합 니 다.
https://blog.csdn.net/fujia_jzyl / article / details / 8839434343 오리지널 이 쉽 지 않 습 니 다. 전재 출처 를 밝 혀 주 십시오. 감사합니다!

좋은 웹페이지 즐겨찾기