#include <stddef.h>
#include "chibicc.h"

static unsigned long hash_type(Type *type) {
  unsigned long hash = 6997;
  if (!type) return hash;
  if (type->hashing) return hash;
  type->hashing = 1;
#define EXTEND_HASH(v) hash = (hash * 33) ^ (size_t)(v)
  EXTEND_HASH(type->kind);
  EXTEND_HASH(type->size);
  EXTEND_HASH(type->align);
  EXTEND_HASH(type->is_unsigned);
  EXTEND_HASH(type->is_atomic);
  // EXTEND_HASH(hash_type(type->origin));

  EXTEND_HASH(hash_type(type->base));
  EXTEND_HASH(type->array_len);
  EXTEND_HASH(type->vla_len);
  EXTEND_HASH(type->vla_size);
  EXTEND_HASH(type->members);

  // TODO: assume the members pointers are actually same?
  // for (Member *m = type->members; m; m = m->next) {
  //   EXTEND_HASH(hash_type(m->ty));
  //   EXTEND_HASH(m->name); // token
  //   EXTEND_HASH(m->idx);
  //   EXTEND_HASH(m->align);
  //   EXTEND_HASH(m->offset);
  //   EXTEND_HASH(m->is_bitfield);
  //   EXTEND_HASH(m->bit_offset);
  //   EXTEND_HASH(m->bit_width);
  // }
  EXTEND_HASH(type->is_flexible);
  EXTEND_HASH(type->is_packed);

  EXTEND_HASH(hash_type(type->return_ty));
  EXTEND_HASH(hash_type(type->params));
  EXTEND_HASH(type->is_variadic);
  // EXTEND_HASH(type->next);

  type->hashing = 0;
  return hash;
}

int definitely_same_type(Type *type1, Type *type2) {
  if (!type1 || !type2) return type1 == type2;
  if (type1->hashing != type2->hashing) return 0;
  if (type1->hashing) return type1 == type2;
  type1->hashing = 1;
  type2->hashing = 1;
#define FIELD_CHECK(field) if (type1->field != type2->field) goto disequal
#define RECURSE_CHECK(field) if (!definitely_same_type(type1->field, type2->field)) goto disequal
  FIELD_CHECK(kind);
  FIELD_CHECK(size);
  FIELD_CHECK(align);
  FIELD_CHECK(is_unsigned);
  FIELD_CHECK(is_atomic);
  // RECURSE_CHECK(origin);
  RECURSE_CHECK(base);
  FIELD_CHECK(array_len);
  FIELD_CHECK(vla_len);
  FIELD_CHECK(vla_size);
  FIELD_CHECK(members);
  FIELD_CHECK(is_flexible);
  FIELD_CHECK(is_packed);
  RECURSE_CHECK(return_ty);
  FIELD_CHECK(params);
  FIELD_CHECK(is_variadic);
  // RECURSE_CHECK(next);
  type1->hashing = 0;
  type2->hashing = 0;
  return 1;
disequal:
  type1->hashing = 0;
  type2->hashing = 0;
  return 0;
}

static Type **HASH_MAP = 0;
static int CAP_HASH_MAP = 0;
static int N_HASH_MAP = 0;
Type *hash_lookup(Type *type) {
  if (!CAP_HASH_MAP) return 0;

  size_t idx = hash_type(type) % CAP_HASH_MAP;
  while (HASH_MAP[idx]) {
    if (definitely_same_type(HASH_MAP[idx], type)) {
      return HASH_MAP[idx];
    }
    if (++idx == CAP_HASH_MAP) idx = 0;
  }
  return 0;
}

void hash_insert(Type *type) {
  if ((N_HASH_MAP + 1) >= (CAP_HASH_MAP / 2)) {
    // RESIZE AND REHASH
    int old_cap = CAP_HASH_MAP;
    Type **old_hash_map = HASH_MAP;

    CAP_HASH_MAP = (CAP_HASH_MAP + 1) * 4;
    N_HASH_MAP = 0;
    HASH_MAP = calloc(CAP_HASH_MAP, sizeof(HASH_MAP[0]));
    for (int i = 0; i < old_cap; i++)
      if (old_hash_map[i])
        hash_insert(old_hash_map[i]);
    if (old_hash_map) free(old_hash_map);
  }

  N_HASH_MAP++;
  size_t idx = hash_type(type) % CAP_HASH_MAP;
  while (HASH_MAP[idx])
    if (++idx == CAP_HASH_MAP) idx = 0;
  HASH_MAP[idx] = type;
}