← Back to branch summary

~ubuntu-branches/debian/sid/grub2/sid-200907171837

« back to all changes in this revision

Viewing changes to script/lua/ltablib.c

  • Committer: Bazaar Package Importer
  • Author(s): Robert Millan
  • Date: 2009-07-02 13:23:51 UTC
  • mfrom: (1.1.10 upstream)
  • Revision ID: james.westby@ubuntu.com-20090702132351-tanpn0ryyijp93gu
Tags: 1.96+20090702-1
http://bugs.debian.org/535026
* New SVN snapshot.
* rules: Remove duplicated files in sparc64-ieee1275 port.
* rules: Comment out -DGRUB_ASSUME_LINUX_HAS_FB_SUPPORT=1 setting.  We'll
  re-evaluate using it when it's more mature.  (Closes: #535026).

Show diffs side-by-side

added added

removed removed

Lines of Context:
script/lua/ltablib.c
 
1
/*
 
2
** $Id: ltablib.c,v 1.38.1.3 2008/02/14 16:46:58 roberto Exp $
 
3
** Library for Table Manipulation
 
4
** See Copyright Notice in lua.h
 
5
*/
 
6
 
 
7
#if 0
 
8
#include <stddef.h>
 
9
#endif
 
10
 
 
11
#define ltablib_c
 
12
#define LUA_LIB
 
13
 
 
14
#include "lua.h"
 
15
 
 
16
#include "lauxlib.h"
 
17
#include "lualib.h"
 
18
 
 
19
 
 
20
#define aux_getn(L,n)   (luaL_checktype(L, n, LUA_TTABLE), luaL_getn(L, n))
 
21
 
 
22
 
 
23
static int foreachi (lua_State *L) {
 
24
  int i;
 
25
  int n = aux_getn(L, 1);
 
26
  luaL_checktype(L, 2, LUA_TFUNCTION);
 
27
  for (i=1; i <= n; i++) {
 
28
    lua_pushvalue(L, 2);  /* function */
 
29
    lua_pushinteger(L, i);  /* 1st argument */
 
30
    lua_rawgeti(L, 1, i);  /* 2nd argument */
 
31
    lua_call(L, 2, 1);
 
32
    if (!lua_isnil(L, -1))
 
33
      return 1;
 
34
    lua_pop(L, 1);  /* remove nil result */
 
35
  }
 
36
  return 0;
 
37
}
 
38
 
 
39
 
 
40
static int foreach (lua_State *L) {
 
41
  luaL_checktype(L, 1, LUA_TTABLE);
 
42
  luaL_checktype(L, 2, LUA_TFUNCTION);
 
43
  lua_pushnil(L);  /* first key */
 
44
  while (lua_next(L, 1)) {
 
45
    lua_pushvalue(L, 2);  /* function */
 
46
    lua_pushvalue(L, -3);  /* key */
 
47
    lua_pushvalue(L, -3);  /* value */
 
48
    lua_call(L, 2, 1);
 
49
    if (!lua_isnil(L, -1))
 
50
      return 1;
 
51
    lua_pop(L, 2);  /* remove value and result */
 
52
  }
 
53
  return 0;
 
54
}
 
55
 
 
56
 
 
57
static int maxn (lua_State *L) {
 
58
  lua_Number max = 0;
 
59
  luaL_checktype(L, 1, LUA_TTABLE);
 
60
  lua_pushnil(L);  /* first key */
 
61
  while (lua_next(L, 1)) {
 
62
    lua_pop(L, 1);  /* remove value */
 
63
    if (lua_type(L, -1) == LUA_TNUMBER) {
 
64
      lua_Number v = lua_tonumber(L, -1);
 
65
      if (v > max) max = v;
 
66
    }
 
67
  }
 
68
  lua_pushnumber(L, max);
 
69
  return 1;
 
70
}
 
71
 
 
72
 
 
73
static int getn (lua_State *L) {
 
74
  lua_pushinteger(L, aux_getn(L, 1));
 
75
  return 1;
 
76
}
 
77
 
 
78
 
 
79
static int setn (lua_State *L) {
 
80
  luaL_checktype(L, 1, LUA_TTABLE);
 
81
#ifndef luaL_setn
 
82
  luaL_setn(L, 1, luaL_checkint(L, 2));
 
83
#else
 
84
  luaL_error(L, LUA_QL("setn") " is obsolete");
 
85
#endif
 
86
  lua_pushvalue(L, 1);
 
87
  return 1;
 
88
}
 
