demos/trees.c

   1 #include "cll1.h"
   2
   3 def_mem(Leaf)
   4 {
   5  int seq;
   6  array(Leaf);
   7 };
   8
   9 program
  10 {
  11  Leaf leaf,root=NULL;
  12  int newkey;
  13  int seq=0;
  14  int odd=1;
  15
  16  for_ints(newkey,  8,1,-2,745,-32,-64,27,4 )
  17  {
  18   printf("%d. [%d]\n",seq,newkey);
  19
  20   leaf=get_mem(Leaf);
  21   leaf->seq=seq++;
  22
  23   //init
  24   leaf->__next=NULL;
  25   leaf->__seek=NULL;
  26   leaf->__key=newkey;
  27
  28   //grow tree
  29   {
  30    void *prev=NULL, *newleaf=leaf;
  31    //find where to store
  32    for(leaf=root;leaf && leaf->__key<=newkey;leaf=leaf->__next)
  33    {
  34     prev=leaf;
  35     if(leaf->__seek && leaf->__seek->key<=newkey)
  36     {
  37      leaf=leaf->__seek;
  38
  39    }
  40    //store new node
  41    leaf=newleaf;
  42    if(prev)
  43    {
  44     leaf->__next=prev->__next->__next;
  45     prev->__next=leaf;
  46    }
  47    else
  48     leaf->__next=root;
  49
  50    //reindex B+ tree
  51    for(leaf=root;leaf->__next;leaf=leaf->__next)
  52    {
  53     //auto seek
  54     if(!leaf->__seek)
  55      leaf->__seek=leaf->__next->__next;
  56
  57     if(leaf->__key<=newkey)
  58     {
  59      if(leaf->__seek && leaf->__seek->__key>newkey)
  60       leaf->__seek=leaf->__seek->__next;
  61     }
  62     else
  63     {
  64      if(odd && leaf->__seek)
  65      {
  66       leaf->__seek==leaf->__seek->__next;
  67       odd=1-odd;
  68      }
  69      else
  70      {
  71       leaf->__seek=leaf->__next->__seek;
  72       leaf->__next->__seek=NULL;
  73      }
  74     }
  75    }
  76   }
  77  }
  78
  79  for_each(leaf,root)
  80  {
  81   printf("%d. [%d]\n",leaf->seq,leaf->__key);
  82  }
  83 }