misc/liblua/ltable.c
author nemo
Fri, 26 Nov 2010 10:21:53 -0500
changeset 4421 58c6918acde4
parent 3697 d5b30d6373fc
child 10017 de822cd3df3a
permissions -rw-r--r--
corrected steps
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