89
 
 
90
 
 
91
static int tinsert (lua_State *L) {
 
92
  int e = aux_getn(L, 1) + 1;  /* first empty element */
 
93
  int pos;  /* where to insert new element */
 
94
  switch (lua_gettop(L)) {
 
95
    case 2: {  /* called with only 2 arguments */
 
96
      pos = e;  /* insert new element at the end */
 
97
      break;
 
98
    }
 
99
    case 3: {
 
100
      int i;
 
101
      pos = luaL_checkint(L, 2);  /* 2nd argument is the position */
 
102
      if (pos > e) e = pos;  /* `grow' array if necessary */
 
103
      for (i = e; i > pos; i--) {  /* move up elements */
 
104
        lua_rawgeti(L, 1, i-1);
 
105
        lua_rawseti(L, 1, i);  /* t[i] = t[i-1] */
 
106
      }
 
107
      break;
 
108
    }
 
109
    default: {
 
110
      return luaL_error(L, "wrong number of arguments to " LUA_QL("insert"));
 
111
    }
 
112
  }
 
113
  luaL_setn(L, 1, e);  /* new size */
 
114
  lua_rawseti(L, 1, pos);  /* t[pos] = v */
 
115
  return 0;
 
116
}
 
117
 
 
118
 
 
119
static int tremove (lua_State *L) {
 
120
  int e = aux_getn(L, 1);
 
121
  int pos = luaL_optint(L, 2, e);
 
122
  if (!(1 <= pos && pos <= e))  /* position is outside bounds? */
 
123
   return 0;  /* nothing to remove */
 
124
  luaL_setn(L, 1, e - 1);  /* t.n = n-1 */
 
125
  lua_rawgeti(L, 1, pos);  /* result = t[pos] */
 
126
  for ( ;pos<e; pos++) {
 
127
    lua_rawgeti(L, 1, pos+1);
 
128
    lua_rawseti(L, 1, pos);  /* t[pos] = t[pos+1] */
 
129
  }
 
130
  lua_pushnil(L);
 
131
  lua_rawseti(L, 1, e);  /* t[e] = nil */
 
132
  return 1;
 
133
}
 
134
 
 
135
 
 
136
static void addfield (lua_State *L, luaL_Buffer *b, int i) {
 
137
  lua_rawgeti(L, 1, i);
 
138
  if (!lua_isstring(L, -1))
 
139
    luaL_error(L, "invalid value (%s) at index %d in table for "
 
140
                  LUA_QL("concat"), luaL_typename(L, -1), i);
 
141
    luaL_addvalue(b);
 
142
}
 
143
 
 
144
 
 
145
static int tconcat (lua_State *L) {
 
146
  luaL_Buffer b;
 
147
  size_t lsep;
 
148
  int i, last;
 
149
  const char *sep = luaL_optlstring(L, 2, "", &lsep);
 
150
  luaL_checktype(L, 1, LUA_TTABLE);
 
151
  i = luaL_optint(L, 3, 1);
 
152
  last = luaL_opt(L, luaL_checkint, 4, luaL_getn(L, 1));
 
153
  luaL_buffinit(L, &b);
 
154
  for (; i < last; i++) {
 
155
    addfield(L, &b, i);
 
156
    luaL_addlstring(&b, sep, lsep);
 
157
  }
 
158
  if (i == last)  /* add last value (if interval was not empty) */
 
159
    addfield(L, &b, i);
 
160
  luaL_pushresult(&b);
 
161
  return 1;
 
162
}
 
163
 
 
164
 
 
165
 
 
166
/*
 
167
** {======================================================
 
168
** Quicksort
 
169
** (based on `Algorithms in MODULA-3', Robert Sedgewick;
 
170
**  Addison-Wesley, 1993.)
 
171
*/
 
172
 
 
173
 
 
174
static void set2 (lua_State *L, int i, int j) {
 
175
  lua_rawseti(L, 1, i);
 
176
  lua_rawseti(L, 1, j);
 
177
}
 
178
 
 
179
static int sort_comp (lua_State *L, int a, int b) {
 
180
  if (!lua_isnil(L, 2)) {  /* function? */
 
181
    int res;
 
182
    lua_pushvalue(L, 2);
 
183
    lua_pushvalue(L, a-1);  /* -1 to compensate function */
 
184
    lua_pushvalue(L, b-2);  /* -2 to compensate function and `a' */
 
185
    lua_call(L, 2, 1);
 
186
    res = lua_toboolean(L, -1);
 
187
    lua_pop(L, 1);
 
188
    return res;
 
189
  }
 
190
  else  /* a < b? */
 
191
    return lua_lessthan(L, a, b);
 
192
}
 
