Logo Search packages:      
Sourcecode: maqview version File versions  Download package

btree.c

#include <stdlib.h>
#include "btree.h"

BTree* btree_init(){
      BTree *tree;
      tree = (BTree*)malloc(sizeof(BTree));
      tree->parent = NULL;
      tree->size   = 0;
      tree->childs = NULL;
      tree->left   = 0;
      tree->right  = 0;
      tree->indexs[0] = tree->indexs[1] = 0;
      return tree;
}

void _trim_tree(BTree *tree){
      int i;
      if(tree->childs){
            if(tree->size < BTREE_MAX_NODES){
                  tree->childs = (BTree**)realloc(tree->childs, sizeof(BTree*) * tree->size);
            }
            for(i=0;i<tree->size;i++) _trim_tree(tree->childs[i]);
      }
}

/**
 * Return last node
 */
BTree* btree_append(BTree **root, BTree *last_node, int *layer_ref, int64_t index, int64_t value){
      BTree *tree, *node, *n;
      int i, layer;
      layer = *layer_ref;
      node = last_node;
      if(value == node->right){
            node->size ++;
            node->indexs[1] = index;
            return node;
      } else if(value < node->right){
            fprintf(stderr, "** Value appended to BTree was not sorted(ASC), ignored %ld (%ld) at %s:%d\n", value, node->right, __FILE__, __LINE__);
            return node;
      }
      if(node->size < BTREE_MAX_ELEMENTS){
            node->size ++;
            node->indexs[1] = index;
            n = node;
            for(i=1;i<=layer;i++){
                  n->right = value;
                  n = n->parent;
            }
            return node;
      }
      for(i=1;i<layer;i++){
            node = node->parent;
            if(node->size < BTREE_MAX_NODES){
                  break;
            }
      }
      if(i == layer){
            layer ++;
            tree = btree_init();
            tree->childs = (BTree**)malloc(sizeof(BTree*) * BTREE_MAX_NODES);
            tree->childs[0] = node;
            tree->size = 1;
            tree->left = node->left;
            node->parent = tree;
            node = tree;
            *root = tree;
            *layer_ref = layer;
      }
      for(;i>1;i--){
            n = btree_init();
            n->left = value;
            n->childs = (BTree**)malloc(sizeof(BTree*) * BTREE_MAX_NODES);
            n->parent = node;
            node->childs[node->size++] = n;
            node = n;
      }
      n = btree_init();
      n->left  = value;
      n->right = value;
      n->indexs[0] = index;
      n->indexs[1] = index;
      n->size   = 1;
      n->parent = node;
      node->childs[node->size++] = n;
      node = n;
      for(i=1;i<=layer;i++){
            n->right = value;
            n = n->parent;
      }
      return node;
}

BTree* btree_build(int (*get_next)(void *obj, int64_t last_index, int64_t *value), void *obj){
      int i, layer;
      int64_t index;
      int64_t value;
      BTree *tree, *node, *n;
      tree = btree_init();
      node = tree;
      index = 0;
      layer = 1;
      if(get_next(obj, index, &value)){
            node->left = node->right = value;
            node->indexs[0] = node->indexs[1] = index;
            node->size ++;
      } else {
            return NULL;
      }
      while(get_next(obj, index, &value)){
            index ++;
            if(value != node->right && node->size >= BTREE_MAX_ELEMENTS){
                  for(i=1;i<layer;i++){
                        node = node->parent;
                        if(node->size < BTREE_MAX_NODES){
                              break;
                        }
                  }
                  if(i == layer){
                        layer ++;
                        tree = btree_init();
                        tree->childs = (BTree**)malloc(sizeof(BTree*) * BTREE_MAX_NODES);
                        tree->childs[0] = node;
                        tree->size = 1;
                        tree->left = node->left;
                        node->parent = tree;
                        node = tree;
                  }
                  for(;i>1;i--){
                        n = btree_init();
                        n->left = value;
                        n->childs = (BTree**)malloc(sizeof(BTree*) * BTREE_MAX_NODES);
                        n->parent = node;
                        node->childs[node->size++] = n;
                        node = n;
                  }
                  n = btree_init();
                  n->left  = value;
                  n->right = value - 1;
                  n->indexs[0] = index;
                  n->parent = node;
                  node->childs[node->size++] = n;
                  node = n;
            }
            node->indexs[1] = index;
            if(node->right != value){
                  node->size ++;
                  node->right = value;
                  n = node;
                  for(i=1;i<=layer;i++){
                        n->right = value;
                        n = n->parent;
                  }
            }
      }
//    _trim_tree(tree);
      return tree;
}

int64_t _get_min_index(BTree *tree){
      while(tree->childs){
            tree = tree->childs[0];
      }
      return tree->indexs[0];
}

int64_t _get_max_index(BTree *tree){
      while(tree->childs){
            tree = tree->childs[tree->size-1];
      }
      return tree->indexs[1];
}

/**
 * left : the index of element that no more than value
 * right: the index + 1 of element that no less than value
 * RETURN true, if find, visa verse
 */
BTree* btree_find(BTree *tree, int64_t value, int64_t *left, int64_t *right){
      int i;
      if(value < tree->left){
            *left = _get_min_index(tree);
            *right = *left;
            return NULL;
      }
      if(value > tree->right){
            *left = _get_max_index(tree);
            *right = *left;
            return NULL;
      }
      while(tree->childs){
            for(i=0;i<tree->size;i++){
                  if(value <= tree->childs[i]->right) break;
            }
            if(i == tree->size) return NULL;
            if(value < tree->childs[i]->left){
                  *right = _get_min_index(tree->childs[i]);
                  while(1){
                        if(i){
                              *left  = _get_max_index(tree->childs[i-1]);
                              break;
                        } else {
                              for(i=0;i<tree->parent->size;i++){
                                    if(tree == tree->parent->childs[i]) break;
                              }
                              tree = tree->parent;
                        }
                  }
                  return NULL;
            }
            tree = tree->childs[i];
      }
      *left  = tree->indexs[0];
      *right = tree->indexs[1];
      return tree;
}

