Memory reallocation

[Eko]

[IMG]http://img513.imageshack.us/img513/8739/sketchlw8.th.gif[/IMG]
I have something like this : The reallocation of a piece of memory that works like a circular queues
I've made a sketch explaining this ,I hope , very clearly

I just need a clue,a tip,something that will get me started , because right now I'm stucked

Thx

[Ancient Dragon]

that is not a circular queue. Circular queues do not have free space anywhere but at the queue's tail. A circular queue uses two pointers -- head points to the byte for the next insertion, and tail points to the byte for the next extraction. when tail+1 == head the queue is full

Like this example

[Eko]

What ? I don't think you understand . M1,M2,M3 are pieces of memory,and they act like cirular queues,this means that there are 3 queues,separte from each other. Here's another sketch :
[IMG]http://img166.imageshack.us/img166/3310/sketch2er3.th.gif[/IMG]

And some circular queue with free space :
[IMG]http://img295.imageshack.us/img295/5199/queuehp5.th.gif[/IMG]

[~s.o.s~]

Is a image really there ? I don't see any image in my browser window. It would be really a good idea to either attach the image to your post or to upload it at an image hosting site (www.imageshack.us).

Maybe then everyone would be able to help you out.

[Eko]

The images are fine.There uploaded on imageshack
What browser are u using s.o.s ?

Later edit:
Try this
http://img166.imageshack.us/my.php?image=sketch2er3.gif
http://img295.imageshack.us/my.php?image=queuehp5.gif
http://img513.imageshack.us/my.php?image=sketchlw8.gif

[~s.o.s~]

Hmm...I am using the lastest version of Firefox. Maybe you should just provide a direct link to your image via an URL so that it would be easier to access.

[Eko]

This is what I got so far

#include <iostream>

using namespace std;

int main()
{
    int v[90];

    int *first1,*first2,*first3,*last1,*last2,*last3;
/*
   I'm representing the v array as 3 equal parts ,from v[0] to v[30] the first part,
   from v[30] to v[60] the second and from v[60] to v[90] the third.
   The pointers first1,2,3 points to the beginning of each part,and in the initial state
   last1,2,3 will equal first1,2,3 thus creating queues
*/


first1=&v[0];
last1=first1;
first2=&v[30];
last2=first2;
first3=&v[60];
last3=first3;
}

:sad:

[~s.o.s~]

I don't know if I quite get you but what I understand till now is: You have a memory space which is divided in three parts and if one of the part gets filled, the data is to be inserted in the part which has free space ? Correct ?

To do this, you can initialise the whole array or data space to a value which will distinguish between a free space and an occupied space. For eg. the default value can be -1. int v[90] = { -1 } In the start, your start1 and end1 pointers will point to the same record i.e. v[0] . Then as you keep on inserting data, keep on moving or incrementing the last1 pointer to keep track of the growing chunk.

1. At start start1 = last1 .
2. If you want to store value check whether last1 has not exceeded its limit then do, v[last1] = data 3. Increment last1 .
4. If last1 has exceeded the limit, make it point to the 30th element and move on to the next chunk of memory.

It would be better if you kept a marker like current_ptr which will keep track of which chunk you are accessing right now.

Hope it made sense.

[Eko]

I don't know if I quite get you but what I understand till now is: You have a memory space which is divided in three parts and if one of the part gets filled, the data is to be inserted in the part which has free space ? Correct ?

Almost.The free space when one part gets full,is associated to the full one,thus increasing in size .In other words the data inserted into the free space when one part is full , becomes part of the full chunk of memory,and NOT to the one that holds the free space

I'll try to do what you've explained s.o.s but
riight now,I don't know how to increase a part ,by taking free spaces from the others.

[~s.o.s~]

Almost.The free space when one part gets full,is associated to the full one,thus increasing in size .In other words the data inserted into the free space when one part is full , becomes part of the full chunk of memory,and NOT to the one that holds the free space

I'll try to do what you've explained s.o.s but
riight now,I don't know how to increase a part ,by taking free spaces from the others.

I still don't get your problem, isn't this what normally happens when we access normal arrays ?

That is, once we exceed the v[29] mark, data starts getting inserted into the second chunk i.e. from v[30] onwards and the same thing happens when v[59] is reached.

I guess you need to explain in a more concise manner.....

[Eko]

I've chose to use an array just so i can make it easier.

Imagine this : You have 3 different arrays,separate from each other.
Let's say we must get a product name from the user(product name will be stored into the first array,char product_name[100]),then the product description(this will go into the second array,char product_description[100]) and the product's price(into the third array,char product_price[100]).
Since the description of a product takes more space than the price and the name , it's possible that the second array which holds the description will overflow.To prevent that from happening,it must search in the others arrays for free space,and when it finds it ,it adds to her size,thus the description array is getting bigger,and the other are getting smaller.(it borrows the free space from others arrays)

I don't know how the explained better than this.

