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