193
 
 
194
static void auxsort (lua_State *L, int l, int u) {
 
195
  while (l < u) {  /* for tail recursion */
 
196
    int i, j;
 
197
    /* sort elements a[l], a[(l+u)/2] and a[u] */
 
198
    lua_rawgeti(L, 1, l);
 
199
    lua_rawgeti(L, 1, u);
 
200
    if (sort_comp(L, -1, -2))  /* a[u] < a[l]? */
 
201
      set2(L, l, u);  /* swap a[l] - a[u] */
 
202
    else
 
203
      lua_pop(L, 2);
 
204
    if (u-l == 1) break;  /* only 2 elements */
 
205
    i = (l+u)/2;
 
206
    lua_rawgeti(L, 1, i);
 
207
    lua_rawgeti(L, 1, l);
 
208
    if (sort_comp(L, -2, -1))  /* a[i]<a[l]? */
 
209
      set2(L, i, l);
 
210
    else {
 
211
      lua_pop(L, 1);  /* remove a[l] */
 
212
      lua_rawgeti(L, 1, u);
 
213
      if (sort_comp(L, -1, -2))  /* a[u]<a[i]? */
 
214
        set2(L, i, u);
 
215
      else
 
216
        lua_pop(L, 2);
 
217
    }
 
218
    if (u-l == 2) break;  /* only 3 elements */
 
219
    lua_rawgeti(L, 1, i);  /* Pivot */
 
220
    lua_pushvalue(L, -1);
 
221
    lua_rawgeti(L, 1, u-1);
 
222
    set2(L, i, u-1);
 
223
    /* a[l] <= P == a[u-1] <= a[u], only need to sort from l+1 to u-2 */
 
224
    i = l; j = u-1;
 
225
    for (;;) {  /* invariant: a[l..i] <= P <= a[j..u] */
 
226
      /* repeat ++i until a[i] >= P */
 
227
      while (lua_rawgeti(L, 1, ++i), sort_comp(L, -1, -2)) {
 
228
        if (i>u) luaL_error(L, "invalid order function for sorting");
 
229
        lua_pop(L, 1);  /* remove a[i] */
 
230
      }
 
231
      /* repeat --j until a[j] <= P */
 
232
      while (lua_rawgeti(L, 1, --j), sort_comp(L, -3, -1)) {
 
233
        if (j<l) luaL_error(L, "invalid order function for sorting");
 
234
        lua_pop(L, 1);  /* remove a[j] */
 
235
      }
 
236
      if (j<i) {
 
237
        lua_pop(L, 3);  /* pop pivot, a[i], a[j] */
 
238
        break;
 
239
      }
 
240
      set2(L, i, j);
 
241
    }
 
242
    lua_rawgeti(L, 1, u-1);
 
243
    lua_rawgeti(L, 1, i);
 
244
    set2(L, u-1, i);  /* swap pivot (a[u-1]) with a[i] */
 
245
    /* a[l..i-1] <= a[i] == P <= a[i+1..u] */
 
246
    /* adjust so that smaller half is in [j..i] and larger one in [l..u] */
 
247
    if (i-l < u-i) {
 
248
      j=l; i=i-1; l=i+2;
 
249
    }
 
250
    else {
 
251
      j=i+1; i=u; u=j-2;
 
252
    }
 
253
    auxsort(L, j, i);  /* call recursively the smaller one */
 
254
  }  /* repeat the routine for the larger one */
 
255
}
 
256
 
 
257
static int sort (lua_State *L) {
 
258
  int n = aux_getn(L, 1);
 
259
  luaL_checkstack(L, 40, "");  /* assume array is smaller than 2^40 */
 
260
  if (!lua_isnoneornil(L, 2))  /* is there a 2nd argument? */
 
261
    luaL_checktype(L, 2, LUA_TFUNCTION);
 
262
  lua_settop(L, 2);  /* make sure there is two arguments */
 
263
  auxsort(L, 1, n);
 
264
  return 0;
 
265
}
 
266
 
 
267
/* }====================================================== */
 
268
 
 
269
 
 
270
static const luaL_Reg tab_funcs[] = {
 
271
  {"concat", tconcat},
 
272
  {"foreach", foreach},
 
273
  {"foreachi", foreachi},
 
274
  {"getn", getn},
 
275
  {"maxn", maxn},
 
276
  {"insert", tinsert},
 
277
  {"remove", tremove},
 
278
  {"setn", setn},
 
279
  {"sort", sort},
 
280
  {NULL, NULL}
 
281
};
 
282
 
 
283
 
 
284
LUALIB_API int luaopen_table (lua_State *L) {
 
285
  luaL_register(L, LUA_TABLIBNAME, tab_funcs);
 
286
  return 1;
 
287
}
 
288