make-trie.c   [plain text]

/* 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