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 "base.h"
  39 #include "bufford.h"
  40 #include <malloc.h>
  41 #include <string.h>
  42 #include <assert.h>
  43
  44 /** Crea un nuevo nodo, se guarda una copia del dato en el nodo. */
  45 static BUFFORD_NODE* bufford_node_new(void* data, size_t reg_size);
  46
  47 /** Borra un nodo, liberando la memoria propia pero no la del dato. */
  48 static void bufford_node_delete(BUFFORD_NODE* node);
  49
  50 /** Borra un nodo del buffer recursivamente, borrando sus hijos también. */
  51 static void bufford_clear_node_recursive(BUFFORD_NODE* node);
  52
  53 /** Inserta un nodo en el buffer sin modificar el tamaño. */
  54 static void bufford_insert_node(BUFFORD* buff, BUFFORD_NODE* new_node);
  55
  56 BUFFORD_NODE* bufford_node_new(void* data, size_t reg_size)
  57 {
  58         BUFFORD_NODE* n = malloc(sizeof(BUFFORD_NODE));
  59         if (!n) return 0;
  60         assert(data);
  61         /* hago una copia del dato */
  62         n->data = malloc(reg_size);
  63         if (n->data) {
  64                 memcpy(n->data, data, reg_size);
  65         } else {
  66                 free(n);
  67                 return 0;
  68         }
  69         n->right = 0;
  70         n->left  = 0;
  71         return n;
  72 }
  73
  74 void bufford_node_delete(BUFFORD_NODE* node)
  75 {
  76         assert(node);
  77         free(node);
  78 }
  79
  80 void bufford_clear_node_recursive(BUFFORD_NODE* node)
  81 {
  82         assert(node);
  83         assert(node->data);
  84         if (node->left)  bufford_clear_node_recursive(node->left);
  85         if (node->right) bufford_clear_node_recursive(node->right);
  86         free(node->data);
  87         bufford_node_delete(node);
  88 }
  89
  90 void bufford_insert_node(BUFFORD* buff, BUFFORD_NODE* new_node)
  91 {
  92         assert(buff);
  93         assert(new_node);
  94         if (buff->root) { /* no está vacío */
  95                 BUFFORD_NODE* curr = buff->root;
  96                 /* tiene algo */
  97                 while (1) {
  98                         if (LT(buff, new_node->data, curr->data)) {
  99                                 if (curr->left) { /* hay más, paso al próximo */
 100                                         curr = curr->left;
 101                                         continue;
 102                                 }
 103                                 /* no hay más, lo inserto */
 104                                 curr->left = new_node;
 105                                 return;
 106                         }
 107                         if (GT(buff, new_node->data, curr->data)) {
 108                                 if (curr->right) { /* hay más, paso al próximo */
 109                                         curr = curr->right;
 110                                         continue;
 111                                 }
 112                                 /* no hay más, lo inserto */
 113                                 curr->right = new_node;
 114                                 return;
 115                         }
 116                         /* es igual! => error */
 117                         assert(NE(buff, new_node->data, curr->data));
 118                         return;
 119                 }
 120         }
 121         /* está vacío */
 122         buff->root = new_node;
 123 }
 124
 125 BUFFORD* bufford_new(size_t size, size_t reg_size, CMP_FUNC cmp)
 126 {
 127         BUFFORD* b = malloc(sizeof(BUFFORD));
 128         if (!b) return 0;
 129         assert(cmp);
 130         assert(size > 0);
 131         assert(reg_size > 0);
 132         b->cmp      = cmp;
 133         b->size     = 0;
 134         b->root     = 0;
 135         b->max_size = size;
 136         b->reg_size = reg_size;
 137         return b;
 138 }
 139
 140 BUFFORD* bufford_new_bytes_size(size_t size, size_t reg_size, CMP_FUNC cmp)
 141 {
 142         BUFFORD* b = malloc(sizeof(BUFFORD));
 143         if (!b) return 0;
 144         assert(cmp);
 145         assert(reg_size > 0);
 146         assert(size > (reg_size + sizeof(BUFFORD_NODE)));
 147         b->cmp      = cmp;
 148         b->size     = 0;
 149         b->root     = 0;
 150         b->max_size = size / (reg_size + sizeof(BUFFORD_NODE));
 151         b->reg_size = reg_size;
 152         return b;
 153 }
 154
 155 void bufford_delete(BUFFORD* buff)
 156 {
 157         assert(buff);
 158         bufford_clear(buff);
 159         free(buff);
 160 }
 161
 162 void bufford_clear(BUFFORD* buff)
 163 {
 164         assert(buff);
 165         if (buff->root) bufford_clear_node_recursive(buff->root);
 166         buff->root = 0;
 167 }
 168
 169 int bufford_full(BUFFORD* buff)
 170 {
 171         assert(buff);
 172         return buff->size == buff->max_size;
 173 }
 174
 175 int bufford_empty(BUFFORD* buff)
 176 {
 177         assert(buff);
 178         return buff->size == 0;
 179 }
 180
 181 int bufford_push(BUFFORD* buff, void* data)
 182 {
 183         BUFFORD_NODE* new_node;
 184         assert(buff);
 185         assert(data);
 186         if (buff->size == buff->max_size) return 0; /* ERROR, está lleno */
 187         new_node = bufford_node_new(data, buff->reg_size);
 188         if (!new_node) return 0; /* ERROR, no hay memoria */
 189         if (buff->root) { /* no está vacío */
 190                 BUFFORD_NODE* curr = buff->root;
 191                 /* tiene algo */
 192                 while (1) {
 193                         if (LT(buff, data, curr->data)) {
 194                                 if (curr->left) { /* hay más, paso al próximo */
 195                                         curr = curr->left;
 196                                         continue;
 197                                 }
 198                                 /* no hay más, lo inserto */
 199                                 curr->left = new_node;
 200                                 buff->size++;
 201                                 return 1; /* OK */
 202                         }
 203                         if (GT(buff, data, curr->data)) {
 204                                 if (curr->right) { /* hay más, paso al próximo */
 205                                         curr = curr->right;
 206                                         continue;
 207                                 }
 208                                 /* no hay más, lo inserto */
 209                                 curr->right = new_node;
 210                                 buff->size++;
 211                                 return 1; /* OK */
 212                         }
 213                         /* es igual! => error */
 214                         free(new_node);
 215                         assert(NE(buff, data, curr->data));
 216                         return 0; /* ERROR, dato duplicado */
 217                 }
 218         }
 219         /* está vacío */
 220         buff->root = new_node;
 221         buff->size++;
 222         return 1; /* OK */
 223 }
 224
 225 void* bufford_pop_min(BUFFORD* buff)
 226 {
 227         /* nodo iterador */
 228         BUFFORD_NODE* curr = buff->root;
 229         /* nodo previo al iterador */
 230         BUFFORD_NODE* prev = 0;
 231         /* valor mínimo encontrado, si se encontró */
 232         void* min_found = 0;
 233         assert(buff);
 234         if (!curr) return 0; /* si no hay nodos, no hay nada que hacer */
 235         /* buscamos el mínimo nodo */
 236         while (curr->left) {
 237                 prev = curr;
 238                 curr = curr->left;
 239         }
 240         /* lo sacamos del árbol */
 241         if (prev) { /* si tiene padre (no es el raíz) */
 242                 /* le cuelgo de la izquierda el hijo de la derecha, sabemos que a
 243                  * izquierda no tiene nada.*/
 244                 prev->left = curr->right;
 245         } else { /* si es el raíz */
 246                 buff->root = curr->right; /* ponemos el nuevo raíz */
 247         }
 248         min_found = curr->data;
 249         bufford_node_delete(curr);
 250         buff->size--;
 251         return min_found;
 252 }
 253
 254 void* bufford_pop_next(BUFFORD* buff, void* min)
 255 {
 256         /* nodo iterador */
 257         BUFFORD_NODE* curr = buff->root;
 258         /* nodo previo al iterador */
 259         BUFFORD_NODE* prev = 0;
 260         /* nodo con el dato más pequeño encontrado hasta ahora */
 261         BUFFORD_NODE* curr_min = 0;
 262         /* padre del nodo con el dato más pequeño encontrado hasta ahora */
 263         BUFFORD_NODE* padre = 0;
 264         /* valor mínimo encontrado, si se encontró */
 265         void* min_found = 0;
 266         assert(buff);
 267         assert(min);
 268         /* buscamos el mínimo nodo mayor que 'min' */
 269         while (curr) {
 270                 if (GT(buff, curr->data, min)) { /* actual mayor que buscado */
 271                         /* guardo y paso al de la izquierda */
 272                         curr_min = curr;
 273                         padre = prev;
 274                         prev = curr;
 275                         curr = curr->left;
 276                 } else { /* actual no es mayor que buscado, paso a derecha */
 277                         prev = curr;
 278                         curr = curr->right;
 279                 }
 280         }
 281         /* si encontramos uno, lo sacamos del árbol */
 282         if (curr_min) {
 283                 BUFFORD_NODE* link; /* nodo al cual enganchar con el padre */
 284                 BUFFORD_NODE* orphan = 0; /* nodo huerfano */
 285                 if (curr_min->left) {
 286                         link = curr_min->left;
 287                         orphan = curr_min->right;
 288                 } else {
 289                         link = curr_min->right;
 290                 }
 291                 if (padre) { /* si tiene padre (no es el raíz) */
 292                         if (padre->left == curr_min) { /* si es el de la izq */
 293                                 padre->left = link; /* enganchamos */
 294                         } else { /* si no, es el de la derecha */
 295                                 padre->right = link; /* enganchamos */
 296                         }
 297                 } else { /* si es el raíz */
 298                         buff->root = link; /* ponemos el nuevo raíz */
 299                 }
 300                 if (orphan) { /* si quedó un huerfano, lo insertamos */
 301                         bufford_insert_node(buff, orphan);
 302                 }
 303                 min_found = curr_min->data;
 304                 bufford_node_delete(curr_min);
 305                 buff->size--;
 306         }
 307         return min_found;
 308 }
 309
 310 void* bufford_get_min(BUFFORD* buff)
 311 {
 312         /* nodo iterador */
 313         BUFFORD_NODE* curr = buff->root;
 314         assert(buff);
 315         if (!curr) return 0; /* si no hay nodos, no hay nada que hacer */
 316         /* buscamos el mínimo nodo */
 317         while (curr->left) curr = curr->left;
 318         return curr->data;
 319 }
 320
 321 void* bufford_get_next(BUFFORD* buff, void* min)
 322 {
 323         /* nodo iterador */
 324         BUFFORD_NODE* curr = buff->root;
 325         /* nodo con el dato más pequeño encontrado hasta ahora */
 326         BUFFORD_NODE* curr_min = 0;
 327         assert(buff);
 328         assert(min);
 329         /* buscamos el mínimo nodo mayor que 'min' */
 330         while (curr) {
 331                 if (GT(buff, curr->data, min)) { /* actual mayor que buscado */
 332                         /* guardo y paso al de la izquierda */
 333                         curr_min = curr;
 334                         curr = curr->left;
 335                 } else curr = curr->right; /* paso a la derecha */
 336         }
 337         if (curr_min) return curr_min->data;
 338         return 0;
 339 }
 340