Tag: programming

Data structures an introduction

Data structure: Way of organizing data so we can efficiently use it.
Essential ingredients in creating fast and powerful algorithms.
Help to manage and organize data.
makes code cleaner and easier to understand.

Abstract data type: Is an abstraction of a data structure which provides only the interface to which a data structure must adhere to. Interface will not give any specifics to how something should be implemented or in what programming language.

ADT – Implementation(DS)
List – Dynamic Array, Linked list.
Queue – Linked List Based queue, Array based queue, Stack base queue
Map – Tree map, Hash map, Hash table

Computational complexity analysis:
How much time does this algorithm needs to finish the computation?
How much space does this algoritm needs to finish the computation?

Big data
Omega meta data

Big-O notation: Upper bound complexity of the worst case irrespective of the size of data(small data set or large data set)
n – The size of the input
Complexities ordered in from the smallest to largest.
Constant Time : O(1)
Logarithmic Time : O(log(n))
Linear time : O(n)
Linearithmic Time : O(nlog(n))
Quadric Time : O(nsquared)
Cubic Time : O(ncube)
Exponential Time : O(bpowern), b>1
Factorial Time : O(n!)

O(n + c) = O(n)
O(cn) = O(n), c > 0

f(n) = 7 log(n)3 + 15n2 + 2n3 + 8

O(f(n)) = O(n3) as n3 is the biggest value.

Read More…

Variables, data types and variable types in C

Variables are used to store data.  The following are the charateristics for the variable.

  1. Variables will have unique names under a specific scope.
  2. Variable data type defines the storage requirement for the variable.
  3. Storage class of the variable defines the visibility and lifetime of the variable in a program or function or block.

The following are the rules for a variable naming.

  1. Variable can have underscore, letter or alphabet.
  2. Variable can start only with underscore or alphabet.
  3. No whitespaces allowed in a variable name.
  4. Variable name cannot be a reserved keyword.

Data types

  1. char or unsigned char
    1. single byte storage.
    2. signed will have a value -128 to 127
    3. unsigned will have a value 0 to 256
  2. short or unsigned short
    1. double byte storage.
    2. signed will have a value -32,768 to 32,767
    3. unsigned will have value 0 to 65535.
  3. int or unsigned int
    1. 4 byte storage.
    2. signed will have a value -2GB to (2GB -1)
    3. unsigned will have a value 0 to 4GB
  4. long or unsigned long
    1. 4 byte storage on 32 bit machines and 8 byte storage on 64 bit machine.
    2. for 4 bit
      1. signed will have a value -2GB to (2GB -1)
      2. unsigned will have a value 0 to 4GB
    3. for 8 bit
      1. signed will have a value of -2 power 63 to (2 power63 -1)
      2. unsigned will have a value 0 to 2 power 64.
  5. long long and unsigned long long
    1. Both 32 and 64 bit machines certain compilers support long long data type to hold 64 byte values.
    2. signed will have a value of -2 power 63 to (2 power63 -1)
    3. unsigned will have a value 0 to 2 power 64.
  6. void
    1. Data type which can be point to no storage.
    2. Used mainly for pointers to point to any storage types.
  7. pointer type
    1. Qualified with a * to address the variable points to an address which holds the data.
  8. union
    1. combination of multiple types of variable and hold the maximum size of the variable used.
  9. struct
    1. Combination of multiple types of variable and storage will be the combination of all variable datatypes.

Storage class

Storage class defines the scope of the variable and the life time of the variable.

  1. local variables
    1. Variables defined inside a function or block without any storage class specified.
  2. auto variables
    1. auto variables are defined with the keyword auto. By default all local variables are auto type.
  3. static variables
    1. static variables are defined with the keyword static.
    2. static variables can have either scope defined inside a function or a file.
    3. static variables will retain the data even if they goes out of scope and can be accessed when the code access the block/function and file again.
  4. const variables
    1. Constant variables are variable data which cannot be modified later in the code.
    2. Usually they are set to make sure the called API or code executed later cannot modify them.
  5. volatile variables
    1. volatile keyword is used to indicate compiler not to perform any optimization in the code.
  6. extern variable
    1. extern variable is used to indicate the variable is defined somewhere in another file or library.
    2. extern keyword can be used to indicate the variable storage type to compiler so we can modify the data.
  7. register variables
    1. register variables are used to indicate the compiler to use any free register to cache the value.
    2. However the compiler can ignore the register access and treat it as auto variable if not register available or cannot cache the value.

Source: Variables and Keywords in C – GeeksforGeeks

Example code

var.c

 

