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