Subset, Combination and Permutation (Recursion)

#define MAX_K 100 

void subset_rec(
    const char *cont, 
    const size_t start, 
    const size_t n,
    char *res, 
    const size_t last)  
{
    size_t i;

    // print (res, last);
    for (i = start; i < n; i++) {
        res[last] = cont[i];
        subset_rec(cont, i+1, n, res, last+1);
    }
}

void subset(const char *content, const size_t n) {
    char *result;
    result = (char*)malloc(MAX_K * sizeof(char));
    subset_rec(content, 0, n, result, 0);
    free(result);
    result = NULL;
}

void comb_rec(
    const char *cont,       // pointer to combination's content
    const size_t start,     // starting index of the content
    const size_t n,         // n of C(n,k)
    const size_t k,         // k of C(n,k)
    char *res,              // pointer to one combination generated so far
    const size_t last)      // length of the result
{
    size_t i;

    if (k == 0) {
        // print (res, last);
    } else {
        for (i = start; i < n; i++) {
            res[last] = cont[i];
            comb_rec(cont, i+1, n, k-1, res, last+1);
        }
    }
}

void combination(const char *content, const size_t n, const size_t k) 
{
    char *result;
    if (k > n || k == 0 || n == 0)  return;
    result = (char*)malloc(MAX_K * sizeof(char));
    comb_rec(content, 0, n, k, result, 0);
    free(result);
    result = NULL;
}

void perm_rec(
    char *cont, 
    const size_t n, 
    const size_t k, 
    char *res, 
    const size_t last)  
{
    size_t i;
    char t;

    if (k == 0) {
        // print (res, last);
    } else {
        for (i = 0; i < n; i++) {
            t = cont[i];
            res[last] = t;                          // A B C D
            memmove(cont+i, cont+i+1, n-i-1);       // A C D
            perm_rec(cont, n-1, k-1, res, last+1); 
            memmove(cont+i+1, cont+i, n-i-1);       // A A C D
            cont[i] = t;                            // A B C D
        }
    }
}

void permutation(const char *content, const size_t n, const size_t k) 
{
    char *result;
    if (k > n || k == 0 || n == 0)  return;
    result = (char*)malloc(MAX_K * sizeof(char));
    perm_rec((char*)content, n, k, result, 0);
    free(result);
    result = NULL;
} 

For the permutation of set that contains duplicates, the solution can be found here:
https://oj.leetcode.com/discuss/16264/a-simple-recursion-solution-c

Tail Call

// Non tail-call optimization
// Because the last statement is n+sum1() in the function call, 

// which triggers the saving of sum1()'s current context, then do the next call
int sum1(int n) {
 return (n <= 0) ? 0 : n+sum1(n-1);
}

// We can skip this step by passing the current sum as an argument in the function
int sum2(int n, int cur) {
 return (n <= 0) ? cur : sum2(n-1, cur+n);
}

