LCOV - code coverage report
Current view: top level - external/lua/src - lstring.c (source / functions) Hit Total Coverage
Test: rapport Lines: 136 149 91.3 %
Date: 2021-12-10 16:22:55 Functions: 15 15 100.0 %
Branches: 53 68 77.9 %

           Branch data     Line data    Source code
       1                 :            : /*
       2                 :            : ** $Id: lstring.c $
       3                 :            : ** String table (keeps all strings handled by Lua)
       4                 :            : ** See Copyright Notice in lua.h
       5                 :            : */
       6                 :            : 
       7                 :            : #define lstring_c
       8                 :            : #define LUA_CORE
       9                 :            : 
      10                 :            : #include "lprefix.h"
      11                 :            : 
      12                 :            : 
      13                 :            : #include <string.h>
      14                 :            : 
      15                 :            : #include "lua.h"
      16                 :            : 
      17                 :            : #include "ldebug.h"
      18                 :            : #include "ldo.h"
      19                 :            : #include "lmem.h"
      20                 :            : #include "lobject.h"
      21                 :            : #include "lstate.h"
      22                 :            : #include "lstring.h"
      23                 :            : 
      24                 :            : 
      25                 :            : /*
      26                 :            : ** Maximum size for string table.
      27                 :            : */
      28                 :            : #define MAXSTRTB        cast_int(luaM_limitN(MAX_INT, TString*))
      29                 :            : 
      30                 :            : 
      31                 :            : /*
      32                 :            : ** equality for long strings
      33                 :            : */
      34                 :         16 : int luaS_eqlngstr (TString *a, TString *b) {
      35                 :         16 :   size_t len = a->u.lnglen;
      36                 :            :   lua_assert(a->tt == LUA_VLNGSTR && b->tt == LUA_VLNGSTR);
      37         [ -  + ]:         16 :   return (a == b) ||  /* same instance or... */
      38         [ #  # ]:          0 :     ((len == b->u.lnglen) &&  /* equal length and ... */
      39                 :          0 :      (memcmp(getstr(a), getstr(b), len) == 0));  /* equal contents */
      40                 :            : }
      41                 :            : 
      42                 :            : 
      43                 :     190565 : unsigned int luaS_hash (const char *str, size_t l, unsigned int seed) {
      44                 :     190565 :   unsigned int h = seed ^ cast_uint(l);
      45         [ +  + ]:    1344131 :   for (; l > 0; l--)
      46                 :    1153566 :     h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1]));
      47                 :     190565 :   return h;
      48                 :            : }
      49                 :            : 
      50                 :            : 
      51                 :         88 : unsigned int luaS_hashlongstr (TString *ts) {
      52                 :            :   lua_assert(ts->tt == LUA_VLNGSTR);
      53         [ +  + ]:         88 :   if (ts->extra == 0) {  /* no hash? */
      54                 :         16 :     size_t len = ts->u.lnglen;
      55                 :         16 :     ts->hash = luaS_hash(getstr(ts), len, ts->hash);
      56                 :         16 :     ts->extra = 1;  /* now it has its hash */
      57                 :         16 :   }
      58                 :         88 :   return ts->hash;
      59                 :            : }
      60                 :            : 
      61                 :            : 
      62                 :       1620 : static void tablerehash (TString **vect, int osize, int nsize) {
      63                 :            :   int i;
      64         [ +  + ]:     208980 :   for (i = osize; i < nsize; i++)  /* clear new elements */
      65                 :     207360 :     vect[i] = NULL;
      66         [ +  + ]:     105300 :   for (i = 0; i < osize; i++) {  /* rehash old part of the array */
      67                 :     103680 :     TString *p = vect[i];
      68                 :     103680 :     vect[i] = NULL;
      69         [ +  + ]:     207360 :     while (p) {  /* for each string in the list */
      70                 :     103680 :       TString *hnext = p->u.hnext;  /* save next */
      71                 :     103680 :       unsigned int h = lmod(p->hash, nsize);  /* new position */
      72                 :     103680 :       p->u.hnext = vect[h];  /* chain it into array */
      73                 :     103680 :       vect[h] = p;
      74                 :     103680 :       p = hnext;
      75                 :            :     }
      76                 :     103680 :   }
      77                 :       1620 : }
      78                 :            : 
      79                 :            : 
      80                 :            : /*
      81                 :            : ** Resize the string table. If allocation fails, keep the current size.
      82                 :            : ** (This can degrade performance, but any non-zero size should work
      83                 :            : ** correctly.)
      84                 :            : */
      85                 :        810 : void luaS_resize (lua_State *L, int nsize) {
      86                 :        810 :   stringtable *tb = &G(L)->strt;
      87                 :        810 :   int osize = tb->size;
      88                 :            :   TString **newvect;
      89         [ +  - ]:        810 :   if (nsize < osize)  /* shrinking table? */
      90                 :          0 :     tablerehash(tb->hash, osize, nsize);  /* depopulate shrinking part */
      91                 :        810 :   newvect = luaM_reallocvector(L, tb->hash, osize, nsize, TString*);
      92         [ +  - ]:        810 :   if (unlikely(newvect == NULL)) {  /* reallocation failed? */
      93         [ #  # ]:          0 :     if (nsize < osize)  /* was it shrinking table? */
      94                 :          0 :       tablerehash(tb->hash, nsize, osize);  /* restore to original size */
      95                 :            :     /* leave table as it was */
      96                 :          0 :   }
      97                 :            :   else {  /* allocation succeeded */
      98                 :        810 :     tb->hash = newvect;
      99                 :        810 :     tb->size = nsize;
     100         [ -  + ]:        810 :     if (nsize > osize)
     101                 :        810 :       tablerehash(newvect, osize, nsize);  /* rehash for new size */
     102                 :            :   }
     103                 :        810 : }
     104                 :            : 
     105                 :            : 
     106                 :            : /*
     107                 :            : ** Clear API string cache. (Entries cannot be empty, so fill them with
     108                 :            : ** a non-collectable string.)
     109                 :            : */
     110                 :       1965 : void luaS_clearcache (global_State *g) {
     111                 :            :   int i, j;
     112         [ +  + ]:     106110 :   for (i = 0; i < STRCACHE_N; i++)
     113         [ +  + ]:     312435 :     for (j = 0; j < STRCACHE_M; j++) {
     114         [ +  + ]:     208290 :       if (iswhite(g->strcache[i][j]))  /* will entry be collected? */
     115                 :       1868 :         g->strcache[i][j] = g->memerrmsg;  /* replace it with something fixed */
     116                 :     312435 :     }
     117                 :       1965 : }
     118                 :            : 
     119                 :            : 
     120                 :            : /*
     121                 :            : ** Initialize the string table and the string cache
     122                 :            : */
     123                 :        810 : void luaS_init (lua_State *L) {
     124                 :        810 :   global_State *g = G(L);
     125                 :            :   int i, j;
     126                 :        810 :   stringtable *tb = &G(L)->strt;
     127                 :        810 :   tb->hash = luaM_newvector(L, MINSTRTABSIZE, TString*);
     128                 :        810 :   tablerehash(tb->hash, 0, MINSTRTABSIZE);  /* clear array */
     129                 :        810 :   tb->size = MINSTRTABSIZE;
     130                 :            :   /* pre-create memory-error message */
     131                 :        810 :   g->memerrmsg = luaS_newliteral(L, MEMERRMSG);
     132                 :        810 :   luaC_fix(L, obj2gco(g->memerrmsg));  /* it should never be collected */
     133         [ +  + ]:      43740 :   for (i = 0; i < STRCACHE_N; i++)  /* fill cache with valid strings */
     134         [ +  + ]:     128790 :     for (j = 0; j < STRCACHE_M; j++)
     135                 :     128790 :       g->strcache[i][j] = g->memerrmsg;
     136                 :        810 : }
     137                 :            : 
     138                 :            : 
     139                 :            : 
     140                 :            : /*
     141                 :            : ** creates a new string object
     142                 :            : */
     143                 :     174066 : static TString *createstrobj (lua_State *L, size_t l, int tag, unsigned int h) {
     144                 :            :   TString *ts;
     145                 :            :   GCObject *o;
     146                 :            :   size_t totalsize;  /* total size of TString object */
     147                 :     174066 :   totalsize = sizelstring(l);
     148                 :     174066 :   o = luaC_newobj(L, tag, totalsize);
     149                 :     174066 :   ts = gco2ts(o);
     150                 :     174066 :   ts->hash = h;
     151                 :     174066 :   ts->extra = 0;
     152                 :     174066 :   getstr(ts)[l] = '\0';  /* ending 0 */
     153                 :     174066 :   return ts;
     154                 :            : }
     155                 :            : 
     156                 :            : 
     157                 :       2417 : TString *luaS_createlngstrobj (lua_State *L, size_t l) {
     158                 :       2417 :   TString *ts = createstrobj(L, l, LUA_VLNGSTR, G(L)->seed);
     159                 :       2417 :   ts->u.lnglen = l;
     160                 :       2417 :   return ts;
     161                 :            : }
     162                 :            : 
     163                 :            : 
     164                 :      12225 : void luaS_remove (lua_State *L, TString *ts) {
     165                 :      12225 :   stringtable *tb = &G(L)->strt;
     166                 :      12225 :   TString **p = &tb->hash[lmod(ts->hash, tb->size)];
     167         [ +  + ]:      13928 :   while (*p != ts)  /* find previous element */
     168                 :       1703 :     p = &(*p)->u.hnext;
     169                 :      12225 :   *p = (*p)->u.hnext;  /* remove element from its list */
     170                 :      12225 :   tb->nuse--;
     171                 :      12225 : }
     172                 :            : 
     173                 :            : 
     174                 :        810 : static void growstrtab (lua_State *L, stringtable *tb) {
     175         [ +  - ]:        810 :   if (unlikely(tb->nuse == MAX_INT)) {  /* too many strings? */
     176                 :          0 :     luaC_fullgc(L, 1);  /* try to free some... */
     177         [ #  # ]:          0 :     if (tb->nuse == MAX_INT)  /* still too many? */
     178                 :          0 :       luaM_error(L);  /* cannot even create a message... */
     179                 :          0 :   }
     180         [ -  + ]:        810 :   if (tb->size <= MAXSTRTB / 2)  /* can grow string table? */
     181                 :        810 :     luaS_resize(L, tb->size * 2);
     182                 :        810 : }
     183                 :            : 
     184                 :            : 
     185                 :            : /*
     186                 :            : ** Checks whether short string exists and reuses it or creates a new one.
     187                 :            : */
     188                 :     189739 : static TString *internshrstr (lua_State *L, const char *str, size_t l) {
     189                 :            :   TString *ts;
     190                 :     189739 :   global_State *g = G(L);
     191                 :     189739 :   stringtable *tb = &g->strt;
     192                 :     189739 :   unsigned int h = luaS_hash(str, l, g->seed);
     193                 :     189739 :   TString **list = &tb->hash[lmod(h, tb->size)];
     194                 :            :   lua_assert(str != NULL);  /* otherwise 'memcmp'/'memcpy' are undefined */
     195         [ +  + ]:     293760 :   for (ts = *list; ts != NULL; ts = ts->u.hnext) {
     196   [ +  +  +  + ]:     122111 :     if (l == ts->shrlen && (memcmp(str, getstr(ts), l * sizeof(char)) == 0)) {
     197                 :            :       /* found! */
     198         [ -  + ]:      18090 :       if (isdead(g, ts))  /* dead (but not collected yet)? */
     199                 :          0 :         changewhite(ts);  /* resurrect it */
     200                 :      18090 :       return ts;
     201                 :            :     }
     202                 :     104021 :   }
     203                 :            :   /* else must create a new string */
     204         [ +  + ]:     171649 :   if (tb->nuse >= tb->size) {  /* need to grow string table? */
     205                 :        810 :     growstrtab(L, tb);
     206                 :        810 :     list = &tb->hash[lmod(h, tb->size)];  /* rehash with new size */
     207                 :        810 :   }
     208                 :     171649 :   ts = createstrobj(L, l, LUA_VSHRSTR, h);
     209                 :     171649 :   memcpy(getstr(ts), str, l * sizeof(char));
     210                 :     171649 :   ts->shrlen = cast_byte(l);
     211                 :     171649 :   ts->u.hnext = *list;
     212                 :     171649 :   *list = ts;
     213                 :     171649 :   tb->nuse++;
     214                 :     171649 :   return ts;
     215                 :     189739 : }
     216                 :            : 
     217                 :            : 
     218                 :            : /*
     219                 :            : ** new string (with explicit length)
     220                 :            : */
     221                 :     191870 : TString *luaS_newlstr (lua_State *L, const char *str, size_t l) {
     222         [ +  + ]:     191870 :   if (l <= LUAI_MAXSHORTLEN)  /* short string? */
     223                 :     189739 :     return internshrstr(L, str, l);
     224                 :            :   else {
     225                 :            :     TString *ts;
     226         [ -  + ]:       2131 :     if (unlikely(l >= (MAX_SIZE - sizeof(TString))/sizeof(char)))
     227                 :          0 :       luaM_toobig(L);
     228                 :       2131 :     ts = luaS_createlngstrobj(L, l);
     229                 :       2131 :     memcpy(getstr(ts), str, l * sizeof(char));
     230                 :       2131 :     return ts;
     231                 :            :   }
     232                 :     191870 : }
     233                 :            : 
     234                 :            : 
     235                 :            : /*
     236                 :            : ** Create or reuse a zero-terminated string, first checking in the
     237                 :            : ** cache (using the string address as a key). The cache can contain
     238                 :            : ** only zero-terminated strings, so it is safe to use 'strcmp' to
     239                 :            : ** check hits.
     240                 :            : */
     241                 :     248641 : TString *luaS_new (lua_State *L, const char *str) {
     242                 :     248641 :   unsigned int i = point2uint(str) % STRCACHE_N;  /* hash */
     243                 :            :   int j;
     244                 :     248641 :   TString **p = G(L)->strcache[i];
     245         [ +  + ]:     628220 :   for (j = 0; j < STRCACHE_M; j++) {
     246         [ +  + ]:     445758 :     if (strcmp(str, getstr(p[j])) == 0)  /* hit? */
     247                 :      66179 :       return p[j];  /* that is it */
     248                 :     379579 :   }
     249                 :            :   /* normal route */
     250         [ +  + ]:     364924 :   for (j = STRCACHE_M - 1; j > 0; j--)
     251                 :     182462 :     p[j] = p[j - 1];  /* move out last element */
     252                 :            :   /* new element is first in the list */
     253                 :     182462 :   p[0] = luaS_newlstr(L, str, strlen(str));
     254                 :     182462 :   return p[0];
     255                 :     248641 : }
     256                 :            : 
     257                 :            : 
     258                 :       3268 : Udata *luaS_newudata (lua_State *L, size_t s, int nuvalue) {
     259                 :            :   Udata *u;
     260                 :            :   int i;
     261                 :            :   GCObject *o;
     262   [ +  +  -  + ]:       3268 :   if (unlikely(s > MAX_SIZE - udatamemoffset(nuvalue)))
     263                 :          0 :     luaM_toobig(L);
     264         [ +  + ]:       3268 :   o = luaC_newobj(L, LUA_VUSERDATA, sizeudata(nuvalue, s));
     265                 :       3268 :   u = gco2u(o);
     266                 :       3268 :   u->len = s;
     267                 :       3268 :   u->nuvalue = nuvalue;
     268                 :       3268 :   u->metatable = NULL;
     269         [ +  + ]:       3296 :   for (i = 0; i < nuvalue; i++)
     270                 :         28 :     setnilvalue(&u->uv[i].uv);
     271                 :       3268 :   return u;
     272                 :            : }
     273                 :            : 

Generated by: LCOV version 1.15