Changeset View
Changeset View
Standalone View
Standalone View
contrib/lua/src/ltable.c
| /* | /* | ||||
| ** $Id: ltable.c,v 2.118 2016/11/07 12:38:35 roberto Exp $ | ** $Id: ltable.c,v 2.118.1.4 2018/06/08 16:22:51 roberto Exp $ | ||||
| ** Lua tables (hash) | ** Lua tables (hash) | ||||
| ** See Copyright Notice in lua.h | ** See Copyright Notice in lua.h | ||||
| */ | */ | ||||
| #define ltable_c | #define ltable_c | ||||
| #define LUA_CORE | #define LUA_CORE | ||||
| #include "lprefix.h" | #include "lprefix.h" | ||||
| ▲ Show 20 Lines • Show All 207 Lines • ▼ Show 20 Lines | |||||
| */ | */ | ||||
| static unsigned int computesizes (unsigned int nums[], unsigned int *pna) { | static unsigned int computesizes (unsigned int nums[], unsigned int *pna) { | ||||
| int i; | int i; | ||||
| unsigned int twotoi; /* 2^i (candidate for optimal size) */ | unsigned int twotoi; /* 2^i (candidate for optimal size) */ | ||||
| unsigned int a = 0; /* number of elements smaller than 2^i */ | unsigned int a = 0; /* number of elements smaller than 2^i */ | ||||
| unsigned int na = 0; /* number of elements to go to array part */ | unsigned int na = 0; /* number of elements to go to array part */ | ||||
| unsigned int optimal = 0; /* optimal size for array part */ | unsigned int optimal = 0; /* optimal size for array part */ | ||||
| /* loop while keys can fill more than half of total size */ | /* loop while keys can fill more than half of total size */ | ||||
| for (i = 0, twotoi = 1; *pna > twotoi / 2; i++, twotoi *= 2) { | for (i = 0, twotoi = 1; | ||||
| twotoi > 0 && *pna > twotoi / 2; | |||||
| i++, twotoi *= 2) { | |||||
| if (nums[i] > 0) { | if (nums[i] > 0) { | ||||
| a += nums[i]; | a += nums[i]; | ||||
| if (a > twotoi/2) { /* more than half elements present? */ | if (a > twotoi/2) { /* more than half elements present? */ | ||||
| optimal = twotoi; /* optimal size (till now) */ | optimal = twotoi; /* optimal size (till now) */ | ||||
| na = a; /* all elements up to 'optimal' will go to array part */ | na = a; /* all elements up to 'optimal' will go to array part */ | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| ▲ Show 20 Lines • Show All 90 Lines • ▼ Show 20 Lines | for (i = 0; i < (int)size; i++) { | ||||
| setnilvalue(gval(n)); | setnilvalue(gval(n)); | ||||
| } | } | ||||
| t->lsizenode = cast_byte(lsize); | t->lsizenode = cast_byte(lsize); | ||||
| t->lastfree = gnode(t, size); /* all positions are free */ | t->lastfree = gnode(t, size); /* all positions are free */ | ||||
| } | } | ||||
| } | } | ||||
| typedef struct { | |||||
| Table *t; | |||||
| unsigned int nhsize; | |||||
| } AuxsetnodeT; | |||||
| static void auxsetnode (lua_State *L, void *ud) { | |||||
| AuxsetnodeT *asn = cast(AuxsetnodeT *, ud); | |||||
| setnodevector(L, asn->t, asn->nhsize); | |||||
| } | |||||
| void luaH_resize (lua_State *L, Table *t, unsigned int nasize, | void luaH_resize (lua_State *L, Table *t, unsigned int nasize, | ||||
| unsigned int nhsize) { | unsigned int nhsize) { | ||||
| unsigned int i; | unsigned int i; | ||||
| int j; | int j; | ||||
| AuxsetnodeT asn; | |||||
| unsigned int oldasize = t->sizearray; | unsigned int oldasize = t->sizearray; | ||||
| int oldhsize = allocsizenode(t); | int oldhsize = allocsizenode(t); | ||||
| Node *nold = t->node; /* save old hash ... */ | Node *nold = t->node; /* save old hash ... */ | ||||
| if (nasize > oldasize) /* array part must grow? */ | if (nasize > oldasize) /* array part must grow? */ | ||||
| setarrayvector(L, t, nasize); | setarrayvector(L, t, nasize); | ||||
| /* create new hash part with appropriate size */ | /* create new hash part with appropriate size */ | ||||
| setnodevector(L, t, nhsize); | asn.t = t; asn.nhsize = nhsize; | ||||
| if (luaD_rawrunprotected(L, auxsetnode, &asn) != LUA_OK) { /* mem. error? */ | |||||
| setarrayvector(L, t, oldasize); /* array back to its original size */ | |||||
| luaD_throw(L, LUA_ERRMEM); /* rethrow memory error */ | |||||
| } | |||||
| if (nasize < oldasize) { /* array part must shrink? */ | if (nasize < oldasize) { /* array part must shrink? */ | ||||
| t->sizearray = nasize; | t->sizearray = nasize; | ||||
| /* re-insert elements from vanishing slice */ | /* re-insert elements from vanishing slice */ | ||||
| for (i=nasize; i<oldasize; i++) { | for (i=nasize; i<oldasize; i++) { | ||||
| if (!ttisnil(&t->array[i])) | if (!ttisnil(&t->array[i])) | ||||
| luaH_setint(L, t, i + 1, &t->array[i]); | luaH_setint(L, t, i + 1, &t->array[i]); | ||||
| } | } | ||||
| /* shrink array */ | /* shrink array */ | ||||
| ▲ Show 20 Lines • Show All 253 Lines • ▼ Show 20 Lines | else { | ||||
| TValue k; | TValue k; | ||||
| setivalue(&k, key); | setivalue(&k, key); | ||||
| cell = luaH_newkey(L, t, &k); | cell = luaH_newkey(L, t, &k); | ||||
| } | } | ||||
| setobj2t(L, cell, value); | setobj2t(L, cell, value); | ||||
| } | } | ||||
| static int unbound_search (Table *t, unsigned int j) { | static lua_Unsigned unbound_search (Table *t, lua_Unsigned j) { | ||||
| unsigned int i = j; /* i is zero or a present index */ | lua_Unsigned i = j; /* i is zero or a present index */ | ||||
| j++; | j++; | ||||
| /* find 'i' and 'j' such that i is present and j is not */ | /* find 'i' and 'j' such that i is present and j is not */ | ||||
| while (!ttisnil(luaH_getint(t, j))) { | while (!ttisnil(luaH_getint(t, j))) { | ||||
| i = j; | i = j; | ||||
| if (j > cast(unsigned int, MAX_INT)/2) { /* overflow? */ | if (j > l_castS2U(LUA_MAXINTEGER) / 2) { /* overflow? */ | ||||
| /* table was built with bad purposes: resort to linear search */ | /* table was built with bad purposes: resort to linear search */ | ||||
| i = 1; | i = 1; | ||||
| while (!ttisnil(luaH_getint(t, i))) i++; | while (!ttisnil(luaH_getint(t, i))) i++; | ||||
| return i - 1; | return i - 1; | ||||
| } | } | ||||
| j *= 2; | j *= 2; | ||||
| } | } | ||||
| /* now do a binary search between them */ | /* now do a binary search between them */ | ||||
| while (j - i > 1) { | while (j - i > 1) { | ||||
| unsigned int m = (i+j)/2; | lua_Unsigned m = (i+j)/2; | ||||
| if (ttisnil(luaH_getint(t, m))) j = m; | if (ttisnil(luaH_getint(t, m))) j = m; | ||||
| else i = m; | else i = m; | ||||
| } | } | ||||
| return i; | return i; | ||||
| } | } | ||||
| /* | /* | ||||
| ** Try to find a boundary in table 't'. A 'boundary' is an integer index | ** Try to find a boundary in table 't'. A 'boundary' is an integer index | ||||
| ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil). | ** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil). | ||||
| */ | */ | ||||
| int luaH_getn (Table *t) { | lua_Unsigned luaH_getn (Table *t) { | ||||
| unsigned int j = t->sizearray; | unsigned int j = t->sizearray; | ||||
| if (j > 0 && ttisnil(&t->array[j - 1])) { | if (j > 0 && ttisnil(&t->array[j - 1])) { | ||||
| /* there is a boundary in the array part: (binary) search for it */ | /* there is a boundary in the array part: (binary) search for it */ | ||||
| unsigned int i = 0; | unsigned int i = 0; | ||||
| while (j - i > 1) { | while (j - i > 1) { | ||||
| unsigned int m = (i+j)/2; | unsigned int m = (i+j)/2; | ||||
| if (ttisnil(&t->array[m - 1])) j = m; | if (ttisnil(&t->array[m - 1])) j = m; | ||||
| else i = m; | else i = m; | ||||
| Show All 20 Lines | |||||