The processor time it takes to execute these two functions are (N is the # of repetitions):

   N      sum1      sum2
 1000     1123      1061
10000    13213     12839

Ref.: http://c2.com/cgi/wiki?TailCallOptimization

Notes on memset

1. memset

  void * memset ( void *pMemoryBlock, int byte, size_t numOfByte );

2. Typical using senarios

• Bytewise memory initialization
• Zero a block of memory
• Zero a POD struct

3. Test

#include<vector>
#include<string>
#include<algorithm>
#include<cstring>

using namespace std;

struct C {
 char a;
 short *b;
 int c[10];
};

struct CPP {
 string a;
 CPP& operator=(const CPP &r);
};

CPP& CPP::operator=(const CPP &r) {
 if (this != &r) {
  (*this).a = r.a;
 }
 return *this;
}

char achar[3];
int aint[3];

C s;
C as[3];

CPP c;
CPP ac[3];

int main (){
 // 1. Initialize a block of memory using a given byte
 memset(achar, 'a', 3);
 
 // 2. Quickly zero a block of memory
 memset(achar, 0, 3);
 memset(achar, 0, sizeof achar);
 
 memset(aint, 0, 3 * sizeof(int));
 memset(aint, 0, sizeof aint);
 
 memset(as, 0, 3 * sizeof as[0]); 
 memset(as, 0, 3 * sizeof (struct C));
 
 // 3. Reset POD struct
 memset(&s, 0, sizeof(struct C));
 
 // Caution 1. memset works byte by byte only
 memset(aint, 1, 3 * sizeof(int)); // aint : 16843009, 16843009, 16843009
 
 // Caution 2. Be careful with pointer in struct
 s.b = new short;
 memset(&s, 0, sizeof s); // address of b : 0
 
 // Caution 3. POD only
 //memset(&c, 0, sizeof(CPP)); // crash!!!
 
 // Either define a reseting member function, or
 // use fill() and '=' overriding
 c.a = "N/A";
 fill(ac, ac+3, c);  // ac : "N/A", "N/A", "N/A"
 
 return 0;
}

 (code test on g++ 4.6.2)

Identify Functions Definition within a C Source File

1. Use the ctags tools, on a console, typing in "ctags -x --c-kinds=f " with the file name(s) (e.g. "flex.c"):

ctags -x --c-kinds=f flex.c

will generate the list of C functions defined in "flex.c" file:

FlexParser       function   2228 flex.c           extern parserDefinition* FlexParser (void)
addContext       function    786 flex.c           static void addContext (tokenInfo* const parent, const tokenInfo* const child)
addToScope       function    796 flex.c           static void addToScope (tokenInfo* const token, vString* const extra)
buildFlexKeywordHash function    207 flex.c           static void buildFlexKeywordHash (void)
copyToken        function    705 flex.c           static void copyToken (tokenInfo *const dest, tokenInfo *const src)
...

Ref.: http://ctags.sourceforge.net/ctags.html

Online C/C++ Coding Reference

1. Simplified C examples: http://www.programmingsimplified.com/c-program-examples
http://www.cis.temple.edu/~giorgio/cis71/code/

2. Algorithms & Data Structure Explaination and Code: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/

3. Online C quick reference (quick reference to all the std library function): http://www.cplusplus.com/reference/clibrary/

4. Online C Graphical Tutorial: http://www.howstuffworks.com/c.htm/printable

5. Online C example: http://www.c.happycodings.com/

6. Some C++ Code samples: http://users.cs.fiu.edu/~weiss/dsaa_c++/code/

7. C++ Optimization:
http://www.tantalon.com/pete/cppopt/main.htm
http://www.shlomifish.org/philosophy/computers/optimizing-code-for-speed/#meta

8. Google Code style (C++):
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml

9. Catching C integer overflow:
http://www.fefe.de/intof.html

10. Valgrind:
http://valgrind.org/

memcpy and memmove

It is interesting to notice the difference between the memcpy and memmove when programming in C. 

While the memcpy copies the data byte-by-byte sequentially from source to destination, the memmove function copies the block of data to the source to the destination. The difference implies that the memcpy function can generate the repeating data results (see below) if the source data being copied happens to be overlapping with the destination data:

#include <stdio.h>
#include <string.h>


int main()
{
    char src1[] = "abcdefg";
    char src2[] = "abcdefg";
    char *dest1;
    char *dest2;
    
    if ((dest1 = (char*)malloc(8*sizeof(char))) == NULL
        || (dest2 = (char*)malloc(8*sizeof(char))) == NULL)
        exit(1);
    
    //memcpy src1 -> dest1
    memcpy(dest1, src1, 7);
    printf("memcpy\tsrc1:%s\tdest1:%s\n", src1, dest1);
    
    //memmove src2 -> dest2
    memmove(dest2, src2, 7);
    printf("memmove\tsrc2:%s\tdest2:%s\n", src2, dest2);
    
    //memcpy src1 -> src1+1
    memcpy(src1+1, src1, 6);
    printf("memcpy\tsrc1:%s\n", src1);
        
    //memmove src2 -> src2+1
    memmove(src2+1, src2, 6);
    printf("memmove\tsrc2:%s\n", src2);
    
    free (dest1);
    free (dest2);
    return 0;
}

The result would be:


memcpy  src1:abcdefg    dest1:abcdefg
memmove src2:abcdefg    dest2:abcdefg
memcpy  src1:aaaaaaa
memmove src2:aabcdef


Thus, memcpy should be used with caution when the data is overlapping with each other.  Specifically, the memmove works identically to memcpy if:

src_addr + length_copy < dest_addr or src_addr > dest_addr 

and it works reversely in the other way. So, the memmove can also be implemented as memmove2:


void * memmove2(void *dest, const void *src, size_t len)
{
    if (src != dest)
    {
        if ((const char*)src+len < dest || (const char*)src > dest)
            memcpy(dest, src, len);
        else
            while (len--)
                *((char*)dest+len) = *((const char*)src+len);
    }
    return dest;
}

If we compare the following code snippets, the running time are also different between:

    for (i = 0; i < 100000000; i++)
        memmove(dest, src, n);

and

    for (i = 0; i < 100000000; i++)

        memmove2(dest, src, n);

The results depend on the relationship between dest and src, where n denotes the length of string to be copied:

                dest < src | dest==src | dest > src | dest > src + n
    memmove         4.020       0.321       18.070      4.036
   memmove2         3.148       0.892       3.096       3.295

The running time is in second. It is obvious that while the memmove2 function outperforms the standard function in cases where dest!=src, the memmove is better when dest==src.


(Compiled using gcc 3.4.4)

malloc() and free()

In C, the malloc() and free() function allows dynamic memory management. However, when using this function with char string (char*), sometimes it is easy to forget padding '\0' after the string:

int main() {

    size_t i;

    char *str1;

    for (i = 0; i < 3; i++)

    {

        str1 = (char*)malloc(10 * sizeof(char));

        memset (str1, 'a', 9-i);

        printf("ADDRESS:0x%x  DATA:%s\n", str1, str1);

        free(str1);

    }

    return 0;

}

And the output might be something like:

ADDRESS:0x4701e0  DATA:aaaaaaaaa
ADDRESS:0x4701e0  DATA:aaaaaaaa►
ADDRESS:0x4701e0  DATA:aaaaaaaa►

The reason for that whenever free(pointer) is called in the C program, the space pointed by the pointer is collected back in the free mem list which can be reused later by another malloc call. So depending on the mechanism of free(), there is a chance that the content in the part of the memory to which a pointer previously points, was not erased after calling free() (ref here). Then we can see the previous content in the pointer, if no '\0' was padding to the end of str1.


Normally, I choose to add memset after malloc, or pad a '\0' to the end, or use calloc instead, e.g. in the loop:

        str1 = (char*)malloc(10 * sizeof(char));
        // Option 1. Add memset to set the init values
        //memset (str1, '\0', 10);
        // Option 2. Use calloc() to init to NULL instead
        //str1 = (char*)calloc(10, sizeof(char));
        memset (str1, 'a', 9-i);
        // Option 3. Add the '\0' to the end
        //*(str1+9-i) = '\0';
        printf("ADDRESS:0x%x  DATA:%s\n", str1, str1);
        free(str1);

Then the result will be good:

ADDRESS:0x4701e0  DATA:aaaaaaaaa
ADDRESS:0x4701e0  DATA:aaaaaaaa
ADDRESS:0x4701e0  DATA:aaaaaaa

How to use strptime() function in Windows

The GNU C strptime function is used to convert a given string (s), which is described as format, into a standard C time struct called tm:

char *strptime(const char *s, const char *format, struct tm *tm);


This time function is very handy when you try to convert a DateTime string into a time struct in C. And is often used together with its counterpart, strftime, to perform translation of the input DateTime string in the original format into the target format (e.g. here).


Recently, when working with the program using VS 2005 compiler, I found that the strptime function was not supported in the Windows' compiler. When checking out the time.h header file in \VC\include\time.h in the Visual Studio folders, you won't see the declaration of the strptime. So in order to use this function on Windows:


1. Since the glibc is designed for UNIX-like system, and it is advisable to use a gcc compiler on Windows (e.g. cygwin) to compile your program;


2. Or use other implementations instead:
1) http://plibc.sourceforge.net/doxygen/strptime_8c-source.html
2) http://www.opensource.apple.com/source/lukemftp/lukemftp-3/lukemftp/libukem/strptime.c
3) (In C++, Boost C++ Libs) http://www.boost.org/doc/libs/1_47_0/doc/html/date_time/date_time_io.html


