emufs/external_sort/bufford.c

   1
   2 #include "bufford.h"
   3 #include <malloc.h>
   4 #include <string.h>
   5 #include <assert.h>
   6
   7 #define LT(b, x, y) (b->cmp(x, y) < 0)
   8 #define GT(b, x, y) (b->cmp(x, y) > 0)
   9 #define EQ(b, x, y) (b->cmp(x, y) == 0)
  10 #define NE(b, x, y) (b->cmp(x, y) != 0)
  11 #define LE(b, x, y) (b->cmp(x, y) <= 0)
  12 #define GE(b, x, y) (b->cmp(x, y) >= 0)
  13
  14 static BUFFORD_NODE* bufford_node_new(void* data, size_t reg_size);
  15
  16 static void bufford_node_delete(BUFFORD_NODE* node);
  17
  18 static void bufford_clear_node_recursive(BUFFORD_NODE* node);
  19
  20 static void bufford_insert_node(BUFFORD* buff, BUFFORD_NODE* new_node);
  21
  22 BUFFORD_NODE* bufford_node_new(void* data, size_t reg_size)
  23 {
  24         BUFFORD_NODE* n = malloc(sizeof(BUFFORD_NODE));
  25         if (!n) return 0;
  26         assert(data);
  27         /* hago una copia del dato */
  28         n->data = malloc(reg_size);
  29         if (n->data) {
  30                 memcpy(n->data, data, reg_size);
  31         } else {
  32                 free(n);
  33                 return 0;
  34         }
  35         n->right = 0;
  36         n->left  = 0;
  37         return n;
  38 }
  39
  40 void bufford_node_delete(BUFFORD_NODE* node)
  41 {
  42         assert(node);
  43         free(node);
  44 }
  45
  46 void bufford_clear_node_recursive(BUFFORD_NODE* node)
  47 {
  48         assert(node);
  49         assert(node->data);
  50         if (node->left)  bufford_clear_node_recursive(node->left);
  51         if (node->right) bufford_clear_node_recursive(node->right);
  52         free(node->data);
  53         bufford_node_delete(node);
  54 }
  55
  56 void bufford_insert_node(BUFFORD* buff, BUFFORD_NODE* new_node)
  57 {
  58         assert(buff);
  59         assert(new_node);
  60         if (buff->root) { /* no está vacío */
  61                 BUFFORD_NODE* curr = buff->root;
  62                 /* tiene algo */
  63                 while (1) {
  64                         if (LT(buff, new_node->data, curr->data)) {
  65                                 if (curr->left) { /* hay más, paso al próximo */
  66                                         curr = curr->left;
  67                                         continue;
  68                                 }
  69                                 /* no hay más, lo inserto */
  70                                 curr->left = new_node;
  71                                 return;
  72                         }
  73                         if (GT(buff, new_node->data, curr->data)) {
  74                                 if (curr->right) { /* hay más, paso al próximo */
  75                                         curr = curr->right;
  76                                         continue;
  77                                 }
  78                                 /* no hay más, lo inserto */
  79                                 curr->right = new_node;
  80                                 return;
  81                         }
  82                         /* es igual! => error */
  83                         assert(NE(buff, new_node->data, curr->data));
  84                         return;
  85                 }
  86         }
  87         /* está vacío */
  88         buff->root = new_node;
  89 }
  90
  91 BUFFORD* bufford_new(size_t size, size_t reg_size, CMP_FUNC cmp)
  92 {
  93         BUFFORD* b = malloc(sizeof(BUFFORD));
  94         if (!b) return 0;
  95         assert(cmp);
  96         assert(reg_size > 0);
  97         assert(size > reg_size);
  98         b->cmp      = cmp;
  99         b->size     = 0;
 100         b->root     = 0;
 101         b->max_size = size / reg_size;
 102         b->reg_size = reg_size;
 103         return b;
 104 }
 105
 106 void bufford_delete(BUFFORD* buff)
 107 {
 108         assert(buff);
 109         bufford_clear(buff);
 110         free(buff);
 111 }
 112
 113 void bufford_clear(BUFFORD* buff)
 114 {
 115         assert(buff);
 116         if (buff->root) bufford_clear_node_recursive(buff->root);
 117         buff->root = 0;
 118 }
 119
 120 int bufford_full(BUFFORD* buff)
 121 {
 122         assert(buff);
 123         return buff->size == buff->max_size;
 124 }
 125
 126 int bufford_empty(BUFFORD* buff)
 127 {
 128         assert(buff);
 129         return buff->size == 0;
 130 }
 131
 132 int bufford_push(BUFFORD* buff, void* data)
 133 {
 134         BUFFORD_NODE* new_node;
 135         assert(buff);
 136         assert(data);
 137         if (buff->size == buff->max_size) return 0; /* ERROR, está lleno */
 138         new_node = bufford_node_new(data, buff->reg_size);
 139         if (!new_node) return 0; /* ERROR, no hay memoria */
 140         if (buff->root) { /* no está vacío */
 141                 BUFFORD_NODE* curr = buff->root;
 142                 /* tiene algo */
 143                 while (1) {
 144                         if (LT(buff, data, curr->data)) {
 145                                 if (curr->left) { /* hay más, paso al próximo */
 146                                         curr = curr->left;
 147                                         continue;
 148                                 }
 149                                 /* no hay más, lo inserto */
 150                                 curr->left = new_node;
 151                                 buff->size++;
 152                                 return 1; /* OK */
 153                         }
 154                         if (GT(buff, data, curr->data)) {
 155                                 if (curr->right) { /* hay más, paso al próximo */
 156                                         curr = curr->right;
 157                                         continue;
 158                                 }
 159                                 /* no hay más, lo inserto */
 160                                 curr->right = new_node;
 161                                 buff->size++;
 162                                 return 1; /* OK */
 163                         }
 164                         /* es igual! => error */
 165                         free(new_node);
 166                         assert(NE(buff, data, curr->data));
 167                         return 0; /* ERROR, dato duplicado */
 168                 }
 169         }
 170         /* está vacío */
 171         buff->root = new_node;
 172         buff->size++;
 173         return 1; /* OK */
 174 }
 175
 176 void* bufford_pop(BUFFORD* buff, void* min)
 177 {
 178         /* nodo iterador */
 179         BUFFORD_NODE* curr = buff->root;
 180         /* nodo previo al iterador */
 181         BUFFORD_NODE* prev = 0;
 182         /* nodo con el dato más pequeño encontrado hasta ahora */
 183         BUFFORD_NODE* curr_min = 0;
 184         /* padre del nodo con el dato más pequeño encontrado hasta ahora */
 185         BUFFORD_NODE* padre = 0;
 186         /* valor mínimo encontrado, si se encontró */
 187         void* min_found = 0;
 188         assert(buff);
 189         assert(min);
 190         /* buscamos el mínimo nodo mayor que 'min' */
 191         while (curr) {
 192                 if (GT(buff, curr->data, min)) { /* actual mayor que buscado */
 193                         /* guardo y paso al de la izquierda */
 194                         curr_min = curr;
 195                         padre = prev;
 196                         prev = curr;
 197                         curr = curr->left;
 198                 } else { /* actual no es mayor que buscado, paso a derecha */
 199                         prev = curr;
 200                         curr = curr->right;
 201                 }
 202         }
 203         /* si encontramos uno, lo sacamos del árbol */
 204         if (curr_min) {
 205                 BUFFORD_NODE* link; /* nodo al cual enganchar con el padre */
 206                 BUFFORD_NODE* orphan = 0; /* nodo huerfano */
 207                 if (curr_min->left) {
 208                         link = curr_min->left;
 209                         orphan = curr_min->right;
 210                 } else {
 211                         link = curr_min->right;
 212                 }
 213                 if (padre) { /* si tiene padre (no es el raíz) */
 214                         if (padre->left == curr_min) { /* si es el de la izq */
 215                                 padre->left = link; /* enganchamos */
 216                         } else { /* si no, es el de la derecha */
 217                                 padre->right = link; /* enganchamos */
 218                         }
 219                 } else { /* si es el raíz */
 220                         buff->root = link; /* ponemos el nuevo raíz */
 221                 }
 222                 if (orphan) { /* si quedó un huerfano, lo insertamos */
 223                         bufford_insert_node(buff, orphan);
 224                 }
 225                 min_found = curr_min->data;
 226                 bufford_node_delete(curr_min);
 227                 buff->size--;
 228         }
 229         return min_found;
 230 }
 231
 232 void* bufford_pop_min(BUFFORD* buff)
 233 {
 234         /* nodo iterador */
 235         BUFFORD_NODE* curr = buff->root;
 236         /* nodo previo al iterador */
 237         BUFFORD_NODE* prev = 0;
 238         /* valor mínimo encontrado, si se encontró */
 239         void* min_found = 0;
 240         assert(buff);
 241         if (!curr) return 0; /* si no hay nodos, no hay nada que hacer */
 242         /* buscamos el mínimo nodo */
 243         while (curr->left) {
 244                 prev = curr;
 245                 curr = curr->left;
 246         }
 247         /* lo sacamos del árbol */
 248         if (prev) { /* si tiene padre (no es el raíz) */
 249                 /* le cuelgo de la izquierda el hijo de la derecha, sabemos que a
 250                  * izquierda no tiene nada.*/
 251                 prev->left = curr->right;
 252         } else { /* si es el raíz */
 253                 buff->root = curr->right; /* ponemos el nuevo raíz */
 254         }
 255         min_found = curr->data;
 256         bufford_node_delete(curr);
 257         buff->size--;
 258         return min_found;
 259 }
 260
 261 void* bufford_get_min(BUFFORD* buff)
 262 {
 263         /* nodo iterador */
 264         BUFFORD_NODE* curr = buff->root;
 265         assert(buff);
 266         if (!curr) return 0; /* si no hay nodos, no hay nada que hacer */
 267         /* buscamos el mínimo nodo */
 268         while (curr->left) curr = curr->left;
 269         return curr->data;
 270 }
 271
 272 void* bufford_get_next(BUFFORD* buff, void* min)
 273 {
 274         /* nodo iterador */
 275         BUFFORD_NODE* curr = buff->root;
 276         /* nodo con el dato más pequeño encontrado hasta ahora */
 277         BUFFORD_NODE* curr_min = 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                         curr = curr->left;
 286                 } else curr = curr->right; /* paso a la derecha */
 287         }
 288         if (curr_min) return curr_min->data;
 289         return 0;
 290 }
 291