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