pdf_name_tree.c

Fri, 14 Mar 2003 08:56:38 +0000

author
eric
date
Fri, 14 Mar 2003 08:56:38 +0000
changeset 132
ccf1c28a2940
parent 131
4b8c80d77f76
permissions
-rw-r--r--

remove debug output.

     1 /*
     2  * tumble: build a PDF file from image files
     3  *
     4  * PDF routines
     5  * $Id: pdf_name_tree.c,v 1.10 2003/03/14 00:24:37 eric Exp $
     6  * Copyright 2003 Eric Smith <eric@brouhaha.com>
     7  *
     8  * This program is free software; you can redistribute it and/or modify
     9  * it under the terms of the GNU General Public License version 2 as
    10  * published by the Free Software Foundation.  Note that permission is
    11  * not granted to redistribute this program under the terms of any
    12  * other version of the General Public License.
    13  *
    14  * This program is distributed in the hope that it will be useful,
    15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
    16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    17  * GNU General Public License for more details.
    18  *
    19  * You should have received a copy of the GNU General Public License
    20  * along with this program; if not, write to the Free Software
    21  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA
    22  */
    25 #include <stdbool.h>
    26 #include <stdint.h>
    27 #include <stdio.h>
    28 #include <stdlib.h>
    29 #include <string.h>
    32 #include "bitblt.h"
    33 #include "pdf.h"
    34 #include "pdf_util.h"
    35 #include "pdf_prim.h"
    36 #include "pdf_private.h"
    37 #include "pdf_name_tree.h"
    40 struct pdf_name_tree *pdf_new_name_tree (pdf_file_handle pdf_file,
    41 					 bool number_tree)
    42 {
    43   struct pdf_name_tree *tree;
    44   struct pdf_name_tree_node *root;
    46   root = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
    47   tree = pdf_calloc (1, sizeof (struct pdf_name_tree));
    49   tree->pdf_file = pdf_file;
    50   tree->root = root;
    51   tree->number_tree = number_tree;
    53   root->parent = NULL;
    54   root->leaf = 1;
    56   tree->next = pdf_file->name_tree_list;
    57   pdf_file->name_tree_list = tree;
    59   return (tree);
    60 }
    63 static void pdf_split_name_tree_node (struct pdf_name_tree *tree,
    64 				      struct pdf_name_tree_node *node)
    65 {
    66   struct pdf_name_tree_node *parent;
    67   struct pdf_name_tree_node *new_node;
    68   int i, j;
    70   parent = node->parent;
    71   if (! parent)
    72     {
    73       /* create new root above current root */
    74       struct pdf_name_tree_node *new_root_node;
    76       new_root_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
    78       new_root_node->parent = NULL;
    79       new_root_node->leaf = 0;
    81       new_root_node->count = 1;
    82       new_root_node->kids [0] = node;
    84       new_root_node->min_key = node->min_key;
    85       new_root_node->max_key = node->max_key;
    87       parent = new_root_node;
    88       node->parent = new_root_node;
    89       tree->root = new_root_node;
    90     }
    92   if (parent->count == MAX_NAME_TREE_NODE_ENTRIES)
    93     {
    94       pdf_split_name_tree_node (tree, parent);
    95       parent = node->parent;
    96     }
    98   new_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
    99   new_node->parent = parent;
   100   new_node->leaf = node->leaf;
   102   /* move half the node's entries into the new node */
   103   i = node->count / 2;
   104   j = node->count - i;
   106   memcpy (& new_node->kids [0],
   107 	  & node->kids [i],
   108 	  j * sizeof (struct pdf_name_tree_node *));
   109   memcpy (& new_node->keys [0],
   110 	  & node->keys [i],
   111 	  j * sizeof (struct pdf_obj *));
   112   memcpy (& new_node->values [0],
   113 	  & node->values [i],
   114 	  j * sizeof (struct pdf_obj *));
   116   node->count = i;
   117   new_node->count = j;
   119   if (! new_node->leaf)
   120     for (i = 0; i < j; i++)
   121       new_node->kids [i]->parent = new_node;
   123   /* set max_key of the old node */
   124   if (node->leaf)
   125     node->max_key = node->keys [node->count - 1];
   126   else
   127     node->max_key = node->kids [node->count - 1]->max_key;
   129   /* set min_key and max_key in the new node */
   130   if (new_node->leaf)
   131     {
   132       new_node->min_key = new_node->keys [0];
   133       new_node->max_key = new_node->keys [new_node->count - 1];
   134     }
   135   else
   136     {
   137       new_node->min_key = new_node->kids [0]->min_key;
   138       new_node->max_key = new_node->kids [new_node->count - 1]->max_key;
   139     }
   141   /* insert new node in parent's kids array */
   142   /* find entry of old node */
   143   for (i = 0; i < parent->count; i++)
   144     if (parent->kids [i] == node)
   145       break;
   147   /* it had better have been there! */
   148   pdf_assert (i < parent->count);
   150   /* the new node goes in the slot to the right of the old node */
   151   i++;
   153   /* move other entries right one position */
   154   if (i != parent->count)
   155     {
   156       memmove (& parent->kids [i+1],
   157 	       & parent->kids [i],
   158 	       (parent->count - i) * sizeof (struct pdf_name_tree_node *));
   159     }
   161   parent->kids [i] = new_node;
   162   parent->count++;
   163 }
   166 static void pdf_add_tree_element (struct pdf_name_tree *tree,
   167 				  struct pdf_obj *key,
   168 				  struct pdf_obj *val)
   169 {
   170   struct pdf_name_tree_node *node;
   171   int i;
   173   /* find node which should contain element */
   174   node = tree->root;
   175   while (! node->leaf)
   176     {
   177       for (i = 0; i < (node->count - 1); i++)
   178 	if (pdf_compare_obj (key, node->kids [i + 1]->min_key) < 0)
   179 	  break;
   180       node = node->kids [i];
   181     }
   183   /* if node is full, split, recursing to root if necessary */
   184   if (node->count == MAX_NAME_TREE_NODE_ENTRIES)
   185     {
   186       pdf_split_name_tree_node (tree, node);
   187       pdf_add_tree_element (tree, key, val);
   188       return;
   189     }
   191   /* figure out in which slot to insert it */
   192   for (i = 0; i < node->count; i++)
   193     if (pdf_compare_obj (key, node->keys [i]) < 0)
   194       break;
   196   /* move other entries right one position */
   197   if (i != node->count)
   198     {
   199       memmove (& node->keys [i+1],
   200 	       & node->keys [i],
   201 	       (node->count - i) * sizeof (struct pdf_obj *));
   202       memmove (& node->values [i+1],
   203 	       & node->values [i],
   204 	       (node->count - i) * sizeof (struct pdf_obj *));
   205     }
   207   node->keys [i] = key;
   208   node->values [i] = val;
   210   node->count++;
   212   /* update limits, recursing upwards if necessary */
   213   if (i == 0)
   214     {
   215       node->min_key = key;
   216       while (node->parent && (node->parent->kids [0] == node))
   217 	{
   218 	  node = node->parent;
   219 	  node->min_key = key;
   220 	}
   221     }
   222   if (i == (node->count - 1))
   223     {
   224       node->max_key = key;
   225       while (node->parent && (node->parent->kids [node->parent->count - 1] == node))
   226 	{
   227 	  node = node->parent;
   228 	  node->max_key = key;
   229 	}
   230     }
   231 }
   234 void pdf_add_name_tree_element (struct pdf_name_tree *tree,
   235 				char *key,
   236 				struct pdf_obj *val)
   237 {
   238   struct pdf_obj *key_obj = pdf_new_string (key);
   239   pdf_add_tree_element (tree, key_obj, val);
   240 }
   243 void pdf_add_number_tree_element (struct pdf_name_tree *tree,
   244 				  long key,
   245 				  struct pdf_obj *val)
   246 {
   247   struct pdf_obj *key_obj = pdf_new_integer (key);
   248   pdf_add_tree_element (tree, key_obj, val);
   249 }
   252 static void pdf_finalize_name_tree_node (struct pdf_name_tree *tree,
   253 					 struct pdf_name_tree_node *node)
   254 {
   255   int i;
   257   node->dict = pdf_new_ind_ref (tree->pdf_file, pdf_new_obj (PT_DICTIONARY));
   259   if (node->leaf)
   260     {
   261       /* write Names or Nums array */
   262       struct pdf_obj *names = pdf_new_obj (PT_ARRAY);
   263       for (i = 0; i < node->count; i++)
   264 	{
   265 	  pdf_add_array_elem (names, node->keys [i]);
   266 	  pdf_add_array_elem (names, node->values [i]);
   267 	}
   268       pdf_set_dict_entry (node->dict,
   269 			  tree->number_tree ? "Nums" : "Names",
   270 			  names);
   271     }
   272   else
   273     {
   274       /* finalize the children first so that their dict ind ref is
   275 	 available */
   276       struct pdf_obj *kids;
   278       for (i = 0; i < node->count; i++)
   279 	pdf_finalize_name_tree_node (tree, node->kids [i]);
   281       /* write Kids array */
   282       kids = pdf_new_obj (PT_ARRAY);
   283       for (i = 0; i < node->count; i++)
   284 	pdf_add_array_elem (kids, node->kids [i]->dict);
   285       pdf_set_dict_entry (node->dict, "Kids", kids);
   286     }
   288   if (node->parent)
   289     {
   290       /* write Limits array */
   291       struct pdf_obj *limits = pdf_new_obj (PT_ARRAY);
   292       pdf_add_array_elem (limits, node->min_key);
   293       pdf_add_array_elem (limits, node->max_key);
   294       pdf_set_dict_entry (node->dict, "Limits", limits);
   295     }
   296 }
   299 void pdf_finalize_name_trees (pdf_file_handle pdf_file)
   300 {
   301   struct pdf_name_tree *tree;
   303   for (tree = pdf_file->name_tree_list; tree; tree = tree->next)
   304     pdf_finalize_name_tree_node (tree, tree->root);
   305 }