gcc/testsuite/go.test/test/bench/k-nucleotide.c

   1 /*
   2 Redistribution and use in source and binary forms, with or without
   3 modification, are permitted provided that the following conditions are met:
   4
   5     * Redistributions of source code must retain the above copyright
   6     notice, this list of conditions and the following disclaimer.
   7
   8     * Redistributions in binary form must reproduce the above copyright
   9     notice, this list of conditions and the following disclaimer in the
  10     documentation and/or other materials provided with the distribution.
  11
  12     * Neither the name of "The Computer Language Benchmarks Game" nor the
  13     name of "The Computer Language Shootout Benchmarks" nor the names of
  14     its contributors may be used to endorse or promote products derived
  15     from this software without specific prior written permission.
  16
  17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  18 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20 ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  21 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  22 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  23 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  24 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  25 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  26 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  27 POSSIBILITY OF SUCH DAMAGE.
  28 */
  29
  30 #include <stdio.h>
  31 #include <string.h>
  32 #include <ctype.h>
  33 #include <stdlib.h>
  34 #include <glib.h>
  35
  36 typedef struct stat_s stat_t;
  37 struct stat_s
  38 {
  39    const gchar *key;
  40    long stat;
  41 };
  42
  43 #define MAX_ELM (8192 / sizeof (stat_t))
  44
  45 static int
  46 generate_frequencies (int fl, char *buffer, long buflen,
  47                       GHashTable *ht, GTrashStack **ts, GPtrArray *roots, GStringChunk *sc)
  48 {
  49    gchar *key;
  50    long i;
  51
  52    if (fl > buflen) return 0;
  53    if (fl == 0) return 0;
  54
  55    for (i = 0; i < buflen - fl + 1; ++i)
  56      {
  57         char nulled;
  58         stat_t *stat;
  59
  60         nulled = buffer[i + fl];
  61         buffer[i + fl] = '\0';
  62
  63         key = g_string_chunk_insert_const(sc, buffer + i);
  64
  65         stat = g_hash_table_lookup(ht, key);
  66         if (!stat)
  67           {
  68              stat = g_trash_stack_pop(ts);
  69              if (!stat)
  70                {
  71                   int j;
  72
  73                   stat = malloc(sizeof (stat_t) * MAX_ELM);
  74                   g_ptr_array_add(roots, stat);
  75
  76                   for (j = 1; j < MAX_ELM; ++j)
  77                     g_trash_stack_push(ts, stat + j);
  78                }
  79              stat->stat = 1;
  80              stat->key = key;
  81
  82              g_hash_table_insert(ht, key, stat);
  83           }
  84         else
  85           stat->stat++;
  86
  87         buffer[i + fl] = nulled;
  88      }
  89
  90    return buflen - fl + 1;
  91 }
  92
  93 static int
  94 cmp_func(gconstpointer a, gconstpointer b)
  95 {
  96    const stat_t *left = a;
  97    const stat_t *right = b;
  98
  99    return right->stat - left->stat;
 100 }
 101
 102 static void
 103 sorted_list(gpointer key, gpointer value, gpointer user_data)
 104 {
 105    stat_t *data = value;
 106    GList **lst = user_data;
 107
 108    *lst = g_list_insert_sorted(*lst, data, cmp_func);
 109 }
 110
 111 static void
 112 display_stat(gpointer data, gpointer user_data)
 113 {
 114    long *total = user_data;
 115    stat_t *st = data;
 116
 117    printf("%s %.3f\n", st->key, 100 * (float) st->stat / *total);
 118 }
 119
 120 void
 121 write_frequencies (int fl, char *buffer, long buflen, GTrashStack **ts, GPtrArray *roots)
 122 {
 123    GStringChunk *sc;
 124    GHashTable *ht;
 125    GList *lst;
 126    long total;
 127
 128    ht = g_hash_table_new_full(g_str_hash, g_str_equal, NULL /* free key */, NULL /* free value */);
 129    sc = g_string_chunk_new(buflen);
 130    lst = NULL;
 131
 132    total = generate_frequencies (fl, buffer, buflen, ht, ts, roots, sc);
 133
 134    if (!total) goto on_error;
 135
 136    g_hash_table_foreach(ht, sorted_list, &lst);
 137    g_list_foreach(lst, display_stat, &total);
 138    g_list_free(lst);
 139
 140  on_error:
 141    g_hash_table_destroy(ht);
 142    g_string_chunk_free(sc);
 143 }
 144
 145 void
 146 write_count (char *searchFor, char *buffer, long buflen, GTrashStack **ts, GPtrArray *roots)
 147 {
 148    GStringChunk *sc;
 149    GHashTable *ht;
 150    stat_t *result;
 151    GList *lst;
 152    long total;
 153    long fl;
 154
 155    fl = strlen(searchFor);
 156
 157    ht = g_hash_table_new_full(g_str_hash, g_str_equal, NULL /* free key */, NULL /* free value */);
 158    sc = g_string_chunk_new(buflen);
 159    lst = NULL;
 160    result = NULL;
 161
 162    total = generate_frequencies (fl, buffer, buflen, ht, ts, roots, sc);
 163
 164    if (!total) goto on_error;
 165
 166    result = g_hash_table_lookup(ht, searchFor);
 167
 168  on_error:
 169    printf("%ld\t%s\n", result ? result->stat : 0, searchFor);
 170
 171    g_hash_table_destroy(ht);
 172    g_string_chunk_free(sc);
 173 }
 174
 175 int
 176 main ()
 177 {
 178    char buffer[4096];
 179    GTrashStack *ts;
 180    GPtrArray *roots;
 181    GString *stuff;
 182    gchar *s;
 183    int len;
 184
 185    roots = g_ptr_array_new();
 186    ts = NULL;
 187
 188    while (fgets(buffer, sizeof (buffer), stdin))
 189      if (strncmp(buffer, ">THREE", 6) == 0)
 190        break;
 191
 192    stuff = g_string_new(NULL);
 193
 194    while (fgets(buffer, sizeof (buffer), stdin))
 195      {
 196         size_t sz;
 197
 198         if (buffer[0] == '>')
 199           break;
 200
 201         sz = strlen(buffer);
 202         if (buffer[sz - 1] == '\n')
 203           --sz;
 204
 205         stuff = g_string_append_len(stuff, buffer, sz);
 206      }
 207
 208    stuff = g_string_ascii_up(stuff);
 209    len = stuff->len;
 210    s = g_string_free(stuff, FALSE);
 211
 212    write_frequencies(1, s, len, &ts, roots);
 213    printf("\n");
 214    write_frequencies(2, s, len, &ts, roots);
 215    printf("\n");
 216    write_count("GGT", s, len, &ts, roots);
 217    write_count("GGTA", s, len, &ts, roots);
 218    write_count("GGTATT", s, len, &ts, roots);
 219    write_count("GGTATTTTAATT", s, len, &ts, roots);
 220    write_count("GGTATTTTAATTTATAGT", s, len, &ts, roots);
 221
 222    free(s);
 223
 224    g_ptr_array_foreach(roots, free, NULL);
 225    g_ptr_array_free(roots, TRUE);
 226
 227    return 0;
 228 }