index_fst_registry.c

/*
 * Copyright (c) 2019 TAOS Data, Inc. <jhtao@taosdata.com>
 *
 * This program is free software: you can use, redistribute, and/or modify
 * it under the terms of the GNU Affero General Public License, version 3
 * or later ("AGPL"), as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 */

#include "index_fst_registry.h"

uint64_t fstRegistryHash(FstRegistry* registry, FstBuilderNode* bNode) {
  // TODO(yihaoDeng): refactor later
  const uint64_t FNV_PRIME = 1099511628211;
  uint64_t       h = 14695981039346656037u;

  h = (h ^ (uint64_t)bNode->isFinal) * FNV_PRIME;
  h = (h ^ (bNode)->finalOutput) * FNV_PRIME;

  uint32_t sz = (uint32_t)taosArrayGetSize(bNode->trans);
  for (uint32_t i = 0; i < sz; i++) {
    FstTransition* trn = taosArrayGet(bNode->trans, i);
    h = (h ^ (uint64_t)(trn->inp)) * FNV_PRIME;
    h = (h ^ (uint64_t)(trn->out)) * FNV_PRIME;
    h = (h ^ (uint64_t)(trn->addr)) * FNV_PRIME;
  }
  return h % (registry->tableSize);
}
static void fstRegistryCellSwap(SArray* arr, uint32_t a, uint32_t b) {
  size_t sz = taosArrayGetSize(arr);
  if (a >= sz || b >= sz) { return; }

  FstRegistryCell* cell1 = (FstRegistryCell*)taosArrayGet(arr, a);
  FstRegistryCell* cell2 = (FstRegistryCell*)taosArrayGet(arr, b);

  FstRegistryCell t = {.addr = cell1->addr, .node = cell1->node};

  cell1->addr = cell2->addr;
  cell1->node = cell2->node;

  cell2->addr = t.addr;
  cell2->node = t.node;
  return;
}

static void fstRegistryCellPromote(SArray* arr, uint32_t start, uint32_t end) {
  size_t sz = taosArrayGetSize(arr);
  if (start >= sz && end >= sz) { return; }

  assert(start >= end);

  int32_t s = (int32_t)start;
  int32_t e = (int32_t)end;
  while (s > e) {
    fstRegistryCellSwap(arr, s - 1, s);
    s -= 1;
  }
}

FstRegistry* fstRegistryCreate(uint64_t tableSize, uint64_t mruSize) {
  FstRegistry* registry = malloc(sizeof(FstRegistry));
  if (registry == NULL) { return NULL; }

  uint64_t nCells = tableSize * mruSize;
  SArray*  tb = (SArray*)taosArrayInit(nCells, sizeof(FstRegistryCell));
  if (NULL == tb) {
    free(registry);
    return NULL;
  }

  for (uint64_t i = 0; i < nCells; i++) {
    FstRegistryCell cell = {.addr = NONE_ADDRESS, .node = fstBuilderNodeDefault()};
    taosArrayPush(tb, &cell);
  }

  registry->table = tb;
  registry->tableSize = tableSize;
  registry->mruSize = mruSize;
  return registry;
}

void fstRegistryDestroy(FstRegistry* registry) {
  if (registry == NULL) { return; }

  SArray* tb = registry->table;
  size_t  sz = taosArrayGetSize(tb);
  for (size_t i = 0; i < sz; i++) {
    FstRegistryCell* cell = taosArrayGet(tb, i);
    fstBuilderNodeDestroy(cell->node);
  }
  taosArrayDestroy(tb);
  free(registry);
}

FstRegistryEntry* fstRegistryGetEntry(FstRegistry* registry, FstBuilderNode* bNode) {
  if (taosArrayGetSize(registry->table) <= 0) { return NULL; }
  uint64_t bucket = fstRegistryHash(registry, bNode);
  uint64_t start = registry->mruSize * bucket;
  uint64_t end = start + registry->mruSize;

  FstRegistryEntry* entry = malloc(sizeof(FstRegistryEntry));
  if (end - start == 1) {
    FstRegistryCell* cell = taosArrayGet(registry->table, start);
    // cell->isNode &&
    if (cell->addr != NONE_ADDRESS && fstBuilderNodeEqual(cell->node, bNode)) {
      entry->state = FOUND;
      entry->addr = cell->addr;
      return entry;
    } else {
      fstBuilderNodeCloneFrom(cell->node, bNode);
      entry->state = NOTFOUND;
      entry->cell = cell;  // copy or not
    }
  } else if (end - start == 2) {
    FstRegistryCell* cell1 = taosArrayGet(registry->table, start);
    if (cell1->addr != NONE_ADDRESS && fstBuilderNodeEqual(cell1->node, bNode)) {
      entry->state = FOUND;
      entry->addr = cell1->addr;
      return entry;
    }
    FstRegistryCell* cell2 = taosArrayGet(registry->table, start + 1);
    if (cell2->addr != NONE_ADDRESS && fstBuilderNodeEqual(cell2->node, bNode)) {
      entry->state = FOUND;
      entry->addr = cell2->addr;
      // must swap here
      fstRegistryCellSwap(registry->table, start, start + 1);
      return entry;
    }
    // clone from bNode, refactor later
    fstBuilderNodeCloneFrom(cell2->node, bNode);

    fstRegistryCellSwap(registry->table, start, start + 1);
    FstRegistryCell* cCell = taosArrayGet(registry->table, start);
    entry->state = NOTFOUND;
    entry->cell = cCell;
  } else {
    uint32_t i = start;
    for (; i < end; i++) {
      FstRegistryCell* cell = (FstRegistryCell*)taosArrayGet(registry->table, i);
      if (cell->addr != NONE_ADDRESS && fstBuilderNodeEqual(cell->node, bNode)) {
        entry->state = FOUND;
        entry->addr = cell->addr;
        fstRegistryCellPromote(registry->table, i, start);
        break;
      }
    }
    if (i >= end) {
      uint64_t         last = end - 1;
      FstRegistryCell* cell = (FstRegistryCell*)taosArrayGet(registry->table, last);
      // clone from bNode, refactor later
      fstBuilderNodeCloneFrom(cell->node, bNode);

      fstRegistryCellPromote(registry->table, last, start);
      FstRegistryCell* cCell = taosArrayGet(registry->table, start);
      entry->state = NOTFOUND;
      entry->cell = cCell;
    }
  }
  return entry;
}
void fstRegistryEntryDestroy(FstRegistryEntry* entry) {
  free(entry);
}