C 101

programming

Basic syntax

  • Type: unsigned int, int, float, double, char, long, long long.

  • c pre-processor(macros): #include …, #define

    1
    2
    3
    int main (int argc, char *argv[])
    const float g = 1.222;
    enum color {RED, GREEN, BLUE}; //a group of related integer constants

  • struct, unions

    • structs: groups list of variables under one block in memory
    • Union: store different data types in same region of memory

  • Control flow: for, switch

  • Variable declarations

    ANSI C: A variable may be initialized in its declaration. if not, it holds garbage!

    C99 has changed and is similar to java.

  • Undefined behavior: Heisenbugs

  • string: Null-character (‘\0’) terminated character arrays

  • Macros: replace a name with its macro definition.

    Constants, simple operations, …

    use parentheses around macro arguments and result.

    1
    2
    3
    4
    5
    #define INT_MAX 0x7FFFFFFFF
    #define MAX(A, B) ((A) > (B) ? (A) : (B))
    #define REQUIRES(COND) assert(COND)
    #define WORD_SIZE 4
    #define NEXT_WORD(a) ((char*)(a) + WORD_SIZE)

  • header guards: double-inclusion problem

    • include same header file twice.

pointers/arrays

Declaring a pointer allocates space to hold the pointer without allocating space to the value pointing to. Local variables in C are not initialized and may contain anything.

  • Pointers allow cleaner,more compact code while hiding bugs like dangling references and memory leaks due to dynamic memory management.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void * (a type that can point to anything)
      
    //pointers to functions.
    int (*fn) (void *, void *) = &foo  //fn is a function that accepts two void * pointers and returns an int and is initially pointing to the function foo.
    //(*fn)(x,y) call the function
      
    //NULL pointers
    if (!p) /* p is a null pointer*/
    if q /* q is not a null pointer*/

  • null pointers: program crash when u write/read a null pointer

  • Modern machines are “byte-addressable”.(8-bit storage cells.) We want word allignment. Programs can be slow if you try to access unaligned memory.

  • Pointer arithmetic

    sizeof, the unit is byte. Pointer + n means adding n*sizeof(type) to the memory addresss

  • pointer to pointer

    1
    2
    3
    4
    5
    6
    void IncrementPtr(int **h){
      *h = *h + 1;
    }
    int A[3] = {1,2,3}
    int *q = A; //*q = A[0]
    IncrementPtr(&q); //*q = A[1]

array

An array variable is a pointer to the first element

1
2
3
4
5
//declaration
char *string ar
char string[] ar
//ar[0] = *ar
//ar[2] = *(ar+2)

declarations of array differ in: incrementing, declaration of filled arrays.

Declared arrays are only allocated while the scope
is valid. An array in C does not know its own length, & bounds not checked.

bit mask and Shifting

Logical shift correspond to (left-shift) multiplication by 2, (right-shift) integer division by 2.

  • <<,>> is logical shifting.

Arithmetic shift is something related to 2’s-complement representation of signed numbers. In this representation, the sign is the leftmost bit, then arithmetic shift preserves the sign (this is called sign extension).

Rotate has no ordinary mathematical meaning, and is almost an obsolete operation even in computers.

1
2
//number representations
unsigned char mask = 1; // 00000001,binary

Memory management

dynamic memory allocation

Rule:

  • Malloc what you free, free what you malloc.

  • #mallocs = #frees, or memeory leak/double free

  • Free a malloced block exactly once

  • only malloc when necessary

    • Persistent, variable sized data structures
    • concurrent accesses.

Assume size of objects can be misleading and is bad style, so use sizeof(type).

  • malloc():To allocate room for something new to point to, use malloc(). Once malloc() is called, the memory location contains garbage, so don’t use it

  • free():until you’ve set its value. After dynamically allocating space, we must dynamically free it.

    • Bugs happen when free(): frees the same memory twice; frees on sth you didn’t get back from malloc().
1
2
3
4
ptr = (int*) malloc (sizeof(int));
free(ptr);

realloc(p, size);
  • Realloc(): managing the heap. Resize a previously allocated block at p to a new size.
    • if p is NULL, behaves like malloc
    • if size is 0, behaves like free
  • void* malloc (size_t size): allocate block of memory of size bytes,does not initialize memory
  • void* calloc (size_t num, size_t size): allocate block of memory for array of num elements, each size bytes long, initializes memory to zero.

memory location

  • Allocate memory for data

    • declaration of local variable
    • Dynamic allocation at runtime by calling allocation function
    • date delcared outside of any procedure(global)

  • Stack: last in, first out data structure. Stack grows down.

    Stack frames contiguous blocks of memory; stack pointer tells where top stack frame is. When procedure ends, stack frame is tossed off the stack; frees memory for future stack frames.

  • Heap: not contiguous.

    需要效率和最小使用内存，避免可用内存碎片化。

    Implementation:

    memory structure: Each block of memory is preceded by a header that has two fields: size of the block and a pointer to the next block. All free blocks are kept in a circular linked list, the pointer field is unused in an allocated block.

    Malloc() 在可用的内存列表寻找是否有足够的空间，如果没有，向操作系统请求更多的内存。free()检查当前可用空间周围的空间是否可用，如果可用就合并，否则就将另外的可用内存块加入链表。

    Malloc() 如何在多个均符合条件的内存块中选择？

    • Best-fit
    • First-fit
    • Next-fit: first-fit + remember where we finished searching and resume searching from there.

things go wrong

  • returning pointers into the stack

    Pointers in C allow access to deallocated memory, leading to hard-to-find bugs.

    The address of something on the stack will be invalid after the function’s execution

  • use after free

  • Forgetting realloc can move data

  • Freeing the wrong stuff

  • Double-free

  • Losing the initial pointer