I've searched the web,but I couldn't find what i was looking for.
You are my last hope

[~s.o.s~]

As far as your above problem statement is considered, the solution is pretty obvious and less complicated than you are making it to be. Two solutions leap out to the eye:

1. Create an array of altogether 300 characters, name it product_details and then keep inserting data into it with a delimiter between them, something like a pipe |( use strcat( ) to concat the three items ). [ not so cool, nonetheless a solution ]

2. Create a structure called Products with three char pointers in it and allocate memory dynamically to them based on the input given by the user.

typedef struct 
{
    char* name ;
    char* desc ;
    char* price ;
} Product ;

// accept user input

// pass the user input to a function which creates instances of
// product structure.

Product p ;
p->name = (char*)malloc( strlen( entered_name ) + 1 ) ;
strcpy( p->name, entered_name ) ;

p->desc = (char*) malloc( strlen( entered_desc ) + 1 ) ;
strcpy( p->desc, entered_desc ) ;

p->price = (char*) malloc( strlen( entered_price ) + 1 ) ;
p->price = strcpy( p->price, entered_price ) ;

// likewise create more enteries of the Product structure or if
// required create an array of structure.

Better use one of the above mentioned solutions rather than doing it the hard way.

If you still have doubts, repost.

[Eko]

Well,the hole project is strongly recommended for the use of static allocation and the insert ,delete must be made as a circular queue .
So i got a circular queue :

#include<stdio.h>
#include<stdlib.h>
#define MAX 5
char queue[MAX][30];
int front, rear, temp;
void init()
{
    front = rear = -1;
}
int condition()
{
    if (rear == front)
        {
            front = rear = -1;
            return 1;
        }
    else
        return 0;
}
void insert()
{
    //if (rear >= MAX-1)
    //    {
    //        printf("\nQueue overflow");
    //        return;
    //    }
    temp = rear;
    rear = (rear + 1) % MAX;
    if (condition())
        {
            rear = temp;
            printf("\nQueue overflow");
        }
    else
        {
            printf("\nEnter name to be inserted :\n");
            scanf("%s",queue[rear]);
        }
}
void del()
{
    if (condition())
        printf("\nError : Underflow");
    else
        {
            front = (front + 1) % MAX;
            printf("\nDeleted name from the CQ is %s",queue[front]);
        }
}

void display()
{
    int i;
    printf("\nThe queue content is :\n");
    if (front > rear)
        {
            for (i = front + 1; i < MAX; i++)
                printf("%s\t",queue[i]);
            for (i = 0; i <= rear; i++)
                printf("%s\t",queue[i]);
        }
    else
        for (i = front + 1; i <= rear; i++)
            printf("%s\t",queue[i]);
    printf("\n");
}

int main()
{
    int choice;
    init();
    while(1)
    {
        printf("\nMENU\n1. Insert\n2. Delete\n3. Display\n4. Exit\n");
        printf("\nYour choice = ?");
        scanf("%d",&choice);
        switch(choice)
        {
            case 1:
                        insert();
                        break;

            case 2:
                        del();
                        break;

            case 3:
                        if (condition())
                            printf("\nNo elements in the list");
                        else
                            display();
                        break;

            case 4:
                        exit(0);

            default:
                        printf("Invalid Choice");
        }
    }
   return 0;
}

I don't have a clue what to do next

I quess it has something to do with realloc()

[~s.o.s~]

I would be better if you could exactly describe your requirements wrt the current code. Is it not working as expected, what is it supposed to do ? What is the concept in short behind this ?

Do you plan on increasing the size of the array during runtime ? If yes then sorry, you can't do that. Normal arrays declared in C can't be increased or decreased in size. You should create your arrays dynamically (on the fly) using pointers if you want such kind of behaviour.

[Infarction]

I'm thinking your circular queue is more complicated than it should be. Here's how I would write one:

struct circular_queue
{
  someFormOfData** data;
  int head, tail, count, size;
};

void insert(ciruclar_queue* q, someFormOfData* d)
{
  if(count == size) // it's full
  {  growTheQueue(q) }
  q->data[q->tail++] = d; // add the new data
  q->count++; // update the count
}

someFormOfData* remove(circular_q q)
{
  if(count == 0) // it's empty
    return NULL;
  q->count--; // reduce the count
  return q->data[head++]; // return the value
}

void growTheQueue(circular_queue q)
{
  // make a new array with more room
  someFormOfData** newData = (someFormOfData*)calloc(q->size * 2, sizeof(someFormOfData*));
  // copy the data
  for(int i = 0; i < q->count; ++i)
  {
    newData[i] = q->data[head + i];
  }
  // update the values in the struct as appropriate
  free(q->data);
  q->data = newData;
  q->head = 0;
  q->tail = q->count;
  q->size *= 2;
}

Just wrote this, didn't compile or test it at all. Hopefully it gives you an idea of how it could be written. I left out init, because that's trivial.