pdf_name_tree.c

changeset 87
870a093b587c
parent 85
dcfd1d4b5c24
child 88
a9991578aa3f
     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