Thread: redundant allocation

Thanks Mats,


1.

Originally Posted by matsp

Depends on how you do that: I was thinking of something along the lines of:
a block of data is a fixed size (say 256 items)
each block is a member of a linked list [or such].
When you need to insert into a block, if the block itself is full, we create a new block, and move "half" the data on to the new block.

Agree. Great!

2.

Originally Posted by matsp

But you could also have blocks that are part of a larger contiguous block, so when you split something, it becomes a block of it's own [perhaps with some "spare" space], but the remaining parts of the block is just half of the original block.
Mats

Is (2) a new idea of a continue part of (1)? I feel it is a separate idea which is not a part of (1).

If it is a part of (1), I do not understand if you use continuous storage for deque, and how do you split one block into two continuous blocks in place, with each new block half full?


regards,
George

Thanks Mats,


Great sample. Two questions,

1. why p->data is not assigned with any value?

2. What is the meaning of first and last member?

Originally Posted by matsp

I think 1 and 2 are sort of separate, but you could concievably have a hybrid version of the two - the #2 concept is derived from laserlights comments (maybe misconstrued, but I think that's what laserlight implied).

And in 2, you wouldn't (as I see it) split a block as such, you would just make a link. Say we have this:

Code:

struct dqBlock
{
    int first, last;
    int blocksize;
    T *data;       // T is the data type stores. 
    struct dqBlock *next;   
    // Other stuff may be here too.
};

Currently we have ONE block with ABCDMNOP
We want to insert E in order:

Code:

// Pseudo C++ code:
insertBlock(dqBlock &current, T newData, int insertPos)
   dqBlock p = new dqBlock;
   dqBlock n = new dqBlock;
   
   p->first = 0;
   p->last = current.last - insertPos;
   p->blocksize = current.blocksize - insertPos;
   current.last = insertPos-1;
   current.blocksize = insertPos;
  
   current.next = n;

   n->first = BLOCKSIZE/2;
   n->last = BLOCKSIZE/2+1;
   n->next = p;
   n->data = new T [BLOCKSIZE];
   n->blockSize = BLOCKSIZE;
   n->data[BLOCKSIZE/2] = newData;

This is just to give you an idea.

And as I said, it's probably not a good idea to ONLY do this inside a deque implementation - you will potentially end up with a linked list with one item per node - not a good situation for performance reasons, and you should probably use a list if that's what you actually want.

Also, I have not looked at the specifications for deque, nor have I looked inside anyones implementation to see what they actual internal data structure is.

--
Mats

regards,
George

Corrrect fix, thanks Mats!

Originally Posted by matsp

1. That's a mistake. It should say "p->data = &current.data[insertPos]" somewhere in that code.

2. They indicate where in a particular block the data starts and end respectively.

Note that you could use the same technique of "splitting" for removing items.

--
Mats

regards,
George