The tutorial will cover basics of C concepts, and implementations of a couple functions.
Part I - Basics of C
Arrays and Pointers are ideally the same. Actually, the name of an array is the same as a pointer to its first element. In simple terms a pointer is just an unsigned int, with "special powers." Pointers have the ability to go to the address it holds and access the data type T, if the pointer is of type "pointer to T" (T *). An array can be thought of as a T * const type, that is the address that it points to cannot be changed.
Also, you can think of there being the most basic unit of pointers, the char*, since a char is one byte. In any event, I will give some examples to demonstrate this:
struct A a;
struct A* pa = &a;
pa points to a struct, or put another way, pa holds the address of a struct A type.
*pa will go to the memory location that pa currently holds and extract the type to which it points, namely the type is struct A.
so
*pa holds the exact same object of "a" in the example above.
Since, the universal pointer is the char*, we can access each byte of the "a" object like so:
char *c = pa; // point to the starting address of "a"
We can scan through every byte, but there is something essential we must know about incrementing a pointer:
If we have a pointer of type T, then incrementing the pointer by one is equivalent to doing:
T *p;
p + 1 ; // increment by one
start at p's address and add sizeof(T) bytes to get "p+1"
That's why a char* is universal, everytime you increment a char*, it gets increased by only one.
Thereby, letting you move freely within any aggregate data type, using a char*.
Malloc() is a function call that returns an address; ideally, you just cast to the proper T* for proper assignment. However, if you understand what pointers are, then it's legal to just assign it to an unsigned int. (if you cast correctly)
Malloc, basically keeps track of a header that will hold the total size of the current block, as well as have a flag to check if it's currently in use. Free() knows the size of this magical header and will set the flag back to unused, so that this memory can be used again some time later. Think of the header something like so:
struct malloc_header {
size_t totalSizeToAllocateIncludingHeader;
char isBeingUsed;
};
So when you call malloc(), it's actually adding the size of the header to the total number of bytes to allocate:
int MALLOC(size_t size) {
return size + sizeof( struct malloc_header);
}
where the standard malloc() will return
the total number of bytes actually needed.
and when you call free, it moves back sizeof(struct malloc_header) bytes to get to the header and unset the isBeingUsed flag and deallocate that block of memory.
Another concept that should be known is pass by value and pass by reference. In C, there is no such thing as pass by reference. However, there is a hack to get passed this dilemma. Just pass a pointer (address of an object), and if you change the value through this pointer, then the object will be changed after the function call. That's the entire concept of "trying to make C parameters pass by reference." An example follows:
void func( char *c ) {
*c = 3;
}
char c = 5;
func(&c);
// c is now 3 after the function call
Address-of operator is a nice operator to have. Bascially, it just does a look-up on the type that is using the address-of (&) operator and returns a pointer of that type. For example,
char c = 3;
char *d = &c; // c's type is "char", so &c returns a pointer to type char, char*
char **s = &d; // d's type is "char*", so &d returns a pointer to type char*, char**
char a[3];
&a is of type char (*)[3], because a is of type char[3], therefore it's a pointer to an array of 3 chars.
Common things to know about strings. In C, there is a little problem with C-style strings, as they call it. They are basically null-terminated strings, meaning, they need to end in the integer value 0, or ascii char value '\0'. It's basically a hack that was agreed upon. If this value is not present, none of the string library functions will work for you. Also, string literals (sequences of characters in double quotes) always end with a '\0' (null-terminator character). Therefore,
"hello" is actually seen as hello\0 by the compiler. There are some differences when assigning string literals though.
In pointer notation:
char *s = "hello"; // s points to the address where 'h' is located
char s[] = "hello"; // s contains the string 'h', 'e', 'l', 'l', 'o', '\0' as its elements in the array
The value of s, in both cases hold the address of a char that has value 'h', though they are NOT the same address, but they both hold the same value.
Function calls in C -
Basically when a function call is executed, an activation record is set up and added to the stack.
First what happens is that the parameters to the function get added, then the return address get added, and then the local variables (sometimes called automatic variables) are added to the stack. They are popped back off the stack in reverse order. That's why they tell you to NEVER return the address of a local variable. (It's automatically deleted)
*You should know fork(), waitpid(), wait() and semaphores/locks *
Part II - Examples (Code)
int atoi(char *str) {
// str holds "1235"
char isNeg = str[0] == '-'; // is it neg?
int i, currValue = 0;
/* if we multiply currValue by 10, we are shifting the currValue to the left */
/* for example, say we have "23" and currValue = 2, currValue * 10 = 20, so
currValue * 10 + 3 = 23
*/
for( i = isNeg; i < strlen(str); ++i )
currValue = currValue * 10 + (str[i]-'0'); // shift it to the left and add an integer if( isNeg ) currValue = -currValue; return currValue; } char *itoa(int number) { char isNeg = number < number =" -number;" s =" (char*)malloc(32);" count =" 0;" t =" s;" count =" 0;" half =" size/2;" i =" 0;" i =" 0;" curr ="="" next =" curr-">next;
curr->next = prev;
return reverse(curr, next);
}
// iterative solution
struct Node * reverse( struct Node *head) {
struct Node *prev = NULL;
while( head ) {
// keep track of the next Node* in the list
struct Node *next = head->next;
// let head's next pointer be its previous
head->next = prev;
// update the pointers for prev and head
prev = head;
head = next;
}
return prev;
}
// inorder traversal for a binary tree
void inOrder( struct Node *root ) {
if( !root ) return;
inOrder(root->left);
/* print out the value of this node */
printf("%d\n", root->id);
inOrder(root->right);
}
