From 9009a690b916de3e98f33a11629d572d4c50f97b Mon Sep 17 00:00:00 2001 From: Anthony Wang Date: Tue, 19 Apr 2022 12:54:07 -0500 Subject: Finish porting SD code --- README.md | 2 +- cd.c | 98 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++--- segmenttree.c | 42 +++++++++++++------------ segmenttree.h | 10 +++++- 4 files changed, 125 insertions(+), 27 deletions(-) diff --git a/README.md b/README.md index 819b73d..3e5ef03 100644 --- a/README.md +++ b/README.md @@ -6,7 +6,7 @@ C port of [SD](https://git.exozy.me/Ta180m/SD), a very efficient flash cards app Flash cards are stored in the `cards` table of a SQLite database. There are four columns: `idx INTEGER PRIMARY KEY, weight INTEGER, key STRING, val STRING`. The `idx` is a unique index for each card, starting at 0. The weight is how often the card should come up. The key and value are the front and reverse sides of the card. You can use the `sqlite3` CLI to create a card deck. -Now build this project with `gcc cd.c -o cd -l sqlite3 -O2 -march=native` and run `./cd` to enjoy a fast flash cards experience! The program will display the `key` of a randomly selected card. Press any key to show the `val` of the card. Now press either `y` or `n` depending on whether you got the card correct, and the program adjusts that card's weight. +Now build this project with `gcc cd.c segmenttree.c -o cd -lsqlite3 -O2 -march=native` and run `./cd` to enjoy a fast flash cards experience! The program will display the `key` of a randomly selected card. Press any key to show the `val` of the card. Now press either `y` or `n` depending on whether you got the card correct, and the program adjusts that card's weight. If you're wondering where the name came from, this is the C port of [SD](https://git.exozy.me/Ta180m/SD). diff --git a/cd.c b/cd.c index 14a9105..7d0cb0b 100644 --- a/cd.c +++ b/cd.c @@ -2,6 +2,7 @@ #include #include #include +#include #include #include #include @@ -11,9 +12,10 @@ int main(int argc, char* argv[]) { char *file = "cards"; bool verbose = false; + /* Proccess args */ static struct option long_options[] = { - {"file", required_argument, 0, 'f'}, - {"verbose", no_argument, 0, 'v'} + {"file", required_argument, NULL, 'f'}, + {"verbose", no_argument, NULL, 'v'} }; while (1) { int option_index = 0; @@ -26,17 +28,103 @@ int main(int argc, char* argv[]) { } } - printf("%s", file); + /* Seed the RNG */ + srand(time(0)); + /* Connect to db */ sqlite3 *db; int rc = sqlite3_open(file, &db); if (rc) { fprintf(stderr, "Can't open database: %s\n", sqlite3_errmsg(db)); abort(); } - fprintf(stderr, "Opened database successfully\n"); - //int N = sqlite3_exec(db, "SELECT COUNT(*) FROM cards", callback) + /* Get number of cards */ + sqlite3_stmt *stmt; + rc = sqlite3_prepare_v3(db, "SELECT COUNT(*) FROM cards", -1, 0, &stmt, NULL); + if (rc != SQLITE_OK) { + fprintf(stderr, "Database error: %s\n", sqlite3_errmsg(db)); + abort(); + } + sqlite3_step(stmt); + int N = sqlite3_column_int(stmt, 0); + sqlite3_finalize(stmt); + + /* Get card weights */ + rc = sqlite3_prepare_v3(db, "SELECT weight FROM cards", -1, 0, &stmt, NULL); + if (rc != SQLITE_OK) { + fprintf(stderr, "Database error: %s\n", sqlite3_errmsg(db)); + abort(); + } + seg = malloc(4 * N * sizeof(int)); + build(stmt, 0, N - 1, 1); + sqlite3_finalize(stmt); + + if (verbose) { + for (int i = 0; i < N; i++) { + printf("%d ", seg[i]); + } + printf("\n"); + } + + /* Disable input buffering */ + system("stty -F /dev/tty cbreak min 1"); + system("stty -F /dev/tty -echo"); + + while (true) { + int x = (long long)rand() * rand() % seg[1]; + int res[2]; + query(res, x, 0, N-1, 1); + int w = res[0], i = res[1]; + + if (verbose) { + printf("%d %d %d %d\n", seg[1], x, w, i); + } + + /* Get card contents from database */ + rc = sqlite3_prepare_v3(db, "SELECT key, val FROM cards WHERE idx=?", -1, 0, &stmt, NULL); + if (rc != SQLITE_OK) { + fprintf(stderr, "Database error: %s\n", sqlite3_errmsg(db)); + abort(); + } + sqlite3_bind_int(stmt, 1, i); + sqlite3_step(stmt); + char *key, *val; + key = strdup(sqlite3_column_text(stmt, 0)); + val = strdup(sqlite3_column_text(stmt, 1)); + sqlite3_finalize(stmt); + + printf("> %s\n", key); + + /* Wait for confirmation */ + char b = getchar(); + printf("%s\n", val); + + /* Read user input */ + b = getchar(); + if (b == 'y') { + w >>= 1; + } + else if (b == 'n') { + w <<= 3; + } + else { + break; + } + + /* Update segment tree and database */ + update(i, w, 0, N - 1, 1); + rc = sqlite3_prepare_v3(db, "UPDATE cards SET weight=? WHERE idx=?", -1, 0, &stmt, NULL); + if (rc != SQLITE_OK) { + fprintf(stderr, "Database error: %s\n", sqlite3_errmsg(db)); + abort(); + } + sqlite3_bind_int(stmt, 1, w); + sqlite3_bind_int(stmt, 2, i); + sqlite3_finalize(stmt); + } + /* Cleanup */ + system("stty -F /dev/tty echo"); sqlite3_close(db); } diff --git a/segmenttree.c b/segmenttree.c index 1bf0fcd..4471369 100644 --- a/segmenttree.c +++ b/segmenttree.c @@ -1,46 +1,48 @@ -struct SegmentTree { - int N; - int * seg; -} +#include + +int * seg; -// Build segment tree -void Build(int l, int r, int n) { +/* Build segment tree */ +void build(sqlite3_stmt *stmt, int l, int r, int n) { if (l == r) { - + sqlite3_step(stmt); + seg[l] = sqlite3_column_int(stmt, 0); + return; } int m = l + r >> 1; - Build(l, m, n << 1); - Build(m + 1, r, n << 1 | 1); + build(stmt, l, m, n << 1); + build(stmt, m + 1, r, n << 1 | 1); seg[n] = seg[n << 1] + seg[n << 1 | 1]; } -// Update value at index x -void Update(int x, int v, int l, int r, int n) { +/* Update value at index x*/ +void update(int x, int v, int l, int r, int n) { if (l == r) { seg[n] += v; return; } int m = l + r >> 1; if (x <= m) { - Update(x, v, l, m, n<<1); + update(x, v, l, m, n<<1); } else { - Update(x, v, m+1, r, n<<1|1); + update(x, v, m+1, r, n<<1|1); } seg[n] = seg[n << 1] + seg[n << 1 | 1]; } -// Find element with prefix sum v -int Query(int v, int l, int r, int n) { +/* Find element with prefix sum v */ +void query(int *res, int v, int l, int r, int n) { if (l == r) { - return s.seg[n], l; + res[0] = seg[n]; + res[1] = l; + return; } int m = l + r >> 1; if (seg[n << 1] >= v) { - return Query(v, l, m, n << 1); + query(res, v, l, m, n << 1); } else { - return Query(v - s.seg[n << 1], m + 1, r, n << 1 | 1); + query(res, v - seg[n << 1], m + 1, r, n << 1 | 1); } -} - +} \ No newline at end of file diff --git a/segmenttree.h b/segmenttree.h index ed7efe4..251e139 100644 --- a/segmenttree.h +++ b/segmenttree.h @@ -1 +1,9 @@ -struct SegmentTree; +#include + +extern int * seg; + +void build(sqlite3_stmt *stmt, int l, int r, int n); + +void update(int x, int v, int l, int r, int n); + +void query(int *res, int v, int l, int r, int n); \ No newline at end of file -- cgit v1.2.3-70-g09d2