libhed/tree.c

   1 /* $Id$ */
   2
   3 /*
   4  * hed - Hexadecimal editor
   5  * Copyright (C) 2004  Petr Baudis <pasky@ucw.cz>
   6  *
   7  * This program is free software; you can redistribute it and/or modify
   8  * it under the terms of version 2 of the GNU General Public License as
   9  * published by the Free Software Foundation.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  19  */
  20
  21 /*
  22  * When his eyes were in turn uncovered, Frodo looked up and caught his breath.
  23  * They were standing in an open space. To the left stood a great mound,
  24  * covered with a sward of grass as green as Spring-time in the Elder Days.
  25  * Upon it, as a double crown, grew two circles of trees: the outer had bark of
  26  * snowy white, and were leafless but beautiful in their shapely nakedness; the
  27  * inner were mallorn-trees of great height, still arrayed in pale gold. High
  28  * amid the branches of a towering tree that stood in the centre of all there
  29  * gleamed a white flet. At the feet of the trees, and all about the green
  30  * hillsides the grass was studded with small golden flowers shaped like stars.
  31  * Among them, nodding on slender stalks, were other flowers, white and palest
  32  * green: they glimmered as a mist amid the rich hue of the grass. Over all the
  33  * sky was blue, and the sun of afternoon glowed upon the hill and cast long
  34  * green shadows beneath the trees.
  35  */
  36
  37 #include <config.h>
  38
  39 #include <stdio.h>
  40 #include <stddef.h>
  41 #include <stdlib.h>
  42 #include <assert.h>
  43
  44 #include "tree.h"
  45
  46
  47 /* Define to enable debug messages */
  48 #undef TREE_DEBUG
  49 #ifdef TREE_DEBUG
  50 #define TDEBUG(x...) fprintf(stderr, x)
  51 #else
  52 #define TDEBUG(x...)
  53 #endif
  54
  55 /* You shouldn't need to call these directly unless you want to
  56  * do special optimizations for certain items. */
  57 static void splay(struct hed_tree *tree, struct hed_tree_node *item);
  58 static void unsplay(struct hed_tree *tree, struct hed_tree_node *item);
  59
  60 static void
  61 recalc_node(struct hed_tree *tree, struct hed_tree_node *item)
  62 {
  63         item->cover_size = item->size;
  64         if (is_a_node(tree, item->left)) {
  65                 item->cover_size += item->left->cover_size;
  66                 item->left->up = item;
  67         }
  68         if (is_a_node(tree, item->right)) {
  69                 item->cover_size += item->right->cover_size;
  70                 item->right->up = item;
  71         }
  72 }
  73
  74 void
  75 recalc_node_recursive(struct hed_tree *tree, struct hed_tree_node *item)
  76 {
  77         while (is_a_node(tree, item)) {
  78                 recalc_node(tree, item);
  79                 item = item->up;
  80         }
  81 }
  82
  83 static void
  84 del_leaf(struct hed_tree *tree, struct hed_tree_node *item)
  85 {
  86         list_del(&item->link);
  87
  88         if (item == tree->root) {
  89                 tree->root = null_node(tree);
  90                 return;
  91         }
  92
  93         assert(!is_a_node(tree, item->left) && !is_a_node(tree, item->right) &&
  94                is_a_node(tree, item->up));
  95         if (item->up->left == item) {
  96                 item->up->left = null_node(tree);
  97         } else {
  98                 assert(item->up->right == item);
  99                 item->up->right = null_node(tree);
 100         }
 101
 102         item->up = null_node(tree);
 103 }
 104
 105 void
 106 del_from_tree(struct hed_tree *tree, struct hed_tree_node *item)
 107 {
 108         unsplay(tree, item);
 109         del_leaf(tree, item);
 110 }
 111
 112 void
 113 recalc_del_from_tree(struct hed_tree *tree, struct hed_tree_node *item)
 114 {
 115         struct hed_tree_node *parent;
 116
 117         /*
 118          * 'I'll give your name and number to the Nazgyl,' said the soldier
 119          * lowering his voice to a hiss. 'One of *them*'s in charge at the
 120          * Tower now.'
 121          */
 122
 123         unsplay(tree, item);
 124         parent = item->up;
 125         del_leaf(tree, item);
 126         assert(item->size == item->cover_size);
 127         while (is_a_node(tree, parent)) {
 128                 parent->cover_size -= item->size;
 129                 parent = parent->up;
 130         }
 131 }
 132
 133 void
 134 insert_into_tree(struct hed_tree *tree, struct hed_tree_node *item,
 135                  struct hed_tree_node *pos)
 136 {
 137         item->up = item->left = item->right = null_node(tree);
 138         item->cover_size = item->size;
 139
 140         splay(tree, is_a_node(tree, pos) ? pos : first_in_tree(tree));
 141
 142         list_add(&item->link, &pos->link);
 143
 144         if (!is_a_node(tree, pos)) {
 145                 pos = tree->root;
 146                 item->left = null_node(tree);
 147                 item->right = pos;
 148         } else {
 149                 assert(tree->root == pos);
 150                 item->left = pos;
 151                 item->right = pos->right;
 152                 pos->right = null_node(tree);
 153                 recalc_node(tree, pos);
 154         }
 155         if (is_a_node(tree, pos))
 156                 pos->up = item;
 157         tree->root = item;
 158         recalc_node(tree, item);
 159 }
 160
 161 void
 162 append_to_tree(struct hed_tree *tree, struct hed_tree_node *item)
 163 {
 164         insert_into_tree(tree, item, last_in_tree(tree));
 165 }
 166
 167 struct hed_tree_node *
 168 find_in_tree(struct hed_tree *tree, hed_uoff_t offset)
 169 {
 170         struct hed_tree_node *item = null_node(tree), *nitem = tree->root;
 171         hed_uoff_t pos = is_a_node(tree, nitem) && is_a_node(tree, nitem->left)
 172                 ? nitem->left->cover_size : 0;
 173
 174         while (is_a_node(tree, nitem)) {
 175                 /* We splay as we go. */
 176                 TDEBUG("find_in_tree(%llx): %llx\n", offset, pos);
 177                 /* rot_up(tree, nitem); */
 178                 item = nitem;
 179                 if (pos <= offset && offset < pos + item->size) {
 180                         TDEBUG("find_in_tree(%llx): match - pos %llx, size %llx\n", offset, pos, item->size);
 181                         nitem = null_node(tree);
 182                 } else if (pos > offset) {
 183                         TDEBUG("find_in_tree(%llx): going left\n", offset);
 184                         nitem = item->left;
 185                         pos -= is_a_node(tree, nitem)
 186                                 ? nitem->size + (is_a_node(tree, nitem->right)
 187                                         ? nitem->right->cover_size
 188                                         : 0)
 189                                 : 0;
 190                 } else { assert(pos <= offset && pos + item->size <= offset);
 191                         TDEBUG("find_in_tree(%llx): going right\n", offset);
 192                         nitem = item->right;
 193                         pos += item->size + (is_a_node(tree, nitem) &&
 194                                              is_a_node(tree, nitem->left)
 195                                 ? nitem->left->cover_size
 196                                 : 0);
 197                         /* If we are going far too left, we must return NULL. */
 198                         item = nitem;
 199                 }
 200         }
 201
 202         if (is_a_node(tree, item))
 203                 TDEBUG("find_in_tree(%llx): chosen %llx + %llx\n", offset, pos, item->size);
 204         else
 205                 TDEBUG("find_in_tree(%llx): chosen %llx - but not found\n", offset, pos);
 206
 207         /* TODO: Splay as we go? */
 208         if (is_a_node(tree, item))
 209                 splay(tree, item);
 210
 211         return item;
 212 }
 213
 214 hed_uoff_t
 215 tree_block_offset(struct hed_tree *tree, struct hed_tree_node *item)
 216 {
 217         struct hed_tree_node *up;
 218         hed_uoff_t off;
 219
 220         assert(is_a_node(tree, item));
 221         off = is_a_node(tree, item->left) ? item->left->cover_size : 0;
 222         while (is_a_node(tree, up = item->up)) {
 223                 if (item == up->right)
 224                         off += up->cover_size - item->cover_size;
 225                 item = up;
 226         }
 227         return off;
 228 }
 229
 230 static void
 231 update_parent(struct hed_tree *tree,
 232               struct hed_tree_node *old, struct hed_tree_node *new)
 233 {
 234         new->up = old->up;
 235         if (!is_a_node(tree, new->up)) {
 236                 assert(tree->root == old);
 237                 tree->root = new;
 238         } else {
 239                 if (old->up->left == old) {
 240                         new->up->left = new;
 241                 } else { assert(old->up->right == old);
 242                         new->up->right = new;
 243                 }
 244         }
 245 }
 246
 247 static void
 248 splay(struct hed_tree *tree, struct hed_tree_node *item)
 249 {
 250         struct hed_tree_node *item_mid, *item_top;
 251
 252         assert(is_a_node(tree, item) || item == tree->root);
 253         assert(is_a_node(tree, tree->root) || item == tree->root);
 254
 255         while (item != tree->root) {
 256                 item_top = tree->root;
 257
 258                 if (item->up == item_top) {
 259                         if (item_top->left == item) {
 260                                 item_top->left = item->right;
 261                                 item->right = item_top;
 262                         } else { assert(item_top->right == item);
 263                                 item_top->right = item->left;
 264                                 item->left = item_top;
 265                         }
 266                         recalc_node(tree, item_top);
 267                         recalc_node(tree, item);
 268                         tree->root = item;
 269                         item->up = null_node(tree);
 270                         return;
 271                 }
 272
 273                 /*
 274                 * 'Come on, you slugs!' he cried. 'This is no time for
 275                 * slouching.' He took a step towards them, and even in the
 276                 * gloom he recognized the devices on their shields.
 277                 * 'Deserting, eh?' he snarled. 'Or thinking of it? All your
 278                 * folk should have been inside Udyn before yesterday evening.
 279                 * You know that. Up you get and fall in, or I'll have your
 280                 * numbers and report you.'
 281                 */
 282
 283                 assert(is_a_node(tree, item->up));
 284
 285                 item_mid = item->up; assert(is_a_node(tree, item_mid));
 286                 item_top = item_mid->up; assert(is_a_node(tree, item_top));
 287
 288                 update_parent(tree, item_top, item);
 289                 item_top->up = item;
 290
 291                 if (item_top->left == item_mid &&
 292                     item_mid->left == item) {
 293                         item_mid->left = item->right;
 294                         item->right = item_top;
 295                 } else if (item_top->right == item_mid &&
 296                            item_mid->right == item) {
 297                         /* Inverse operation. */
 298                         item_mid->right = item->left;
 299                         item->left = item_top;
 300                 } else if (item_top->left == item_mid &&
 301                            item_mid->right == item) {
 302                         item_top->left = item->right;
 303                         item->right = item_top;
 304
 305                         item_mid->up = item;
 306                         item_mid->right = item->left;
 307                         item->left = item_mid;
 308                 } else { assert(item_top->right == item_mid &&
 309                                 item_mid->left == item);
 310                         /* Inverse operation. */
 311                         item_top->right = item->left;
 312                         item->left = item_top;
 313
 314                         item_mid->up = item;
 315                         item_mid->left = item->right;
 316                         item->right = item_mid;
 317                 }
 318
 319                 recalc_node(tree, item_mid);
 320                 recalc_node(tree, item_top);
 321                 recalc_node(tree, item);
 322         }
 323 }
 324
 325 static void
 326 unsplay(struct hed_tree *tree, struct hed_tree_node *item)
 327 {
 328         assert(is_a_node(tree, tree->root));
 329
 330         for (;;) {
 331                 struct hed_tree_node *item_down;
 332
 333                 /* TODO: If we kept track of how many items are in each
 334                  * subtree, we could've made an actually inteligent
 335                  * choice. */
 336                 if (is_a_node(tree, item->left)) {
 337                         item_down = item->left;
 338                         item->left = item_down->right;
 339                         item_down->right = item;
 340                 } else if(is_a_node(tree, item->right)) {
 341                         item_down = item->right;
 342                         item->right = item_down->left;
 343                         item_down->left = item;
 344                 } else
 345                         break;
 346
 347                 update_parent(tree, item, item_down);
 348                 item->up = item_down;
 349                 recalc_node(tree, item);
 350                 recalc_node(tree, item_down);
 351         }
 352 }