emufs/external_sort/bufford.c

   1 /* vim: set noexpandtab tabstop=4 shiftwidth=4 wrap:
   2  *----------------------------------------------------------------------------
   3  *                                  emufs
   4  *----------------------------------------------------------------------------
   5  * This file is part of emufs.
   6  *
   7  * emufs is free software; you can redistribute it and/or modify it under the
   8  * terms of the GNU General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option) any later
  10  * version.
  11  *
  12  * emufs is distributed in the hope that it will be useful, but WITHOUT ANY
  13  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  14  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
  15  * details.
  16  *
  17  * You should have received a copy of the GNU General Public License along
  18  * with emufs; if not, write to the Free Software Foundation, Inc., 59 Temple
  19  * Place, Suite 330, Boston, MA  02111-1307  USA
  20  *----------------------------------------------------------------------------
  21  * Creado:  mié may 26 19:46:31 ART 2004
  22  * Autores: Leandro Lucarella <llucare@fi.uba.ar>
  23  *----------------------------------------------------------------------------
  24  *
  25  * $Id$
  26  *
  27  */
  28
  29 /** \file
  30  *
  31  * Buffer ordenado.
  32  *
  33  * Implementación de un buffer ordenado. Al obtener un dato del buffer, se
  34  * obtiene de forma ordenada.
  35  *
  36  */
  37
  38 #include "bufford.h"
  39 #include <malloc.h>
  40 #include <string.h>
  41 #include <assert.h>
  42
  43 /** Prueba si \c x es menor que \c y usando la función de comparación. */
  44 #define LT(b, x, y) (b->cmp(x, y) < 0)
  45 /** Prueba si \c x es mayor que \c y usando la función de comparación. */
  46 #define GT(b, x, y) (b->cmp(x, y) > 0)
  47 /** Prueba si \c x es igual a \c y usando la función de comparación. */
  48 #define EQ(b, x, y) (b->cmp(x, y) == 0)
  49 /** Prueba si \c x es distinto a \c y usando la función de comparación. */
  50 #define NE(b, x, y) (b->cmp(x, y) != 0)
  51 /** Prueba si \c x es menor o igual a \c y usando la función de comparación. */
  52 #define LE(b, x, y) (b->cmp(x, y) <= 0)
  53 /** Prueba si \c x es mayor o igual a \c y usando la función de comparación. */
  54 #define GE(b, x, y) (b->cmp(x, y) >= 0)
  55
  56 /** Crea un nuevo nodo, se guarda una copia del dato en el nodo. */
  57 static BUFFORD_NODE* bufford_node_new(void* data, size_t reg_size);
  58
  59 /** Borra un nodo, liberando la memoria propia pero no la del dato. */
  60 static void bufford_node_delete(BUFFORD_NODE* node);
  61
  62 /** Borra un nodo del buffer recursivamente, borrando sus hijos también. */
  63 static void bufford_clear_node_recursive(BUFFORD_NODE* node);
  64
  65 /** Inserta un nodo en el buffer sin modificar el tamaño. */
  66 static void bufford_insert_node(BUFFORD* buff, BUFFORD_NODE* new_node);
  67
  68 BUFFORD_NODE* bufford_node_new(void* data, size_t reg_size)
  69 {
  70         BUFFORD_NODE* n = malloc(sizeof(BUFFORD_NODE));
  71         if (!n) return 0;
  72         assert(data);
  73         /* hago una copia del dato */
  74         n->data = malloc(reg_size);
  75         if (n->data) {
  76                 memcpy(n->data, data, reg_size);
  77         } else {
  78                 free(n);
  79                 return 0;
  80         }
  81         n->right = 0;
  82         n->left  = 0;
  83         return n;
  84 }
  85
  86 void bufford_node_delete(BUFFORD_NODE* node)
  87 {
  88         assert(node);
  89         free(node);
  90 }
  91
  92 void bufford_clear_node_recursive(BUFFORD_NODE* node)
  93 {
  94         assert(node);
  95         assert(node->data);
  96         if (node->left)  bufford_clear_node_recursive(node->left);
  97         if (node->right) bufford_clear_node_recursive(node->right);
  98         free(node->data);
  99         bufford_node_delete(node);
 100 }
 101
 102 void bufford_insert_node(BUFFORD* buff, BUFFORD_NODE* new_node)
 103 {
 104         assert(buff);
 105         assert(new_node);
 106         if (buff->root) { /* no está vacío */
 107                 BUFFORD_NODE* curr = buff->root;
 108                 /* tiene algo */
 109                 while (1) {
 110                         if (LT(buff, new_node->data, curr->data)) {
 111                                 if (curr->left) { /* hay más, paso al próximo */
 112                                         curr = curr->left;
 113                                         continue;
 114                                 }
 115                                 /* no hay más, lo inserto */
 116                                 curr->left = new_node;
 117                                 return;
 118                         }
 119                         if (GT(buff, new_node->data, curr->data)) {
 120                                 if (curr->right) { /* hay más, paso al próximo */
 121                                         curr = curr->right;
 122                                         continue;
 123                                 }
 124                                 /* no hay más, lo inserto */
 125                                 curr->right = new_node;
 126                                 return;
 127                         }
 128                         /* es igual! => error */
 129                         assert(NE(buff, new_node->data, curr->data));
 130                         return;
 131                 }
 132         }
 133         /* está vacío */
 134         buff->root = new_node;
 135 }
 136
 137 BUFFORD* bufford_new(size_t size, size_t reg_size, CMP_FUNC cmp)
 138 {
 139         BUFFORD* b = malloc(sizeof(BUFFORD));
 140         if (!b) return 0;
 141         assert(cmp);
 142         assert(size > 0);
 143         assert(reg_size > 0);
 144         b->cmp      = cmp;
 145         b->size     = 0;
 146         b->root     = 0;
 147         b->max_size = size;
 148         b->reg_size = reg_size;
 149         return b;
 150 }
 151
 152 BUFFORD* bufford_new_bytes_size(size_t size, size_t reg_size, CMP_FUNC cmp)
 153 {
 154         BUFFORD* b = malloc(sizeof(BUFFORD));
 155         if (!b) return 0;
 156         assert(cmp);
 157         assert(reg_size > 0);
 158         assert(size > (reg_size + sizeof(BUFFORD_NODE)));
 159         b->cmp      = cmp;
 160         b->size     = 0;
 161         b->root     = 0;
 162         b->max_size = size / (reg_size + sizeof(BUFFORD_NODE));
 163         b->reg_size = reg_size;
 164         return b;
 165 }
 166
 167 void bufford_delete(BUFFORD* buff)
 168 {
 169         assert(buff);
 170         bufford_clear(buff);
 171         free(buff);
 172 }
 173
 174 void bufford_clear(BUFFORD* buff)
 175 {
 176         assert(buff);
 177         if (buff->root) bufford_clear_node_recursive(buff->root);
 178         buff->root = 0;
 179 }
 180
 181 int bufford_full(BUFFORD* buff)
 182 {
 183         assert(buff);
 184         return buff->size == buff->max_size;
 185 }
 186
 187 int bufford_empty(BUFFORD* buff)
 188 {
 189         assert(buff);
 190         return buff->size == 0;
 191 }
 192
 193 int bufford_push(BUFFORD* buff, void* data)
 194 {
 195         BUFFORD_NODE* new_node;
 196         assert(buff);
 197         assert(data);
 198         if (buff->size == buff->max_size) return 0; /* ERROR, está lleno */
 199         new_node = bufford_node_new(data, buff->reg_size);
 200         if (!new_node) return 0; /* ERROR, no hay memoria */
 201         if (buff->root) { /* no está vacío */
 202                 BUFFORD_NODE* curr = buff->root;
 203                 /* tiene algo */
 204                 while (1) {
 205                         if (LT(buff, data, curr->data)) {
 206                                 if (curr->left) { /* hay más, paso al próximo */
 207                                         curr = curr->left;
 208                                         continue;
 209                                 }
 210                                 /* no hay más, lo inserto */
 211                                 curr->left = new_node;
 212                                 buff->size++;
 213                                 return 1; /* OK */
 214                         }
 215                         if (GT(buff, data, curr->data)) {
 216                                 if (curr->right) { /* hay más, paso al próximo */
 217                                         curr = curr->right;
 218                                         continue;
 219                                 }
 220                                 /* no hay más, lo inserto */
 221                                 curr->right = new_node;
 222                                 buff->size++;
 223                                 return 1; /* OK */
 224                         }
 225                         /* es igual! => error */
 226                         free(new_node);
 227                         assert(NE(buff, data, curr->data));
 228                         return 0; /* ERROR, dato duplicado */
 229                 }
 230         }
 231         /* está vacío */
 232         buff->root = new_node;
 233         buff->size++;
 234         return 1; /* OK */
 235 }
 236
 237 void* bufford_pop_min(BUFFORD* buff)
 238 {
 239         /* nodo iterador */
 240         BUFFORD_NODE* curr = buff->root;
 241         /* nodo previo al iterador */
 242         BUFFORD_NODE* prev = 0;
 243         /* valor mínimo encontrado, si se encontró */
 244         void* min_found = 0;
 245         assert(buff);
 246         if (!curr) return 0; /* si no hay nodos, no hay nada que hacer */
 247         /* buscamos el mínimo nodo */
 248         while (curr->left) {
 249                 prev = curr;
 250                 curr = curr->left;
 251         }
 252         /* lo sacamos del árbol */
 253         if (prev) { /* si tiene padre (no es el raíz) */
 254                 /* le cuelgo de la izquierda el hijo de la derecha, sabemos que a
 255                  * izquierda no tiene nada.*/
 256                 prev->left = curr->right;
 257         } else { /* si es el raíz */
 258                 buff->root = curr->right; /* ponemos el nuevo raíz */
 259         }
 260         min_found = curr->data;
 261         bufford_node_delete(curr);
 262         buff->size--;
 263         return min_found;
 264 }
 265
 266 void* bufford_pop_next(BUFFORD* buff, void* min)
 267 {
 268         /* nodo iterador */
 269         BUFFORD_NODE* curr = buff->root;
 270         /* nodo previo al iterador */
 271         BUFFORD_NODE* prev = 0;
 272         /* nodo con el dato más pequeño encontrado hasta ahora */
 273         BUFFORD_NODE* curr_min = 0;
 274         /* padre del nodo con el dato más pequeño encontrado hasta ahora */
 275         BUFFORD_NODE* padre = 0;
 276         /* valor mínimo encontrado, si se encontró */
 277         void* min_found = 0;
 278         assert(buff);
 279         assert(min);
 280         /* buscamos el mínimo nodo mayor que 'min' */
 281         while (curr) {
 282                 if (GT(buff, curr->data, min)) { /* actual mayor que buscado */
 283                         /* guardo y paso al de la izquierda */
 284                         curr_min = curr;
 285                         padre = prev;
 286                         prev = curr;
 287                         curr = curr->left;
 288                 } else { /* actual no es mayor que buscado, paso a derecha */
 289                         prev = curr;
 290                         curr = curr->right;
 291                 }
 292         }
 293         /* si encontramos uno, lo sacamos del árbol */
 294         if (curr_min) {
 295                 BUFFORD_NODE* link; /* nodo al cual enganchar con el padre */
 296                 BUFFORD_NODE* orphan = 0; /* nodo huerfano */
 297                 if (curr_min->left) {
 298                         link = curr_min->left;
 299                         orphan = curr_min->right;
 300                 } else {
 301                         link = curr_min->right;
 302                 }
 303                 if (padre) { /* si tiene padre (no es el raíz) */
 304                         if (padre->left == curr_min) { /* si es el de la izq */
 305                                 padre->left = link; /* enganchamos */
 306                         } else { /* si no, es el de la derecha */
 307                                 padre->right = link; /* enganchamos */
 308                         }
 309                 } else { /* si es el raíz */
 310                         buff->root = link; /* ponemos el nuevo raíz */
 311                 }
 312                 if (orphan) { /* si quedó un huerfano, lo insertamos */
 313                         bufford_insert_node(buff, orphan);
 314                 }
 315                 min_found = curr_min->data;
 316                 bufford_node_delete(curr_min);
 317                 buff->size--;
 318         }
 319         return min_found;
 320 }
 321
 322 void* bufford_get_min(BUFFORD* buff)
 323 {
 324         /* nodo iterador */
 325         BUFFORD_NODE* curr = buff->root;
 326         assert(buff);
 327         if (!curr) return 0; /* si no hay nodos, no hay nada que hacer */
 328         /* buscamos el mínimo nodo */
 329         while (curr->left) curr = curr->left;
 330         return curr->data;
 331 }
 332
 333 void* bufford_get_next(BUFFORD* buff, void* min)
 334 {
 335         /* nodo iterador */
 336         BUFFORD_NODE* curr = buff->root;
 337         /* nodo con el dato más pequeño encontrado hasta ahora */
 338         BUFFORD_NODE* curr_min = 0;
 339         assert(buff);
 340         assert(min);
 341         /* buscamos el mínimo nodo mayor que 'min' */
 342         while (curr) {
 343                 if (GT(buff, curr->data, min)) { /* actual mayor que buscado */
 344                         /* guardo y paso al de la izquierda */
 345                         curr_min = curr;
 346                         curr = curr->left;
 347                 } else curr = curr->right; /* paso a la derecha */
 348         }
 349         if (curr_min) return curr_min->data;
 350         return 0;
 351 }
 352