const pointer to const data

This post explores the difference between constant pointers and pointers to constant data, and the priority difference between reference operator (*) and increment operator (++). This is a very common question asked in interviews.

#include <stdio.h>

int main (){

    int v[] = {5, 20};
    int *p = v;
    printf("p: %d, ", (*p)++); // increments data pointed
    printf("p: %d, ", *p++);   // increments pointer. Equivalent to *(p++) because '++' has higher priority
    printf("p: %d\n", *p);
    
    /* pointer to constant data (can't modified data pointed) */
    const int *p2 = v;
    //int const *p2 = v; // same as above
    //printf("const ptr: %d, ", (*p2)++); // error: increment of read-only location
    printf("const ptr: %d, ", *p2++);   // '++' has priority, so incrementing pointer
    //printf("const ptr: %d, ", *(p2++)); // same as above 
    printf("const ptr: %d\n", *p2);
    
    /* constant pointer (can't modified pointer). Same as 'int p3[] = v' */
    int * const p3 = v;
    //int * p3 const = v;    // error: expected ‘=’,..., before ‘const’
    printf("ptr to const data: %d, ", (*p3)++); // incrementing data refered by pointer
    //printf("ptr to const data: %d, ", *p3++); // error: increment of read-only variable ‘p3’
    printf("ptr to const data: %d\n", *p3);
    
    /* constant pointer to constant data */
    const int * const p4 = v;
    // int const * const p4; // same as above
    //printf("const ptr to const data: %d, ", (*p4)++); // error: increment of read-only location ‘*p4’
    //printf("const ptr to const data: %d, ", *p4++);   // error: increment of read-only variable ‘p4’
    printf("const ptr to const data: p4: %d\n", *p4);
    
    /* array definition is equivalent to constant pointer. Same as 'int * const v' */
    printf("ptr from array: %d, ", (*v)++);
    //printf("ptr from array: %d, ", *v++); // error: lvalue required as increment operand
    printf("ptr from array: %d\n", *v);
    
    return 1;
}

gcc sorting2.c
./a.out 
p: 5, p: 6, p: 20
const ptr: 6, const ptr: 20
ptr to const data: 6, ptr to const data: 7
const ptr to const data: p4: 7
ptr from array: 7, ptr from array: 8

Find if all characters are unique in string

I found this problem in ‘Cracking the Code Interview’ book. It’s actually the first problem given (1.1) in the book. It is a pretty common question asked in interviews. The problem is about writing a function that returns true if all characters in string are unique, and false otherwise. There is actually a lot more to it that it may look like first. I implemented a few solutions in C.

#define FALSE 0
#define TRUE 1

/* implement function that returns true
is all characters in a string are
unique, and false otherwise
*/

// time O(n^2). No extra space needed
int uniqueCharac1(char *ptr1) {
    char *ptr2;
    while (*ptr1++ != '\0') {
        ptr2 = ptr1;
        while (*ptr2++ != '\0') {
            if (*ptr2 == *ptr1) {
                printf("Letter %c repeated\n", *ptr2);
                return FALSE;
            }
        }
    }
    return TRUE;
}

//time O(n). Extra space O(1). Using bitmap
int uniqueCharac2(char *ptr) {
    unsigned int bit_field = 0x0; // needs 27 bits (one bit per letter).
    // int gives 4 bytes (32 bits)
    int character;
    while (*ptr++ != '\0') {
        character = *ptr - 'a' + 1; // 'a' is 1
        //printf("Letter %c is number %d\n", *ptr, character);
        // checking if bit set
        if (bit_field && (1<<character)) {
            printf("Letter %c repeated\n", *ptr);
            return FALSE;
        }
        // setting bit
        bit_field |= (1&lt;&lt;character);
    }
    return TRUE;
}

char * quicksort(char *string) { // TO DO
    return string;
}
int binarysearch(char *string, char letter) { // TO DO
    return TRUE;
}