3. Or write your own conversion function strptime().

A very simple gcc makfile for Creating and Linking a static C lib on Windows

The short makfile script below is to create and use a static c lib in gcc compiler for C code.


Requirement:
1. gcc compiler (e.g. cygwin);
2. Put in a folder the following files:
   main.c //main program, to call mylib.lib
   mylib.c //lib's src, to generate mylib.lib
   mylib.h //lib's hearder
   makefile


makefile:
#my library
LIB_SRC = mylib.c
LIB_DEP = $(LIB_SRC:.c=.h)
LIB_OBJ = $(LIB_SRC:.c=.o)
LIB = $(LIB_SRC:.c=.lib)
#main program
SRC = main.c
BIN = main.exe
# include directories
INCLUDES = -I.
# compiler
CC = gcc
# dependency
$(BIN): $(LIB) $(SRC)
$(CC) -o $(BIN) $(SRC) $(LIB)
$(LIB): $(LIB_OBJ)
ar rcs $(LIB) $(LIB_OBJ)
$(LIB_OBJ): $(LIB_SRC) $(LIB_DEP)
$(CC) -c -o $@ $< $(INCLUDES)
clean:
rm -f $(LIB_OBJ) $(LIB) $(BIN)


Add tab before for each command line.


Usage:
To run on a UNIX-like command line tool in Windows:
$ make
or
$ make main.exe
will compile and generate both mylib.lib and main.exe
$ make mylib.lib
will compile and generate only mylib.lib


