Differences

This shows you the differences between two versions of the page.

--- fuss:c [2017/02/22 18:30]
127.0.0.1 external edit
+++ fuss:c [2017/04/26 11:18] (current)
office [Get the Length of an Array]
@@ Line 1: / Line 1: @@
+====== Random 32-Long Hex String ======
+<code c>
+char* wasRandom32Hex(void) {
+    static const char am[] = "0123456789abcdef";
+    char* s = (char*) malloc(32);
+    srand(time(NULL));
+    for (int i=0; i<32; ++i) {
+        s[i] = am[rand()%(sizeof(am)-1)];
+    }
+    return s;
+}
+</code>
+====== Generate Random Floating Point Number ======
+Using the formula to generate a random number $r \in [0..m]$:
+\begin{eqnarray*}
+r &=& m * \frac{N}{M}
+\end{eqnarray*}
+where:
+  * $N$ is a generated random number.
+  * $M$ is the maximal random number (''RAND_MAX'').
+we can write the macro ''RAND_F'':
+<code c>
+#define RAND_F(x) (float)rand()/(float)(RAND_MAX/x)
+</code>
+that, when called, will generate a random number $r \in [0..x]$.
+====== Flush File Descriptors ======
+Instead of flushing ''stdout'' every time you write to it using ''fflush(stdout)'' consider using:
+<code c>
+setvbuf(stdout, NULL, _IONBF, 0);
+</code>
+which sets the terminal to unbuffered mode (data will be printed as soon as it is pushed).
+====== Moon Activity Spinner ======
+Works well under OS X, Lion and above because the terminal seems to display pictures for many UTF-8 characters. This snippet starts with the [[http://www.fileformat.info/info/unicode/char/1f311/index.htm|new moon symbol]] and loops over the moon phases.
+<code c>
+/*************************************************************************/
+/*    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    */
+/*************************************************************************/
+#include <stdio.h>
+#include <unistd.h>
+int main(void) {
+    setvbuf(stdout, NULL, _IONBF, 0);
+    char *m = "\xF0\x9F\x8C";
+    char i;
+cycle:
+    // 0x91 - new moon
+    i = 145;
+    do {
+        printf("%s%c ", m, i);
+        usleep(100000);
+        printf("\b\b");
+    } while(++i<-104);
+    goto cycle;
+}
+</code>
+====== Create a Formatted Date and Time ======
+This can be accomplished using ''strftime'':
+<code c>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+int main(void) {
+    time_t rawtime;                         /* raw time */
+    struct tm* timeinfo;                    /* initialize structure to hold the local time */
+    char *now = (char *) malloc(17);        /* length("It is now ") + 2 + length(" ") + 2 + 1 + 1 = 17 */
+    time ( &rawtime );                      /* get the current time */
+    timeinfo = localtime ( &rawtime );      /* populate the tm structure */
+    if(timeinfo == NULL) {
+        printf("Error: unable to obtain local time.\n");
+        return 1;
+    }
+    /* from strftime(3): %I the hour, %p AM or PM */
+    if(strftime(now, 17, "It is now %I %p.", timeinfo) == 0) {
+        printf("Error: unable to format time.\n");
+        return 1;
+    }
+    /* print the string */
+    printf("%s\n", now);
+    return 0;
+}
+</code>
+more information on the possible escape characters can be found in ''strftime'' man section 3.
+====== Number of Milliseconds to Hour ======
+''wasMillisecondsToClock'' takes as parameter the current minute (''min''), current second (''sec'') and current number of milliseconds (''mil'') and computes the number of milliseconds to the hour:
+<code c>
+/*************************************************************************/
+/*    Copyright (C) 2015 Wizardry and Steamworks - License: GNU GPLv3    */
+/*************************************************************************/
+int wasMillisecondsToClock(int min, int sec, int mil) {
+    return (
+        3600000 - (
+            sec % 60
+        ) * 1000 - (
+            min % 60
+        ) * 60 * 1000 - mil
+    ) % 3600000;
+}
+</code>
+For example, suppose that the hour is ''8:01:20.100'' and we want to know how many seconds till ''9:00:00.000''. We then call:
+<code c>
+wasMillisecondsToClock(1, 20, 100)
+</code>
+which returns ''3519900'' milliseconds.
+====== Queue Implementations ======
+{{indexmenu>fuss/c/data_structures/queues}}
+====== Combine two Paths ======
+The ''pathCombine'' function takes as argument two paths, for example:
+  - /home/test
+  - file.c
+and combines the two paths together, returning a pointer to the combined path. In this example, the pointer will point to the string ''/home/test/file.c''.
+<code c>
+/*************************************************************************/
+/*    Copyright (C) 2013 Wizardry and Steamworks - License: GNU GPLv3    */
+/*************************************************************************/
+/* Concatenates two filesystem paths a and b together.                   */
+/*************************************************************************/
+char *pathCombine(char *a, char *b) {
+    size_t sa = strlen(a);
+    size_t sb = strlen(b);
+    char *rt = (char*)calloc(sa + sb + 1, sizeof(char *));
+    memcpy(rt, a, sa);
+    switch (a[sa - 1]) {
+        case '/':
+            break;
+        default:
+            rt = (char*)realloc(rt, (strlen(rt) + 1) * sizeof(char *));
+            rt[sa] = '/';
+        break;
+    }
+    memcpy(rt + strlen(rt), b, sb + 1);
+    return rt;
+}
+</code>
+The ''pathCombine'' function makes sure that the path separator between two paths will not appear twice in case the first path contains a separator.
+====== Stack Implementations ======
+{{indexmenu>fuss/c/data_structures/stacks}}
+====== QuickSort ======
+<code c>
+/*************************************************************************/
+/*    Copyright (C) 2015 Wizardry and Steamworks - License: GNU GPLv3    */
+/*************************************************************************/
+void QuickSort(int *a, int n) {
+    int p, i, j, t;
+    if (n < 2) return;
+    p = a[ n / 2 ];
+    i = -1;
+    j = n;
+    do {
+        while (a[++i] < p);
+        while (p < a[--j]);
+        if (j > i) {
+            t = a[i];
+            a[i] = a[j];
+            a[j] = t;
+        }
+    } while (j > i);
+    QuickSort(a, i);
+    QuickSort(a + i, n - i);
+}
+</code>
+====== Double Linked Lists Implementation ======
+{{indexmenu>fuss/c/data_structures/linked_lists/double_linked_lists}}
+====== Two-Dimensional Array to Uni-Dimensional Array ======
+The ''set'' function takes as parameters two indexes $x$ and $y$ of a 2D array and set the value $v$ to its corresponding location in an uni-dimensional array using row-major order:
+<code c>
+int array[SIZE_X * SIZE_Y];
+void set(int x, int y, int v) {
+    array[SIZE_X * x + y] = v;
+}
+</code>
+the converse function ''get'':
+<code c>
+int array[SIZE_X * SIZE_Y];
+int get(int x, int y) {
+    return array[SIZE_X * x + y];
+}
+</code>
+returns the value stored in the 2D array at indices $x$ and $y$;
+This follows the row-major order convention, if column-major order is desired, then the formula ''SIZE_X * x + y'' can be changed to ''SIZE_Y * x + y''.
+====== Determine if The System is Big Endian ======
+This can be done with a macro:
+<code c>
+#define IS_BIG_ENDIAN (*(uint16_t *)"\0\xff" < 0x100)
+</code>
+====== Merge Two Sorted Arrays by Preserving Sort Order ======
+This is an interview question at Quora: "Given two lists of sorted integers, develop an algorithm to sort these numbers into a single list efficiently."
+The ''wasMergeSortedArrays'' does that with complexity $O(n)$ where $n$ is the sum of the length of both arrays:
+<code c>
+/*************************************************************************/
+/*    Copyright (C) 2015 Wizardry and Steamworks - License: GNU GPLv3    */
+/*************************************************************************/
+int *wasMergeSortedArrays(int *a, int size_a, int *b, int size_b) {
+    int s = size_a + size_b;
+    int *c = (int *)calloc(s, sizeof(int));
+    int a_i = 0;
+    int b_i = 0;
+    int c_i = 0;
+    do {
+        if(a_i >= size_a) {
+            if(b_i < size_b) {
+                *c++ = *b++;
+                ++b_i;
+                continue;
+            }
+            continue;
+        }
+        if(b_i >= size_b) {
+            if(a_i < size_a) {
+                *c++ = *a++;
+                ++a_i;
+                continue;
+            }
+            continue;
+        }
+        if(*a < *b) {
+            *c++ = *a++;
+            ++a_i;
+            continue;
+        }
+        *c++ = *b++;
+        ++b_i;
+    } while(++c_i < s);
+    return c - s;
+}
+</code>
+and the example call would be:
+<code c>
+int main(void) {
+    int a[5] = { 1, 2, 5, 8, 77 };
+    int b[7] = { 4, 9, 48, 99, 204, 500, 1024 };
+    int *c = wasMergeSortedArrays(a, 5, b, 7);
+    printf("Result: ");
+    int i = 0;
+    do {
+        printf("%d ", *c++);
+    } while(++i < 12);
+    printf("\n");
+}
+</code>
+====== Weighted Selection Algorithm ======
+Given a list of elements each with an attributed weight, every time the ''wasWeightedSelect'' function is called, it will select an element from the list based on its probability.
+<code c>
+/*************************************************************************/
+/*    Copyright (C) 2016 Wizardry and Steamworks - License: GNU GPLv3    */
+/*************************************************************************/
+float wasWeightedSelect(float *s, float *p, float size) {
+    float t = 0, c, f;
+    srand(time(NULL));
+    do {
+        c = *p++;
+        t += c;
+        if ((float)rand() / (float)(RAND_MAX / t) < c)
+            f = *s;
+        s++;
+    } while(--size > 0);
+    return f;
+}
+</code>
+An example call would be:
+<code c>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+int main(void) {
+    float a[4] = { 1, 9, 7, 5 };
+    float b[4] = { 12.5, 12.5, 25, 50 };
+    float p = wasWeightedSelect(a, b, 4);
+    printf("%f\n", p);
+}
+</code>
+====== Get the Length of an Array ======
+The array length can roughly be seen as the size of the array divided by the size of the type that the array contains. These macros should be avoided at all costs and instead the length of the array should be passed along with the function call. Nevertheless, the variants are:
+<code c>
+#define SIZE(array, type) (sizeof(array) / (sizeof(type))
+#define length(array) (sizeof(array)/sizeof(*(array)))
+#define ARRAY_LENGTH(array) (sizeof((array))/sizeof((array)[0]))
+</code>
+Google Chromium defines ''COUNT_OF'' for arrays as:
+<code c>
+#define COUNT_OF(x) ((sizeof(x)/sizeof(0[x])) / ((size_t)(!(sizeof(x) % sizeof(0[x])))))
+</code>
+and it does cause a division by zero that may be caught by some compilers.
+====== Overloading Functions ======
+Given a function that creates a new stack structure such as:
+<code c>
+/*
+ * Creates a new stringStack with a given size.
+ */
+stringStack* stringStackCreate(int size) {
+   stringStack *s = (stringStack*)calloc(1, sizeof(stringStack));
+   if ((s->store = (char**)calloc(size, sizeof(char **))) == NULL)
+       return NULL;
+   s->size = size;
+   s->top = 0;
+   return s;
+}
+</code>
+it is preferable to have an overload that automatically sets the size to ''1'' when the function is invoked with zero parameters.
+The function can be renamed to ''stringStackCreate_Internal'' and then the following macros can be added in order to conditionally invoke''stringStackCreate_Internal'' conditionally depending on the number of arguments:
+<code c>
+// Zero or one arguments for StackCreate_Internal.
+#define stringStackCreate_0() stringStackCreate_Internal(1)
+#define stringStackCreate_1(x) stringStackCreate_Internal(x)
+#define _FUNC_OVERRIDE(_1, FUNC) FUNC
+#define stringStackCreate(...) _FUNC_OVERRIDE(stringStackCreate_1(__VA_ARGS__), stringStackCreate_0())
+</code>
+This can then be generalised to any number of arguments (in this case, up to 4 overloads of ''stringStackCreate'' progressively taking: 0, 1, 2 and 3 arguments respectively):
+<code c>
+// Zero or one arguments for StackCreate_Internal.
+#define stringStackCreate_0() stringStackCreate_Internal(1)
+#define stringStackCreate_1(x) stringStackCreate_Internal(x)
+#define stringStackCreate_2(x, y) stringStackCreate_Internal(x, y)
+#define stringStackCreate_3(x, y, z) stringStackCreate_Internal(x, y, z)
+#define _FUNC_OVERRIDE(_1, _2, _3, /* ad nauseum */, FUNC, ...) FUNC
+#define stringStackCreate(...) _FUNC_OVERRIDE(stringStackCreate_3(__VA_ARGS__), stringStackCreate_2(__VA_ARGS__), stringStackCreate_1(__VA_ARGS__), stringStackCreate_0())
+</code>