Pure Functions | GeeksforGeeks

A function is called pure function if it always returns the same result for same argument values and it has no side effects like modifying an argument (or global variable) or outputting something. The only result of calling a pure function is the return value. Examples of pure functions are strlen(), pow(), sqrt() etc. Examples of impure functions are printf(), rand(), time(), etc.

If a function is known as pure to compiler then Loop optimization and subexpression elimination can be applied to it. In GCC, we can mark functions as pure using the “pure” attribute.

__attribute__ ((pure)) return-type fun-name(arguments1, …)
{
    /* function body */
}

If “strlen()” function is not marked as pure function then compiler will invoke the “strlen()” function with each iteration of the loop, and if function is marked as pure function then compiler knows that value of “strlen()” function will be same for each call, that’s why compiler optimizes the for loop and generates code like following.

Marking function as pure says that the hypothetical function “my_strlen()” is safe to call fewer times than the program says.

Read full article from Pure Functions | GeeksforGeeks

Stack and Heap in C and C++

The Stack
It's a special region of your computer's memory that stores temporary variables created by each function (including the main() function). The stack is a "FILO" (first in, last out) data structure, that is managed and optimized by the CPU quite closely. Every time a function declares a new variable, it is "pushed" onto the stack. Then every time a function exits, all of the variables pushed onto the stack by that function, are freed (that is to say, they are deleted). Once a stack variable is freed, that region of memory becomes available for other stack variables.

Variables allocated on the stack, or automatic variables, are stored directly to this memory. Access to this memory is very fast, and it’s allocation is dealt with when the program is compiled.

1. lives in RAM (random-access memory), but has direct support from the processor via its stack pointer.
2. stack pointer is moved down to create new memory and moved up to release that memory.
3. extremely fast and efficient way to allocate storage, second only to registers.
Every thread requires its own stack, they are separated from other stacks, each stack may grow separately.
very fast access
don't have to explicitly de-allocate variables
space is managed efficiently by CPU, memory will not become fragmented
local variables only
limit on stack size (OS-dependent)
variables cannot be resized

The place where arguments of a function call are stored
The place where registers of the calling function are saved
The place where local data of called function is allocated
The place where called function leaves result for calling function
Supports recursive function calls

The Heap
Variables allocated on the heap, or dynamic variables, have their memory allocated at run time (ie: as the program is executing). Accessing this memory is a bit slower, but the heap size is only limited by the size of virtual memory. This memory remains allocated until explicitly freed by the program and, as a result, may be accessed outside of the block in which it was allocated.

