Dict.h

#if 1
/*
* Functions for dealing with dictionaries.
*/
inline int tp_lua_hash(void const *v, int l) {
  int i, step = (l >> 5) + 1;
  int h = l + (l >= 4 ? *(int*)v : 0);
  for (i = l; i >= step; i -= step) {
    h = h ^ ((h << 5) + (h >> 2) + ((unsigned char *)v)[i - 1]);
  }
  return h;
}

inline void _tp_dict_free(tp_vm *tp, _tp_dict *self) {
  free(self->items);
  free(self);
}

inline int tp_hash(tp_vm *tp, tp_obj v) {
  switch (v.type) {
  case TP_NONE: return 0;
  case TP_NUMBER: return tp_lua_hash(&v.number.val, sizeof(double));
  case TP_STRING: return tp_lua_hash(v.string.val, v.string.len);
  case TP_DICT: return tp_lua_hash(&v.dict.val, sizeof(void*));
  case TP_LIST: {
    int r = v.list.val->len; int n; for (n = 0; n < v.list.val->len; n++) {
      tp_obj vv = v.list.val->items[n]; r += vv.type != TP_LIST ? tp_hash(tp, v.list.val->items[n]) : tp_lua_hash(&vv.list.val, sizeof(void*));
    } return r;
  }
  case TP_FNC: return tp_lua_hash(&v.fnc.info, sizeof(void*));
  case TP_DATA: return tp_lua_hash(&v.data.val, sizeof(void*));
  }
  tp_raise(0, tp_string("(tp_hash) TypeError: value unhashable"));
}

inline void _tp_dict_hash_set(tp_vm *tp, _tp_dict *self, int hash, tp_obj k, tp_obj v) {
  tp_item item;
  int i, idx = hash&self->mask;
  for (i = idx; i < idx + self->alloc; i++) {
    int n = i&self->mask;
    if (self->items[n].used > 0) { continue; }
    if (self->items[n].used == 0) { self->used += 1; }
    item.used = 1;
    item.hash = hash;
    item.key = k;
    item.val = v;
    self->items[n] = item;
    self->len += 1;
    return;
  }
  tp_raise(, tp_string("(_tp_dict_hash_set) RuntimeError: ?"));
}

inline void _tp_dict_tp_realloc(tp_vm *tp, _tp_dict *self, int len) {
  tp_item *items = self->items;
  int i, alloc = self->alloc;
  len = _tp_max(8, len);

  self->items = (tp_item*)calloc(len * sizeof(tp_item), 1);
  self->alloc = len; self->mask = len - 1;
  self->len = 0; self->used = 0;

  for (i = 0; i < alloc; i++) {
    if (items[i].used != 1) { continue; }
    _tp_dict_hash_set(tp, self, items[i].hash, items[i].key, items[i].val);
  }
  free(items);
}

inline int _tp_dict_hash_find(tp_vm *tp, _tp_dict *self, int hash, tp_obj k)
{
  int i, idx = hash&self->mask;
  for (i = idx; i < idx + self->alloc; i++) {
    int n = i&self->mask;
    if (self->items[n].used == 0) { break; }
    if (self->items[n].used < 0) { continue; }
    if (self->items[n].hash != hash) { continue; }
    if (tp_cmp(tp, self->items[n].key, k) != 0) { continue; }
    return n;
  }
  return -1;
}

inline int _tp_dict_find(tp_vm *tp, _tp_dict *self, tp_obj k) {
  return _tp_dict_hash_find(tp, self, tp_hash(tp, k), k);
}

inline void _tp_dict_setx(tp_vm *tp, _tp_dict *self, tp_obj k, tp_obj v) {
  int hash = tp_hash(tp, k); int n = _tp_dict_hash_find(tp, self, hash, k);
  if (n == -1) {
    if (self->len >= (self->alloc / 2)) {
      _tp_dict_tp_realloc(tp, self, self->alloc * 2);
    }
    else if (self->used >= (self->alloc * 3 / 4)) {
      _tp_dict_tp_realloc(tp, self, self->alloc);
    }
    _tp_dict_hash_set(tp, self, hash, k, v);
  }
  else {
    self->items[n].val = v;
  }
}

inline void _tp_dict_set(tp_vm *tp, _tp_dict *self, tp_obj k, tp_obj v) {
  _tp_dict_setx(tp, self, k, v);
  tp_grey(tp, k); tp_grey(tp, v);
}

inline tp_obj _tp_dict_get(tp_vm *tp, _tp_dict *self, tp_obj k, const char *error) {
  int n = _tp_dict_find(tp, self, k);
  if (n < 0) {
    tp_raise(tp_None, tp_add(tp, tp_string("(_tp_dict_get) KeyError: "), tp_str(tp, k)));
  }
  return self->items[n].val;
}

inline void _tp_dict_del(tp_vm *tp, _tp_dict *self, tp_obj k, const char *error) {
  int n = _tp_dict_find(tp, self, k);
  if (n < 0) {
    tp_raise(, tp_add(tp, tp_string("(_tp_dict_del) KeyError: "), tp_str(tp, k)));
  }
  self->items[n].used = -1;
  self->len -= 1;
}

inline _tp_dict *_tp_dict_new(tp_vm *tp) {
  _tp_dict *self = (_tp_dict*)calloc(sizeof(_tp_dict), 1);
  return self;
}

inline tp_obj _tp_dict_copy(tp_vm *tp, tp_obj rr) {
  tp_obj obj = { TP_DICT };
  _tp_dict *o = rr.dict.val;
  _tp_dict *r = _tp_dict_new(tp);
  *r = *o; r->gci = 0;
  r->items = (tp_item*)calloc(sizeof(tp_item)*o->alloc, 1);
  memcpy(r->items, o->items, sizeof(tp_item)*o->alloc);
  obj.dict.val = r;
  obj.dict.dtype = 1;
  return tp_track(tp, obj);
}

inline int _tp_dict_next(tp_vm *tp, _tp_dict *self)
{
  if (!self->len) {
    tp_raise(0, tp_string("(_tp_dict_next) RuntimeError"));
  }
  while (1) {
    self->cur = ((self->cur + 1) & self->mask);
    if (self->items[self->cur].used > 0) {
      return self->cur;
    }
  }
}

inline tp_obj tp_merge(tp_vm *tp)
{
  tp_obj self = TP_OBJ();
  tp_obj v = TP_OBJ();
  int i; for (i = 0; i < v.dict.val->len; i++) {
    int n = _tp_dict_next(tp, v.dict.val);
    _tp_dict_set(tp, self.dict.val,
      v.dict.val->items[n].key, v.dict.val->items[n].val);
  }
  return tp_None;
}

/* Function: tp_dict
*
* Creates a new dictionary object.
*
* *Note* If you use <tp_setmeta> on the dictionary, you have to use <tp_getraw> to
* access the "raw" dictionary again.
*
* Returns:
* The newly created dictionary.
*/
inline tp_obj tp_dict(tp_vm *tp) {
  tp_obj r = { TP_DICT };
  r.dict.val = _tp_dict_new(tp);
  r.dict.dtype = 1;
  return tp ? tp_track(tp, r) : r;
}

inline tp_obj tp_dict_n(tp_vm *tp, int n, tp_obj* argv) {
  tp_obj r = tp_dict(tp);
  int i; for (i = 0; i < n; i++) { tp_set(tp, r, argv[i * 2], argv[i * 2 + 1]); }
  return r;
}

#endif