binaries/src/tcoffee/t_coffee_source/hsearch.c

   1
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <math.h>
   5 #include <stdarg.h>
   6
   7
   8 #include "io_lib_header.h"
   9 #include "util_lib_header.h"
  10 #include "define_header.h"
  11
  12 HaschT * hcreate ( int n_elements,struct Hasch_data * declare_data(struct Hasch_entry *), struct Hasch_data *free_data(struct Hasch_data *) )
  13        {
  14          HaschT *T;
  15          int a;
  16
  17          n_elements=n_elements*2+1;
  18
  19          T=vcalloc ( 1, sizeof (HaschT));
  20          T->ne=n_elements;
  21          T->p=vcalloc (n_elements,sizeof ( Hasch_entry*));
  22          for ( a=0; a<n_elements; a++)
  23            {
  24              T->p[a]=allocate_hasch_entry(NULL,DECLARE,declare_data, free_data);
  25            }
  26          return T;
  27        }
  28 HaschT *hdestroy (HaschT *T,struct Hasch_data * declare_data(struct Hasch_entry *), struct Hasch_data *free_data(struct Hasch_data *) )
  29
  30
  31        {
  32          int a;
  33          Hasch_entry *p, *pp;
  34
  35          if ( T==NULL)return NULL;
  36
  37          for (a=0; a< T->ne; a++)
  38            {
  39              p=T->p[a];
  40              while (p)
  41                {
  42                  pp=p;
  43                  p=p->n;
  44                  allocate_hasch_entry(pp,FREE, declare_data, free_data);
  45                }
  46            }
  47          vfree (T->p);
  48          vfree ( T);
  49          return NULL;
  50        }
  51
  52
  53 Hasch_entry* hsearch (HaschT *T, int k, int action, struct Hasch_data * declare_data(struct Hasch_entry *), struct Hasch_data *free_data(struct Hasch_data *) )
  54
  55
  56        {
  57          /*action: FIND,ADD, REMOVE*/
  58          Hasch_entry *p, *pi;
  59          int h;
  60
  61
  62
  63          /* find the key: k->h*/
  64
  65          h=k%T->ne;
  66
  67
  68          if ( action==ADD || action==FIND)
  69            {
  70              p=pi=T->p[h];
  71              while (p && p->k!=k){p=p->n;}
  72              if (action==ADD && !p)
  73               {
  74                 p=insert_hasch_entry_in_list (pi, NULL, NULL, declare_data, free_data);
  75                 p->k=k;
  76               }
  77             else if (action==FIND && !p)p=NULL;
  78             return p;
  79            }
  80          else if ( action==REMOVE)
  81            {
  82              allocate_hasch_entry(hsearch ( T, k, FIND, declare_data, free_data), FREE, declare_data, free_data);
  83              return NULL;
  84            }
  85        return NULL;
  86        }
  87
  88
  89 Hasch_entry * extract_hasch_entry_from_list (Hasch_entry *e, struct Hasch_data * declare_data(struct Hasch_entry *), struct Hasch_data *free_data(struct Hasch_data *) )
  90
  91
  92   {
  93     /*extracts entry e and returns p, or next if is NULL*/
  94     Hasch_entry *p=NULL, *n=NULL;
  95
  96     if (!e);
  97     else
  98       {
  99         p=e->p;
 100         n=e->n;
 101
 102         if (p)p->n=n;
 103         if (n)n->p=p;
 104         e->p=e->n=NULL;
 105       }
 106     return e;
 107   }
 108
 109 Hasch_entry * insert_hasch_entry_in_list (Hasch_entry *p, Hasch_entry *e, Hasch_entry *n, struct Hasch_data * declare_data(struct Hasch_entry *), struct Hasch_data *free_data(struct Hasch_data *) )
 110
 111
 112 {
 113     /*inserts entry e between entry p and entry n and returns e*/
 114
 115     if (!e)e=allocate_hasch_entry (NULL,DECLARE, declare_data, free_data);
 116
 117
 118
 119     if (!p && !n);
 120     else if ( !p)p=n->p;
 121     else if ( !n)n=p->n;
 122
 123     e->p=p;
 124     if (p)p->n=e;
 125
 126     e->n=n;
 127     if (n)n->p=e;
 128
 129     return e;
 130   }
 131
 132 Hasch_entry * allocate_hasch_entry (Hasch_entry *e, int action,struct Hasch_data * declare_data(struct Hasch_entry *), struct Hasch_data *free_data(struct Hasch_data *) )
 133
 134
 135 {
 136     static Hasch_entry *s;
 137     Hasch_entry *ns;
 138
 139     if ( !s)s=vcalloc ( 1, sizeof (Hasch_entry));
 140
 141     if ( action==DECLARE)
 142       {
 143         ns=s->p;
 144         e=extract_hasch_entry_from_list (s, declare_data, free_data);
 145         if ( e->free_data)(e->free_data)(e->data);
 146         e->declare_data=declare_data;
 147         e->free_data=free_data;
 148         e->declare_data (e);
 149         e->k=UNDEFINED;
 150         s=ns;
 151       }
 152     else if ( action==FREE)
 153       {
 154         extract_hasch_entry_from_list (e,declare_data, free_data );
 155         e->k=UNDEFINED;
 156         if ( e->free_data)e->data=(e->free_data)(e->data);
 157         e->free_data=NULL;
 158         e->declare_data=NULL;
 159         s=insert_hasch_entry_in_list (s, e, NULL, declare_data, free_data);
 160
 161       }
 162     else if ( action==FREE_STACK)
 163       {
 164         while (s)
 165           {
 166             e=s->p;
 167             allocate_hasch_entry (s, FREE, declare_data,free_data);
 168             vfree (s);
 169             s=e;
 170           }
 171       }
 172     else crash ("Unknown MODE for allocate_hasch_entry\n");
 173     return e;
 174   }
 175
 176 /*********************************************************************/
 177 /*                                                                   */
 178 /*                         Get string key                                   */
 179 /*                                                                   */
 180 /*                                                                   */
 181 /*********************************************************************/
 182
 183
 184 int string2key (char *s, Char_node *n)
 185 {
 186   static Char_node *root;
 187
 188   if ( !root)root=declare_char_node (DECLARE);
 189
 190   if ( n==NULL && s==NULL)
 191     {
 192       declare_char_node (FREE_STACK);
 193     }
 194   else if (n==NULL)
 195     {
 196       return string2key(s, root);
 197     }
 198   else if ( s[0]=='\0')
 199     {
 200       return n->key;
 201     }
 202   else
 203     {
 204       return string2key(s+1, (n->c[(int)s[0]])?(n->c[(int)s[0]]):(n->c[(int)s[0]]=declare_char_node (DECLARE)));
 205     }
 206   return 0;
 207 }
 208
 209 Char_node * declare_char_node (int action)
 210 {
 211 static struct Char_node **heap;
 212 static int heap_size, free_heap, a;
 213 static int key;
 214  if ( action==DECLARE)
 215     {
 216       if ( free_heap==0)
 217         {
 218           free_heap=100;
 219
 220           heap=vrealloc (heap,(heap_size+free_heap)*sizeof (struct Char_node *));
 221           for ( a=heap_size; a<heap_size+free_heap; a++)
 222             {
 223               (heap[a])=vcalloc ( 1, sizeof ( struct Char_node));
 224               (heap[a])->c=vcalloc ( 256, sizeof (Char_node*));
 225               (heap[a])->key=key++;
 226             }
 227           heap_size+=free_heap;
 228         }
 229       return heap[heap_size-(free_heap--)];
 230     }
 231   else if ( action==FREE_STACK)
 232     {
 233       for (a=0; a< heap_size; a++)
 234         {
 235           heap[a]->key=key++;
 236           vfree ( heap[a]->c);
 237           (heap[a])->c=vcalloc ( 256, sizeof (Char_node*));
 238         }
 239       free_heap=heap_size;
 240       return NULL;
 241     }
 242   return NULL;
 243 }
 244
 245 /* old declare_char_node (too hungry)
 246 Char_node * declare_char_node (int action)
 247 {
 248   static int key;
 249   Char_node *cn;
 250   static Char_node *root;
 251
 252   if ( action==DECLARE)
 253     {
 254       cn=vcalloc (1, sizeof (Char_node));
 255       cn->key=++key;
 256       cn->c=vcalloc (256, sizeof (Char_node *));
 257
 258       }
 259   return cn;
 260 }
 261 */
 262 /******************************COPYRIGHT NOTICE*******************************/
 263 /*© Centro de Regulacio Genomica */
 264 /*and */
 265 /*Cedric Notredame */
 266 /*Fri Feb 18 08:27:45 CET 2011 - Revision 596. */
 267 /*All rights reserved.*/
 268 /*This file is part of T-COFFEE.*/
 269 /**/
 270 /*    T-COFFEE is free software; you can redistribute it and/or modify*/
 271 /*    it under the terms of the GNU General Public License as published by*/
 272 /*    the Free Software Foundation; either version 2 of the License, or*/
 273 /*    (at your option) any later version.*/
 274 /**/
 275 /*    T-COFFEE is distributed in the hope that it will be useful,*/
 276 /*    but WITHOUT ANY WARRANTY; without even the implied warranty of*/
 277 /*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the*/
 278 /*    GNU General Public License for more details.*/
 279 /**/
 280 /*    You should have received a copy of the GNU General Public License*/
 281 /*    along with Foobar; if not, write to the Free Software*/
 282 /*    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA*/
 283 /*...............................................                                                                                      |*/
 284 /*  If you need some more information*/
 285 /*  cedric.notredame@europe.com*/
 286 /*...............................................                                                                                                                                     |*/
 287 /**/
 288 /**/
 289 /*      */
 290 /******************************COPYRIGHT NOTICE*******************************/