#include <stdio.h>

int a=1; // initialized global variable.
int b; // uninitialized global variable.

static int c; //global static variable.
extern int d;

typedef struct _abc{
char a;
short b;
int c;
}ABC;

typedef union _def{
char a;
short b;
int c;
}DEF;

int increment()
{
static int p = 5;
a=a+1;
p=p+1;

printf("dataof(p)=%d\n", p);
return 0;
}

int main(int argc, char * argv[])
{
auto int e=5; //auto variable
int f=6; //local variable
const int g=7; // constant variable
long j=10; // long type variable
long long k=11; // long long type variable
ABC h; // structure type variable
DEF i; // union type variable
char l='a'; // character type variable
short m=10; // short type variable
char *n=&l; // pointer variable.
void *o=(void *)n; // void pointer variable.
// Size check
printf("Size of char is %d bytes\n", sizeof(l));
printf("Size of short is %d bytes\n", sizeof(m));
printf("Size of int is %d bytes\n", sizeof(f));
printf("Size of long is %d bytes\n", sizeof(j));
printf("Size of long long is %d bytes\n", sizeof(k));
printf("Size of pointer is %d bytes\n", sizeof(n));
printf("Size of structure ABC is %d bytes\n", sizeof(h));
printf("Size of union DEF is %d bytes\n", sizeof(i));

//Access check
increment();
increment();
printf("dataof(a)=%d, addressof(a)=0x%x\n", a, &a);
printf("dataof(b)=%d, addressof(b)=0x%x\n", b, &b);
printf("dataof(c)=%d, addressof(c)=0x%x\n", c, &c);
printf("dataof(d)=%d, addressof(d)=0x%x\n", d, &d);
printf("dataof(e)=%d\n", e);
printf("dataof(f)=%d\n", f);
// g = g+10; in correct as its a constant 
printf("dataof(g)=%d\n", g);
printf("dataof(j)=%d\n", j);
printf("dataof(k)=%d\n", k);

return 0;
}


ext.c

int d = 4;

compilation

gcc -o test var.c ext.c

Output

yogi@localhost devel]$ ./test
Size of char is 1 bytes
Size of short is 2 bytes
Size of int is 4 bytes
Size of long is 8 bytes
Size of long long is 8 bytes
Size of pointer is 8 bytes
Size of structure ABC is 8 bytes
Size of union DEF is 4 bytes
dataof(p)=6
dataof(p)=7
dataof(a)=3, addressof(a)=0x601024
dataof(b)=0, addressof(b)=0x601038
dataof(c)=0, addressof(c)=0x601034
dataof(d)=4, addressof(d)=0x60102c
dataof(e)=5
dataof(f)=6
dataof(g)=7
dataof(j)=10
dataof(k)=11

C/C++ Tokens – GeeksforGeeks

In C/C++ tokens are the smallest element of a program. Tokens can be split into the following

1. Keywords
Predefined tokens in a programming language having fixed meaning.
e.g:- switch, case, int,return etc.

C++ has 31 additional keywords
few of the common ones used are
bool, class,static_cast,try, catch etc

2. Identifiers
Identifiers are used to name variables, labels etc. There are certain rules for the identifiers
a. They can start only with a letter or underscore(_).
b. They must contain only digits, letters and underscore.
c. They cannot contain white space.
d. maximum up to 31 characters long.
e. white space not allowed.

3. Constants
Constants refer to fixed values. e.g:- integer constants, floating point constants, character constants, octal or hexadecimal constants and string constants.
E.g:-
char *p=”Yogi”;
int age=43;

In the above examples “Yogi” and 43 are string and integer constants.

4. Strings
They are array of characters ended with null character(\0)

eg:- char test[20]=”Yogi”;

5. Symbols
Symbols have special meaning.
a. Brackets[]- used for array subscripts.
b. Paranthesis() – used for function calls and parameter passing.
c. Braces{} – Used for separating blocks of code. A variable defined inside the brace will have the scope within the brace.
d. comma, – separates statements and parameters.
e. asterisk * – Use to dereference a pointer.

There are other set of symbols also used and each has its own meaning.

6. Operators
Operators are symbols that are used to perform with operands to create a statement.
Based on the number of operands operator can act upon, operators can be classified as

a. Unary operator – i++, i–;
b. Binary operators – Arithmetic, relational, logical, assignment, conditional, bitwise
c. Ternary operator – ?:

Source: C/C++ Tokens – GeeksforGeeks

Line Splicing 

In C and C++ you can join the next line to the current line using Line spicing. Requires ‘\’ to be added at the end of the line.

 

