pdf_name_tree.c

changeset 80
96c64a7566df
child 83
bbc7dd27aa5b
     1.1 diff -r 4cd9d23d924a -r 96c64a7566df pdf_name_tree.c
     1.2 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.3 +++ b/pdf_name_tree.c	Fri Mar 07 10:16:08 2003 +0000
     1.4 @@ -0,0 +1,203 @@
     1.5 +/*
     1.6 + * t2p: Create a PDF file from the contents of one or more TIFF
     1.7 + *      bilevel image files.  The images in the resulting PDF file
     1.8 + *      will be compressed using ITU-T T.6 (G4) fax encoding.
     1.9 + *
    1.10 + * PDF routines
    1.11 + * $Id: pdf_name_tree.c,v 1.1 2003/03/07 02:16:08 eric Exp $
    1.12 + * Copyright 2003 Eric Smith <eric@brouhaha.com>
    1.13 + *
    1.14 + * This program is free software; you can redistribute it and/or modify
    1.15 + * it under the terms of the GNU General Public License version 2 as
    1.16 + * published by the Free Software Foundation.  Note that permission is
    1.17 + * not granted to redistribute this program under the terms of any
    1.18 + * other version of the General Public License.
    1.19 + *
    1.20 + * This program is distributed in the hope that it will be useful,
    1.21 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
    1.22 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    1.23 + * GNU General Public License for more details.
    1.24 + *
    1.25 + * You should have received a copy of the GNU General Public License
    1.26 + * along with this program; if not, write to the Free Software
    1.27 + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111 USA
    1.28 + */
    1.29 +
    1.30 +
    1.31 +#include <stdbool.h>
    1.32 +#include <stdint.h>
    1.33 +#include <stdio.h>
    1.34 +#include <stdlib.h>
    1.35 +#include <string.h>
    1.36 +
    1.37 +
    1.38 +#include "bitblt.h"
    1.39 +#include "pdf.h"
    1.40 +#include "pdf_util.h"
    1.41 +#include "pdf_prim.h"
    1.42 +#include "pdf_private.h"
    1.43 +#include "pdf_name_tree.h"
    1.44 +
    1.45 +
    1.46 +#define MAX_NAME_TREE_NODE_ENTRIES 16
    1.47 +
    1.48 +
    1.49 +struct pdf_name_tree_node
    1.50 +{
    1.51 +  struct pdf_obj *dict;    /* indirect reference */
    1.52 +
    1.53 +  struct pdf_name_tree_node *parent;  /* NULL for root */
    1.54 +  bool leaf;
    1.55 +
    1.56 +  int count;               /* how many kids or names/numbers are
    1.57 +			      attached to this node */
    1.58 +
    1.59 +  struct pdf_name_tree_node *kids [MAX_NAME_TREE_NODE_ENTRIES];  /* non-leaf only */
    1.60 +
    1.61 +  struct pdf_obj *min_key;
    1.62 +  struct pdf_obj *max_key;
    1.63 +
    1.64 +  /* following fields valid in leaf nodes only: */
    1.65 +
    1.66 +  struct pdf_obj *keys [MAX_NAME_TREE_NODE_ENTRIES];
    1.67 +  struct pdf_obj *values [MAX_NAME_TREE_NODE_ENTRIES];
    1.68 +};
    1.69 +
    1.70 +
    1.71 +struct pdf_name_tree *pdf_new_name_tree (pdf_file_handle pdf_file,
    1.72 +					 bool number_tree)
    1.73 +{
    1.74 +  struct pdf_name_tree *tree;
    1.75 +  struct pdf_name_tree_node *root;
    1.76 +
    1.77 +  root = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
    1.78 +  tree = pdf_calloc (1, sizeof (struct pdf_name_tree));
    1.79 +
    1.80 +  tree->pdf_file = pdf_file;
    1.81 +  tree->root = root;
    1.82 +  tree->number_tree = number_tree;
    1.83 +
    1.84 +  root->parent = NULL;
    1.85 +  root->leaf = 1;
    1.86 +
    1.87 +  return (tree);
    1.88 +}
    1.89 +
    1.90 +
    1.91 +static void pdf_split_name_tree_node (struct pdf_name_tree *tree,
    1.92 +				      struct pdf_name_tree_node *node)
    1.93 +{
    1.94 +  struct pdf_name_tree_node *new_node;
    1.95 +
    1.96 +  if (node == tree->root)
    1.97 +    {
    1.98 +      /* create new root above current root */
    1.99 +      struct pdf_name_tree_node *new_root_node;
   1.100 +
   1.101 +      new_root_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
   1.102 +
   1.103 +      new_root_node->parent = NULL;
   1.104 +      new_root_node->leaf = 0;
   1.105 +
   1.106 +      new_root_node->count = 1;
   1.107 +      new_root_node->kids [0] = node;
   1.108 +
   1.109 +      new_root_node->min_key = node->min_key;
   1.110 +      new_root_node->max_key = node->max_key;
   1.111 +
   1.112 +      node->parent = new_root_node;
   1.113 +      tree->root = new_root_node;
   1.114 +    }
   1.115 +
   1.116 +  new_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node));
   1.117 +  new_node->parent = node->parent;
   1.118 +  new_node->leaf = node->leaf;
   1.119 +}
   1.120 +
   1.121 +
   1.122 +static void pdf_add_tree_element (struct pdf_name_tree *tree,
   1.123 +				  struct pdf_obj *key,
   1.124 +				  struct pdf_obj *val)
   1.125 +{
   1.126 +  struct pdf_name_tree_node *node;
   1.127 +
   1.128 +  /* find node which should contain element */
   1.129 +  node = tree->root;
   1.130 +
   1.131 +  /* if node is full, split, recursing to root if necessary */
   1.132 +  if (node->count == MAX_NAME_TREE_NODE_ENTRIES)
   1.133 +    {
   1.134 +      pdf_split_name_tree_node (tree, node);
   1.135 +      pdf_add_tree_element (tree, key, val);
   1.136 +      return;
   1.137 +    }
   1.138 +}
   1.139 +
   1.140 +
   1.141 +void pdf_add_name_tree_element (struct pdf_name_tree *tree,
   1.142 +				char *key,
   1.143 +				struct pdf_obj *val)
   1.144 +{
   1.145 +  struct pdf_obj *key_obj = pdf_new_string (key);
   1.146 +  pdf_add_tree_element (tree, key_obj, val);
   1.147 +}
   1.148 +
   1.149 +
   1.150 +void pdf_add_number_tree_element (struct pdf_name_tree *tree,
   1.151 +				  long key,
   1.152 +				  struct pdf_obj *val)
   1.153 +{
   1.154 +  struct pdf_obj *key_obj = pdf_new_integer (key);
   1.155 +  pdf_add_tree_element (tree, key_obj, val);
   1.156 +}
   1.157 +
   1.158 +
   1.159 +static void pdf_finalize_name_tree_node (struct pdf_name_tree *tree,
   1.160 +					 struct pdf_name_tree_node *node)
   1.161 +{
   1.162 +  int i;
   1.163 +
   1.164 +  node->dict = pdf_new_ind_ref (tree->pdf_file, pdf_new_obj (PT_DICTIONARY));
   1.165 +
   1.166 +  if (node->leaf)
   1.167 +    {
   1.168 +      /* write Names or Nums array */
   1.169 +      struct pdf_obj *names = pdf_new_obj (PT_ARRAY);
   1.170 +      for (i = 0; i < node->count; i++)
   1.171 +	{
   1.172 +	  pdf_add_array_elem (names, node->keys [i]);
   1.173 +	  pdf_add_array_elem (names, node->values [i]);
   1.174 +	}
   1.175 +      pdf_set_dict_entry (node->dict,
   1.176 +			  tree->number_tree ? "Nums" : "Names",
   1.177 +			  names);
   1.178 +    }
   1.179 +  else
   1.180 +    {
   1.181 +      /* finalize the children first so that their dict ind ref is
   1.182 +	 available */
   1.183 +      for (i = 0; i < node->count; i++)
   1.184 +	pdf_finalize_name_tree_node (tree, node->kids [i]);
   1.185 +
   1.186 +      /* write Kids array */
   1.187 +      struct pdf_obj *kids = pdf_new_obj (PT_ARRAY);
   1.188 +      for (i = 0; i < node->count; i++)
   1.189 +	pdf_add_array_elem (kids, node->kids [i]->dict);
   1.190 +      pdf_set_dict_entry (node->dict, "Kids", kids);
   1.191 +    }
   1.192 +
   1.193 +  if (! node->parent)
   1.194 +    {
   1.195 +      /* write Limits array */
   1.196 +      struct pdf_obj *limits = pdf_new_obj (PT_ARRAY);
   1.197 +      pdf_add_array_elem (limits, node->min_key);
   1.198 +      pdf_add_array_elem (limits, node->max_key);
   1.199 +      pdf_set_dict_entry (node->dict, "Limits", limits);
   1.200 +    }
   1.201 +}
   1.202 +
   1.203 +
   1.204 +void pdf_finalize_name_tree (struct pdf_name_tree *tree)
   1.205 +{
   1.206 +  pdf_finalize_name_tree_node (tree, tree->root);
   1.207 +}