Lua 5.1.4: ltablib.c

L0001    /*
L0002    ** $Id: ltablib.c,v 1.38.1.3 2008/02/14 16:46:58 roberto Exp $
L0003    ** Library for Table Manipulation
L0004    ** See Copyright Notice in lua.h
L0005    */
L0006    
L0007    
L0008    #include <stddef.h>
L0009    
L0010    #define ltablib_c
L0011    #define LUA_LIB
L0012    
L0013    #include "lua.h"
L0014    
L0015    #include "lauxlib.h"
L0016    #include "lualib.h"
L0017    
L0018    
L0019    #define aux_getn(L,n)	(luaL_checktype(L, n, LUA_TTABLE), luaL_getn(L, n))
L0020    
L0021    
L0022    static int foreachi (lua_State *L) {
manl:table.foreachi
L0023      int i;
L0024      int n = aux_getn(L, 1);
L0025      luaL_checktype(L, 2, LUA_TFUNCTION);
L0026      for (i=1; i <= n; i++) {
L0027        lua_pushvalue(L, 2);  /* function */
L0028        lua_pushinteger(L, i);  /* 1st argument */
L0029        lua_rawgeti(L, 1, i);  /* 2nd argument */
L0030        lua_call(L, 2, 1);
L0031        if (!lua_isnil(L, -1))
L0032          return 1;
L0033        lua_pop(L, 1);  /* remove nil result */
L0034      }
L0035      return 0;
L0036    }
L0037    
L0038    
L0039    static int foreach (lua_State *L) {
manl:table.foreach
L0040      luaL_checktype(L, 1, LUA_TTABLE);
L0041      luaL_checktype(L, 2, LUA_TFUNCTION);
L0042      lua_pushnil(L);  /* first key */
L0043      while (lua_next(L, 1)) {
L0044        lua_pushvalue(L, 2);  /* function */
L0045        lua_pushvalue(L, -3);  /* key */
L0046        lua_pushvalue(L, -3);  /* value */
L0047        lua_call(L, 2, 1);
L0048        if (!lua_isnil(L, -1))
L0049          return 1;
L0050        lua_pop(L, 2);  /* remove value and result */
L0051      }
L0052      return 0;
L0053    }
L0054    
L0055    
L0056    static int maxn (lua_State *L) {
manl:table.maxn
L0057      lua_Number max = 0;
L0058      luaL_checktype(L, 1, LUA_TTABLE);
L0059      lua_pushnil(L);  /* first key */
L0060      while (lua_next(L, 1)) {
L0061        lua_pop(L, 1);  /* remove value */
L0062        if (lua_type(L, -1) == LUA_TNUMBER) {
L0063          lua_Number v = lua_tonumber(L, -1);
L0064          if (v > max) max = v;
L0065        }
L0066      }
L0067      lua_pushnumber(L, max);
L0068      return 1;
L0069    }
L0070    
L0071    
L0072    static int getn (lua_State *L) {
manl:table.getn
L0073      lua_pushinteger(L, aux_getn(L, 1));
L0074      return 1;
L0075    }
L0076    
L0077    
L0078    static int setn (lua_State *L) {
manl:table.setn
L0079      luaL_checktype(L, 1, LUA_TTABLE);
L0080    #ifndef luaL_setn
L0081      luaL_setn(L, 1, luaL_checkint(L, 2));
L0082    #else
L0083      luaL_error(L, LUA_QL("setn") " is obsolete");
L0084    #endif
L0085      lua_pushvalue(L, 1);
L0086      return 1;
L0087    }
L0088    
L0089    
L0090    static int tinsert (lua_State *L) {
manl:table.insert
L0091      int e = aux_getn(L, 1) + 1;  /* first empty element */
L0092      int pos;  /* where to insert new element */
L0093      switch (lua_gettop(L)) {
L0094        case 2: {  /* called with only 2 arguments */
L0095          pos = e;  /* insert new element at the end */
L0096          break;
L0097        }
L0098        case 3: {
L0099          int i;
L0100          pos = luaL_checkint(L, 2);  /* 2nd argument is the position */
L0101          if (pos > e) e = pos;  /* `grow' array if necessary */
L0102          for (i = e; i > pos; i--) {  /* move up elements */
L0103            lua_rawgeti(L, 1, i-1);
L0104            lua_rawseti(L, 1, i);  /* t[i] = t[i-1] */
L0105          }
L0106          break;
L0107        }
L0108        default: {
L0109          return luaL_error(L, "wrong number of arguments to " LUA_QL("insert"));
L0110        }
L0111      }
L0112      luaL_setn(L, 1, e);  /* new size */
L0113      lua_rawseti(L, 1, pos);  /* t[pos] = v */
L0114      return 0;
L0115    }
L0116    
L0117    
L0118    static int tremove (lua_State *L) {
manl:table.remove
L0119      int e = aux_getn(L, 1);
L0120      int pos = luaL_optint(L, 2, e);
L0121      if (!(1 <= pos && pos <= e))  /* position is outside bounds? */
L0122       return 0;  /* nothing to remove */
L0123      luaL_setn(L, 1, e - 1);  /* t.n = n-1 */
L0124      lua_rawgeti(L, 1, pos);  /* result = t[pos] */
L0125      for ( ;pos<e; pos++) {
L0126        lua_rawgeti(L, 1, pos+1);
L0127        lua_rawseti(L, 1, pos);  /* t[pos] = t[pos+1] */
L0128      }
L0129      lua_pushnil(L);
L0130      lua_rawseti(L, 1, e);  /* t[e] = nil */
L0131      return 1;
L0132    }
L0133    
L0134    
L0135    static void addfield (lua_State *L, luaL_Buffer *b, int i) {
L0136      lua_rawgeti(L, 1, i);
L0137      if (!lua_isstring(L, -1))
L0138        luaL_error(L, "invalid value (%s) at index %d in table for "
L0139                      LUA_QL("concat"), luaL_typename(L, -1), i);
L0140        luaL_addvalue(b);
L0141    }
L0142    
L0143    
L0144    static int tconcat (lua_State *L) {
manl:table.concat
L0145      luaL_Buffer b;
L0146      size_t lsep;
L0147      int i, last;
L0148      const char *sep = luaL_optlstring(L, 2, "", &lsep);
L0149      luaL_checktype(L, 1, LUA_TTABLE);
L0150      i = luaL_optint(L, 3, 1);
L0151      last = luaL_opt(L, luaL_checkint, 4, luaL_getn(L, 1));
L0152      luaL_buffinit(L, &b);
L0153      for (; i < last; i++) {
L0154        addfield(L, &b, i);
L0155        luaL_addlstring(&b, sep, lsep);
L0156      }
L0157      if (i == last)  /* add last value (if interval was not empty) */
L0158        addfield(L, &b, i);
L0159      luaL_pushresult(&b);
L0160      return 1;
L0161    }
L0162    
L0163    
L0164    
L0165    /*
L0166    ** {======================================================
L0167    ** Quicksort
L0168    ** (based on `Algorithms in MODULA-3', Robert Sedgewick;
L0169    **  Addison-Wesley, 1993.)
L0170    */
L0171    
L0172    
L0173    static void set2 (lua_State *L, int i, int j) {
L0174      lua_rawseti(L, 1, i);
L0175      lua_rawseti(L, 1, j);
L0176    }
L0177    
L0178    static int sort_comp (lua_State *L, int a, int b) {
L0179      if (!lua_isnil(L, 2)) {  /* function? */
L0180        int res;
L0181        lua_pushvalue(L, 2);
L0182        lua_pushvalue(L, a-1);  /* -1 to compensate function */
L0183        lua_pushvalue(L, b-2);  /* -2 to compensate function and `a' */
L0184        lua_call(L, 2, 1);
L0185        res = lua_toboolean(L, -1);
L0186        lua_pop(L, 1);
L0187        return res;
L0188      }
L0189      else  /* a < b? */
L0190        return lua_lessthan(L, a, b);
L0191    }
L0192    
L0193    static void auxsort (lua_State *L, int l, int u) {
L0194      while (l < u) {  /* for tail recursion */
L0195        int i, j;
L0196        /* sort elements a[l], a[(l+u)/2] and a[u] */
L0197        lua_rawgeti(L, 1, l);
L0198        lua_rawgeti(L, 1, u);
L0199        if (sort_comp(L, -1, -2))  /* a[u] < a[l]? */
L0200          set2(L, l, u);  /* swap a[l] - a[u] */
L0201        else
L0202          lua_pop(L, 2);
L0203        if (u-l == 1) break;  /* only 2 elements */
L0204        i = (l+u)/2;
L0205        lua_rawgeti(L, 1, i);
L0206        lua_rawgeti(L, 1, l);
L0207        if (sort_comp(L, -2, -1))  /* a[i]<a[l]? */
L0208          set2(L, i, l);
L0209        else {
L0210          lua_pop(L, 1);  /* remove a[l] */
L0211          lua_rawgeti(L, 1, u);
L0212          if (sort_comp(L, -1, -2))  /* a[u]<a[i]? */
L0213            set2(L, i, u);
L0214          else
L0215            lua_pop(L, 2);
L0216        }
L0217        if (u-l == 2) break;  /* only 3 elements */
L0218        lua_rawgeti(L, 1, i);  /* Pivot */
L0219        lua_pushvalue(L, -1);
L0220        lua_rawgeti(L, 1, u-1);
L0221        set2(L, i, u-1);
L0222        /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
L0223        i = l; j = u-1;
L0224        for (;;) {  /* invariant: a[l..i] <= P <= a[j..u] */
L0225          /* repeat ++i until a[i] >= P */
L0226          while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {
L0227            if (i>u) luaL_error(L, "invalid order function for sorting");
L0228            lua_pop(L, 1);  /* remove a[i] */
L0229          }
L0230          /* repeat --j until a[j] <= P */
L0231          while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {
L0232            if (j<l) luaL_error(L, "invalid order function for sorting");
L0233            lua_pop(L, 1);  /* remove a[j] */
L0234          }
L0235          if (j<i) {
L0236            lua_pop(L, 3);  /* pop pivot, a[i], a[j] */
L0237            break;
L0238          }
L0239          set2(L, i, j);
L0240        }
L0241        lua_rawgeti(L, 1, u-1);
L0242        lua_rawgeti(L, 1, i);
L0243        set2(L, u-1, i);  /* swap pivot (a[u-1]) with a[i] */
L0244        /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
L0245        /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
L0246        if (i-l < u-i) {
L0247          j=l; i=i-1; l=i+2;
L0248        }
L0249        else {
L0250          j=i+1; i=u; u=j-2;
L0251        }
L0252        auxsort(L, j, i);  /* call recursively the smaller one */
L0253      }  /* repeat the routine for the larger one */
L0254    }
L0255    
L0256    static int sort (lua_State *L) {
manl:table.sort
L0257      int n = aux_getn(L, 1);
L0258      luaL_checkstack(L, 40, "");  /* assume array is smaller than 2^40 */
L0259      if (!lua_isnoneornil(L, 2))  /* is there a 2nd argument? */
L0260        luaL_checktype(L, 2, LUA_TFUNCTION);
L0261      lua_settop(L, 2);  /* make sure there is two arguments */
L0262      auxsort(L, 1, n);
L0263      return 0;
L0264    }
L0265    
L0266    /* }====================================================== */
L0267    
L0268    
L0269    static const luaL_Reg tab_funcs[] = {
L0270      {"concat", tconcat},
L0271      {"foreach", foreach},
L0272      {"foreachi", foreachi},
L0273      {"getn", getn},
L0274      {"maxn", maxn},
L0275      {"insert", tinsert},
L0276      {"remove", tremove},
L0277      {"setn", setn},
L0278      {"sort", sort},
L0279      {NULL, NULL}
L0280    };
L0281    
L0282    
L0283    LUALIB_API int luaopen_table (lua_State *L) {
L0284      luaL_register(L, LUA_TABLIBNAME, tab_funcs);
L0285      return 1;
L0286    }
L0287