text: //
  // Created by zhao chenyang on 2021/1/19.
  //
  
  #include <stdlib.h>
  #include <string.h>
  
  #include "memory.h"
  #include "object.h"
  #include "table.h"
  #include "value.h"
  
  #define TABLE_MAX_LOAD 0.6
  
  void initTable(Table *table) {
      table->count = 0;
      table->capacity = -1;
      table->entries = NULL;
  }
  
  void freeTable(Table *table) {
      FREE_ARRAY(Entry, table->entries, table->capacity + 1);
      initTable(table);
  }
  
  // 返回value对应的桶
  static Entry *findEntry(Entry *entries, int capacity,
                          ObjString *key) {
      uint32_t index = key->hash & capacity;
      for (;;) {
          Entry *entry = &entries[index];
          Entry *tombstone = NULL; //由于顺序
  
          if (entry->key == NULL) {
              if (IS_NIL(entry->value)) {
                  // Empty entry.
                  return tombstone != NULL ? tombstone : entry;
              } else {
                  // We found a tombstone.
                  if (tombstone == NULL) tombstone = entry;
              }
          } else if (entry->key == key) {
              // We found the key.
              return entry;
          }
  
          index = (index + 1) & capacity;
      }
  }
  
  bool tableGet(Table *table, ObjString *key, Value *value) {
      if (table->count == 0) return false;
  
      Entry *entry = findEntry(table->entries, table->capacity, key);
      if (entry->key == NULL) return false;
  
      *value = entry->value;
      return true;
  }
  
  bool tableDelete(Table *table, ObjString *key) {
      if (table->count == 0) return false;
  
      // Find the entry.
      Entry *entry = findEntry(table->entries, table->capacity, key);
      if (entry->key == NULL) return false;
  
      // Place a tombstone in the entry.
      // 避免有冲突时，删除中间的值使冲突链中断
      entry->key = NULL;
      entry->value = BOOL_VAL(true);
  
      return true;
  }
  
  static void adjustCapacity(Table *table, int capacity) {
      Entry *entries = ALLOCATE(Entry, capacity + 1);
      for (int i = 0; i <= capacity; i++) {
          entries[i].key = NULL;
          entries[i].value = NIL_VAL;
      }
  
      table->count = 0;
      for (int i = 0; i <= table->capacity; i++) {
          Entry *entry = &table->entries[i];
          if (entry->key == NULL) continue;
  
          Entry *dest = findEntry(entries, capacity, entry->key);
          dest->key = entry->key;
          dest->value = entry->value;
          table->count++;
      }
  
      FREE_ARRAY(Entry, table->entries, table->capacity + 1);
      table->entries = entries;
      table->capacity = capacity;
  
  }
  
  bool tableSet(Table *table, ObjString *key, Value value) {
      // 看hash表容量是否足够
      if (table->count + 1 > (table->capacity + 1) * TABLE_MAX_LOAD) {
          int capacity = GROW_CAPACITY(table->capacity + 1) - 1;
          // 分配并转移entry数组
          adjustCapacity(table, capacity);
      }
  
      // 返回桶的指针
      Entry *entry = findEntry(table->entries, table->capacity, key);
  
      bool isNewKey = entry->key == NULL;
      if (isNewKey && IS_NIL(entry->value)) table->count++;
  
      entry->key = key;
      entry->value = value;
      return isNewKey;
  }
  
  void tableAddAll(Table *from, Table *to) {
      for (int i = 0; i <= from->capacity; i++) {
          Entry *entry = &from->entries[i];
          if (entry->key != NULL) {
              tableSet(to, entry->key, entry->value);
          }
      }
  }
  
  ObjString *tableFindString(Table *table, const char *chars, int length, uint32_t hash) {
      if (table->count == 0) return NULL;
  
      uint32_t index = hash & table->capacity;
  
      for (;;) {
          Entry *entry = &table->entries[index];
  
          if (entry->key == NULL) {
              // Stop if we find an empty non-tombstone entry.
              if (IS_NIL(entry->value)) return NULL;
          } else if (entry->key->length == length &&
                     entry->key->hash == hash &&
                     memcmp(entry->key->chars, chars, length) == 0) {
              // We found it.
              return entry->key;
          }
  
          index = (index + 1) & table->capacity;
      }
  }
  
  void markTable(Table *table) {
      for (int i = 0; i <= table->capacity; i++) {
          Entry *entry = &table->entries[i];
          markObject((Obj *) entry->key);
          markValue(entry->value);
      }
  }
  
  void tableRemoveWhite(Table *table) {
      for (int i = 0; i <= table->capacity; i++) {
          Entry *entry = &table->entries[i];
          if (entry->key != NULL && !entry->key->obj.isMarked) {
              tableDelete(table, entry->key);
          }
      }
  }
  
  
  