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