Merge branch 'stclib:master' into modifiedHEADmodified

7 files changed, 431 insertions, 0 deletions

diff --git a/misc/examples/hashmaps/birthday.c b/misc/examples/hashmaps/birthday.c
new file mode 100644
index 00000000..4742cb45
--- /dev/null
+++ b/misc/examples/hashmaps/birthday.c
@@ -0,0 +1,68 @@
+#include <math.h>
+#include <stdio.h>
+#include <time.h>
+#include <stc/crand.h>
+
+#define i_tag ic
+#define i_key uint64_t
+#define i_val int
+#include <stc/cmap.h>
+
+static uint64_t seed = 12345;
+
+static void test_repeats(void)
+{
+    enum {BITS = 46, BITS_TEST = BITS/2 + 2};
+    static const uint64_t N = 1ull << BITS_TEST;
+    static const uint64_t mask = (1ull << BITS) - 1;
+
+    printf("birthday paradox: value range: 2^%d, testing repeats of 2^%d values\n", BITS, BITS_TEST);
+    crand_t rng = crand_init(seed);
+
+    cmap_ic m = cmap_ic_with_capacity(N);
+    c_forrange (i, N) {
+        uint64_t k = crand_u64(&rng) & mask;
+        int v = cmap_ic_insert(&m, k, 0).ref->second += 1;
+        if (v > 1) printf("repeated value %" PRIu64 " (%d) at 2^%d\n",
+                          k, v, (int)log2((double)i));
+    }
+    cmap_ic_drop(&m);
+}
+
+#define i_key uint32_t
+#define i_val uint64_t
+#define i_tag x
+#include <stc/cmap.h>
+
+void test_distribution(void)
+{
+    enum {BITS = 26};
+    printf("distribution test: 2^%d values\n", BITS);
+    crand_t rng = crand_init(seed);
+    const size_t N = 1ull << BITS ;
+
+    cmap_x map = {0};
+    c_forrange (N) {
+        uint64_t k = crand_u64(&rng);
+        cmap_x_insert(&map, k & 0xf, 0).ref->second += 1;
+    }
+
+    uint64_t sum = 0;
+    c_foreach (i, cmap_x, map) sum += i.ref->second;
+    sum /= (uint64_t)map.size;
+
+    c_foreach (i, cmap_x, map) {
+        printf("%4" PRIu32 ": %" PRIu64 " - %" PRIu64 ": %11.8f\n",
+                i.ref->first, i.ref->second, sum,
+                (1.0 - (double)i.ref->second / (double)sum));
+    }
+
+    cmap_x_drop(&map);
+}
+
+int main(void)
+{
+    seed = (uint64_t)time(NULL);
+    test_distribution();
+    test_repeats();
+}
diff --git a/misc/examples/hashmaps/books.c b/misc/examples/hashmaps/books.c
new file mode 100644
index 00000000..1fd57f27
--- /dev/null
+++ b/misc/examples/hashmaps/books.c
@@ -0,0 +1,62 @@
+// https://doc.rust-lang.org/std/collections/struct.HashMap.html
+#define i_implement
+#include <stc/cstr.h>
+#define i_key_str
+#define i_val_str
+#include <stc/cmap.h>
+
+// Type inference lets us omit an explicit type signature (which
+// would be `HashMap<String, String>` in this example).
+int main(void)
+{
+    cmap_str book_reviews = {0};
+
+    // Review some books.
+    cmap_str_emplace(&book_reviews,
+        "Adventures of Huckleberry Finn",
+        "My favorite book."
+    );
+    cmap_str_emplace(&book_reviews,
+        "Grimms' Fairy Tales",
+        "Masterpiece."
+    );
+    cmap_str_emplace(&book_reviews,
+        "Pride and Prejudice",
+        "Very enjoyable"
+    );
+    cmap_str_insert(&book_reviews,
+        cstr_lit("The Adventures of Sherlock Holmes"),
+        cstr_lit("Eye lyked it alot.")
+    );
+
+    // Check for a specific one.
+    // When collections store owned values (String), they can still be
+    // queried using references (&str).
+    if (cmap_str_contains(&book_reviews, "Les Misérables")) {
+        printf("We've got %" c_ZI " reviews, but Les Misérables ain't one.",
+                    cmap_str_size(&book_reviews));
+    }
+
+    // oops, this review has a lot of spelling mistakes, let's delete it.
+    cmap_str_erase(&book_reviews, "The Adventures of Sherlock Holmes");
+
+    // Look up the values associated with some keys.
+    const char* to_find[] = {"Pride and Prejudice", "Alice's Adventure in Wonderland"};
+    c_forrange (i, c_arraylen(to_find)) {
+        const cmap_str_value* b = cmap_str_get(&book_reviews, to_find[i]);
+        if (b)
+            printf("%s: %s\n", cstr_str(&b->first), cstr_str(&b->second));
+        else
+            printf("%s is unreviewed.\n", to_find[i]);
+    }
+
+    // Look up the value for a key (will panic if the key is not found).
+    printf("Review for Jane: %s\n", cstr_str(cmap_str_at(&book_reviews, "Pride and Prejudice")));
+
+    // Iterate over everything.
+    c_forpair (book, review, cmap_str, book_reviews) {
+        printf("%s: \"%s\"\n", cstr_str(_.book), cstr_str(_.review));
+    }
+
+    cmap_str_drop(&book_reviews);
+}
diff --git a/misc/examples/hashmaps/hashmap.c b/misc/examples/hashmaps/hashmap.c
new file mode 100644
index 00000000..cf11b7f7
--- /dev/null
+++ b/misc/examples/hashmaps/hashmap.c
@@ -0,0 +1,50 @@
+// https://doc.rust-lang.org/rust-by-example/std/hash.html
+#define i_implement
+#include <stc/cstr.h>
+#define i_key_str
+#define i_val_str
+#include <stdio.h>
+#include <stc/cmap.h>
+
+const char* call(const char* number) {
+    if (!strcmp(number, "798-1364"))
+        return "We're sorry, the call cannot be completed as dialed." 
+               " Please hang up and try again.";
+    else if (!strcmp(number, "645-7689")) 
+        return "Hello, this is Mr. Awesome's Pizza. My name is Fred."
+               " What can I get for you today?";
+    else
+        return "Hi! Who is this again?";
+}
+
+int main(void) {
+    cmap_str contacts = {0};
+
+    cmap_str_emplace(&contacts, "Daniel", "798-1364");
+    cmap_str_emplace(&contacts, "Ashley", "645-7689");
+    cmap_str_emplace(&contacts, "Katie", "435-8291");
+    cmap_str_emplace(&contacts, "Robert", "956-1745");
+
+    const cmap_str_value* v;
+    if ((v = cmap_str_get(&contacts, "Daniel")))
+        printf("Calling Daniel: %s\n", call(cstr_str(&v->second)));
+    else
+        printf("Don't have Daniel's number.");
+
+    cmap_str_emplace_or_assign(&contacts, "Daniel", "164-6743");
+
+    if ((v = cmap_str_get(&contacts, "Ashley")))
+        printf("Calling Ashley: %s\n", call(cstr_str(&v->second)));
+    else
+        printf("Don't have Ashley's number.");
+
+    cmap_str_erase(&contacts, "Ashley");
+
+    puts("");
+    c_forpair (contact, number, cmap_str, contacts) {
+        printf("Calling %s: %s\n", cstr_str(_.contact), call(cstr_str(_.number)));
+    }
+    puts("");
+
+    cmap_str_drop(&contacts);
+}
diff --git a/misc/examples/hashmaps/new_map.c b/misc/examples/hashmaps/new_map.c
new file mode 100644
index 00000000..de990040
--- /dev/null
+++ b/misc/examples/hashmaps/new_map.c
@@ -0,0 +1,75 @@
+#define i_implement
+#include <stc/cstr.h>
+#include <stc/forward.h>
+
+forward_cmap(cmap_pnt, struct Point, int);
+
+typedef struct MyStruct {
+    cmap_pnt pntmap;
+    cstr name;
+} MyStruct;
+
+// int => int map
+#define i_key int
+#define i_val int
+#include <stc/cmap.h>
+
+// Point => int map
+typedef struct Point { int x, y; } Point;
+
+int point_cmp(const Point* a, const Point* b) {
+    int c = a->x - b->x;
+    return c ? c : a->y - b->y;
+}
+
+// Point => int map
+#define i_key Point
+#define i_val int
+#define i_cmp point_cmp
+#define i_hash c_default_hash
+#define i_is_forward
+#define i_tag pnt
+#include <stc/cmap.h>
+
+// cstr => cstr map
+#define i_key_str
+#define i_val_str
+#include <stc/cmap.h>
+
+// string set
+#define i_key_str
+#include <stc/cset.h>
+
+
+int main(void)
+{
+    cmap_pnt pmap = c_init(cmap_pnt, {{{42, 14}, 1}, {{32, 94}, 2}, {{62, 81}, 3}});
+
+    c_foreach (i, cmap_pnt, pmap)
+        printf(" (%d, %d: %d)", i.ref->first.x, i.ref->first.y, i.ref->second);
+    puts("");
+
+    cmap_str smap = c_init(cmap_str, {
+        {"Hello, friend", "long time no see"},
+        {"So long", "see you around"},
+    });
+
+    cset_str sset = c_init(cset_str, {
+        "Hello, friend",
+        "Nice to see you again",
+        "So long",
+    });
+
+    cmap_int map = {0};
+    cmap_int_insert(&map, 123, 321);
+    cmap_int_insert(&map, 456, 654);
+    cmap_int_insert(&map, 789, 987);
+
+    c_foreach (i, cset_str, sset)
+        printf(" %s\n", cstr_str(i.ref));
+
+    cmap_int_drop(&map);
+    cset_str_drop(&sset);
+    cmap_str_drop(&smap);
+    cmap_pnt_drop(&pmap);
+}
diff --git a/misc/examples/hashmaps/phonebook.c b/misc/examples/hashmaps/phonebook.c
new file mode 100644
index 00000000..faf7566e
--- /dev/null
+++ b/misc/examples/hashmaps/phonebook.c
@@ -0,0 +1,72 @@
+// The MIT License (MIT)
+// Copyright (c) 2018 Maksim Andrianov
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to
+// deal in the Software without restriction, including without limitation the
+// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
+// sell copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+// IN THE SOFTWARE.
+
+// Program to emulates the phone book.
+#define i_implement
+#include <stc/cstr.h>
+
+#define i_key_str
+#define i_val_str
+#include <stc/cmap.h>
+
+#define i_key_str
+#include <stc/cset.h>
+
+void print_phone_book(cmap_str phone_book)
+{
+    c_foreach (i, cmap_str, phone_book)
+        printf("%s\t- %s\n", cstr_str(&i.ref->first), cstr_str(&i.ref->second));
+}
+
+int main(int argc, char **argv)
+{
+    cmap_str phone_book = c_init(cmap_str, {
+        {"Lilia Friedman", "(892) 670-4739"},
+        {"Tariq Beltran", "(489) 600-7575"},
+        {"Laiba Juarez", "(303) 885-5692"},
+        {"Elliott Mooney", "(945) 616-4482"},
+    });
+
+    printf("Phone book:\n");
+    print_phone_book(phone_book);
+
+    cmap_str_emplace(&phone_book, "Zak Byers", "(551) 396-1880");
+    cmap_str_emplace(&phone_book, "Zak Byers", "(551) 396-1990");
+
+    printf("\nPhone book after adding Zak Byers:\n");
+    print_phone_book(phone_book);
+
+    if (cmap_str_contains(&phone_book, "Tariq Beltran"))
+        printf("\nTariq Beltran is in phone book\n");
+
+    cmap_str_erase(&phone_book, "Tariq Beltran");
+    cmap_str_erase(&phone_book, "Elliott Mooney");
+
+    printf("\nPhone book after erasing Tariq and Elliott:\n");
+    print_phone_book(phone_book);
+
+    cmap_str_emplace_or_assign(&phone_book, "Zak Byers", "(555) 396-188");
+
+    printf("\nPhone book after update phone of Zak Byers:\n");
+    print_phone_book(phone_book);
+
+    cmap_str_drop(&phone_book);
+}
diff --git a/misc/examples/hashmaps/unordered_set.c b/misc/examples/hashmaps/unordered_set.c
new file mode 100644
index 00000000..dd899d78
--- /dev/null
+++ b/misc/examples/hashmaps/unordered_set.c
@@ -0,0 +1,45 @@
+// https://iq.opengenus.org/containers-cpp-stl/
+// C program to demonstrate various function of stc cset
+#define i_implement
+#include <stc/cstr.h>
+#define i_key_str
+#include <stc/cset.h>
+
+int main(void)
+{
+    // declaring set for storing string data-type
+    cset_str stringSet = {0};
+    c_defer(
+        cset_str_drop(&stringSet)
+    ){
+        // inserting various string, same string will be stored
+        // once in set
+        cset_str_emplace(&stringSet, "code");
+        cset_str_emplace(&stringSet, "in");
+        cset_str_emplace(&stringSet, "C");
+        cset_str_emplace(&stringSet, "is");
+        cset_str_emplace(&stringSet, "fast");
+
+        const char* key = "slow";
+
+        //     find returns end iterator if key is not found,
+        //  else it returns iterator to that key
+
+        if (cset_str_find(&stringSet, key).ref == NULL)
+            printf("\"%s\" not found\n", key);
+        else
+            printf("Found \"%s\"\n", key);
+
+        key = "C";
+        if (!cset_str_contains(&stringSet, key))
+            printf("\"%s\" not found\n", key);
+        else
+            printf("Found \"%s\"\n", key);
+
+        // now iterating over whole set and printing its
+        // content
+        printf("All elements :\n");
+        c_foreach (itr, cset_str, stringSet)
+            printf("%s\n", cstr_str(itr.ref));
+    }
+}
diff --git a/misc/examples/hashmaps/vikings.c b/misc/examples/hashmaps/vikings.c
new file mode 100644
index 00000000..cef17a04
--- /dev/null
+++ b/misc/examples/hashmaps/vikings.c
@@ -0,0 +1,59 @@
+#define i_implement
+#include <stc/cstr.h>
+
+typedef struct Viking {
+    cstr name;
+    cstr country;
+} Viking;
+
+void Viking_drop(Viking* vk) {
+    cstr_drop(&vk->name);
+    cstr_drop(&vk->country);
+}
+
+// Define Viking lookup struct with hash, cmp, and convertion functions between Viking and RViking structs:
+
+typedef struct RViking {
+    const char* name;
+    const char* country;
+} RViking;
+
+static inline int RViking_cmp(const RViking* rx, const RViking* ry) {
+    int c = strcmp(rx->name, ry->name);
+    return c ? c : strcmp(rx->country, ry->country);
+}
+
+static inline Viking Viking_from(RViking raw) { // note: parameter is by value
+    return c_LITERAL(Viking){cstr_from(raw.name), cstr_from(raw.country)};
+}
+
+static inline RViking Viking_toraw(const Viking* vp) {
+    return c_LITERAL(RViking){cstr_str(&vp->name), cstr_str(&vp->country)};
+}
+
+// With this in place, we define the Viking => int hash map type:
+#define i_type      Vikings
+#define i_keyclass  Viking      // key type
+#define i_rawclass  RViking     // lookup type
+#define i_keyfrom   Viking_from
+#define i_opt       c_no_clone
+#define i_hash(rp)  stc_strhash(rp->name) ^ stc_strhash(rp->country)
+#define i_val       int         // mapped type
+#include <stc/cmap.h>
+
+int main(void)
+{
+    Vikings vikings = {0};
+    Vikings_emplace(&vikings, c_LITERAL(RViking){"Einar", "Norway"}, 20);
+    Vikings_emplace(&vikings, c_LITERAL(RViking){"Olaf", "Denmark"}, 24);
+    Vikings_emplace(&vikings, c_LITERAL(RViking){"Harald", "Iceland"}, 12);
+    Vikings_emplace(&vikings, c_LITERAL(RViking){"Björn", "Sweden"}, 10);
+
+    Vikings_value* v = Vikings_get_mut(&vikings, c_LITERAL(RViking){"Einar", "Norway"});
+    v->second += 3; // add 3 hp points to Einar
+
+    c_forpair (vk, hp, Vikings, vikings) {
+        printf("%s of %s has %d hp\n", cstr_str(&_.vk->name), cstr_str(&_.vk->country), *_.hp);
+    }
+    Vikings_drop(&vikings);
+}