binaries/src/clustalo/src/clustal/util.c

   1 /* -*- mode: c; tab-width: 4; c-basic-offset: 4;  indent-tabs-mode: nil -*- */
   2
   3 /*********************************************************************
   4  * Clustal Omega - Multiple sequence alignment
   5  *
   6  * Copyright (C) 2010 University College Dublin
   7  *
   8  * Clustal-Omega is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU General Public License as
  10  * published by the Free Software Foundation; either version 2 of the
  11  * License, or (at your option) any later version.
  12  *
  13  * This file is part of Clustal-Omega.
  14  *
  15  ********************************************************************/
  16
  17 /*
  18  *  RCS $Id: util.c 235 2011-04-13 14:13:19Z andreas $
  19  */
  20
  21 #ifdef HAVE_CONFIG_H
  22 #include "config.h"
  23 #endif
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <assert.h>
  29 #include <time.h>
  30
  31 #include "log.h"
  32 #include "util.h"
  33
  34
  35
  36
  37 /* struct for QSortAndTrackIndex and SortAndTrackIndexCmp[Asc|Desc] */
  38 typedef struct {
  39     int piIndex;
  40     int piValue;
  41 } sortwithindex_t;
  42
  43
  44
  45
  46 /**
  47  * @brief Copy of squid's FileExists(). Copied here to make squid independent.
  48  */
  49 int
  50 CheckIfFileExists(char *pcFilename)
  51 {
  52   FILE *prFile;
  53   if ((prFile = fopen(pcFilename, "r"))) {
  54       fclose(prFile);
  55       return TRUE;
  56   }
  57   return FALSE;
  58 }
  59 /* end of CheckIfFileExists */
  60
  61
  62 /**
  63  * @brief Allocates memory (malloc)
  64  *
  65  * @param[in] bytes
  66  * bytes to allocated
  67  * @param[in] function
  68  * calling function name
  69  * @param[in] line
  70  * calling function line
  71  *
  72  * @return void pointer to the newly allocated memory
  73  *
  74  * @note use provided macro CKMALLOC() which automatically adds
  75  * function name and line number
  76  *
  77  */
  78 void *
  79 CkMalloc(size_t bytes, const char *function, const int line)
  80 {
  81     void *ret;
  82
  83     if(NULL == (ret = malloc(bytes * sizeof(char)))) {
  84         Log(&rLog, LOG_FATAL, "Out of memory (requested from %s:%d)\n", function, line);
  85     }
  86
  87     return ret;
  88 }
  89 /***   end: ckmalloc   ***/
  90
  91
  92
  93 /**
  94  * @brief Allocates memory (calloc). Memory will be
  95  * set to zero.
  96  *
  97  * @param[in] count
  98  * Allocate space for count objects
  99  * @param[in] size
 100  * Objects are of this size
 101  * @param[in] function
 102  * calling function name
 103  * @param[in] line
 104  * calling function line
 105  *
 106  * @return void pointer to the newly allocated and zeroed memory (calloc).
 107  *
 108  * @note use provided macro CKCALLOC() which automatically adds
 109  * function name and line number
 110  *
 111  *
 112  */
 113 void *
 114 CkCalloc(size_t count, size_t size, const char *function, const int line)
 115 {
 116     void *ret;
 117
 118     if(NULL == (ret = calloc(count, size))) {
 119         Log(&rLog, LOG_FATAL, "Out of memory (requested from %s:%d)\n",
 120                 function, line);
 121         exit(EXIT_FAILURE);
 122     }
 123
 124     return ret;
 125 }
 126 /***   end: CkCalloc   ***/
 127
 128
 129 /**
 130 * @brief Reallocates memory
 131  *
 132  * @param[in] ptr
 133  * Pointer to memory to be reallocated
 134  * @param[in] bytes
 135  * bytes to allocated
 136  * @param[in] function
 137  * calling function name
 138  * @param[in] line
 139  * calling function line
 140  *
 141  * @return void pointer to the newly allocated memory
 142  *
 143  * @note use provided macro CKREALLOC() which automatically adds
 144  * function name and line number
 145  *
 146  */
 147 void *
 148 CkRealloc(void *ptr, size_t bytes, const char *function, const int line)
 149 {
 150     void *ret=NULL;
 151
 152     if(NULL == (ret = realloc(ptr, bytes))) {
 153         Log(&rLog, LOG_FATAL, "FATAL: Out of memory (requested from %s:%d)\n",
 154                 function, line);
 155     }
 156
 157     return ret;
 158 }
 159 /***   end: ckrealloc   ***/
 160
 161
 162
 163 /**
 164  *
 165  * @brief Frees memory
 166  *
 167  * @param[in] ptr
 168  * Pointer to memory to be freed
 169  * @param[in] function
 170  * calling function name
 171  * @param[in] line
 172  * calling function line
 173  *
 174  * @return void pointer to the now zeroed memory
 175  *
 176  * @note use provided macro CKFREE()
 177  *
 178  */
 179 void *
 180 CkFree(void *ptr, const char *function, const int line)
 181 {
 182     if (ptr == NULL) {
 183         Log(&rLog, LOG_WARN, "Bad call to CkFree from %s:%d (pointer was NULL)\n", function, line);
 184     } else {
 185         free(ptr);
 186         ptr = NULL;
 187     }
 188     return ptr;
 189 }
 190 /***   end: CkFree   ***/
 191
 192
 193
 194
 195 /**
 196  * @brief safe version of strdup
 197  *
 198  * @param[in] src
 199  * String to copy from
 200  *
 201  * @return copy of string
 202  *
 203  * @note src is not allowed to be NULL.
 204  *
 205  */
 206 char *
 207 CkStrdup(const char *src)
 208 {
 209     char *cp;
 210     assert(NULL!=src);
 211
 212     /*cp = strdup(src); always makes trouble... */
 213     cp = (char *) CKMALLOC(strlen(src) +1);
 214     strcpy(cp, src);
 215
 216     return cp;
 217 }
 218 /***   end: CkStrdup   ***/
 219
 220
 221
 222
 223 /**
 224  * @brief Creates an int array of size len with len-1 random but unique
 225  * integers with values 0--len-1. This is "a modified version of
 226  * Fisher-Yates known as Durstenfeld-Fisher-Yates or
 227  * Knuth-Fisher-Yates". See
 228  * http://stackoverflow.com/questions/196017/unique-random-numbers-in-o1
 229  *
 230  * @param[in] perm
 231  * The permutation array. Has to be preallocated
 232  * @param[out] len
 233  * Length of the permutation array
 234  *
 235  */
 236 void
 237 PermutationArray(int **perm, const int len)
 238 {
 239     int max, i;
 240
 241     assert(len>0);
 242
 243     srand((unsigned int) time(0));
 244     (*perm) = (int *) CKMALLOC(len * sizeof(int));
 245     max = len-1;
 246     for (i=0; i<len; i++) {
 247         (*perm)[i] = i;
 248     }
 249
 250     while (max>=0) {
 251         int tmp, randno;
 252         /* randno = addrand((unsigned long) len); / returns 0--n-1 */
 253         randno = (rand()%len);
 254
 255         /* swap */
 256         tmp = (*perm)[randno];
 257         (*perm)[randno] = (*perm)[max];
 258         (*perm)[max] = tmp;
 259
 260         max--;
 261     }
 262     return;
 263 }
 264 /***   end: PermutationArray()   ***/
 265
 266
 267
 268 /**
 269  * @brief Creates an array filled with random, but unique ints of
 270  * given range. Implementation of the Floyd algorithm. See
 271  * http://stackoverflow.com/questions/1608181/unique-random-numbers-in-an-integer-array-in-the-c-programming-language
 272  * Assuming M is the length of the desired array and N is the numeric
 273  * range: "This approach has the complexity of about O(M) (depends on
 274  * the search structure used), so it is better suitable when M << N.
 275  * This approach keeps track of already generated random numbers, so
 276  * it requires extra memory. However, the beauty of it is that it does
 277  * not make any of those horrendous "trial and error" iterations,
 278  * trying to find an unused random number. This algorithm is
 279  * guaranteed to generate one unique random number after each single
 280  * call to the random number generator."
 281  *
 282  * @warning This won't work if max_value<=array_len. Only use for
 283  * cases where array_len<<max_value
 284  *
 285  * @param[in] array
 286  * Preallocated int array whose values will be set
 287  * @param[in] array_len
 288  * Size of array
 289  * @param[in] max_value
 290  *
 291  */
 292 void
 293 RandomUniqueIntArray(int *array, const int array_len, const int max_value)
 294 {
 295     bool *is_used;
 296     int in, im;
 297
 298     assert(array_len<max_value);
 299     srand((unsigned int) time(0));
 300     is_used = (bool *) CKCALLOC(max_value, sizeof(bool));
 301
 302     im = 0;
 303
 304     for (in = max_value - array_len; in < max_value && im < array_len; ++in) {
 305         int r = rand() % (in + 1);
 306         if (is_used[r]==TRUE) {
 307             r = in; /* use 'in' instead of generated number */
 308         }
 309         assert(! is_used[r]);
 310         array[im++] = r;
 311         is_used[r] = TRUE;
 312     }
 313
 314     assert(im == array_len);
 315
 316     free(is_used);
 317
 318     return;
 319 }
 320 /***   end: RandomUniqueIntArray()   ***/
 321
 322
 323
 324 /**
 325  * @brief int comparison function for qsort
 326  *
 327  */
 328 int
 329 IntCmp(const void *a, const void *b)
 330 {
 331     const int *ia = (const int *)a;
 332     const int *ib = (const int *)b;
 333     return *ia  - *ib;
 334 }
 335 /***   end: IntCmp()   ***/
 336
 337
 338
 339
 340
 341 /**
 342  * @brief Compare two sortwithindex_t pointers and return the
 343  * difference between the int value of the 1st sortwithindex_t and the
 344  * 2nd. Used for ascending sort order in QSortWithIndexes()/
 345  *
 346  * @see SortAndTrackIndexCmpDesc() and QSortAndTrackIndex()
 347  */
 348 int
 349 SortAndTrackIndexCmpAsc(const void *a, const void *b)
 350 {
 351     const sortwithindex_t *a_t = (const sortwithindex_t *)a;
 352     const sortwithindex_t *b_t = (const sortwithindex_t *)b;
 353
 354     const int ia = (const int) a_t->piValue;
 355     const int ib = (const int) b_t->piValue;
 356     return ia  - ib;
 357 }
 358 /***   end: SortAndTrackIndexCmpAsc   ***/
 359
 360
 361
 362
 363 /**
 364  * @brief Compare two sortwithindex_t pointers and return the
 365  * difference between the int value of the 2nd sortwithindex_t and the
 366  * 1st. Used for descending sort order in QSortWithIndexes()
 367  *
 368  * @see SortAndTrackIndexCmpDesc() and QSortAndTrackIndex()
 369  */
 370 int
 371 SortAndTrackIndexCmpDesc(const void *a, const void *b)
 372 {
 373     const sortwithindex_t *a_t = (const sortwithindex_t *)a;
 374     const sortwithindex_t *b_t = (const sortwithindex_t *)b;
 375
 376     const int ia = (const int) a_t->piValue;
 377     const int ib = (const int) b_t->piValue;
 378     return ib - ia;
 379 }
 380 /***   end: SortAndTrackIndexCmpDesc   ***/
 381
 382
 383
 384
 385 /**
 386  * @brief Sort a given int array in ascending or descending order,
 387  * while keeping track of the element order.
 388  *
 389  * @param[out] piSortedIndices
 390  * Will contain the indices of the sorted elements. Has to be preallocated.
 391  * @param[out] piArrayToSort
 392  * Array with values to sort. Will only be overwritten if
 393  * bOverwriteArrayToSort it true.
 394  * @param[in] iArrayLen
 395  * Number of elements in piArrayToSort.
 396  * @param[in] cOrder
 397  * Sort order. 'a' for ascending, 'd' for descending.
 398  * @param[in] bOverwriteArrayToSort
 399  * If false do not overwrite the array to sort.
 400  *
 401  */
 402 void
 403 QSortAndTrackIndex(int *piSortedIndices, int *piArrayToSort,
 404                    const int iArrayLen, const char cOrder,
 405                    const bool bOverwriteArrayToSort)
 406 {
 407     int iCtr; /**< aux */
 408
 409     sortwithindex_t *prSort;
 410
 411
 412     assert(NULL!=piSortedIndices);
 413     assert(iArrayLen>0);
 414     assert(NULL!=piArrayToSort);
 415     assert('a'==cOrder || 'd'==cOrder);
 416
 417     prSort = (sortwithindex_t *) CKMALLOC(iArrayLen * sizeof(sortwithindex_t));
 418
 419     for (iCtr=0; iCtr<iArrayLen; iCtr++) {
 420         prSort[iCtr].piIndex = iCtr;
 421         prSort[iCtr].piValue = piArrayToSort[iCtr];
 422 #if 0
 423         LOG_DEBUG("b4 sort: prSort idx %d = val %d",
 424                   prSort[iCtr].piIndex, prSort[iCtr].piValue);
 425 #endif
 426     }
 427
 428     if ('a'==cOrder) {
 429         qsort(prSort, iArrayLen, sizeof(sortwithindex_t), SortAndTrackIndexCmpAsc);
 430     } else if ('d'==cOrder) {
 431         qsort(prSort, iArrayLen, sizeof(sortwithindex_t), SortAndTrackIndexCmpDesc);
 432     } else {
 433         Log(&rLog, LOG_FATAL, "Internal error: unknown order %c", cOrder);
 434     }
 435
 436     for (iCtr=0; iCtr<iArrayLen; iCtr++) {
 437         piSortedIndices[iCtr] = prSort[iCtr].piIndex;
 438
 439         if (bOverwriteArrayToSort) {
 440             piArrayToSort[iCtr] = prSort[iCtr].piValue;
 441         }
 442 #if 0
 443         LOG_DEBUG("after sort: prSort idx %d = val %d",
 444                   prSort[iCtr].piIndex, prSort[iCtr].piValue);
 445 #endif
 446     }
 447     free(prSort);
 448
 449     return;
 450 }
 451 /***   end: QSortWithIndexes()   ***/
 452
 453
 454
 455
 456 /**
 457  * @brief Test if file is writable. File may or may not exist.
 458  *
 459  * @param[in] pcFileName
 460  * Filename to check
 461  *
 462  * @return True if file is writable at the time of calling
 463  *
 464  */
 465 bool
 466 FileIsWritable(char *pcFileName)
 467 {
 468     bool bFileAlreadyExisted;
 469     FILE *prFilePointer;
 470     bool bIsWritable;
 471
 472     if (0 != CheckIfFileExists(pcFileName)) {
 473         bFileAlreadyExisted = TRUE;
 474     } else {
 475         bFileAlreadyExisted = FALSE;
 476     }
 477
 478     if (NULL == (prFilePointer=fopen(pcFileName, "a"))) {
 479         bIsWritable = FALSE;
 480     } else {
 481         bIsWritable = TRUE;
 482         if (0 != fclose(prFilePointer)) {
 483             Log(&rLog, LOG_ERROR, "Couldn't close temporily created file %s. Expect trouble...");
 484         }
 485     }
 486
 487 #if 0
 488     LOG_DEBUG("%s existed?=%d writable=%d", pcFileName,
 489               (TRUE==bFileAlreadyExisted? 1 : 0),
 490               (TRUE==bIsWritable? 1:0));
 491 #endif
 492
 493     /* delete if file didn't exist before and was created here
 494      * temporarily
 495      */
 496     if (FALSE==bFileAlreadyExisted && TRUE==bIsWritable) {
 497         if (0 != remove(pcFileName)) {
 498             Log(&rLog, LOG_ERROR, "Removing of temporarily created file %s failed. Expect trouble...");
 499         }
 500     }
 501     return bIsWritable;
 502 }
 503 /***   end: FileIsWritable()   ***/
 504
 505