Programming Notes

Module Design

• If there is only one instance, make it a file scope variable and provide access functions
• If there are multiple instances, make a constructor function that returns a pointer
• Put structure definitions in *.c files and declarations only in *.h files

Miscellaneous

• Use fdopen() to get a FILE* to a socket fd. Allows use of stdio with socket
• Use typeof in macros instead of passing in type
• #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0])))
• Don’t ‘return’ from main–use ‘exit()’

Reservoir Sampling

Let `R` be the result array of size s
Let `I` be an input queue
> Fill the reservoir array
for j in the range [1,s]:
    R[j]=I.pop()

elements_seen=s
while I is not empty:
    elements_seen+=1
    j=random(1,elements_seen)       > This is inclusive
    if j<=s:
        R[j]=I.pop()
    else:
        I.pop()

Reservoir sampling when k = 1

Let `R` by the result
Let `I` be an input queue

> Fill the reservoir array
R=I.pop()

elements_seen=1
while I is not empty:
    elements_seen+=1
    j=random(1,elements_seen) > This is inclusive
    if j<=s:
        R=I.pop()
    else:
        I.pop()

Remove Modulo Bias

int x;
int n = 3;
int rand_limit;
int rand_excess;
rand_excess = (RAND_MAX % n) + 1;
if (rand_excess == n)
    rand_excess = 0;
rand_limit = RAND_MAX - rand_excess;
while (x = rand() > rand_limit)
    ;
return x % n;

Generate Random Numbers

od -A n -t d -N 1 /dev/urandom | sed -e 's/ \*//'
   -A n # do not output offset base
   -t d # output signed decimal
   -N <n> # Generate an n-byte number

git

Sync a Fork with Upstream

• Create local branch and upstream remote:

$ git branch <local branch name>
$ git remote add upstream <upstream repo>

• Fetch upstream updates:

$ git fetch upstream
$ git checkout master
$ git merge upstream/master

• Once merge is complete, push both branches:

$ git push origin <local branch name>
$ git push origin master

• Change the default branch in GitHub

Under Settings → Branches change the default branch