Subversion Repositories scarts

/* Copyright (C) 1999  Free Software Foundation

   This file is part of libgcj.

This software is copyrighted work licensed under the terms of the

Libgcj License.  Please consult the file "LIBGCJ_LICENSE" for

details.  */

#include <stdio.h>

#include <stdlib.h>

typedef struct trie_node

{

  int key;

  int level;

  int position;

  union

  {

    int value;

    struct trie_node *node;

  } u[16];

} trie_node;

trie_node *

make_node ()

{

  trie_node *node = (trie_node *) malloc (sizeof(trie_node));

  if (node == NULL)

    abort();

  return node;

}

trie_node *

make_leaf_node ()

{

  trie_node *node = make_node ();

  int i = 16;

  while (--i >= 0)

    node->u[i].value = -1;

  return node;

}

trie_node *

make_branch_node ()

{

  trie_node *node = make_node ();

  int i = 16;

  while (--i >= 0)

    node->u[i].node = NULL;

  return node;

}

trie_node *table = NULL;

void

enter (int key, int value)

{

  trie_node **ptr = &table;

  int shift = 12;

  for (; shift > 0;  shift -= 4)

    {

      if (*ptr == NULL)

        {

          *ptr = make_branch_node ();

          (*ptr)->key = key & (0xFFFF << (shift + 4));

          (*ptr)->level = shift / 4;

        }

      ptr = &(*ptr)->u[(key >> shift) & 0xF].node;

    }

  if (*ptr == NULL)

    {

      *ptr = make_leaf_node ();

      (*ptr)->key = key & 0xFFF0;

      (*ptr)->level = 0;

    }

  if ((*ptr)->u[key & 0xF].value != -1

      && (*ptr)->u[key & 0xF].value != value)

    fprintf(stderr, "duplicate value for key: %d, %d!\n", key, value);

  (*ptr)->u[key & 0xF].value = value;

}

int assigned = 0;

void

assign (trie_node *node, int level)

{

  int i;

  if (node == NULL)

    return;

  if (node->level != level)

    abort();

  node->position = assigned;

  assigned++;

  if (level == 0)

    return;

  for (i = 0;  i < 16;  i++)

    {

      assign (node->u[i].node, level-1);

    }

}

int next_node_index_toprint = 0;

void

print (trie_node *node, int index, int level, FILE *out)

{

  int i;

  if (node->key != index || node->level != level)

    abort();

  if (level == 0) /* leaf node */

    {

      for (i = 0;  i < 16;  i++)

        {

          int node_index = index | (i << (level * 4));

          if (node_index < next_node_index_toprint)

            abort();

          if (node->u[i].value == -1)

            fprintf (out, " /* key: 0x%x */ 0xffff,\n", node_index);

          else

            fprintf (out, " /* key: 0x%x */ 0x%x,\n",

                     node_index, node->u[i].value);

          next_node_index_toprint = node_index + 1;

        }

    }

  else

    {

      for (i = 0;  i < 16;  i++)

        {

          int node_index = index | (i << (level * 4));

          fprintf (out, " /* branch: 0x%0*x%.*s */ ",

                  4 - level, node_index  >> ( 4 * level),

                  level, "XXXX");

          if (node->u[i].node == NULL)

            fprintf (out, "0,\n");

          else

            fprintf (out, "%d,\n", 16 * node->u[i].node->position);

        }

      for (i = 0;  i < 16;  i++)

        {

          int node_index = index | (i << (level * 4));

          if (node->u[i].node != NULL)

            print (node->u[i].node, node_index, level-1, out);

        }

    }

}

void

print_table (char *name, FILE *out)

{

  assign (table, 3);

  fprintf(out, "/* This file is automatically generated. */\n");

  fprintf(out, "unsigned short %s[] = {\n", name);

  print (table, 0x0000, 3, out);

  fprintf(out, "};\n");

}

#if 0

int

main (int argc, char **argv)

{

  int count = 0;

  for (;;)

    {

      int key, value;

      int i = scanf (" 0x%x 0x%x", &key, &value);

      if (i < 2)

        break;

      count++;

      enter (key, value);

    }

  return 0;

}

#endif