git.cworth.org Git - mnemon/blob - mnemon.c

   1 /*
   2  * Copyright © 2006 Carl Worth
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License as published by
   6  * the Free Software Foundation; either version 2, or (at your option)
   7  * any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software Foundation,
  16  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
  17  */
  18
  19 /* for asprintf */
  20 #define _GNU_SOURCE
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <stdarg.h>
  24 #include <stdint.h>
  25
  26 #include <sys/types.h>
  27 #include <dirent.h>
  28 #include <errno.h>
  29 #include <string.h>
  30 #include <assert.h>
  31
  32 #include <readline/readline.h>
  33 #include <readline/history.h>
  34
  35 typedef int bool_t;
  36
  37 typedef struct _item {
  38     int count;
  39     char *challenge;
  40     char *response;
  41 } item_t;
  42
  43 typedef struct _bin {
  44     int count;
  45     int items_size;
  46     int num_items;
  47     item_t **items;
  48 } bin_t;
  49
  50 typedef struct _category {
  51     char *name;
  52     int items_size;
  53     int num_items;
  54     item_t *items;
  55 } category_t;
  56
  57 typedef struct _mnemon {
  58     char *dir_name;
  59
  60     int categories_size;
  61     int num_categories;
  62     category_t *categories;
  63
  64     int bins_size;
  65     int num_bins;
  66     bin_t *bins;
  67 } mnemon_t;
  68
  69 static void *
  70 xmalloc (size_t size)
  71 {
  72     void *ret;
  73
  74     ret = malloc (size);
  75     if (ret == NULL) {
  76         fprintf (stderr, "Error: out of memory\n");
  77         exit (1);
  78     }
  79
  80     return ret;
  81 }
  82
  83 static void *
  84 xrealloc (void *ptr, size_t size)
  85 {
  86     void *ret;
  87
  88     ret = realloc (ptr, size);
  89     if (ret == NULL) {
  90         fprintf (stderr, "Error: out of memory\n");
  91         exit (1);
  92     }
  93
  94     return ret;
  95 }
  96
  97 static char *
  98 xstrdup (const char *s)
  99 {
 100     char *ret;
 101
 102     ret = strdup (s);
 103     if (s == NULL) {
 104         fprintf (stderr, "Error: out of memory\n");
 105         exit (1);
 106     }
 107
 108     return ret;
 109 }
 110
 111 static void
 112 xasprintf (char **strp, const char *fmt, ...)
 113 {
 114     va_list ap;
 115     int ret;
 116
 117     va_start (ap, fmt);
 118     ret = vasprintf (strp, fmt, ap);
 119     va_end (ap);
 120
 121     if (ret < 0) {
 122         fprintf (stderr, "Error: out of memory\n");
 123         exit (1);
 124     }
 125 }
 126
 127 static void
 128 item_init (item_t       *item,
 129            int           count,
 130            const char   *challenge,
 131            const char   *response)
 132 {
 133     item->count = count;
 134
 135     item->challenge = xmalloc (strlen (challenge) + 1 +
 136                                strlen (response) + 1);
 137     item->response = item->challenge + strlen (challenge) + 1;
 138
 139     strcpy (item->challenge, challenge);
 140     strcpy (item->response, response);
 141 }
 142
 143 static void
 144 item_fini (item_t *item)
 145 {
 146     /* item->response shares allocation with item->challenge, so
 147      * doesn't require a separate call to free */
 148     free (item->challenge);
 149 }
 150
 151 static void
 152 category_init (category_t *category,
 153                const char *name)
 154 {
 155     category->name = xstrdup (name);
 156
 157     category->items_size = 0;
 158     category->num_items = 0;
 159     category->items = NULL;
 160 }
 161
 162 static void
 163 category_fini (category_t *category)
 164 {
 165     int i;
 166
 167     for (i = 0; i < category->num_items; i++)
 168         item_fini (&category->items[i]);
 169
 170     free (category->items);
 171
 172     free (category->name);
 173 }
 174
 175 static void
 176 category_grow (category_t *category)
 177 {
 178     if (category->items_size)
 179         category->items_size *= 2;
 180     else
 181         category->items_size = 1;
 182
 183     category->items = xrealloc (category->items,
 184                                 category->items_size * sizeof (item_t));
 185 }
 186
 187 static item_t *
 188 category_add_item (category_t   *category,
 189                    int           count,
 190                    const char   *challenge,
 191                    const char   *response)
 192 {
 193     item_t *item;
 194
 195     if (category->num_items == category->items_size)
 196         category_grow (category);
 197
 198     item = &category->items[category->num_items++];
 199
 200     item_init (item, count, challenge, response);
 201
 202     return item;
 203 }
 204
 205 static void
 206 category_print (category_t      *category,
 207                 FILE            *file)
 208 {
 209     int i;
 210     item_t *item;
 211
 212     for (i = 0; i < category->num_items; i++) {
 213         item = &category->items[i];
 214         if (i != 0)
 215             fprintf (file, "\n");
 216         fprintf (file, "%d\n%s\n%s\n",
 217                  item->count,
 218                  item->challenge,
 219                  item->response);
 220     }
 221 }
 222
 223 static void
 224 bin_init (bin_t *bin,
 225           int    count)
 226 {
 227     bin->count = count;
 228
 229     bin->items_size = 0;
 230     bin->num_items = 0;
 231     bin->items = NULL;
 232 }
 233
 234 static void
 235 bin_fini (bin_t *bin)
 236 {
 237     free (bin->items);
 238 }
 239
 240 static void
 241 bin_grow (bin_t *bin)
 242 {
 243     if (bin->items_size)
 244         bin->items_size *= 2;
 245     else
 246         bin->items_size = 1;
 247
 248     bin->items = xrealloc (bin->items,
 249                            bin->items_size * sizeof (item_t*));
 250 }
 251
 252 static void
 253 bin_add_item (bin_t     *bin,
 254               item_t    *item)
 255 {
 256     assert (item->count == bin->count);
 257
 258     if (bin->num_items == bin->items_size)
 259         bin_grow (bin);
 260
 261     bin->items[bin->num_items++] = item;
 262 }
 263
 264 static void
 265 bin_remove_item (bin_t  *bin,
 266                  int     item_index)
 267 {
 268     /* Replace the current item with the last item, (no need to shift
 269      * any more than that since we don't care about the order of the
 270      * items within a bin). */
 271     bin->num_items--;
 272     if (bin->num_items)
 273         bin->items[item_index] = bin->items[bin->num_items];
 274 }
 275
 276 static void
 277 mnemon_init (mnemon_t *mnemon)
 278 {
 279     char *home;
 280
 281     home = getenv ("HOME");
 282     if (home == NULL)
 283         home = "";
 284
 285     xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
 286
 287     mnemon->categories_size = 0;
 288     mnemon->num_categories = 0;
 289     mnemon->categories = NULL;
 290
 291     mnemon->bins_size = 0;
 292     mnemon->num_bins = 0;
 293     mnemon->bins = NULL;
 294 }
 295
 296 static void
 297 mnemon_fini (mnemon_t *mnemon)
 298 {
 299     int i;
 300
 301     for (i = 0; i < mnemon->num_bins; i++)
 302         bin_fini (&mnemon->bins[i]);
 303     free (mnemon->bins);
 304
 305     for (i = 0; i < mnemon->num_categories; i++)
 306         category_fini (&mnemon->categories[i]);
 307     free (mnemon->categories);
 308
 309     free (mnemon->dir_name);
 310 }
 311
 312 static void
 313 mnemon_categories_grow (mnemon_t *mnemon)
 314 {
 315     if (mnemon->categories_size)
 316         mnemon->categories_size *= 2;
 317     else
 318         mnemon->categories_size = 1;
 319
 320     mnemon->categories = xrealloc (mnemon->categories,
 321                                    mnemon->categories_size * sizeof (category_t));
 322 }
 323
 324 static category_t *
 325 mnemon_get_category (mnemon_t   *mnemon,
 326                      const char *name)
 327 {
 328     int i;
 329     category_t *category;
 330
 331     for (i = 0; i < mnemon->num_categories; i++)
 332         if (strcmp (mnemon->categories[i].name, name) == 0)
 333             return &mnemon->categories[i];
 334
 335     mnemon_categories_grow (mnemon);
 336
 337     category = &mnemon->categories[mnemon->num_categories++];
 338
 339     category_init (category, name);
 340
 341     return category;
 342 }
 343
 344 static void
 345 mnemon_bins_grow (mnemon_t *mnemon)
 346 {
 347     if (mnemon->bins_size)
 348         mnemon->bins_size *= 2;
 349     else
 350         mnemon->bins_size = 1;
 351
 352     mnemon->bins = xrealloc (mnemon->bins,
 353                              mnemon->bins_size * sizeof (bin_t));
 354 }
 355
 356 static bin_t *
 357 mnemon_get_bin (mnemon_t        *mnemon,
 358                 int              count)
 359 {
 360     int i;
 361     bin_t *bin;
 362
 363     for (i = 0; i < mnemon->num_bins; i++)
 364         if (mnemon->bins[i].count == count)
 365             return &mnemon->bins[i];
 366         else if (mnemon->bins[i].count > count)
 367             break;
 368
 369     mnemon_bins_grow (mnemon);
 370
 371     bin = &mnemon->bins[i];
 372
 373     /* Make room to insert new bin at its sorted location. */
 374     memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
 375     mnemon->num_bins++;
 376
 377     bin_init (bin, count);
 378
 379     return bin;
 380 }
 381
 382 static void
 383 chomp (char *s)
 384 {
 385     int len = strlen (s);
 386     if (len == 0)
 387         return;
 388     if (s[len - 1] == '\n')
 389         s[len - 1] = '\0';
 390 }
 391
 392 static void
 393 mnemon_load_category (mnemon_t          *mnemon,
 394                       const char        *name)
 395 {
 396     FILE *file;
 397     char *line = NULL, *end;
 398     size_t line_size = 0;
 399     ssize_t bytes_read;
 400     int line_count = 0;
 401     char *path;
 402     category_t *category;
 403     int i;
 404
 405     path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
 406     sprintf (path, "%s/%s", mnemon->dir_name, name);
 407
 408     file = fopen (path, "r");
 409     if (file == NULL) {
 410         fprintf (stderr, "Error: Failed to open %s: %s\n",
 411                  path, strerror (errno));
 412         exit (1);
 413     }
 414
 415     category = mnemon_get_category (mnemon, name);
 416
 417     while (1) {
 418         int count;
 419         char *challenge, *response;
 420
 421         /* Read bin number (ignoring blank separator lines) */
 422         do {
 423             bytes_read = getline (&line, &line_size, file);
 424             if (bytes_read == -1)
 425                 goto END_OF_FILE;
 426             line_count++;
 427             chomp (line);
 428         } while (*line == '\0');
 429
 430         count = strtol (line, &end, 10);
 431         if (*end != '\0') {
 432             fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
 433                      line, path, line_count);
 434             exit (1);
 435         }
 436
 437         /* Read challenge */
 438         bytes_read = getline (&line, &line_size, file);
 439         if (bytes_read == -1)
 440             break;
 441         line_count++;
 442         chomp (line);
 443         challenge = strdup (line);
 444
 445         /* Read response */
 446         bytes_read = getline (&line, &line_size, file);
 447         if (bytes_read == -1)
 448             break;
 449         line_count++;
 450         chomp (line);
 451         response = line;
 452
 453         category_add_item (category, count, challenge, response);
 454
 455         free (challenge);
 456     }
 457   END_OF_FILE:
 458
 459     free (line);
 460     fclose (file);
 461     free (path);
 462
 463     /* Resize category items to fit exactly. */
 464     category->items_size = category->num_items;
 465     category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
 466
 467     /* Now that the category is completely loaded, with stable
 468      * pointers to every item, we can add each item to its appropriate
 469      * bin. */
 470     for (i = 0; i < category->num_items; i++) {
 471         item_t *item = &category->items[i];
 472         bin_t *bin = mnemon_get_bin (mnemon, item->count);
 473
 474         bin_add_item (bin, item);
 475     }
 476 }
 477
 478 static void
 479 mnemon_load (mnemon_t *mnemon)
 480 {
 481     DIR *dir;
 482     struct dirent *dirent;
 483
 484     dir = opendir (mnemon->dir_name);
 485     if (dir == NULL) {
 486         fprintf (stderr, "Error: Failed to open directory %s: %s\n",
 487                  mnemon->dir_name, strerror (errno));
 488         exit (1);
 489     }
 490
 491     while (1) {
 492         dirent = readdir (dir);
 493         if (dirent == NULL)
 494             break;
 495
 496         if (dirent->d_type == DT_REG) {
 497             /* Ignore files matching *~, (yes, this shouldn't be
 498              * hard-coded in such an ad-hoc way, but there you go. */
 499             if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
 500                 mnemon_load_category (mnemon, dirent->d_name);
 501         }
 502     }
 503
 504     closedir (dir);
 505 }
 506
 507 static void
 508 mnemon_save (mnemon_t *mnemon)
 509 {
 510     int i, err;
 511     char *filename, *lock_filename;
 512     FILE *file;
 513     category_t *category;
 514
 515     for (i = 0; i < mnemon->num_categories; i++) {
 516         category = &mnemon->categories[i];
 517
 518         xasprintf (&filename, "%s/%s",
 519                    mnemon->dir_name, category->name);
 520         xasprintf (&lock_filename, "%s/.#%s",
 521                    mnemon->dir_name, category->name);
 522
 523         file = fopen (lock_filename, "w");
 524         if (file == NULL) {
 525             fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
 526                      lock_filename, strerror (errno));
 527             continue;
 528         }
 529
 530         category_print (category, file);
 531
 532         fclose (file);
 533
 534         err = rename (lock_filename, filename);
 535         if (err < 0) {
 536             fprintf (stderr, "Error: Failes to rename %s to %s: %s\n",
 537                      lock_filename, filename, strerror (errno));
 538             continue;
 539         }
 540
 541         free (filename);
 542         free (lock_filename);
 543     }
 544 }
 545
 546 /* Return a uniformly-distributed pseudo-random integer within the
 547  * range:
 548  *
 549  *      0 <= result < num_values
 550  */
 551 static int
 552 rand_within (int num_values)
 553 {
 554     return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
 555 }
 556
 557 /* Return an exponentially-distributed pseudo-random integer within
 558  * the range:
 559  *
 560  *      0 <= result < num_values
 561  *
 562  * The distribution is such that each successively larger value will
 563  * occur with a probability of half of the previous value.
 564  */
 565 static int
 566 rand_within_exponential (int num_values)
 567 {
 568     static int r;
 569     static uint32_t mask = 0;
 570     int ones;
 571     int bit;
 572
 573     /* Optimize the constant case. */
 574     if (num_values == 1)
 575         return 0;
 576
 577     ones = 0;
 578
 579     do {
 580         if (mask == 0) {
 581             r = rand ();
 582             mask = 1 << 31;
 583             while (mask > RAND_MAX)
 584                 mask >>= 1;
 585         }
 586         bit = r & mask;
 587         mask >>= 1;
 588         if (bit) {
 589             ones++;
 590             if (ones == num_values)
 591                 ones = 0;
 592         }
 593     } while (bit);
 594
 595     return ones;
 596 }
 597
 598 static void
 599 mnemon_select_item (mnemon_t     *mnemon,
 600                     bin_t       **bin_ret,
 601                     int          *item_index_ret)
 602 {
 603     int bin_index;
 604     bin_t *bin;
 605
 606     bin_index = rand_within_exponential (mnemon->num_bins);
 607
 608     bin = &mnemon->bins[bin_index];
 609
 610     *bin_ret = bin;
 611     *item_index_ret = rand_within (bin->num_items);
 612 }
 613
 614 static void
 615 mnemon_do_challenges (mnemon_t *mnemon)
 616 {
 617     bin_t *bin;
 618     int item_index;
 619     item_t *item;
 620     char *response;
 621     bool_t correct;
 622
 623     while (1) {
 624         mnemon_select_item (mnemon, &bin, &item_index);
 625         item = bin->items[item_index];
 626
 627         printf ("%s\n", item->challenge);
 628
 629         response = readline ("> ");
 630         if (response == NULL)
 631             break;
 632
 633         correct = (strcmp (response, item->response) == 0);
 634
 635         bin_remove_item (bin, item_index);
 636
 637         if (correct) {
 638             printf ("Correct!\n\n");
 639             if (item->count < 0)
 640                 item->count = 1;
 641             else
 642                 item->count++;
 643         } else {
 644             printf ("  %s is the correct answer.\n\n",
 645                     item->response);
 646             if (item->count > 0)
 647                 item->count = -1;
 648             else
 649                 item->count--;
 650         }
 651
 652         bin = mnemon_get_bin (mnemon, item->count);
 653
 654         bin_add_item (bin, item);
 655     }
 656 }
 657
 658 int
 659 main (int argc, char *argv[])
 660 {
 661     mnemon_t mnemon;
 662
 663     srand (time (NULL));
 664
 665     mnemon_init (&mnemon);
 666
 667     mnemon_load (&mnemon);
 668
 669     mnemon_do_challenges (&mnemon);
 670
 671     mnemon_save (&mnemon);
 672
 673     mnemon_fini (&mnemon);
 674
 675     return 0;
 676 }