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     if (mnemon->num_bins == mnemon->bins_size)
 370         mnemon_bins_grow (mnemon);
 371
 372     bin = &mnemon->bins[i];
 373
 374     /* Make room to insert new bin at its sorted location. */
 375     if (i < mnemon->num_bins)
 376         memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
 377     mnemon->num_bins++;
 378
 379     bin_init (bin, count);
 380
 381     return bin;
 382 }
 383
 384 static void
 385 mnemon_remove_bin (mnemon_t     *mnemon,
 386                    bin_t        *bin)
 387 {
 388     int i = bin - mnemon->bins;
 389
 390     bin_fini (bin);
 391
 392     memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
 393     mnemon->num_bins--;
 394 }
 395
 396 static void
 397 chomp (char *s)
 398 {
 399     int len = strlen (s);
 400     if (len == 0)
 401         return;
 402     if (s[len - 1] == '\n')
 403         s[len - 1] = '\0';
 404 }
 405
 406 static void
 407 mnemon_load_category (mnemon_t          *mnemon,
 408                       const char        *name)
 409 {
 410     FILE *file;
 411     char *line = NULL, *end;
 412     size_t line_size = 0;
 413     ssize_t bytes_read;
 414     int line_count = 0;
 415     char *path;
 416     category_t *category;
 417     int i;
 418
 419     path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
 420     sprintf (path, "%s/%s", mnemon->dir_name, name);
 421
 422     file = fopen (path, "r");
 423     if (file == NULL) {
 424         fprintf (stderr, "Error: Failed to open %s: %s\n",
 425                  path, strerror (errno));
 426         exit (1);
 427     }
 428
 429     category = mnemon_get_category (mnemon, name);
 430
 431     while (1) {
 432         int count;
 433         char *challenge, *response;
 434
 435         /* Read bin number (ignoring blank separator lines) */
 436         do {
 437             bytes_read = getline (&line, &line_size, file);
 438             if (bytes_read == -1)
 439                 goto END_OF_FILE;
 440             line_count++;
 441             chomp (line);
 442         } while (*line == '\0');
 443
 444         count = strtol (line, &end, 10);
 445         if (*end != '\0') {
 446             fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
 447                      line, path, line_count);
 448             exit (1);
 449         }
 450
 451         /* Read challenge */
 452         bytes_read = getline (&line, &line_size, file);
 453         if (bytes_read == -1)
 454             break;
 455         line_count++;
 456         chomp (line);
 457         challenge = strdup (line);
 458
 459         /* Read response */
 460         bytes_read = getline (&line, &line_size, file);
 461         if (bytes_read == -1)
 462             break;
 463         line_count++;
 464         chomp (line);
 465         response = line;
 466
 467         category_add_item (category, count, challenge, response);
 468
 469         free (challenge);
 470     }
 471   END_OF_FILE:
 472
 473     free (line);
 474     fclose (file);
 475     free (path);
 476
 477     /* Resize category items to fit exactly. */
 478     category->items_size = category->num_items;
 479     category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
 480
 481     /* Now that the category is completely loaded, with stable
 482      * pointers to every item, we can add each item to its appropriate
 483      * bin. */
 484     for (i = 0; i < category->num_items; i++) {
 485         item_t *item = &category->items[i];
 486         bin_t *bin = mnemon_get_bin (mnemon, item->count);
 487
 488         bin_add_item (bin, item);
 489     }
 490 }
 491
 492 static void
 493 mnemon_load (mnemon_t *mnemon)
 494 {
 495     DIR *dir;
 496     struct dirent *dirent;
 497
 498     dir = opendir (mnemon->dir_name);
 499     if (dir == NULL) {
 500         fprintf (stderr, "Error: Failed to open directory %s: %s\n",
 501                  mnemon->dir_name, strerror (errno));
 502         exit (1);
 503     }
 504
 505     while (1) {
 506         dirent = readdir (dir);
 507         if (dirent == NULL)
 508             break;
 509
 510         if (dirent->d_type == DT_REG) {
 511             /* Ignore files matching *~, (yes, this shouldn't be
 512              * hard-coded in such an ad-hoc way, but there you go. */
 513             if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
 514                 mnemon_load_category (mnemon, dirent->d_name);
 515         }
 516     }
 517
 518     closedir (dir);
 519 }
 520
 521 static void
 522 mnemon_save (mnemon_t *mnemon)
 523 {
 524     int i, err;
 525     char *filename, *lock_filename;
 526     FILE *file;
 527     category_t *category;
 528
 529     for (i = 0; i < mnemon->num_categories; i++) {
 530         category = &mnemon->categories[i];
 531
 532         xasprintf (&filename, "%s/%s",
 533                    mnemon->dir_name, category->name);
 534         xasprintf (&lock_filename, "%s/.#%s",
 535                    mnemon->dir_name, category->name);
 536
 537         file = fopen (lock_filename, "w");
 538         if (file == NULL) {
 539             fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
 540                      lock_filename, strerror (errno));
 541             continue;
 542         }
 543
 544         category_print (category, file);
 545
 546         fclose (file);
 547
 548         err = rename (lock_filename, filename);
 549         if (err < 0) {
 550             fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
 551                      lock_filename, filename, strerror (errno));
 552             continue;
 553         }
 554
 555         free (filename);
 556         free (lock_filename);
 557     }
 558 }
 559
 560 /* Return a uniformly-distributed pseudo-random integer within the
 561  * range:
 562  *
 563  *      0 <= result < num_values
 564  */
 565 static int
 566 rand_within (int num_values)
 567 {
 568     return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
 569 }
 570
 571 /* Return an exponentially-distributed pseudo-random integer within
 572  * the range:
 573  *
 574  *      0 <= result < num_values
 575  *
 576  * The distribution is such that each successively larger value will
 577  * occur with a probability of half of the previous value.
 578  */
 579 static int
 580 rand_within_exponential (int num_values)
 581 {
 582     static int r;
 583     static uint32_t mask = 0;
 584     int ones;
 585     int bit;
 586
 587     /* Optimize the constant case. */
 588     if (num_values == 1)
 589         return 0;
 590
 591     ones = 0;
 592
 593     do {
 594         if (mask == 0) {
 595             r = rand ();
 596             mask = 1 << 31;
 597             while (mask > RAND_MAX)
 598                 mask >>= 1;
 599         }
 600         bit = r & mask;
 601         mask >>= 1;
 602         if (bit) {
 603             ones++;
 604             if (ones == num_values)
 605                 ones = 0;
 606         }
 607     } while (bit);
 608
 609     return ones;
 610 }
 611
 612 static void
 613 mnemon_select_item (mnemon_t     *mnemon,
 614                     bin_t       **bin_ret,
 615                     int          *item_index_ret)
 616 {
 617     int bin_index;
 618     bin_t *bin;
 619
 620     bin_index = rand_within_exponential (mnemon->num_bins);
 621
 622     bin = &mnemon->bins[bin_index];
 623
 624     *bin_ret = bin;
 625     *item_index_ret = rand_within (bin->num_items);
 626 }
 627
 628 static void
 629 mnemon_do_challenges (mnemon_t *mnemon,
 630                       int       to_introduce)
 631 {
 632     bin_t *bin;
 633     int item_index;
 634     item_t *item;
 635     char *response;
 636     bool_t correct;
 637     int unlearned;
 638     int i;
 639
 640     /* Count the number of items with negative counts. */
 641     unlearned = 0;
 642     for (i = 0; i < mnemon->num_bins; i++) {
 643         bin = &mnemon->bins[i];
 644         if (bin->count >= 0)
 645             break;
 646         unlearned += bin->num_items;
 647     }
 648
 649     to_introduce -= unlearned;
 650     if (to_introduce < 0)
 651         to_introduce = 0;
 652
 653     if (unlearned) {
 654         printf ("You've got %d items to learn already. ", unlearned);
 655         if (to_introduce)
 656             printf ("I'll introduce %d more as we go.", to_introduce);
 657         printf ("\n");
 658     } else {
 659         printf ("Introducing %d new items.\n", to_introduce);
 660     }
 661     printf ("\n");
 662
 663     do {
 664         mnemon_select_item (mnemon, &bin, &item_index);
 665
 666         if (bin->count == 0)
 667             to_introduce--;
 668
 669         item = bin->items[item_index];
 670
 671         printf ("%s\n", item->challenge);
 672
 673         response = readline ("> ");
 674         if (response == NULL) {
 675             printf ("\n");
 676             break;
 677         }
 678
 679         correct = (strcmp (response, item->response) == 0);
 680
 681         bin_remove_item (bin, item_index);
 682
 683         /* If the bin is now empty, we must remove it. Also if we just
 684          * picked the last word we'll ever pick from the bin with
 685          * count 0, then we can remove that as well. */
 686         if (bin->num_items == 0 ||
 687             (bin->count == 0 && to_introduce == 0))
 688         {
 689             mnemon_remove_bin (mnemon, bin);
 690         }
 691
 692         if (correct) {
 693             item->count++;
 694             /* We reserve an item count of 0 for an item that has
 695              * never been asked. */
 696             if (item->count == 0) {
 697                 item->count = 1;
 698                 unlearned--;
 699                 printf ("You got it!");
 700             } else if (item->count < 0) {
 701                 printf ("Yes---just give me %d more.",
 702                         - item->count);
 703             } else if (item->count == 1) {
 704                 printf ("On your first try, no less!");
 705             } else {
 706                 printf ("Masterful (%dx).", item->count);
 707             }
 708         } else {
 709             printf ("  %s is the correct answer.",
 710                     item->response);
 711             if (item->count >= 0)
 712                 unlearned++;
 713             item->count--;
 714             /* Penalize an incorrect response by forcing the count
 715              * negative. */
 716             if (item->count >= 0) {
 717                 item->count = -1;
 718                 printf ( " Oops, you knew that, right?\n ");
 719             }
 720         }
 721
 722         printf (" (");
 723         if (to_introduce)
 724             printf ("%d to come.", to_introduce);
 725         if (to_introduce && unlearned)
 726             printf (" ");
 727         if (unlearned)
 728             printf ("%d still unlearned.", unlearned);
 729         if (to_introduce == 0 && unlearned == 0)
 730             printf ("Great job!");
 731         printf (")\n\n");
 732
 733         bin = mnemon_get_bin (mnemon, item->count);
 734
 735         bin_add_item (bin, item);
 736     } while (unlearned || to_introduce);
 737 }
 738
 739 int
 740 main (int argc, char *argv[])
 741 {
 742     mnemon_t mnemon;
 743
 744     srand (time (NULL));
 745
 746     mnemon_init (&mnemon);
 747
 748     mnemon_load (&mnemon);
 749
 750     mnemon_do_challenges (&mnemon, 10);
 751
 752     mnemon_save (&mnemon);
 753
 754     mnemon_fini (&mnemon);
 755
 756     return 0;
 757 }