//time O(n*log n). No extra space needed. Using quicksort
int uniqueCharac3(char *ptr) {
    char *sorted = quicksort(ptr);
    while (*ptr++ != '') {
        if (binarysearch(ptr + 1, *ptr)) {
            printf("Letter %c repeated\n", *ptr);
            return TRUE;
        }
    }
    return FALSE;
}

int main(int argc, char **argv){
    char string[] = "asdfqwersdfga";
    if (uniqueCharac1(string)) {printf("Characters in %s are unique\n", string); }
    if (uniqueCharac2(string)) {printf("Characters in %s are unique\n", string); }

}

memcpy implementation

I was asked once during an interview to implement memcpy in C. The questions sounds simple first, but there is a lot to it actually. I think I did learn a lot by pointers and memory by researching this question. The code below shows 4 implementations of memcpy. The first one is the trivial implementation. The second one improves security by avoiding overwriting memory from the pointers. The third ones improves performance by copying one word at a time, instead of 1 bytes at a time. The fourth one copies a word at a time, and start copying with destination aligned to word byte boundary. The fifth one (TBD) copies with both source and destination aligned to word byte boundary.

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

void mymemcpy1(void *, const void *, size_t );
void mymemcpy2(void *, const void *, size_t );
void mymemcpy3(void *, const void *, size_t );
void mymemcpy4(void *, const void *, size_t );

int main(int argc, char **argv) {
 char source[] = &amp;quot;0123456789abdcdefghi&amp;quot;;  // 21 bytes (20 letters + '\0')
    char dest[100];

    // void * memcpy ( void * destination, const void * source, size_t num );
    memcpy(dest, source, strlen(source) + 1);
    printf(&amp;quot;Source: %s. Destination: %s\n&amp;quot;, source, dest);

    strcpy(source, &amp;quot;0123456789abdcdefghi&amp;quot;);
    mymemcpy1(dest, source, strlen(source) + 1);
    printf(&amp;quot;Source: %s. Destination: %s\n&amp;quot;, source, dest);

    strcpy(source, &amp;quot;0123456789abdcdefghi&amp;quot;);
    mymemcpy2(dest, source, strlen(source) + 1);
    printf(&amp;quot;Source: %s. Destination: %s\n&amp;quot;, source, dest);

    strcpy(source, &amp;quot;0123456789abdcdefghi&amp;quot;);
    mymemcpy3(dest, source, strlen(source) + 1);
    printf(&amp;quot;Source: %s. Destination: %s\n&amp;quot;, source, dest);

    strcpy(source, &amp;quot;0123456789abdcdefghi&amp;quot;);
    mymemcpy4(dest, source, strlen(source) + 1);
    printf(&amp;quot;Source: %s. Destination: %s\n&amp;quot;, source, dest);
    return 0;
}

// simple implementation
void mymemcpy1(void *dest, const void *source, size_t num) {
    int i = 0;
    // casting pointers
    char *dest8 = (char *)dest;
    char *source8 = (char *)source;
    printf(&amp;quot;Copying memory %d byte(s) at a time\n&amp;quot;, sizeof(char));
    for (i = 0; i &amp;lt; num; i++) {
        dest8[i] = source8[i];
    }
}
// it checks that destination array does not overwrite
// source memory
void mymemcpy2(void *dest, const void *source, size_t num) {
    int i = 0;
    // casting pointers
    char *dest8 = (char *)dest;
    char *source8 = (char *)source;
    printf(&amp;quot;Copying memory %d byte(s) at a time\n&amp;quot;, sizeof(char));
    for (i = 0; i &amp;lt; num; i++) {
        // make sure destination doesnt overwrite source
        if (&amp;amp;dest8[i] == source8) {
            printf(&amp;quot;destination array address overwrites source address\n&amp;quot;);
            return;
        }
        dest8[i] = source8[i];
    }
}

