1.1 diff -r 7de78f7789ef -r 870a093b587c pdf_name_tree.c 1.2 --- a/pdf_name_tree.c Sat Mar 08 07:23:49 2003 +0000 1.3 +++ b/pdf_name_tree.c Sat Mar 08 07:45:46 2003 +0000 1.4 @@ -4,7 +4,7 @@ 1.5 * will be compressed using ITU-T T.6 (G4) fax encoding. 1.6 * 1.7 * PDF routines 1.8 - * $Id: pdf_name_tree.c,v 1.4 2003/03/07 22:52:09 eric Exp $ 1.9 + * $Id: pdf_name_tree.c,v 1.5 2003/03/07 23:45:46 eric Exp $ 1.10 * Copyright 2003 Eric Smith <eric@brouhaha.com> 1.11 * 1.12 * This program is free software; you can redistribute it and/or modify 1.13 @@ -90,9 +90,12 @@ 1.14 static void pdf_split_name_tree_node (struct pdf_name_tree *tree, 1.15 struct pdf_name_tree_node *node) 1.16 { 1.17 + struct pdf_name_tree_node *parent; 1.18 struct pdf_name_tree_node *new_node; 1.19 + int i, j; 1.20 1.21 - if (node == tree->root) 1.22 + parent = node->parent; 1.23 + if (! parent) 1.24 { 1.25 /* create new root above current root */ 1.26 struct pdf_name_tree_node *new_root_node; 1.27 @@ -108,15 +111,71 @@ 1.28 new_root_node->min_key = node->min_key; 1.29 new_root_node->max_key = node->max_key; 1.30 1.31 + parent = new_root_node; 1.32 node->parent = new_root_node; 1.33 tree->root = new_root_node; 1.34 } 1.35 1.36 new_node = pdf_calloc (1, sizeof (struct pdf_name_tree_node)); 1.37 - new_node->parent = node->parent; 1.38 + new_node->parent = parent; 1.39 new_node->leaf = node->leaf; 1.40 1.41 - /* $$$ insert new node in parent's kids array */ 1.42 + /* move half the node's entries into the new node */ 1.43 + i = node->count / 2; 1.44 + j = node->count - i; 1.45 + 1.46 + memcpy (& new_node->kids [0], 1.47 + & node->kids [i], 1.48 + j * sizeof (struct pdf_name_tree_node *)); 1.49 + memcpy (& new_node->keys [0], 1.50 + & node->keys [i], 1.51 + j * sizeof (struct pdf_obj *)); 1.52 + memcpy (& new_node->values [0], 1.53 + & node->values [i], 1.54 + j * sizeof (struct pdf_obj *)); 1.55 + node->count = i; 1.56 + new_node->count = j; 1.57 + 1.58 + /* set max_key of the old node */ 1.59 + if (node->leaf) 1.60 + node->max_key = node->keys [node->count - 1]; 1.61 + else 1.62 + node->max_key = node->kids [node->count - 1]->max_key; 1.63 + 1.64 + /* set min_key and max_key in the new node */ 1.65 + if (new_node->leaf) 1.66 + { 1.67 + new_node->min_key = new_node->keys [0]; 1.68 + new_node->max_key = new_node->keys [new_node->count - 1]; 1.69 + } 1.70 + else 1.71 + { 1.72 + new_node->min_key = new_node->kids [0]->min_key; 1.73 + new_node->max_key = new_node->kids [new_node->count - 1]->max_key; 1.74 + } 1.75 + 1.76 + /* insert new node in parent's kids array */ 1.77 + /* find entry of old node */ 1.78 + for (i = 0; i < parent->count; i++) 1.79 + if (parent->kids [i] == node) 1.80 + break; 1.81 + 1.82 + /* it had better have been there! */ 1.83 + pdf_assert (i < parent->count); 1.84 + 1.85 + /* the new node goes in the slot to the right of the old node */ 1.86 + i++; 1.87 + 1.88 + /* move other entries right one position */ 1.89 + if (i != node->count) 1.90 + { 1.91 + memmove (& parent->kids [i+1], 1.92 + & parent->kids [i], 1.93 + (parent->count - i) * sizeof (struct pdf_name_tree_node *)); 1.94 + } 1.95 + 1.96 + parent->kids [i] = new_node; 1.97 + parent->count++; 1.98 } 1.99 1.100