/*****************************************************************************\
* Copyright (c) 2003 Pelle Johansson.                                         *
* All rights reserved.                                                        *
*                                                                             *
* This file is part of the moftpd package. Use and distribution of            *
* this software is governed by the terms in the file LICENCE, which           *
* should have come with this package.                                         *
\*****************************************************************************/

/* $moftpd: table.c 1251 2005-03-06 22:24:29Z morth $ */

#include "system.h"

#include "table.h"

const int *search_forward (const int forwardTable[][6], int size, int tag)
{
  while (size)
  {
    int odd = size & 1;
    
    size = size / 2;
    if (forwardTable[size][0] == tag)
      return forwardTable[size];
    if (forwardTable[size][0] < tag)
    {
      forwardTable += size + 1;
      if (!odd)
	size--;
    }
  }
  return NULL;
}

const sized_table_t *search_table (const sized_table_t *table, int tag)
{
  int size = table->size;
  const table_t *tab = table->table;
  
  while (size)
  {
    int odd = size & 1;
    
    size = size / 2;
    if (tab[size].tag == tag)
      return &tab[size].data;
    if (tab[size].tag < tag)
    {
      tab += size + 1;
      if (!odd)
	size--;
    }
  }
  return NULL;
}

int search_reverse (const sized_table_t *reverseTable,
      reverse_search_t *reverseIndexes, int numIndexes, int tag, int *depth)
{
  int i;
  const sized_table_t *tab;
  int ret = 0, didStart = 0;
  
  for (i = 0; i < numIndexes; i++)
  {
    if (reverseIndexes[i].table)
    {
      tab = search_table (reverseIndexes[i].table, tag);
      if (tab && !tab->table)
      {
	ret = tab->size;
	if (depth)
	  *depth = reverseIndexes[i].depth;
	tab = NULL;
      }
      else if (!tab && !reverseIndexes[i].table->table[0].tag)
      {
	ret = reverseIndexes[i].table->table[0].data.size;
	if (depth)
	  *depth = -reverseIndexes[i].depth + 1;
      }
      reverseIndexes[i].table = tab;
      reverseIndexes[i].depth++;
    }
    if (!didStart && !reverseIndexes[i].table)
    {
      didStart = 1;
      tab = search_table (reverseTable, tag);
      if (tab && !tab->table)
      {
	ret = tab->size;
	tab = NULL;
	if (depth)
	  *depth = 1;
      }
      reverseIndexes[i].table = tab;
      reverseIndexes[i].depth = 2;
    }
  }
  return ret;
}