Mailbox #2: String Reverse and Array Bound Checking

Query: How to reverse a string without using any variable. You are not even allowed to use a variable to store a string.

There has to be some temporary variables to be used, for looping over the string.
Reversing a string requires swapping first character with the last, second with second last, third with third last and so on. Now the problem requires the string to be reversed in place (without using any other buffer to store the reversed string). So, we will have to interchange the elements in the original string buffer itself. Following is a pseudo code for the same.

i = 0;
j = StringLength – 1;
while (i < j) { Swap i and j element of String ++i; --j; }

The swapping of the two elements can be done either using a temporary variable or using XOR operator.

Query: “C” doesnt provide boundation checking on array but it is still able to findout the length of array using the sizeof(). Why it cannot enforce boundation checking on array?

The reason why C is able to find out the length of array is because the length of array is part of its type declaration. As the type of a variable is known at compile time, sizeof operator can be used to find the length of array.
Faster execution speed would be one reason why C don’t do array bound checking.

Mailbox #1: Pointer query

Query: What this pointer exactly holds in this case and how it works.

int *p;
p = (int *)300;

In the above assignment statement, we are storing an integer into a pointer. Since it will not be allowed directly, hence a type casting is required.
Once the assignment is done, pointer p will contain 300 and it will be interpreted as an address. Dereferencing the pointer p, will try to access an integer stored at address 300. The result will be garbage (unless you know what is stored at address 300). Also, the safe execution of the dereferencing statement will depend on the OS in which the code is executed. As under Linux the program will generate segment fault/core dump.

Read Pointer in C/C++ Part – 1 for more explanation.

Query: What is this declaration ? For this printf what will be the answer and why?

double *p,*q;
p=(double *)4000;
q=(double *)2000;

For the explanation about declaration, see the above explanation.

In the printf() we are printing the result of subtracting two pointers of the same type. The number of memory locations between the two addresses will be 4000 – 2000 = 2000bytes. Since the size of double (as both are double pointers) is 8 bytes. The result will be 2000 / 8 = 250. Hence, printf() will print 250 as the output.

Read Pointer in C/C++ Part – 2 for more explanation.

Pointer in C/C++ Part – 2

Having covered the basics about pointers in last article, let’s look into pointer arithmetic. The arithmetic operations that are allowed with pointers are adding/subtracting integer to/from a pointer and subtracting two pointers.

How to add/subtract integer to/from pointer?
The result of adding/subtracting an integer (‘n’) to/from a pointer will be the address of the nth element (of the same type as pointer) with address in pointer used as a base address.

Let’s look into this with an example. Say we have an integer (32-bit integer) pointer pointing to address 1000. Now if we want to add integer 4 to this address, what the result will be?
So, we will assume address 1000 as the base address into which we will be adding integer, 4. Now, since the pointer is an integer pointer, it means at address 1000 an integer will be stored, since it’s a 32-bit integer, it will take 4 bytes. Hence, starting from address 4 byte will be used by that integer (address 1000, 1001, 1002 & 1003). So, next integer will be stored only starting from address 1004, and taking 4 bytes.

By the above explanation we can see that since every integer takes 4 bytes, going to next valid integer, we need to increment the address by 4 bytes or 4n bytes to reach nth integer. Now, this number 4 has come from the fact that the pointer’s type was integer pointer. Had it was a character pointer, we would have to increment address by 1 byte to reach the next valid character.

So, we can form the following generic formula to find the result of adding an integer to an address.

Result = Pointer + Integer * sizeof(Value stored at Pointer Address).

Let’s apply this to our example:
Pointer = 1000
Integer = 4
Value stored at Pointer Address = integer (as it is a integer pointer)
Sizeof(Value stored at Pointer Address) = 4 (it is a 32-bit integer)

Result = 1000 + 4 * 4 = 1016.

If we replace addition with subtraction in the above text, we can come up with the following formula to subtract an integer from a pointer.

Result = Pointer – Integer * sizeof(Value stored at Pointer Address).

So what is the type of the value that we get as a result of adding/subtracting integer to/from pointer? The answer is, same type as the pointer which was involved in addition/subtraction operation, i.e.,  Integer pointer, in the above example.

How to subtract two pointers?
Two pointers of same or different types can be subtracted from each other. Though, normally we subtract pointers of same type only.

In short, subtracting two pointers of same type tells us how many elements of the type of pointers can be stored between those two addresses. In case we subtract two pointers of different types, the result is number of elements, of largest type (type that needs more memory) of pointer, that can be stored between two addresses.

The type of value returned by subtracting two pointers is of type integer, as it gives us the element count.