// copies 1 word at a time (8 bytes at a time)
void mymemcpy3(void *dest, const void *source, size_t num) {
    int i = 0;
    // casting pointers
    long *dest32 = (long *)dest;
    long *source32 = (long *)source;
    char *dest8 = (char *)dest;
    char *source8 = (char *)source;

    printf(&amp;quot;Copying memory %d bytes at a time\n&amp;quot;, sizeof(long));
    for (i = 0; i &amp;lt; num/sizeof(long); i++) {
        if (&amp;amp;dest32[i] == source32) {
            printf(&amp;quot;destination array address overwrites source address\n&amp;quot;);
            return;
        }
        dest32[i] = source32[i];
    }
    // copy the last bytes
    i*=sizeof(long);
    for ( ; i &amp;lt; num; i++) {
        dest8[i] = source8[i];
    }
}

/* memory addres is n-byte aligned when address is multiple of n bytes
   b-bit aligned is equivalent to b/8-byte aligned
   padding = n - (offset &amp;amp; ( -1)) = -offset &amp;amp; (n-1)
   aligned offset = (offset + n-1) &amp;amp; ~(n-1)

   Copies 8 bytes at a time with destination align to 64-byte boundary
*/
void mymemcpy4(void * dest, const void * source, size_t size) {

#define NBYTE 8 // n-byte boundary

    int i = 0;
    int j = 0;

    // short and long pointers for copying 1 and 8 (sizeof(long))
    //  bytes at a time
    long * destlong = (long *)dest;
    long * sourcelong = (long *)source;
    char * destshort = (char *)dest;
    char * sourceshort = (char *)dest;


    // copy first bytes until destination hits 64-byte boundary
    while((((uintptr_t)&amp;amp;destshort[i] &amp;amp; (uintptr_t)(NBYTE-1)) != 0) &amp;amp;&amp;amp; \
          (&amp;amp;destshort[i] != source) &amp;amp;&amp;amp; (i &amp;lt; size)) {
        destshort[i] = sourceshort[i];
        i++;
    }
    printf(&amp;quot;%s: copied %d bytes up to %d-byte alignment\n&amp;quot;,
           __func__, i, NBYTE);


    // now copy 8 (sizeof(long)) bytes at a time with dest aligned
    // align destination pointer
    destlong = ((uintptr_t)destlong + (NBYTE-1)) &amp;amp; ~(uintptr_t)(NBYTE-1);
     // continue copying where left off (we should align source as well...)
    sourcelong = (long *)sourceshort;
    // j+1 * 8 - 1 to avoid copying beyond last element in last iteration
    while ((j+1)*sizeof(long) - 1 + i &amp;lt; size &amp;amp;&amp;amp;\
            &amp;amp;destlong[j] &amp;lt; (long *)source) {
        destlong[j] = sourcelong[j];
        j++;
    }
    printf(&amp;quot;%s: copied %d bytes %d bytes at a time\n&amp;quot;, __func__,
           j*sizeof(long), sizeof(long));


    // finally copy last bytes
    i = i + j*sizeof(long);
    int prev_i = i;
    while(i &amp;lt; size &amp;amp;&amp;amp; &amp;amp;destshort[i] &amp;lt; (char *)source) {
        destshort[i] = sourceshort[i];
        i++;
    }
    printf(&amp;quot;%s: copied last %d bytes one at a time\n&amp;quot;,
            __func__, i-prev_i);

}

