pdf_name_tree.c

Thu, 13 Mar 2003 07:59:10 +0000

author
eric
date
Thu, 13 Mar 2003 07:59:10 +0000
changeset 121
e50c7f76f2f6
parent 113
d9a9ee9ff098
child 125
e2ef1c2f9eca
permissions
-rw-r--r--

don't use page mode USE_OUTLINES if there are no outline entries.

     1 /*
     2  * t2p: Create a PDF file from the contents of one or more TIFF
     3  *      bilevel image files.  The images in the resulting PDF file
     4  *      will be compressed using ITU-T T.6 (G4) fax encoding.
     5  *
     6  * PDF routines
     7  * $Id: pdf_name_tree.c,v 1.8 2003/03/12 03:13:28 eric Exp $
     8  * Copyright 2003 Eric Smith <eric@brouhaha.com>
     9  *
    10  * This program is free software; you can redistribute it and/or modify
    11  * it under the terms of the GNU General Public License version 2 as
    12  * published by the Free Software Foundation.  Note that permission is
    13  * not granted to redistribute this program under the terms of any
    14  * other version of the General Public License.
    15  *
    16  * This program is distributed in the hope that it will be useful,
    17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
    18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    19  * GNU General Public License for more details.
    20  *
    21  * You should have received a copy of the GNU General Public License
    22  * along with this program; if not, write to the Free Software
    23  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA
    24  */
    27 #include <stdbool.h>
    28 #include <stdint.h>
    29 #include <stdio.h>
    30 #include <stdlib.h>
    31 #include <string.h>
    34 #include "bitblt.h"
    35 #include "pdf.h"
    36 #include "pdf_util.h"
    37 #include "pdf_prim.h"
    38 #include "pdf_private.h"
    39 #include "pdf_name_tree.h"
    42 #define MAX_NAME_TREE_NODE_ENTRIES 16
    45 struct pdf_name_tree_node
    46 {
    47   struct pdf_obj *dict;    /* indirect reference */
    49   struct pdf_name_tree_node *parent;  /* NULL for root */
    50   bool leaf;
    52   int count;               /* how many kids or names/numbers are
    53 			      attached to this node */
    55   struct pdf_name_tree_node *kids [MAX_NAME_TREE_NODE_ENTRIES];  /* non-leaf only */
    57   struct pdf_obj *min_key;
    58   struct pdf_obj *max_key;
    60   /* following fields valid in leaf nodes only: */
    62   struct pdf_obj *keys [MAX_NAME_TREE_NODE_ENTRIES];
    63   struct pdf_obj *values [MAX_NAME_TREE_NODE_ENTRIES];
    64 };
    67 struct pdf_name_tree *pdf_new_name_tree (pdf_file_handle pdf_file,
    68 					 bool number_tree)
    69 {
    70   struct pdf_name_tree *tree;
    71   struct pdf_name_tree_node *root;
    73   root = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
    74   tree = pdf_calloc (1, sizeof (struct pdf_name_tree));
    76   tree->pdf_file = pdf_file;
    77   tree->root = root;
    78   tree->number_tree = number_tree;
    80   root->parent = NULL;
    81   root->leaf = 1;
    83   tree->next = pdf_file->name_tree_list;
    84   pdf_file->name_tree_list = tree;
    86   return (tree);
    87 }
    90 static void pdf_split_name_tree_node (struct pdf_name_tree *tree,
    91 				      struct pdf_name_tree_node *node)
    92 {
    93   struct pdf_name_tree_node *parent;
    94   struct pdf_name_tree_node *new_node;
    95   int i, j;
    97   parent = node->parent;
    98   if (! parent)
    99     {
   100       /* create new root above current root */
   101       struct pdf_name_tree_node *new_root_node;
   103       new_root_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
   105       new_root_node->parent = NULL;
   106       new_root_node->leaf = 0;
   108       new_root_node->count = 1;
   109       new_root_node->kids [0] = node;
   111       new_root_node->min_key = node->min_key;
   112       new_root_node->max_key = node->max_key;
   114       parent = new_root_node;
   115       node->parent = new_root_node;
   116       tree->root = new_root_node;
   117     }
   119   if (parent->count == MAX_NAME_TREE_NODE_ENTRIES)
   120     {
   121       pdf_split_name_tree_node (tree, parent);
   122       parent = node->parent;
   123     }
   125   new_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
   126   new_node->parent = parent;
   127   new_node->leaf = node->leaf;
   129   /* move half the node's entries into the new node */
   130   i = node->count / 2;
   131   j = node->count - i;
   133   memcpy (& new_node->kids [0],
   134 	  & node->kids [i],
   135 	  j * sizeof (struct pdf_name_tree_node *));
   136   memcpy (& new_node->keys [0],
   137 	  & node->keys [i],
   138 	  j * sizeof (struct pdf_obj *));
   139   memcpy (& new_node->values [0],
   140 	  & node->values [i],
   141 	  j * sizeof (struct pdf_obj *));
   143   node->count = i;
   144   new_node->count = j;
   146   if (! new_node->leaf)
   147     for (i = 0; i < j; i++)
   148       new_node->kids [i]->parent = new_node;
   150   /* set max_key of the old node */
   151   if (node->leaf)
   152     node->max_key = node->keys [node->count - 1];
   153   else
   154     node->max_key = node->kids [node->count - 1]->max_key;
   156   /* set min_key and max_key in the new node */
   157   if (new_node->leaf)
   158     {
   159       new_node->min_key = new_node->keys [0];
   160       new_node->max_key = new_node->keys [new_node->count - 1];
   161     }
   162   else
   163     {
   164       new_node->min_key = new_node->kids [0]->min_key;
   165       new_node->max_key = new_node->kids [new_node->count - 1]->max_key;
   166     }
   168   /* insert new node in parent's kids array */
   169   /* find entry of old node */
   170   for (i = 0; i < parent->count; i++)
   171     if (parent->kids [i] == node)
   172       break;
   174   /* it had better have been there! */
   175   pdf_assert (i < parent->count);
   177   /* the new node goes in the slot to the right of the old node */
   178   i++;
   180   /* move other entries right one position */
   181   if (i != parent->count)
   182     {
   183       memmove (& parent->kids [i+1],
   184 	       & parent->kids [i],
   185 	       (parent->count - i) * sizeof (struct pdf_name_tree_node *));
   186     }
   188   parent->kids [i] = new_node;
   189   parent->count++;
   190 }
   193 static void pdf_add_tree_element (struct pdf_name_tree *tree,
   194 				  struct pdf_obj *key,
   195 				  struct pdf_obj *val)
   196 {
   197   struct pdf_name_tree_node *node;
   198   int i;
   200   /* find node which should contain element */
   201   node = tree->root;
   202   while (! node->leaf)
   203     {
   204       for (i = 0; i < (node->count - 1); i++)
   205 	if (pdf_compare_obj (key, node->kids [i + 1]->min_key) < 0)
   206 	  break;
   207       node = node->kids [i];
   208     }
   210   /* if node is full, split, recursing to root if necessary */
   211   if (node->count == MAX_NAME_TREE_NODE_ENTRIES)
   212     {
   213       pdf_split_name_tree_node (tree, node);
   214       pdf_add_tree_element (tree, key, val);
   215       return;
   216     }
   218   /* figure out in which slot to insert it */
   219   for (i = 0; i < node->count; i++)
   220     if (pdf_compare_obj (key, node->keys [i]) < 0)
   221       break;
   223   /* move other entries right one position */
   224   if (i != node->count)
   225     {
   226       memmove (& node->keys [i+1],
   227 	       & node->keys [i],
   228 	       (node->count - i) * sizeof (struct pdf_obj *));
   229       memmove (& node->values [i+1],
   230 	       & node->values [i],
   231 	       (node->count - i) * sizeof (struct pdf_obj *));
   232     }
   234   node->keys [i] = key;
   235   node->values [i] = val;
   237   node->count++;
   239   /* update limits, recursing upwards if necessary */
   240   if (i == 0)
   241     {
   242       node->min_key = key;
   243       while (node->parent && (node->parent->kids [0] == node))
   244 	{
   245 	  node = node->parent;
   246 	  node->min_key = key;
   247 	}
   248     }
   249   if (i == (node->count - 1))
   250     {
   251       node->max_key = key;
   252       while (node->parent && (node->parent->kids [node->parent->count - 1] == node))
   253 	{
   254 	  node = node->parent;
   255 	  node->max_key = key;
   256 	}
   257     }
   258 }
   261 void pdf_add_name_tree_element (struct pdf_name_tree *tree,
   262 				char *key,
   263 				struct pdf_obj *val)
   264 {
   265   struct pdf_obj *key_obj = pdf_new_string (key);
   266   pdf_add_tree_element (tree, key_obj, val);
   267 }
   270 void pdf_add_number_tree_element (struct pdf_name_tree *tree,
   271 				  long key,
   272 				  struct pdf_obj *val)
   273 {
   274   struct pdf_obj *key_obj = pdf_new_integer (key);
   275   pdf_add_tree_element (tree, key_obj, val);
   276 }
   279 static void pdf_finalize_name_tree_node (struct pdf_name_tree *tree,
   280 					 struct pdf_name_tree_node *node)
   281 {
   282   int i;
   284   node->dict = pdf_new_ind_ref (tree->pdf_file, pdf_new_obj (PT_DICTIONARY));
   286   if (node->leaf)
   287     {
   288       /* write Names or Nums array */
   289       struct pdf_obj *names = pdf_new_obj (PT_ARRAY);
   290       for (i = 0; i < node->count; i++)
   291 	{
   292 	  pdf_add_array_elem (names, node->keys [i]);
   293 	  pdf_add_array_elem (names, node->values [i]);
   294 	}
   295       pdf_set_dict_entry (node->dict,
   296 			  tree->number_tree ? "Nums" : "Names",
   297 			  names);
   298     }
   299   else
   300     {
   301       /* finalize the children first so that their dict ind ref is
   302 	 available */
   303       struct pdf_obj *kids;
   305       for (i = 0; i < node->count; i++)
   306 	pdf_finalize_name_tree_node (tree, node->kids [i]);
   308       /* write Kids array */
   309       kids = pdf_new_obj (PT_ARRAY);
   310       for (i = 0; i < node->count; i++)
   311 	pdf_add_array_elem (kids, node->kids [i]->dict);
   312       pdf_set_dict_entry (node->dict, "Kids", kids);
   313     }
   315   if (node->parent)
   316     {
   317       /* write Limits array */
   318       struct pdf_obj *limits = pdf_new_obj (PT_ARRAY);
   319       pdf_add_array_elem (limits, node->min_key);
   320       pdf_add_array_elem (limits, node->max_key);
   321       pdf_set_dict_entry (node->dict, "Limits", limits);
   322     }
   323 }
   326 void pdf_finalize_name_trees (pdf_file_handle pdf_file)
   327 {
   328   struct pdf_name_tree *tree;
   330   for (tree = pdf_file->name_tree_list; tree; tree = tree->next)
   331     pdf_finalize_name_tree_node (tree, tree->root);
   332 }