Let’s subtract two pointers of the same type. Say the two pointers are pA and pB with addresses 2000 and 1000 and their types are integer pointers. So, if we do pB – pA. The result should be number of integers that can be stored between 2000 and 1000. Since the memory locations between 2000 and 1000 are 1000 and each integer takes 4 bytes (32-bit integer). Number of integers that can fit in 1000bytes will be 1000/4 = 250. So, if we subtract two integer pointers with addresses 2000 and 1000, the result will be 25.

Now, the above can be put in a generic formula as follows.
Result = (PointerA – PointerB)/sizeof(Value stored at PointerA or PointerB).

Now, let’s look at the case where the two pointers are of different types, say pA is character pointer and pB is short integer pointer. Since size of a character is 1byte and size of short integer is 2bytes, the result of subtraction will tell us how many short integers can be stored in between the two pointers getting subtracted. Since there are 1000 memory locations between two pointers, the result will be 1000/2 = 500.

Now, the above can be put in a generic formula as follows.
Result = (PointerA – PointerB)/MAX(sizeof(Value stored at PointerA), sizeof(Value stored at PointerB)).

Similar topics
Pointer in C/C++ Part – 1

Pointer in C/C++ Part – 1

Wanted to start such posts for a long time. After Abhay posted his queries related to pointers, I decided better late than never. I’ll try to post such stuff more frequent. 🙂
Will always be looking forward for your feedback.

What is a pointer?
Pointer is a variable that stores an address as its value.

How to declare a pointer?
To declare a variable as pointer we have to use “*” along with variable name, in its declaration. Following declaration declares variable i as a pointer to integer.

int *i;

“*” in the declaration is associated with the variable name, which means in the following declaration while i is a pointer variable, j is of integer.

int* i, j;

The correct way to declare multiple variables as pointers, in same statement, is by adding “*” before each variable name, as shown below.

int *i, *j;

Another way would be to use typedef to create a new type and use that to declare variables of that type.

typedef int * INT_PTR;
INT_PTR i, j;

Pointer initialization.
While it is ok not to initialize a static and global variable, as they are by default initialized to 0 (zero), it is always better to initialize a local variable, to avoid using the garbage value stored in it. Since a pointer stores an address, it becomes more important to make sure we initialize a pointer to a known value, as accessing a random (garbage) address can result in core dump (linux)/segmentation fault (windows).

Now the question is how do we get a valid address to initialize a pointer variable?

One way is to initialize a pointer with the address of a existing variable, as shown below.

int i;
int *p = &i; // Initialize pointer p, with address of variable i.

Another way is to dynamically allocate memory and use that address to initialize the pointer variable, as shown below.

int *p = (int *) malloc(sizeof(int));
int *q = new int; // Only for C++ programs.

One more way is, this should be used very carefully, to initialize pointer with a “known” address. This known address might be of some memory reserved by OS and documented. In this case we specify the address as a integer and typecast it to pointer type, before storing it in pointer variable, as shown below. When storing integer into a pointer in the following way one must be very careful in doing so becuase after storing that integer into a pointer, any access of that pointer variable will access the contents of the memory address at the integer location.

int *p = (int *) 0x0417; // Address of a byte where MS-DOS stores status of some keyboard keys.

Memory Leak: Scenario #1

Many a times we write code like this:

int *pData1 = NULL;
int *pData2 = NULL;

pData1 = new int [ n ];
pData2 = new int [ m ];

if ( pData1 && pData2 )
// Use pData1 and pData2

delete[ ] pData1;
delete[ ] pData2;

Is there anything wrong with this code? If you think there is nothing wrong with this code, well …

Let us analyze what is wrong here.

The condition in if statement makes sure we use pData1 and pData2 only when both of them are assigned valid addresses after allocating memory successfully, using new operator. When memory allocation is successful, for both pData1 and pData2, we use the pointers and when not required anymore, we release the allocated memory using delete operator.

In case memory allocation fails, for both pData1 and pData2, we never enter the if statement block. So everything looks fine here?

No, what if only one allocation fails, for either pData1 or pData2? Due to the condition in if statement we will not enter the if statement block, resulting in leaking memory which was allocated using new operator.

So what is the correct way to write the above code snippet? Instead of releasing memory inside if statement block we will release the memory out the if statement block. But doing this won’t we will be releasing memory even when it is not allocated? So we will release the memory outside if statement block but conditionally, after checking if it is allocated or not. Below is the modified code snippet.

int *pData1 = NULL;
int *pData2 = NULL;

pData1 = new int [ n ];
pData2 = new int [ m ];

if ( pData1 && pData2 )
// Use pData1 and pData2

if ( pData1 )
delete[ ] pData1;

if ( pData2 )
delete[ ] pData2;