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.

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