Heap grows toward stack
All threads share the same heap
Data structures may be passed from one thread to another.
variables can be accessed globally
no limit on memory size
(relatively) slower access
no guaranteed efficient use of space, memory may become fragmented over time as blocks of memory are allocated, then freed
you must manage memory (you're in charge of allocating and freeing variables)
variables can be resized using realloc()

Difference between the stack and the heap
Both Stack and Heap are stored in RAM.
Every thread has its own stack, but all threads in one application shares one heap.
Variable allocation is fast on stack where as on heap its slow.
Variables on stack go out of scope automatically once their need is done. That means de-allocation on stack is automatic. On heap, in regards to C and C++ we have to manually de-allocate where as high-level languages such as Java has garbage collection schemes.
On stack, we can access variables without the need for pointers and hence its fast and that is the reason it is used to store local data, method arguments and the call stack etc all that which needs less amount of memory.
You would use stack only when you know for sure how much memory for your data you would need even before compile time. On the other hand, we can use heap without us having to know for sure the amount of memory we need.
Stack is used for static memory allocation and Heap for dynamic memory allocation.
Stack is thread specific and Heap is application specific.
Memory block in stack will be freed when thread is terminated while heap is freed only after application termination.

Stack Overflow and Heap Overflow(OutOfMemory)

Can an object be stored on the stack instead of the heap?
Yes, an object can be stored on the stack. If you create an object inside a function without using the “new” operator then this will create and store the object on the stack, and not on the heap. Suppose we have a C++ class called Member, for which we want to create an object.

Can the stack grow in size? Can the heap grow in size?
The stack is set to a fixed size, and can not grow past it’s fixed size (although some languages have extensions that do allow this). So, if there is not enough room on the stack to handle the memory being assigned to it, a stack overflow occurs. This often happens when a lot of nested functions are being called, or if there is an infinite recursive call.

If the current size of the heap is too small to accommodate new memory, then more memory can be added to the heap by the operating system.

What can go wrong with the stack and the heap?
If the stack runs out of memory, then this is called a stack overflow – and could cause the program to crash. 
The heap could have the problem of fragmentation, which occurs when the available memory on the heap is being stored as noncontiguous (or disconnected) blocks – because used blocks of memory are in between the unused memory blocks. When excessive fragmentation occurs, allocating new memory may be impossible because of the fact that even though there is enough memory for the desired allocation, there may not be enough memory in one big block for the desired amount of memory.
heap overflow is generally called 'out of memory'.

References
http://www.quora.com/Objective-C-programming-language/What-is-the-difference-between-the-stack-and-the-heap
http://www.programmerinterview.com/index.php/data-structures/difference-between-stack-and-heap/
http://timmurphy.org/2010/08/11/the-difference-between-stack-and-heap-memory-allocation/comment-page-1/

Memory Layout of C Programs | GeeksforGeeks

A typical memory representation of C program consists of following sections.

1. Text Segment:
A text segment , also known as a code segment or simply as text, is one of the sections of a program in an object file or in memory, which contains executable instructions.

As a memory region, a text segment may be placed below the heap or stack in order to prevent heaps and stack overflows from overwriting it.

Usually, the text segment is sharable so that only a single copy needs to be in memory for frequently executed programs.  Also, the text segment is often read-only, to prevent a program from accidentally modifying its instructions.

2. Initialized Data Segment:
Initialized data segment, usually called simply the Data Segment. A data segment is a portion of virtual address space of a program, which contains the global variables and static variables that are initialized by the programmer.

Note that, data segment is not read-only, since the values of the variables can be altered at run time.

This segment can be further classified into initialized read-only area and initialized read-write area.

3. Uninitialized Data Segment:uninitialized data starts at the end of the data segment and contains all global variables and static variables that are initialized to zero or do not have explicit initialization in source code.

4. Stack:
The stack area traditionally adjoined the heap area and grew the opposite direction; when the stack pointer met the heap pointer, free memory was exhausted. 

The stack area contains the program stack, a LIFO structure, typically located in the higher parts of memory. A “stack pointer” register tracks the top of the stack; it is adjusted each time a value is “pushed” onto the stack. The set of values pushed for one function call is termed a “stack frame”; A stack frame consists at minimum of a return address.

Stack, where automatic variables are stored, along with information that is saved each time a function is called. Each time a function is called, the address of where to return to and certain information about the caller’s environment, such as some of the machine registers, are saved on the stack. The newly called function then allocates room on the stack for its automatic and temporary variables. This is how recursive functions in C can work. Each time a recursive function calls itself, a new stack frame is used, so one set of variables doesn’t interfere with the variables from another instance of the function.

5. Heap:
Heap is the segment where dynamic memory allocation usually takes place.

The heap area begins at the end of the BSS segment and grows to larger addresses from there. The Heap area is shared by all shared libraries and dynamically loaded modules in a process.

Read full article from Memory Layout of C Programs | GeeksforGeeks

G-Facts from geeksforgeeks

In C language, sizeof( ) is an operator. Though it looks like a function, it is an unary operator.

To know the IP address(es) of a URL/website, nslookup can be used at the shell/command prompt (cmd.exe). It works on both types of operating systems i.e. Linux/Windows.

In C, function parameters are always passed by value. Pass-by-reference is simulated in C by explicitly passing pointer values.
In ISO C, you can define main either to take no arguments, or to take two arguments that represent the command line arguments to the program, like this:

int main (int argc, char *argv[])
Other platform-dependent formats are also allowed by the C and C++ standards; for example, Unix (though not POSIX.1) and Microsoft Visual C++ have a third argument giving the program’s environment, otherwise accessible through getenv in stdlib.h:

Bootstrapping (compilers)
http://en.wikipedia.org/wiki/Bootstrapping_(compilers)
In computer science, bootstrapping is the process of writing a compiler (or assembler) in the target programming language which it is intended to compile. Applying this technique leads to a self-hosting compiler.
Many compilers for many programming languages are bootstrapped, including compilers for BASIC, ALGOL, C, Pascal, PL/I, Factor, Haskell, Modula-2, Oberon, OCaml, Common Lisp, Scheme, Java, Python, Scala, Nimrod, Eiffel, and more.

“Pointer arithmetic and array indexing [that] are equivalent in C, pointers and arrays are different” – Wayne Throop

G-Fact 8
To uniquely construct a Binary Tree, Inorder together with either Postorder or Preorder must be given (See this for details). However, either Postorder or Preorder traversal is sufficient to uniquely construct a Binary Search Tree. To construct Binary Search tree, we can get Inorder traversal by sorting the given Preorder or Postorder traversal. So we have the required two traversals and can construct the Binary Search Tree.

The number of structurally different Binary Trees with n nodes is Catalan number Cn = (2n)!/(n+1)!*n!
http://mathworld.wolfram.com/BinaryTree.html
The number of binary trees with n nodes are 1, 2, 5, 14, 42, ... (Sloane's A000108), which are the Catalan number C_n.

Enumeration constants (enum values) are always of type int in C, whereas they are distinct types in C++ and may have size different from that of int.

In C, struct keyword must be used for declaring structure variables, but it is optional in C++.
struct node {
   int x;
   node *next; // Error in C, struct must be there. Works in C++
};

Predict the output of following program.

#include <stdio.h>
int main()
{
   int x = 012;
   printf("%d",  x);
   getchar();
   return 0;
}
The program prints 10. Putting a 0 before an integer constant makes it an octal number and putting 0x (or 0X) makes it a hexadecimal number. It is easy to put a 0 by accident, or as a habit. The mistake is very common with beginners.

Read full article from G-Facts from geeksforgeeks