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: tipo1.c 548 2004-05-28 22:44:27Z llucare $
  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(reg_size > 0);
 143         assert(size > reg_size);
 144         b->cmp      = cmp;
 145         b->size     = 0;
 146         b->root     = 0;
 147         b->max_size = size / reg_size;
 148         b->reg_size = reg_size;
 149         return b;
 150 }
 151
 152 void bufford_delete(BUFFORD* buff)
 153 {
 154         assert(buff);
 155         bufford_clear(buff);
 156         free(buff);
 157 }
 158
 159 void bufford_clear(BUFFORD* buff)
 160 {
 161         assert(buff);
 162         if (buff->root) bufford_clear_node_recursive(buff->root);
 163         buff->root = 0;
 164 }
 165
 166 int bufford_full(BUFFORD* buff)
 167 {
 168         assert(buff);
 169         return buff->size == buff->max_size;
 170 }
 171
 172 int bufford_empty(BUFFORD* buff)
 173 {
 174         assert(buff);
 175         return buff->size == 0;
 176 }
 177
 178 int bufford_push(BUFFORD* buff, void* data)
 179 {
 180         BUFFORD_NODE* new_node;
 181         assert(buff);
 182         assert(data);
 183         if (buff->size == buff->max_size) return 0; /* ERROR, está lleno */
 184         new_node = bufford_node_new(data, buff->reg_size);
 185         if (!new_node) return 0; /* ERROR, no hay memoria */
 186         if (buff->root) { /* no está vacío */
 187                 BUFFORD_NODE* curr = buff->root;
 188                 /* tiene algo */
 189                 while (1) {
 190                         if (LT(buff, data, curr->data)) {
 191                                 if (curr->left) { /* hay más, paso al próximo */
 192                                         curr = curr->left;
 193                                         continue;
 194                                 }
 195                                 /* no hay más, lo inserto */
 196                                 curr->left = new_node;
 197                                 buff->size++;
 198                                 return 1; /* OK */
 199                         }
 200                         if (GT(buff, data, curr->data)) {
 201                                 if (curr->right) { /* hay más, paso al próximo */
 202                                         curr = curr->right;
 203                                         continue;
 204                                 }
 205                                 /* no hay más, lo inserto */
 206                                 curr->right = new_node;
 207                                 buff->size++;
 208                                 return 1; /* OK */
 209                         }
 210                         /* es igual! => error */
 211                         free(new_node);
 212                         assert(NE(buff, data, curr->data));
 213                         return 0; /* ERROR, dato duplicado */
 214                 }
 215         }
 216         /* está vacío */
 217         buff->root = new_node;
 218         buff->size++;
 219         return 1; /* OK */
 220 }
 221
 222 void* bufford_pop_min(BUFFORD* buff)
 223 {
 224         /* nodo iterador */
 225         BUFFORD_NODE* curr = buff->root;
 226         /* nodo previo al iterador */
 227         BUFFORD_NODE* prev = 0;
 228         /* valor mínimo encontrado, si se encontró */
 229         void* min_found = 0;
 230         assert(buff);
 231         if (!curr) return 0; /* si no hay nodos, no hay nada que hacer */
 232         /* buscamos el mínimo nodo */
 233         while (curr->left) {
 234                 prev = curr;
 235                 curr = curr->left;
 236         }
 237         /* lo sacamos del árbol */
 238         if (prev) { /* si tiene padre (no es el raíz) */
 239                 /* le cuelgo de la izquierda el hijo de la derecha, sabemos que a
 240                  * izquierda no tiene nada.*/
 241                 prev->left = curr->right;
 242         } else { /* si es el raíz */
 243                 buff->root = curr->right; /* ponemos el nuevo raíz */
 244         }
 245         min_found = curr->data;
 246         bufford_node_delete(curr);
 247         buff->size--;
 248         return min_found;
 249 }
 250
 251 void* bufford_pop_next(BUFFORD* buff, void* min)
 252 {
 253         /* nodo iterador */
 254         BUFFORD_NODE* curr = buff->root;
 255         /* nodo previo al iterador */
 256         BUFFORD_NODE* prev = 0;
 257         /* nodo con el dato más pequeño encontrado hasta ahora */
 258         BUFFORD_NODE* curr_min = 0;
 259         /* padre del nodo con el dato más pequeño encontrado hasta ahora */
 260         BUFFORD_NODE* padre = 0;
 261         /* valor mínimo encontrado, si se encontró */
 262         void* min_found = 0;
 263         assert(buff);
 264         assert(min);
 265         /* buscamos el mínimo nodo mayor que 'min' */
 266         while (curr) {
 267                 if (GT(buff, curr->data, min)) { /* actual mayor que buscado */
 268                         /* guardo y paso al de la izquierda */
 269                         curr_min = curr;
 270                         padre = prev;
 271                         prev = curr;
 272                         curr = curr->left;
 273                 } else { /* actual no es mayor que buscado, paso a derecha */
 274                         prev = curr;
 275                         curr = curr->right;
 276                 }
 277         }
 278         /* si encontramos uno, lo sacamos del árbol */
 279         if (curr_min) {
 280                 BUFFORD_NODE* link; /* nodo al cual enganchar con el padre */
 281                 BUFFORD_NODE* orphan = 0; /* nodo huerfano */
 282                 if (curr_min->left) {
 283                         link = curr_min->left;
 284                         orphan = curr_min->right;
 285                 } else {
 286                         link = curr_min->right;
 287                 }
 288                 if (padre) { /* si tiene padre (no es el raíz) */
 289                         if (padre->left == curr_min) { /* si es el de la izq */
 290                                 padre->left = link; /* enganchamos */
 291                         } else { /* si no, es el de la derecha */
 292                                 padre->right = link; /* enganchamos */
 293                         }
 294                 } else { /* si es el raíz */
 295                         buff->root = link; /* ponemos el nuevo raíz */
 296                 }
 297                 if (orphan) { /* si quedó un huerfano, lo insertamos */
 298                         bufford_insert_node(buff, orphan);
 299                 }
 300                 min_found = curr_min->data;
 301                 bufford_node_delete(curr_min);
 302                 buff->size--;
 303         }
 304         return min_found;
 305 }
 306
 307 void* bufford_get_min(BUFFORD* buff)
 308 {
 309         /* nodo iterador */
 310         BUFFORD_NODE* curr = buff->root;
 311         assert(buff);
 312         if (!curr) return 0; /* si no hay nodos, no hay nada que hacer */
 313         /* buscamos el mínimo nodo */
 314         while (curr->left) curr = curr->left;
 315         return curr->data;
 316 }
 317
 318 void* bufford_get_next(BUFFORD* buff, void* min)
 319 {
 320         /* nodo iterador */
 321         BUFFORD_NODE* curr = buff->root;
 322         /* nodo con el dato más pequeño encontrado hasta ahora */
 323         BUFFORD_NODE* curr_min = 0;
 324         assert(buff);
 325         assert(min);
 326         /* buscamos el mínimo nodo mayor que 'min' */
 327         while (curr) {
 328                 if (GT(buff, curr->data, min)) { /* actual mayor que buscado */
 329                         /* guardo y paso al de la izquierda */
 330                         curr_min = curr;
 331                         curr = curr->left;
 332                 } else curr = curr->right; /* paso a la derecha */
 333         }
 334         if (curr_min) return curr_min->data;
 335         return 0;
 336 }
 337