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); }