int btree_dump_core(FILE *out, BTree *tree){
      int i, n;
      unsigned char ch;
      ch = (tree->childs != NULL);
      fwrite(&ch, 1, 1, out);
      fwrite(&tree->left, sizeof(int64_t), 1, out);
      fwrite(&tree->right, sizeof(int64_t), 1, out);
      fwrite(tree->indexs, sizeof(int64_t), 2, out);
      fwrite(&tree->size, sizeof(int), 1, out);
      n = 1;
      if(tree->childs){
            for(i=0;i<tree->size;i++){
                  n += btree_dump_core(out, tree->childs[i]);
            }
      }
      return n;
}

int btree_dump(FILE *out, BTree *tree){
      int n;
      if(tree == NULL){
            n = 2; // Write signal 2 in output
            fwrite(&n, 1, 1, out);
            fflush(out);
            return 1;
      }
      n = btree_dump_core(out, tree);
      fflush(out);
      return n;
}

int btree_dump_gz_core(gzFile out, BTree *tree){
      int i, n;
      unsigned char ch;
      ch = (tree->childs != NULL);
      gzwrite(out, &ch, 1);
      gzwrite(out, &tree->left, sizeof(int64_t));
      gzwrite(out, &tree->right, sizeof(int64_t));
      gzwrite(out, tree->indexs, 2 * sizeof(int64_t));
      gzwrite(out, &tree->size, sizeof(int));
      n = 1;
      if(ch){
            for(i=0;i<tree->size;i++){
                  n += btree_dump_gz_core(out, tree->childs[i]);
            }
      }
      return n;
}

int btree_dump_gz(gzFile out, BTree *tree){
      int n;
      if(tree == NULL){
            n = 2; // Write signal 2 in output
            gzwrite(out, &n, 1);
            return 1;
      }
      n = btree_dump_gz_core(out, tree);
      return n;
}

BTree* btree_load(FILE *in){
      BTree *tree, *node;
      int i;
      unsigned char ch;
      tree = (BTree*)malloc(sizeof(BTree));
      tree->parent = NULL;
      fread(&ch, 1, 1, in);
      // Empty tree read, signal 2
      if(ch == 2){
            tree->left  = 0;
            tree->right = 0;
            tree->size  = 0;
            tree->indexs[0] = -1;
            tree->indexs[1] = -1;
            tree->childs    = NULL;
            return tree;
      }
      fread(&tree->left, sizeof(int64_t), 1, in);
      fread(&tree->right, sizeof(int64_t), 1, in);
      fread(tree->indexs, sizeof(int64_t), 2, in);
      fread(&tree->size, sizeof(int), 1, in);
      if(ch){
            tree->childs = (BTree**)malloc(sizeof(BTree*) * tree->size);
            for(i=0;i<tree->size;i++){
                  node = btree_load(in);
                  node->parent = tree;
                  tree->childs[i] = node;
            }
      } else {
            tree->childs = NULL;
      }
      return tree;
}

BTree* btree_load_gz(gzFile in){
      BTree *tree, *node;
      int i;
      unsigned char ch;
      tree = (BTree*)malloc(sizeof(BTree));
      tree->parent = NULL;
      gzread(in, &ch, 1);
      // Empty tree read, signal 2
      if(ch == 2){
            tree->left  = 0;
            tree->right = 0;
            tree->size  = 0;
            tree->indexs[0] = -1;
            tree->indexs[1] = -1;
            tree->childs    = NULL;
            return tree;
      }
      gzread(in, &tree->left, sizeof(int64_t));
      gzread(in, &tree->right, sizeof(int64_t));
      gzread(in, tree->indexs, 2 * sizeof(int64_t));
      gzread(in, &tree->size, sizeof(int));
      if(ch){
            tree->childs = (BTree**)malloc(sizeof(BTree*) * tree->size);
            for(i=0;i<tree->size;i++){
                  node = btree_load_gz(in);
                  node->parent = tree;
                  tree->childs[i] = node;
            }
      } else {
            tree->childs = NULL;
      }
      return tree;
}

void btree_free(BTree *tree){
      int i;
      if(tree == NULL) return;
      if(tree->childs){
            for(i=0;i<tree->size;i++) btree_free(tree->childs[i]);
            free(tree->childs);
      }
      free(tree);
}

#ifdef MAIN_BTREE

int main(){
      int i, l, r, layer;
      FILE *file;
      BTree *tree, *node;
      tree = btree_init();
      node = tree;
      layer = 1;
      node->left = node->right = 0;
      node->indexs[0] = node->indexs[1] = 0;
      node->size ++;
      for(i=1;i<10240;i++){
            node = btree_append(&tree, node, &layer, i, i);
      }
      if(btree_find(tree, 1234, &l, &r)){
            printf("%d is between %d and %d\n", 1234, l, r);
      } else {
            printf("Error\n");
      }
      file = fopen("test.idx", "w+");
      if(file == NULL) perror("FILE OPEN FAILED");
      btree_dump(file, tree);
      btree_free(tree);
      fseek(file, 0, SEEK_SET);
      tree = btree_load(file);
      fclose(file);
      if(btree_find(tree, 1234, &l, &r)){
            printf("%d is between %d and %d\n", 1234, l, r);
      } else {
            printf("Error\n");
      }
      btree_free(tree);
      return 0;
}


#endif

Generated by  Doxygen 1.6.0   Back to index