redundant allocation

This is a discussion on redundant allocation within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by CornedBee It would also need to keep track of the fill status of each block, which would ...

  1. #16
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by CornedBee View Post
    It would also need to keep track of the fill status of each block, which would make things quite complicated.
    Naturally - but that's just a "used_size" and "block_size". Doesn't seem too complicated to me.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  2. #17
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    It's a first_index and a last_index, actually.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #18
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by CornedBee View Post
    It's a first_index and a last_index, actually.
    Of course, and "last_index - first_index" tells us how many items we have.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #19
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    Thanks Mats,


    1.

    Quote Originally Posted by matsp View Post
    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.

    Quote Originally Posted by matsp View Post
    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

  5. #20
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  6. #21
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    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?

    Quote Originally Posted by matsp View Post
    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

  7. #22
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #23
    Registered User
    Join Date
    May 2006
    Posts
    1,579
    Corrrect fix, thanks Mats!


    Quote Originally Posted by matsp View Post
    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

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. dynamic allocation from 1 instead of zero
    By cfdprogrammer in forum C Programming
    Replies: 27
    Last Post: 04-28-2009, 09:21 AM
  2. pointer to array with dynamic allocation
    By cfdprogrammer in forum C Programming
    Replies: 22
    Last Post: 04-07-2009, 10:56 AM
  3. Dynamic memory allocation.
    By HAssan in forum C Programming
    Replies: 3
    Last Post: 09-07-2006, 06:04 PM
  4. Parsing and Fwrite Help Please.
    By Freestyler in forum C Programming
    Replies: 11
    Last Post: 12-06-2005, 11:38 AM
  5. Dynamic allocation (I thought it would crash)
    By Baaaah! in forum C Programming
    Replies: 16
    Last Post: 11-30-2005, 05:10 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21