pdf_name_tree.c

Fri, 14 Mar 2003 08:24:37 +0000

author
eric
date
Fri, 14 Mar 2003 08:24:37 +0000
changeset 131
4b8c80d77f76
parent 125
e2ef1c2f9eca
permissions
-rw-r--r--

finished implementing page labels.

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