For more info: GNU `make`

Calculate Elapsed Time in C

We can use the function and structs in standard C library (sys/time.h) to calculate the elapsed time value between two time instances:

1. To get the processor time of the program, we use the C library clock_t struct to count the CPU clock ticks, and then divide the CLOCKS_PER_SEC to get the time:

    e.g.
        clock_t t;
        t = clock();   
        // Do something
        t = clock() - t;
        double cpu_time_elapsed = (double)t/CLOCKS_PER_SEC;

2. To calculate the time interval in wall clock time, use the C library time_t struct and the time difference function:
   
    double difftime(time_t end, time_t start)
   
  , where the start and end time can be initialized by calling time_t time(time_t *time) function, and the return value is the seconds (in double) elapsed between start and end.

    e.g.   
        time_t start, end;
        time(&start);
        // Do something
        time(&end);
        double time_elapsed = difftime(end, start);

3. To calculate the time interval more precisely (in higher resolution), we can define a C function like:

    double getTimeElapsed(struct timeval end, struct timeval start)
    {
        return (end.tv_sec - start.tv_sec) + (end.tv_usec - start.tv_usec) / 1000000.00;
    }
  , where the struct timeval is elapsed time declared in the sys/time.h. It contains two members:

        tv_sec (number of seconds elapsed)
       
  and
 
        tv_usec (remaining second fraction in microseconds).

    To get the start and end time value, we call the gettimeofday() function.
 
    e.g.
        timeval start, end;
        gettimeofday(&start, NULL);
        // Do something
        gettimeofday(&end, NULL);
        double time_elapsed = getTimeElapsed(end, start);
       
    Another time struct, timespec has two members tv_sec and tv_nsec, where tv_nsec represent remaining second fraction in nanosecond.
   

Reference: 

1. GNU C Library Manual: 21.2 Elapsed Time

2. difftime on cplusplus.com