Yet more "unsiged vs. signed" warning cleanups.
[mnemon] / mnemon.c
1 /* mnemon - A memory training library
2  *
3  * Copyright © 2006,2011 Carl Worth
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation; either version 3, or (at your option)
8  * any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software Foundation,
17  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA."
18  */
19
20 #include "mnemon.h"
21
22 /* for asprintf */
23 #define _GNU_SOURCE
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <stdarg.h>
27 #include <stdint.h>
28 #include <math.h>
29
30 #include <sys/types.h>
31 #include <sys/time.h>
32 #include <sys/stat.h>
33 #include <unistd.h>
34 #include <dirent.h>
35 #include <errno.h>
36 #include <string.h>
37 #include <assert.h>
38
39 #include <readline/readline.h>
40 #include <readline/history.h>
41
42 #define ASSERT_NOT_REACHED              \
43 do {                                    \
44     static const int NOT_REACHED = 0;   \
45     assert (NOT_REACHED);               \
46 } while (0)
47
48 static void *
49 xmalloc (size_t size)
50 {
51     void *ret;
52
53     ret = malloc (size);
54     if (ret == NULL) {
55         fprintf (stderr, "Error: out of memory\n");
56         exit (1);
57     }
58
59     return ret;
60 }
61
62 static void *
63 xrealloc (void *ptr, size_t size)
64 {
65     void *ret;
66
67     ret = realloc (ptr, size);
68     if (ret == NULL) {
69         fprintf (stderr, "Error: out of memory\n");
70         exit (1);
71     }
72
73     return ret;
74 }
75
76 static char *
77 xstrdup (const char *s)
78 {
79     char *ret;
80
81     ret = strdup (s);
82     if (ret == NULL) {
83         fprintf (stderr, "Error: out of memory\n");
84         exit (1);
85     }
86
87     return ret;
88 }
89
90 static void
91 xasprintf (char **strp, const char *fmt, ...)
92 {
93     va_list ap;
94     int ret;
95
96     va_start (ap, fmt);
97     ret = vasprintf (strp, fmt, ap);
98     va_end (ap);
99
100     if (ret < 0) {
101         fprintf (stderr, "Error: out of memory\n");
102         exit (1);
103     }
104 }
105
106 static void
107 item_init (item_t       *item,
108            int           score,
109            const char   *challenge,
110            const char   *response)
111 {
112     item->score = score;
113
114     item->challenge = xmalloc (strlen (challenge) + 1 +
115                                strlen (response) + 1);
116     item->response = item->challenge + strlen (challenge) + 1;
117
118     strcpy (item->challenge, challenge);
119     strcpy (item->response, response);
120 }
121
122 static void
123 item_fini (item_t *item)
124 {
125     /* item->response shares allocation with item->challenge, so
126      * doesn't require a separate call to free */
127     free (item->challenge);
128 }
129
130 static void
131 category_init (category_t *category,
132                const char *name)
133 {
134     category->name = xstrdup (name);
135     
136     category->items_size = 0;
137     category->num_items = 0;
138     category->items = NULL;
139     category->order = CATEGORY_ORDER_RANDOM;
140     category->time_limit = 0.0;
141     category->bin_zero_head = 0;
142     category->challenge_type = xstrdup("");
143     category->repeat = 0;
144 }
145
146 static void
147 category_fini (category_t *category)
148 {
149     unsigned int i;
150
151     for (i = 0; i < category->num_items; i++)
152         item_fini (&category->items[i]);
153
154     free (category->items);
155
156     free (category->name);
157
158     free (category->challenge_type);
159 }
160
161 static void
162 category_grow (category_t *category)
163 {
164     if (category->items_size)
165         category->items_size *= 2;
166     else
167         category->items_size = 1;
168
169     category->items = xrealloc (category->items,
170                                 category->items_size * sizeof (item_t));
171 }
172
173 static item_t *
174 category_add_item (category_t   *category,
175                    int           score,
176                    const char   *challenge,
177                    const char   *response)
178 {
179     item_t *item;
180
181     if (category->num_items == category->items_size)
182         category_grow (category);
183
184     item = &category->items[category->num_items++];
185
186     item_init (item, score, challenge, response);
187
188     return item;
189 }
190
191 static item_t *
192 category_next_bin_zero_item (category_t *category)
193 {
194     unsigned int *i = &category->bin_zero_head;
195
196     for ( ; *i < category->num_items; *i = *i + 1)
197         if (category->items[*i].score == 0)
198             return &category->items[*i];
199
200     return NULL;
201 }
202
203 static void
204 category_print (category_t      *category,
205                 FILE            *file)
206 {
207     unsigned int i;
208     item_t *item;
209
210     fprintf (file, "order = %s\n\n",
211             category->order == CATEGORY_ORDER_RANDOM ? "random" : "sequential");
212     fprintf (file, "time = %f\n\n",
213              category->time_limit);
214
215     fprintf (file, "challenge = %s\n\n", category->challenge_type);
216
217     fprintf (file, "repeat = %d\n\n", category->repeat);
218
219     for (i = 0; i < category->num_items; i++) {
220         item = &category->items[i];
221         if (i != 0)
222             fprintf (file, "\n");
223         fprintf (file, "%d\n%s\n%s\n",
224                  item->score,
225                  item->challenge,
226                  item->response);
227     }
228 }
229
230 static void
231 bin_init (bin_t *bin,
232           int    score)
233 {
234     bin->score = score;
235
236     bin->items_size = 0;
237     bin->num_items = 0;
238     bin->items = NULL;
239 }
240
241 static void
242 bin_fini (bin_t *bin)
243 {
244     free (bin->items);
245 }
246
247 static void
248 bin_grow (bin_t *bin)
249 {
250     if (bin->items_size)
251         bin->items_size *= 2;
252     else
253         bin->items_size = 1;
254
255     bin->items = xrealloc (bin->items,
256                            bin->items_size * sizeof (item_t*));
257 }
258
259 static void
260 bin_add_item (bin_t     *bin,
261               item_t    *item)
262 {
263     assert (item->score == bin->score);
264
265     if (bin->num_items == bin->items_size)
266         bin_grow (bin);
267
268     bin->items[bin->num_items++] = item;
269 }
270
271 static void
272 bin_remove_item (bin_t  *bin,
273                  int     item_index)
274 {
275     /* Replace the current item with the last item, (no need to shift
276      * any more than that since we don't care about the order of the
277      * items within a bin). */
278     bin->num_items--;
279     if (bin->num_items)
280         bin->items[item_index] = bin->items[bin->num_items];
281 }
282
283 /* Find the index for an item within a bin.
284  *
285  * XXX: This is currently a linear search, so is a potential
286  * performance problem.
287  */
288 static int
289 bin_item_index (bin_t   *bin,
290                 item_t  *item)
291 {
292     unsigned int i;
293
294     for (i = 0; i < bin->num_items; i++)
295         if (bin->items[i] == item)
296             return i;
297
298     assert (0);
299 }
300
301 void
302 mnemon_init (mnemon_t *mnemon)
303 {
304     char *home;
305
306     home = getenv ("HOME");
307     if (home == NULL)
308         home = "";
309
310     xasprintf (&mnemon->dir_name, "%s/.mnemon", getenv ("HOME"));
311
312     mnemon->categories_size = 0;
313     mnemon->num_categories = 0;
314     mnemon->categories = NULL;
315
316     mnemon->bins_size = 0;
317     mnemon->num_bins = 0;
318     mnemon->bins = NULL;
319 }
320
321 void
322 mnemon_fini (mnemon_t *mnemon)
323 {
324     unsigned int i;
325
326     for (i = 0; i < mnemon->num_bins; i++)
327         bin_fini (&mnemon->bins[i]);
328     free (mnemon->bins);
329
330     for (i = 0; i < mnemon->num_categories; i++)
331         category_fini (&mnemon->categories[i]);
332     free (mnemon->categories);
333
334     free (mnemon->dir_name);
335 }
336
337 static void
338 mnemon_categories_grow (mnemon_t *mnemon)
339 {
340     if (mnemon->categories_size)
341         mnemon->categories_size *= 2;
342     else
343         mnemon->categories_size = 1;
344
345     mnemon->categories = xrealloc (mnemon->categories,
346                                    mnemon->categories_size * sizeof (category_t));
347 }
348
349 /* Get a category by name if it exists */
350 category_t *
351 mnemon_get_category_if_exists (mnemon_t     *mnemon,
352                                const char   *name)
353 {
354     unsigned int i;
355
356     for (i = 0; i < mnemon->num_categories; i++)
357         if (strcmp (mnemon->categories[i].name, name) == 0)
358             return &mnemon->categories[i];
359
360     return NULL;
361 }
362
363 /* Get a category by name, creating new one if necessary. */
364 static category_t *
365 mnemon_get_category (mnemon_t   *mnemon,
366                      const char *name)
367 {
368     category_t *category;
369
370     category = mnemon_get_category_if_exists (mnemon, name);
371     if (category)
372         return category;
373
374     mnemon_categories_grow (mnemon);
375
376     category = &mnemon->categories[mnemon->num_categories++];
377
378     category_init (category, name);
379
380     return category;
381 }
382
383 static void
384 mnemon_bins_grow (mnemon_t *mnemon)
385 {
386     if (mnemon->bins_size)
387         mnemon->bins_size *= 2;
388     else
389         mnemon->bins_size = 1;
390
391     mnemon->bins = xrealloc (mnemon->bins,
392                              mnemon->bins_size * sizeof (bin_t));
393 }
394
395 static bin_t *
396 mnemon_get_bin (mnemon_t        *mnemon,
397                 int              score)
398 {
399     unsigned int i;
400     bin_t *bin;
401
402     for (i = 0; i < mnemon->num_bins; i++)
403         if (mnemon->bins[i].score == score)
404             return &mnemon->bins[i];
405         else if (mnemon->bins[i].score > score)
406             break;
407
408     if (mnemon->num_bins == mnemon->bins_size)
409         mnemon_bins_grow (mnemon);
410
411     bin = &mnemon->bins[i];
412
413     /* Make room to insert new bin at its sorted location. */
414     if (i < mnemon->num_bins)
415         memmove (bin + 1, bin, (mnemon->num_bins - i) * sizeof (bin_t));
416     mnemon->num_bins++;
417
418     bin_init (bin, score);
419
420     return bin;
421 }
422
423 void
424 mnemon_remove_bin (mnemon_t *mnemon, int bin_number)
425 {
426     bin_t *bin = mnemon_get_bin (mnemon, bin_number);
427     int i;
428
429     if (bin == NULL)
430         return;
431
432     i = bin - mnemon->bins;
433
434     bin_fini (bin);
435
436     memmove (bin, bin + 1, (mnemon->num_bins - i) * sizeof (bin_t));
437     mnemon->num_bins--;
438 }
439
440 static void
441 chomp (char *s)
442 {
443     int len = strlen (s);
444     if (len == 0)
445         return;
446     if (s[len - 1] == '\n')
447         s[len - 1] = '\0';
448 }
449
450 static char *
451 trim_space (char *string)
452 {
453     char *s;
454
455     s = string;
456     while (*s && isspace (*s))
457         s++;
458
459     string = s;
460
461     s = string + strlen (string) - 1;
462     while (s > string && isspace (*s)) {
463         *s = '\0';
464         s--;
465     }
466
467     return string;
468 }
469
470 void
471 mnemon_load_category (mnemon_t          *mnemon,
472                       const char        *name)
473 {
474     FILE *file;
475     char *line = NULL, *end;
476     size_t line_size = 0;
477     ssize_t bytes_read;
478     int line_count = 0;
479     char *path;
480     category_t *category;
481     unsigned int i;
482     struct stat st;
483
484     path = xmalloc (strlen (mnemon->dir_name) + 1 + strlen (name) + 1);
485     sprintf (path, "%s/%s", mnemon->dir_name, name);
486
487     file = fopen (path, "r");
488     if (file == NULL) {
489         fprintf (stderr, "Error: Failed to open %s: %s\n",
490                  path, strerror (errno));
491         exit (1);
492     }
493
494     fstat (fileno(file), &st);
495     if (! S_ISREG(st.st_mode)) {
496         fprintf (stderr, "Error: File %s is not a regular file.\n", path);
497         exit (1);
498     }
499
500     category = mnemon_get_category (mnemon, name);
501
502 #define READ_LINE do {                                  \
503     bytes_read = getline (&line, &line_size, file);     \
504     if (bytes_read == -1)                               \
505         goto END_OF_FILE;                               \
506     line_count++;                                       \
507     chomp (line);                                       \
508 } while (0)
509
510     /* Parse options */
511     while (1) {
512         char *name, *equal, *value;
513
514         /* Ignore blank lines */
515         READ_LINE;
516         if (*line == '\0')
517             continue;
518
519         /* An initial digit means we hit an item. Trigger the
520          * spaghetti machine. */
521         if ((*line >= '0' && *line <= '9') || *line == '-')
522             goto PARSE_BIN;
523
524         equal = strchr (line, '=');
525         if (equal == NULL) {
526             fprintf (stderr, "Malformed option, (expected name=value): \"%s\" at %s:%d\n",
527                      line, path, line_count);
528             exit (1);
529         }
530
531         value = equal + 1;
532         name = line;
533         *equal = '\0';
534
535         name = trim_space (name);
536         value = trim_space (value);
537
538         if (strcmp (name, "order") == 0) {
539             if (strcmp (value, "sequential") == 0) {
540                 category->order = CATEGORY_ORDER_SEQUENTIAL;
541             } else if (strcmp (value, "random") == 0) {
542                 category->order = CATEGORY_ORDER_RANDOM;
543             } else {
544                 fprintf (stderr, "Unknown value for \"order\" option \"%s\" at %s:%d\n",
545                          value, path, line_count);
546                 exit (1);
547             }
548         } else if (strcmp (name, "time") == 0) {
549             double limit;
550             char *end;
551             limit = strtod (value, &end);
552             while (isspace (*end))
553                 end++;
554             if (*end == '\0') {
555                 category->time_limit = limit;
556             } else {
557                 fprintf (stderr, "Failed to parse time value: %s at %s:%d\n",
558                          value, path, line_count);
559                 exit (1);
560             }
561         } else if (strcmp (name, "challenge") == 0) {
562             /* XXX: Need to switch to talloc here. */
563             free (category->challenge_type);
564             category->challenge_type = xstrdup (value);
565         } else if (strcmp (name, "repeat") == 0) {
566             if (strcmp (value, "0") == 0) 
567                 category->repeat = 0;
568             else
569                 category->repeat = 1;
570         } else {
571             fprintf (stderr, "Unknown option %s at %s:%d\n",
572                      name, path, line_count);
573             exit (1);
574         }
575     }
576
577     /* Parse items */
578     while (1) {
579         int score;
580         char *challenge, *response;
581
582         /* Ignore blank lines */
583         READ_LINE;
584         if (*line == '\0')
585             continue;
586
587         /* Read bin number */
588       PARSE_BIN:
589         score = strtol (line, &end, 10);
590         if (*end != '\0') {
591             fprintf (stderr, "Failed to parse bin number from \"%s\" at %s:%d\n",
592                      line, path, line_count);
593             exit (1);
594         }
595
596         /* Read challenge */
597         READ_LINE;
598         challenge = strdup (line);
599
600         /* Read response */
601         READ_LINE;
602         response = line;
603
604         category_add_item (category, score, challenge, response);
605
606         free (challenge);
607     }
608   END_OF_FILE:
609
610     free (line);
611     fclose (file);
612     free (path);
613
614     /* Resize category items to fit exactly. */
615     category->items_size = category->num_items;
616     category->items = xrealloc (category->items, category->items_size * sizeof (item_t));
617
618     /* Now that the category is completely loaded, with stable
619      * pointers to every item, we can add each item to its appropriate
620      * bin. */
621     for (i = 0; i < category->num_items; i++) {
622         item_t *item = &category->items[i];
623         bin_t *bin = mnemon_get_bin (mnemon, item->score);
624
625         bin_add_item (bin, item);
626     }
627 }
628
629 void
630 mnemon_load (mnemon_t *mnemon)
631 {
632     DIR *dir;
633     struct dirent *dirent;
634
635     dir = opendir (mnemon->dir_name);
636     if (dir == NULL) {
637         fprintf (stderr, "Error: Failed to open directory %s: %s\n",
638                  mnemon->dir_name, strerror (errno));
639         exit (1);
640     }
641
642     while (1) {
643         dirent = readdir (dir);
644         if (dirent == NULL)
645             break;
646
647         if (dirent->d_type == DT_REG) {
648             /* Ignore files matching *~, (yes, this shouldn't be
649              * hard-coded in such an ad-hoc way, but there you go. */
650             if (dirent->d_name[strlen(dirent->d_name)-1] != '~')
651                 mnemon_load_category (mnemon, dirent->d_name);
652         }
653     }
654
655     closedir (dir);
656 }
657
658 void
659 mnemon_save (mnemon_t *mnemon)
660 {
661     unsigned int i;
662     int err;
663     char *filename, *lock_filename;
664     FILE *file;
665     category_t *category;
666
667     for (i = 0; i < mnemon->num_categories; i++) {
668         category = &mnemon->categories[i];
669
670         xasprintf (&filename, "%s/%s",
671                    mnemon->dir_name, category->name);
672         xasprintf (&lock_filename, "%s/.#%s",
673                    mnemon->dir_name, category->name);
674
675         file = fopen (lock_filename, "w");
676         if (file == NULL) {
677             fprintf (stderr, "Error: Failed to open %s for writing: %s\n",
678                      lock_filename, strerror (errno));
679             continue;
680         }
681
682         category_print (category, file);
683
684         fsync (fileno (file));
685         fclose (file);
686
687         err = rename (lock_filename, filename);
688         if (err < 0) {
689             fprintf (stderr, "Error: Failed to rename %s to %s: %s\n",
690                      lock_filename, filename, strerror (errno));
691             continue;
692         }
693
694         free (filename);
695         free (lock_filename);
696     }
697 }
698
699 /* Return a uniformly-distributed pseudo-random integer within the
700  * range:
701  *
702  *      0 <= result < num_values
703  */
704 static int
705 rand_within (int num_values)
706 {
707     return (int) (num_values * (rand() / (RAND_MAX + 1.0)));
708 }
709
710 /* Return an exponentially-distributed pseudo-random integer within
711  * the range:
712  *
713  *      0 <= result < num_values
714  *
715  * The distribution is such that each successively larger value will
716  * occur with a probability of half of the previous value.
717  */
718 static int
719 rand_within_exponential (int num_values)
720 {
721     static int r;
722     static uint32_t mask = 0;
723     int ones;
724     int bit;
725
726     /* Optimize the constant case. */
727     if (num_values == 1)
728         return 0;
729
730     ones = 0;
731
732     do {
733         if (mask == 0) {
734             r = rand ();
735             mask = 1 << 31;
736             while (mask > RAND_MAX)
737                 mask >>= 1;
738         }
739         bit = r & mask;
740         mask >>= 1;
741         if (bit) {
742             ones++;
743             if (ones == num_values)
744                 ones = 0;
745         }
746     } while (bit);
747
748     return ones;
749 }
750
751 category_t *
752 mnemon_item_category (mnemon_t  *mnemon,
753                       item_t    *item)
754 {
755     category_t *category;
756     unsigned int i, item_index;
757
758     for (i = 0; i < mnemon->num_categories; i++) {
759         category = &mnemon->categories[i];
760         item_index = item - category->items;
761         if (item_index < category->num_items)
762             return category;
763     }
764
765     assert (0);
766 }
767
768 void
769 mnemon_select_item (mnemon_t     *mnemon,
770                     bin_t       **bin_ret,
771                     int          *item_index_ret,
772                     category_t  **category_ret,
773                     int          *introduced_ret)
774 {
775     int bin_index, item_index;
776     bin_t *bin;
777     item_t *item;
778     category_t *category;
779
780     bin_index = rand_within_exponential (mnemon->num_bins);
781     bin = &mnemon->bins[bin_index];
782
783     /* The most intuitive understanding of the introduced flag that
784      * it's tracking never-before-learned items as they are pulled
785      * from the bin with score 0. But that bin can become empty. So
786      * the refined rule is that we also set introduced whenever we
787      * pull from the lowest-indexed bin with a non-negative score. */
788     if (bin->score >=0 &&
789         (bin_index == 0 || mnemon->bins[bin_index-1].score < 0))
790     {
791         *introduced_ret = 1;
792     }
793     else
794     {
795         *introduced_ret = 0;
796     }
797
798     item_index = rand_within (bin->num_items);
799
800     item = bin->items[item_index];
801     category = mnemon_item_category (mnemon, item);
802
803     if (bin->score == 0) {
804         if (category->order == CATEGORY_ORDER_SEQUENTIAL) {
805             item = category_next_bin_zero_item (category);
806             if (item)
807                 item_index = bin_item_index (bin, item);
808         }
809     }
810
811     *bin_ret = bin;
812     *item_index_ret = item_index;
813     *category_ret = category;
814 }
815
816 void
817 mnemon_score_item (mnemon_t *mnemon,
818                    bin_t *bin,
819                    unsigned int item_index,
820                    bool_t correct)
821 {
822     item_t *item;
823
824     if (item_index >= bin->num_items)
825         return;
826
827     item = bin->items[item_index];
828     bin_remove_item (bin, item_index);
829
830     /* If the bin is now empty, we must remove it. */
831     if (bin->num_items == 0)
832     {
833         mnemon_remove_bin (mnemon, bin->score);
834     }
835
836     if (correct)
837     {
838         item->score++;
839         /* We reserve an item score of 0 for an item that has
840          * never been asked. */
841         if (item->score == 0)
842             item->score = 1;
843     }
844     else
845     {
846         /* Penalize an incorrect response by forcing the score
847          * negative. */
848         if (item->score >= 0) {
849             /* We go to -2 to force a little extra reinforcement
850              * when re-learning an item, (otherwise, it will often
851              * get asked again immediately where it is easy to get
852              * a correct response without any learning). */
853             item->score = -2;
854         } else {
855             item->score--;
856         }
857     }
858
859     bin = mnemon_get_bin (mnemon, item->score);
860
861     bin_add_item (bin, item);
862 }