LCOV - code coverage report
Current view: directory - src - ltable.c Found Hit Coverage
Test: Lua 5.1.4 Lines: 271 253 93.4 %
Date: 2009-09-13
Colors: not hit hit

       1                 : /*
       2                 : ** $Id: ltable.c,v 2.32.1.2 2007/12/28 15:32:23 roberto Exp $
       3                 : ** Lua tables (hash)
       4                 : ** See Copyright Notice in lua.h
       5                 : */
       6                 : 
       7                 : 
       8                 : /*
       9                 : ** Implementation of tables (aka arrays, objects, or hash tables).
      10                 : ** Tables keep its elements in two parts: an array part and a hash part.
      11                 : ** Non-negative integer keys are all candidates to be kept in the array
      12                 : ** part. The actual size of the array is the largest `n' such that at
      13                 : ** least half the slots between 0 and n are in use.
      14                 : ** Hash uses a mix of chained scatter table with Brent's variation.
      15                 : ** A main invariant of these tables is that, if an element is not
      16                 : ** in its main position (i.e. the `original' position that its hash gives
      17                 : ** to it), then the colliding element is in its own main position.
      18                 : ** Hence even when the load factor reaches 100%, performance remains good.
      19                 : */
      20                 : 
      21                 : #include <math.h>
      22                 : #include <string.h>
      23                 : 
      24                 : #define ltable_c
      25                 : #define LUA_CORE
      26                 : 
      27                 : #include "lua.h"
      28                 : 
      29                 : #include "ldebug.h"
      30                 : #include "ldo.h"
      31                 : #include "lgc.h"
      32                 : #include "lmem.h"
      33                 : #include "lobject.h"
      34                 : #include "lstate.h"
      35                 : #include "ltable.h"
      36                 : 
      37                 : 
      38                 : /*
      39                 : ** max size of array part is 2^MAXBITS
      40                 : */
      41                 : #if LUAI_BITSINT > 26
      42                 : #define MAXBITS         26
      43                 : #else
      44                 : #define MAXBITS         (LUAI_BITSINT-2)
      45                 : #endif
      46                 : 
      47                 : #define MAXASIZE        (1 << MAXBITS)
      48                 : 
      49                 : 
      50                 : #define hashpow2(t,n)      (gnode(t, lmod((n), sizenode(t))))
      51                 :   
      52                 : #define hashstr(t,str)  hashpow2(t, (str)->tsv.hash)
      53                 : #define hashboolean(t,p)        hashpow2(t, p)
      54                 : 
      55                 : 
      56                 : /*
      57                 : ** for some types, it is better to avoid modulus by power of 2, as
      58                 : ** they tend to have many 2 factors.
      59                 : */
      60                 : #define hashmod(t,n)    (gnode(t, ((n) % ((sizenode(t)-1)|1))))
      61                 : 
      62                 : 
      63                 : #define hashpointer(t,p)        hashmod(t, IntPoint(p))
      64                 : 
      65                 : 
      66                 : /*
      67                 : ** number of ints inside a lua_Number
      68                 : */
      69                 : #define numints         cast_int(sizeof(lua_Number)/sizeof(int))
      70                 : 
      71                 : 
      72                 : 
      73                 : #define dummynode               (&dummynode_)
      74                 : 
      75                 : static const Node dummynode_ = {
      76                 :   {{NULL}, LUA_TNIL},  /* value */
      77                 :   {{{NULL}, LUA_TNIL, NULL}}  /* key */
      78                 : };
      79                 : 
      80                 : 
      81                 : /*
      82                 : ** hash for lua_Numbers
      83                 : */
      84           53662 : static Node *hashnum (const Table *t, lua_Number n) {
      85                 :   unsigned int a[numints];
      86                 :   int i;
      87           53662 :   if (luai_numeq(n, 0))  /* avoid problems with -0 */
      88            1874 :     return gnode(t, 0);
      89           51788 :   memcpy(a, &n, sizeof(a));
      90           51788 :   for (i = 1; i < numints; i++) a[0] += a[i];
      91           51788 :   return hashmod(t, a[0]);
      92                 : }
      93                 : 
      94                 : 
      95                 : 
      96                 : /*
      97                 : ** returns the `main' position of an element in a table (that is, the index
      98                 : ** of its hash value)
      99                 : */
     100          123938 : static Node *mainposition (const Table *t, const TValue *key) {
     101          123938 :   switch (ttype(key)) {
     102                 :     case LUA_TNUMBER:
     103           26659 :       return hashnum(t, nvalue(key));
     104                 :     case LUA_TSTRING:
     105           96922 :       return hashstr(t, rawtsvalue(key));
     106                 :     case LUA_TBOOLEAN:
     107             151 :       return hashboolean(t, bvalue(key));
     108                 :     case LUA_TLIGHTUSERDATA:
     109               0 :       return hashpointer(t, pvalue(key));
     110                 :     default:
     111             206 :       return hashpointer(t, gcvalue(key));
     112                 :   }
     113                 : }
     114                 : 
     115                 : 
     116                 : /*
     117                 : ** returns the index for `key' if `key' is an appropriate key to live in
     118                 : ** the array part of the table, -1 otherwise.
     119                 : */
     120           70090 : static int arrayindex (const TValue *key) {
     121           70090 :   if (ttisnumber(key)) {
     122           25149 :     lua_Number n = nvalue(key);
     123                 :     int k;
     124           25149 :     lua_number2int(k, n);
     125           25149 :     if (luai_numeq(cast_num(k), n))
     126           25103 :       return k;
     127                 :   }
     128           44987 :   return -1;  /* `key' did not match some condition */
     129                 : }
     130                 : 
     131                 : 
     132                 : /*
     133                 : ** returns the index of a `key' for table traversals. First goes all
     134                 : ** elements in the array part, then elements in the hash part. The
     135                 : ** beginning of a traversal is signalled by -1.
     136                 : */
     137             788 : static int findindex (lua_State *L, Table *t, StkId key) {
     138                 :   int i;
     139             788 :   if (ttisnil(key)) return -1;  /* first iteration */
     140             744 :   i = arrayindex(key);
     141             744 :   if (0 < i && i <= t->sizearray)  /* is `key' inside array part? */
     142              25 :     return i-1;  /* yes; that's the index (corrected to C) */
     143                 :   else {
     144             719 :     Node *n = mainposition(t, key);
     145                 :     do {  /* check whether `key' is somewhere in the chain */
     146                 :       /* key may be dead already, but it is ok to use it in `next' */
     147             975 :       if (luaO_rawequalObj(key2tval(n), key) ||
     148                 :             (ttype(gkey(n)) == LUA_TDEADKEY && iscollectable(key) &&
     149                 :              gcvalue(gkey(n)) == gcvalue(key))) {
     150             718 :         i = cast_int(n - gnode(t, 0));  /* key index in hash table */
     151                 :         /* hash elements are numbered after array ones */
     152             718 :         return i + t->sizearray;
     153                 :       }
     154             257 :       else n = gnext(n);
     155             257 :     } while (n);
     156               1 :     luaG_runerror(L, "invalid key to " LUA_QL("next"));  /* key not found */
     157               0 :     return 0;  /* to avoid warnings */
     158                 :   }
     159                 : }
     160                 : 
     161                 : 
     162             788 : int luaH_next (lua_State *L, Table *t, StkId key) {
     163             788 :   int i = findindex(L, t, key);  /* find original element */
     164             787 :   for (i++; i < t->sizearray; i++) {  /* try first array part */
     165              24 :     if (!ttisnil(&t->array[i])) {  /* a non-nil value? */
     166              24 :       setnvalue(key, cast_num(i+1));
     167              24 :       setobj2s(L, key+1, &t->array[i]);
     168              24 :       return 1;
     169                 :     }
     170                 :   }
     171             972 :   for (i -= t->sizearray; i < sizenode(t); i++) {  /* then hash part */
     172             927 :     if (!ttisnil(gval(gnode(t, i)))) {  /* a non-nil value? */
     173             718 :       setobj2s(L, key, key2tval(gnode(t, i)));
     174             718 :       setobj2s(L, key+1, gval(gnode(t, i)));
     175             718 :       return 1;
     176                 :     }
     177                 :   }
     178              45 :   return 0;  /* no more elements */
     179                 : }
     180                 : 
     181                 : 
     182                 : /*
     183                 : ** {=============================================================
     184                 : ** Rehash
     185                 : ** ==============================================================
     186                 : */
     187                 : 
     188                 : 
     189           32905 : static int computesizes (int nums[], int *narray) {
     190                 :   int i;
     191                 :   int twotoi;  /* 2^i */
     192           32905 :   int a = 0;  /* number of elements smaller than 2^i */
     193           32905 :   int na = 0;  /* number of elements to go to array part */
     194           32905 :   int n = 0;  /* optimal size for array part */
     195           69083 :   for (i = 0, twotoi = 1; twotoi/2 < *narray; i++, twotoi *= 2) {
     196           60481 :     if (nums[i] > 0) {
     197           60189 :       a += nums[i];
     198           60189 :       if (a > twotoi/2) {  /* more than half elements present? */
     199           60142 :         n = twotoi;  /* optimal size (till now) */
     200           60142 :         na = a;  /* all elements smaller than n will go to array part */
     201                 :       }
     202                 :     }
     203           60481 :     if (a == *narray) break;  /* all elements already counted */
     204                 :   }
     205           32905 :   *narray = n;
     206                 :   lua_assert(*narray/2 <= na && na <= *narray);
     207           32905 :   return na;
     208                 : }
     209                 : 
     210                 : 
     211           69346 : static int countint (const TValue *key, int *nums) {
     212           69346 :   int k = arrayindex(key);
     213           69346 :   if (0 < k && k <= MAXASIZE) {  /* is `key' an appropriate array index? */
     214           24592 :     nums[ceillog2(k)]++;  /* count as such */
     215           24592 :     return 1;
     216                 :   }
     217                 :   else
     218           44754 :     return 0;
     219                 : }
     220                 : 
     221                 : 
     222           32905 : static int numusearray (const Table *t, int *nums) {
     223                 :   int lg;
     224                 :   int ttlg;  /* 2^lg */
     225           32905 :   int ause = 0;  /* summation of `nums' */
     226           32905 :   int i = 1;  /* count to traverse all array keys */
     227           68958 :   for (lg=0, ttlg=1; lg<=MAXBITS; lg++, ttlg*=2) {  /* for each slice */
     228           68958 :     int lc = 0;  /* counter */
     229           68958 :     int lim = ttlg;
     230           68958 :     if (lim > t->sizearray) {
     231           32908 :       lim = t->sizearray;  /* adjust upper limit */
     232           32908 :       if (i > lim)
     233           32905 :         break;  /* no more elements to count */
     234                 :     }
     235                 :     /* count elements in range (2^(lg-1), 2^lg] */
     236           80058 :     for (; i <= lim; i++) {
     237           44005 :       if (!ttisnil(&t->array[i-1]))
     238           43947 :         lc++;
     239                 :     }
     240           36053 :     nums[lg] += lc;
     241           36053 :     ause += lc;
     242                 :   }
     243           32905 :   return ause;
     244                 : }
     245                 : 
     246                 : 
     247           32905 : static int numusehash (const Table *t, int *nums, int *pnasize) {
     248           32905 :   int totaluse = 0;  /* total number of elements */
     249           32905 :   int ause = 0;  /* summation of `nums' */
     250           32905 :   int i = sizenode(t);
     251          127886 :   while (i--) {
     252           62076 :     Node *n = &t->node[i];
     253           62076 :     if (!ttisnil(gval(n))) {
     254           36441 :       ause += countint(key2tval(n), nums);
     255           36441 :       totaluse++;
     256                 :     }
     257                 :   }
     258           32905 :   *pnasize += ause;
     259           32905 :   return totaluse;
     260                 : }
     261                 : 
     262                 : 
     263           33340 : static void setarrayvector (lua_State *L, Table *t, int size) {
     264                 :   int i;
     265           33340 :   luaM_reallocvector(L, t->array, t->sizearray, size, TValue);
     266           82833 :   for (i=t->sizearray; i<size; i++)
     267           49493 :      setnilvalue(&t->array[i]);
     268           33340 :   t->sizearray = size;
     269           33340 : }
     270                 : 
     271                 : 
     272           42175 : static void setnodevector (lua_State *L, Table *t, int size) {
     273                 :   int lsize;
     274           42175 :   if (size == 0) {  /* no elements to hash part? */
     275           32174 :     t->node = cast(Node *, dummynode);  /* use common `dummynode' */
     276           32174 :     lsize = 0;
     277                 :   }
     278                 :   else {
     279                 :     int i;
     280           10001 :     lsize = ceillog2(size);
     281           10001 :     if (lsize > MAXBITS)
     282               0 :       luaG_runerror(L, "table overflow");
     283           10001 :     size = twoto(lsize);
     284           10001 :     t->node = luaM_newvector(L, size, Node);
     285           87159 :     for (i=0; i<size; i++) {
     286           77158 :       Node *n = gnode(t, i);
     287           77158 :       gnext(n) = NULL;
     288           77158 :       setnilvalue(gkey(n));
     289           77158 :       setnilvalue(gval(n));
     290                 :     }
     291                 :   }
     292           42175 :   t->lsizenode = cast_byte(lsize);
     293           42175 :   t->lastfree = gnode(t, size);  /* all positions are free */
     294           42175 : }
     295                 : 
     296                 : 
     297           33101 : static void resize (lua_State *L, Table *t, int nasize, int nhsize) {
     298                 :   int i;
     299           33101 :   int oldasize = t->sizearray;
     300           33101 :   int oldhsize = t->lsizenode;
     301           33101 :   Node *nold = t->node;  /* save old hash ... */
     302           33101 :   if (nasize > oldasize)  /* array part must grow? */
     303           24266 :     setarrayvector(L, t, nasize);
     304                 :   /* create new hash part with appropriate size */
     305           33101 :   setnodevector(L, t, nhsize);  
     306           33101 :   if (nasize < oldasize) {  /* array part must shrink? */
     307               0 :     t->sizearray = nasize;
     308                 :     /* re-insert elements from vanishing slice */
     309               0 :     for (i=nasize; i<oldasize; i++) {
     310               0 :       if (!ttisnil(&t->array[i]))
     311               0 :         setobjt2t(L, luaH_setnum(L, t, i+1), &t->array[i]);
     312                 :     }
     313                 :     /* shrink array */
     314               0 :     luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
     315                 :   }
     316                 :   /* re-insert elements from hash part */
     317           95373 :   for (i = twoto(oldhsize) - 1; i >= 0; i--) {
     318           62272 :     Node *old = nold+i;
     319           62272 :     if (!ttisnil(gval(old)))
     320           36441 :       setobjt2t(L, luaH_set(L, t, key2tval(old)), gval(old));
     321                 :   }
     322           33101 :   if (nold != dummynode)
     323            7270 :     luaM_freearray(L, nold, twoto(oldhsize), Node);  /* free old array */
     324           33101 : }
     325                 : 
     326                 : 
     327             196 : void luaH_resizearray (lua_State *L, Table *t, int nasize) {
     328             196 :   int nsize = (t->node == dummynode) ? 0 : sizenode(t);
     329             196 :   resize(L, t, nasize, nsize);
     330             196 : }
     331                 : 
     332                 : 
     333           32905 : static void rehash (lua_State *L, Table *t, const TValue *ek) {
     334                 :   int nasize, na;
     335                 :   int nums[MAXBITS+1];  /* nums[i] = number of keys between 2^(i-1) and 2^i */
     336                 :   int i;
     337                 :   int totaluse;
     338           32905 :   for (i=0; i<=MAXBITS; i++) nums[i] = 0;  /* reset counts */
     339           32905 :   nasize = numusearray(t, nums);  /* count keys in array part */
     340           32905 :   totaluse = nasize;  /* all those keys are integer keys */
     341           32905 :   totaluse += numusehash(t, nums, &nasize);  /* count keys in hash part */
     342                 :   /* count extra key */
     343           32905 :   nasize += countint(ek, nums);
     344           32905 :   totaluse++;
     345                 :   /* compute new size for array part */
     346           32905 :   na = computesizes(nums, &nasize);
     347                 :   /* resize the table to new computed sizes */
     348           32905 :   resize(L, t, nasize, totaluse - na);
     349           32905 : }
     350                 : 
     351                 : 
     352                 : 
     353                 : /*
     354                 : ** }=============================================================
     355                 : */
     356                 : 
     357                 : 
     358            9074 : Table *luaH_new (lua_State *L, int narray, int nhash) {
     359            9074 :   Table *t = luaM_new(L, Table);
     360            9074 :   luaC_link(L, obj2gco(t), LUA_TTABLE);
     361            9074 :   t->metatable = NULL;
     362            9074 :   t->flags = cast_byte(~0);
     363                 :   /* temporary values (kept only if some malloc fails) */
     364            9074 :   t->array = NULL;
     365            9074 :   t->sizearray = 0;
     366            9074 :   t->lsizenode = 0;
     367            9074 :   t->node = cast(Node *, dummynode);
     368            9074 :   setarrayvector(L, t, narray);
     369            9074 :   setnodevector(L, t, nhash);
     370            9074 :   return t;
     371                 : }
     372                 : 
     373                 : 
     374            9074 : void luaH_free (lua_State *L, Table *t) {
     375            9074 :   if (t->node != dummynode)
     376            2731 :     luaM_freearray(L, t->node, sizenode(t), Node);
     377            9074 :   luaM_freearray(L, t->array, t->sizearray, TValue);
     378            9074 :   luaM_free(L, t);
     379            9074 : }
     380                 : 
     381                 : 
     382           56160 : static Node *getfreepos (Table *t) {
     383          142153 :   while (t->lastfree-- > t->node) {
     384           53088 :     if (ttisnil(gkey(t->lastfree)))
     385           23255 :       return t->lastfree;
     386                 :   }
     387           32905 :   return NULL;  /* could not find a free place */
     388                 : }
     389                 : 
     390                 : 
     391                 : 
     392                 : /*
     393                 : ** inserts a new key into a hash table; first, check whether key's main 
     394                 : ** position is free. If not, check whether colliding node is in its main 
     395                 : ** position or not: if it is not, move colliding node to an empty place and 
     396                 : ** put new key in its main position; otherwise (colliding node is in its main 
     397                 : ** position), new key goes to an empty position. 
     398                 : */
     399           99690 : static TValue *newkey (lua_State *L, Table *t, const TValue *key) {
     400           99690 :   Node *mp = mainposition(t, key);
     401           99690 :   if (!ttisnil(gval(mp)) || mp == dummynode) {
     402                 :     Node *othern;
     403           56160 :     Node *n = getfreepos(t);  /* get a free place */
     404           56160 :     if (n == NULL) {  /* cannot find a free place? */
     405           32905 :       rehash(L, t, key);  /* grow table */
     406           32905 :       return luaH_set(L, t, key);  /* re-insert key into grown table */
     407                 :     }
     408                 :     lua_assert(n != dummynode);
     409           23255 :     othern = mainposition(t, key2tval(mp));
     410           23255 :     if (othern != mp) {  /* is colliding node out of its main position? */
     411                 :       /* yes; move colliding node into free position */
     412            3428 :       while (gnext(othern) != mp) othern = gnext(othern);  /* find previous */
     413            3428 :       gnext(othern) = n;  /* redo the chain with `n' in place of `mp' */
     414            3428 :       *n = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
     415            3428 :       gnext(mp) = NULL;  /* now `mp' is free */
     416            3428 :       setnilvalue(gval(mp));
     417                 :     }
     418                 :     else {  /* colliding node is in its own main position */
     419                 :       /* new node will go into free position */
     420           19827 :       gnext(n) = gnext(mp);  /* chain new position */
     421           19827 :       gnext(mp) = n;
     422           19827 :       mp = n;
     423                 :     }
     424                 :   }
     425           66785 :   gkey(mp)->value = key->value; gkey(mp)->tt = key->tt;
     426           66785 :   luaC_barriert(L, t, key);
     427                 :   lua_assert(ttisnil(gval(mp)));
     428           66785 :   return gval(mp);
     429                 : }
     430                 : 
     431                 : 
     432                 : /*
     433                 : ** search function for integers
     434                 : */
     435          530933 : const TValue *luaH_getnum (Table *t, int key) {
     436                 :   /* (1 <= key && key <= t->sizearray) */
     437          530933 :   if (cast(unsigned int, key-1) < cast(unsigned int, t->sizearray))
     438          503930 :     return &t->array[key-1];
     439                 :   else {
     440           27003 :     lua_Number nk = cast_num(key);
     441           27003 :     Node *n = hashnum(t, nk);
     442                 :     do {  /* check whether `key' is somewhere in the chain */
     443           27592 :       if (ttisnumber(gkey(n)) && luai_numeq(nvalue(gkey(n)), nk))
     444             723 :         return gval(n);  /* that's it */
     445           26869 :       else n = gnext(n);
     446           26869 :     } while (n);
     447           26280 :     return luaO_nilobject;
     448                 :   }
     449                 : }
     450                 : 
     451                 : 
     452                 : /*
     453                 : ** search function for strings
     454                 : */
     455          211760 : const TValue *luaH_getstr (Table *t, TString *key) {
     456          211760 :   Node *n = hashstr(t, key);
     457                 :   do {  /* check whether `key' is somewhere in the chain */
     458          249400 :     if (ttisstring(gkey(n)) && rawtsvalue(gkey(n)) == key)
     459          135553 :       return gval(n);  /* that's it */
     460          113847 :     else n = gnext(n);
     461          113847 :   } while (n);
     462           76207 :   return luaO_nilobject;
     463                 : }
     464                 : 
     465                 : 
     466                 : /*
     467                 : ** main search function
     468                 : */
     469          318345 : const TValue *luaH_get (Table *t, const TValue *key) {
     470          318345 :   switch (ttype(key)) {
     471               2 :     case LUA_TNIL: return luaO_nilobject;
     472          167748 :     case LUA_TSTRING: return luaH_getstr(t, rawtsvalue(key));
     473                 :     case LUA_TNUMBER: {
     474                 :       int k;
     475          150413 :       lua_Number n = nvalue(key);
     476          150413 :       lua_number2int(k, n);
     477          150413 :       if (luai_numeq(cast_num(k), nvalue(key))) /* index is int? */
     478          150321 :         return luaH_getnum(t, k);  /* use specialized version */
     479                 :       /* else go through */
     480                 :     }
     481                 :     default: {
     482             274 :       Node *n = mainposition(t, key);
     483                 :       do {  /* check whether `key' is somewhere in the chain */
     484             319 :         if (luaO_rawequalObj(key2tval(n), key))
     485              33 :           return gval(n);  /* that's it */
     486             286 :         else n = gnext(n);
     487             286 :       } while (n);
     488             241 :       return luaO_nilobject;
     489                 :     }
     490                 :   }
     491                 : }
     492                 : 
     493                 : 
     494          174957 : TValue *luaH_set (lua_State *L, Table *t, const TValue *key) {
     495          174957 :   const TValue *p = luaH_get(t, key);
     496          174957 :   t->flags = 0;
     497          174957 :   if (p != luaO_nilobject)
     498           96190 :     return cast(TValue *, p);
     499                 :   else {
     500           78767 :     if (ttisnil(key)) luaG_runerror(L, "table index is nil");
     501           78767 :     else if (ttisnumber(key) && luai_numisnan(nvalue(key)))
     502               0 :       luaG_runerror(L, "table index is NaN");
     503           78767 :     return newkey(L, t, key);
     504                 :   }
     505                 : }
     506                 : 
     507                 : 
     508           87180 : TValue *luaH_setnum (lua_State *L, Table *t, int key) {
     509           87180 :   const TValue *p = luaH_getnum(t, key);
     510           87180 :   if (p != luaO_nilobject)
     511           86798 :     return cast(TValue *, p);
     512                 :   else {
     513                 :     TValue k;
     514             382 :     setnvalue(&k, cast_num(key));
     515             382 :     return newkey(L, t, &k);
     516                 :   }
     517                 : }
     518                 : 
     519                 : 
     520           36294 : TValue *luaH_setstr (lua_State *L, Table *t, TString *key) {
     521           36294 :   const TValue *p = luaH_getstr(t, key);
     522           36294 :   if (p != luaO_nilobject)
     523           15753 :     return cast(TValue *, p);
     524                 :   else {
     525                 :     TValue k;
     526           20541 :     setsvalue(L, &k, key);
     527           20541 :     return newkey(L, t, &k);
     528                 :   }
     529                 : }
     530                 : 
     531                 : 
     532               5 : static int unbound_search (Table *t, unsigned int j) {
     533               5 :   unsigned int i = j;  /* i is zero or a present index */
     534               5 :   j++;
     535                 :   /* find `i' and `j' such that i is present and j is not */
     536              10 :   while (!ttisnil(luaH_getnum(t, j))) {
     537               0 :     i = j;
     538               0 :     j *= 2;
     539               0 :     if (j > cast(unsigned int, MAX_INT)) {  /* overflow? */
     540                 :       /* table was built with bad purposes: resort to linear search */
     541               0 :       i = 1;
     542               0 :       while (!ttisnil(luaH_getnum(t, i))) i++;
     543               0 :       return i - 1;
     544                 :     }
     545                 :   }
     546                 :   /* now do a binary search between them */
     547              10 :   while (j - i > 1) {
     548               0 :     unsigned int m = (i+j)/2;
     549               0 :     if (ttisnil(luaH_getnum(t, m))) j = m;
     550               0 :     else i = m;
     551                 :   }
     552               5 :   return i;
     553                 : }
     554                 : 
     555                 : 
     556                 : /*
     557                 : ** Try to find a boundary in table `t'. A `boundary' is an integer index
     558                 : ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
     559                 : */
     560           18368 : int luaH_getn (Table *t) {
     561           18368 :   unsigned int j = t->sizearray;
     562           18368 :   if (j > 0 && ttisnil(&t->array[j - 1])) {
     563                 :     /* there is a boundary in the array part: (binary) search for it */
     564           17793 :     unsigned int i = 0;
     565           88776 :     while (j - i > 1) {
     566           53190 :       unsigned int m = (i+j)/2;
     567           53190 :       if (ttisnil(&t->array[m - 1])) j = m;
     568           50615 :       else i = m;
     569                 :     }
     570           17793 :     return i;
     571                 :   }
     572                 :   /* else must find a boundary in hash part */
     573             575 :   else if (t->node == dummynode)  /* hash part is empty? */
     574             570 :     return j;  /* that is easy... */
     575               5 :   else return unbound_search(t, j);
     576                 : }
     577                 : 
     578                 : 
     579                 : 
     580                 : #if defined(LUA_DEBUG)
     581                 : 
     582                 : Node *luaH_mainposition (const Table *t, const TValue *key) {
     583                 :   return mainposition(t, key);
     584                 : }
     585                 : 
     586                 : int luaH_isdummy (Node *n) { return n == dummynode; }
     587                 : 
     588                 : #endif

Generated by: LCOV version 1.7