Example code to demostrate line splicing.

[yogi@192 devel]$ cat linesplice.c
#include <stdio.h>

int main(int argc, char *argv[])
{
// test line splice
printf(“Hello\n”);
printf(“World\n”);

return 0;
}
[yogi@192 devel]$ gcc -o linesplice linesplice.c
[yogi@192 devel]$ ./linesplice
Hello
World
[yogi@192 devel]$ vi linesplice.c
[yogi@192 devel]$ cat linesplice.c
#include <stdio.h>

int main(int argc, char *argv[])
{
// test line splice \
printf(“Hello\n”);
printf(“World\n”);

return 0;
}
[yogi@192 devel]$ gcc -o linesplice linesplice.c
[yogi@192 devel]$ ./linesplice
World
[yogi@192 devel]$ vi linesplice.c
[yogi@192 devel]$ gcc -o linesplice linesplice.c
[yogi@192 devel]$ cat linesplice.c
#include <stdio.h>

int main(int argc, char *argv[])
{
// test line splice \
printf(“Hello\n”); \
printf(“World\n”);

return 0;
}
[yogi@192 devel]$ ./linesplice
[yogi@192 devel]$

 

Source: Line Splicing in C/C++ – GeeksforGeeks

Signals in C

Signals are one of the IPC mechanism used to communicate between 2 processes or between OS and a process. If a program hits a serious error, the OS may raise the respective signal for the process to be terminated after a core dump file is generated.

 

The common error signals are

SIGFPE:- some arithhmetic errors or floating point errors like divide by zero.

SIGILL:- Illegal instruction. Usually happens when an unknown instruction or an elevated privilege instructions is run. Common scenario is object file is corrupted or a stack overflow happens.

SIGSEGV:- Happens when a process access the physical memory which it doesn’t have access to. Common scenario is accessing a NULL pointer, stack or heap corruption.

SIGBUS:- Bus error. Invalid memory is accessed. In case of bus error the memory accessed itself is invalid. One scenario is issues with HW where the memory mapped address access fails to read the data from the hardware.

SIGABRT:- The signal is raised when the program calls abort() api. assert() in C++ uses internally abort().

SIGSYS:- The signal is raised when a process passes invalid arguments to a system call.

SIGTRAP:- This signal is raised in conjunction when a debugger is attached to the process. When the code hits a debug point the SIGTRAP can be raised.

Source: Program error signals – GeeksforGeeks

To be continued…

Compiling a C program. Various stages involved.

C is a high level programming language which converts a C code to executable which can be run in the respective target OS environment.

Usually a C program code is written with an extension .c. An IDE or editor is used to add code to the programs. Once done a compiler is used to compile the program code to executable. Some IDE provide built-in compiler while others provide option to select the compiler and debugger.

Steps involved in creating and executable.

  1. Add code using an editor.
  2. Compile using a compiler to create the executable binary. Linux uses gcc and windows uses Microsoft visual studio integrated compiler cl. There are other compilers available in multiple OS environments like borland C compiler.
  3. Fix any coding issues and move to step 1. Otherwise go to step 4.
  4. Run the final executable.
  5. Fix and run time found issues and move to step 1. Otherwise go to step 6.
  6. Final program ready.

The compilation phase can be split into 4.

  1. Pre-processing phase.
  2. Compilation phase.
  3. Assembly phase.
  4. Linking phase.

Pre-processing phase includes the following sub phases. This will generate filename.s file(in linux) which does have the below steps completed.

  • Removal of Comments.
  • Expansion of Macros.
  • Expansion of the included files.
  • Conditional compilation.

Compilation phase takes the pre-processed file and convert to assembly instructions. In case of linux it will generate the GNU assembly code.

Assembly phase include converting the assembly code into object code. filename.s will be converted to filename.o in Linux. This file will contain machine level instruction.

Linking phase is the final phase where the static libraries are linked as well as symbol lookup done for the dynamic libraries which are going to be loaded as part of run time load. The linker also add the extra code to call the main function as well as handling the exit from the program.

Note:- gcc uses dynamic linking for the standard C library functions like printf.

 

Source: Compiling a C program:- Behind the Scenes – GeeksforGeeks

Use -save-temps gcc option to generate the intermediate files.
gcc -Wall -save-temps -o sample -L .  -I . application.c -lcall_lib

yogi@192 0830]$ ls application.*
application.c application.i application.o application.s

application.c – program code.

application.i – preprocessed file.

application.s – assembly file

application.o – object file with machine instructions.

sample – Final program.

Page 1 of 2
1 2