/* simpler implementation of mymemcpy4 */
void mymemcpy4b(const void * dest, void * src, size_t size) {

    char * dest1 = (char *)dest;
    char * src1 = (char *)src;
    int n = 0;
#define NBYTE 64
    // copy up to nbyte alignment
    while ((((uintptr_t)dest1 & ~(NBYTE-1) != 0x00) && (n < size) {
        *dest1++ = *src1++;
        n++;
    }
    printf("copied %d bytes at a time up to %d bytes\n", sizeof(char), n);

    // copy up to end minus last sizeof(long) bytes
    long * dest2 = (long *)dest1;
    long * src2 = (long *)src1;
    while (n &lt; size - sizeof(long)) {
        *dest2++ = *src2++;
        n+=sizeof(long);
    }
    printf("copied %d bytes at a time up to %d bytes\n", sizeof(long), n);

    // copy last bytes
    src1 = (char *)src2;
    dest1 = (char *)dest2;
    while (n &lt; size) {
        *dest1++ = *src1++;
        n++;
    }
    printf("copied up to %d bytes\n", n);
}

The result is this:

Source: 0123456789abdcdefghi. Destination: 0123456789abdcdefghi
Copying memory 1 byte(s) at a time
Source: 0123456789abdcdefghi. Destination: 0123456789abdcdefghi
Copying memory 1 byte(s) at a time
Source: 0123456789abdcdefghi. Destination: 0123456789abdcdefghi
Copying memory 8 bytes at a time
Source: 0123456789abdcdefghi. Destination: 0123456789abdcdefghi
mymemcpy4: copied 0 bytes up to 64-byte alignment
mymemcpy4: copied 16 bytes 8 bytes at a time
mymemcpy4: copied last 5 bytes one at a time
Source: 0123456789abdcdefghi. Destination: 0123456789abdcdefghi

With mymemcpy4b:

 ./a.out
copied 1 bytes at a time up to 0 bytes
copied 8 bytes at a time up to 32 bytes
copied up to 40 bytes
src: 1234567890abcdefghi1234567890ABCDEFGHI
dest: 1234567890abcdefghi1234567890ABCDEFGHI

 ./a.out
copied 1 bytes at a time up to 16 bytes
copied 8 bytes at a time up to 32 bytes
copied up to 40 bytes
src: 1234567890abcdefghi1234567890ABCDEFGHI
dest: 1234567890abcdefghi1234567890ABCDEFGHI

Linked list without head node

I wrote a simple linked list, more than anything to see double pointers in action. Instead of using a dummy node as a head, I used a simple pointer to the list. This pointer to list could be a global variable, so that all functions could modify it. But I made local in the main function, which means it needs to be passed ‘by reference’ to be modify.

#include <stdio.h>
#include <stdlib.h>

typedef int data_t;

struct node {
    //data_t data; // could do this, but let's use void data, which is more flexible
    void *data;
    struct node *next;
};

typedef struct node node_t;


void insertEnd(node_t **, void *);  // passing pointer 'by reference'
void traverse(node_t *);            // passing pointer 'by value'
void delete(node_t **, void *);

int main (int argc, char **argv) {

    // Using pointer to list without dummy node, which makes things a bit more difficult
    // Since headptr needs to be modified in function, it needs to be passed by 'reference'
    // which means passing a pointer to the head pointer
    node_t * headptr = NULL;

    void *somedata[] = {"one", "two", "three"};
    int i;
    for (i = 0; i  0; i--) {
        delete(&amp;headptr, somedata[i]);
        traverse(headptr);
    }
}

void insertEnd(node_t **headptr, void *data) {

    // allocate new node
    node_t *newnode = malloc(sizeof(node_t));
    newnode-&gt;data = data;
    newnode-&gt;next = NULL; // it's last

    node_t *current, *prev;
if (*headptr == NULL) { // if list empty
        *headptr = newnode;
    } else {
        current = *headptr;
        prev = NULL;
        while (current != NULL) {
            prev = current;
            current = current-&gt;next;
        }
        prev-&gt;next = newnode;
    }
}

void traverse(node_t *headptr) {
    node_t *current = headptr;
    while (current != NULL) {
        // watch for segmentation fault. Incrementing current before printing would cause it
        printf ("%s, ", (char *)current-&gt;data);
        current = current-&gt;next;
    }
    printf ("\n");
}

void delete(node_t **headptr, void *data) {

    node_t *current = *headptr;
    node_t *prev;

    if (*headptr != NULL) {
        while (current != NULL &amp;&amp; strcmp((char *)current-&gt;data, (char *)data) != 0) {
            prev = current;
            current = current-&gt;next;
        }
        if (current != NULL) {
            free(current);
            prev-&gt;next = NULL;
        }
    }
}

The output is this:

one,
one, two,
one, two, three,
one, two,
one,

Pointer arithmetic

I was looking at what the ‘+’ and ‘-‘ operators actually performs when applied to pointers and arrays, as well as other tricks, and wrote some programs to test it:

#include <stdio.h>

main()
{
    int Arr[16];
    unsigned int a0 = (unsigned int) &Arr[0];
    unsigned int a3 = (unsigned int) &Arr[3];
    printf("%u\n", a3 - a0);
    printf("%u\n", &Arr[3] - &Arr[0]);
}

The result is this:

12
3

This other program explores this feature and some others:

#include <stdio.h>

int main()
{
    int Arr[16];
    Arr[0] = 9;
    Arr[3] = 5;
    printf("Arr[3]:      \t%d\n",Arr[3]);
    printf("*(Arr + 3):  \t%d\n",*(Arr + 3));
    printf("*(3 + Arr):  \t%d\n",*(3 + Arr));
    printf("*(&Arr[0] + 3):\t%d\n",*(&Arr[0] + 3)); // &Arr[0] is the same as Arr
    printf("3[Arr]:      \t%d\n",3[Arr]); // gets converted by compiler to *(3 + Arr)
    printf("\n");

    // showing how + operation behaves when used with addresses of pointers or arrays
    printf("Arr:         \t%u\n", Arr);
    printf("&Arr[0]:     \t%u\n", &Arr[0]);
    printf("&Arr[0] + 1: \t%u\n", &Arr[0] + 1);
    printf("&*(&Arr[0] + 1):%u\n", &*(&Arr[0] + 1));
    printf("sizeof(Arr): \t%d\n", sizeof(Arr));
    printf("sizeof(Arr[0]):\t%d\n", sizeof(Arr[0]));
    printf("sizeof(int):\t%d\n", sizeof(int));
    printf("\n");

    printf("sizeof(&Arr[0]):%d\n", sizeof(&Arr[0]));
    printf("sizeof(unsigned long):%d\n", sizeof(unsigned long));
    printf("\n");


    unsigned long ArrAddr = (unsigned long)&Arr[0];
    printf("ArrAddr: %u\n", ArrAddr);
    int *p;
    p = ArrAddr;
    printf("*p: %d\n", *p);
    printf("*(p+3): %d\n", *(p+3));
    printf("\n");

    // breaking operator overloading of +
    unsigned long ArrAddr3 = ArrAddr + 3;
    p = ArrAddr3;
    printf("ArrAddr3: %u\n", ArrAddr3);
    printf("*p: %d\n", *p);
    printf("\n");

    // doing manually what overloading of + does automatically
    ArrAddr3 = ArrAddr + 3*sizeof(Arr[0]);
    p = ArrAddr3;
    printf("ArrAddr3: %u\n", ArrAddr3);
    printf("*p: %d\n", *p);
    printf("\n");



    return 0;

}

The result is this:

Arr[3]:         5
*(Arr + 3):     5
*(3 + Arr):     5
*(&Arr[0] + 3): 5
3[Arr]:         5

Arr:            1587159312
&Arr[0]:        1587159312
&Arr[0] + 1:    1587159316
&*(&Arr[0] + 1):1587159316
sizeof(Arr):    64
sizeof(Arr[0]): 4
sizeof(int):    4

sizeof(&Arr[0]):8
sizeof(unsigned long):8

ArrAddr: 1587159312
*p: 9
*(p+3): 5

ArrAddr3: 1587159315
*p: 0

ArrAddr3: 1587159324
*p: 5