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