free() problem

This is a discussion on free() problem within the C Programming forums, part of the General Programming Boards category; Here is the scene: I want to implement queue using array in C. First, I allocating a memory block (e.g. ...

  1. #1
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489

    Question free() problem

    Here is the scene:
    I want to implement queue using array in C.

    First, I allocating a memory block (e.g. 4)
    Code:
    [ ][ ][ ][ ] <-- this is the array
    Then I call unshift function that will append the data similar to the push function in

    stack.

    Code:
    unshift(2)
    [2][ ][ ][ ]
    
    unshift(3)
    [2][3][ ][ ]
    
    unshift(7)
    [2][3][7][ ]
    
    unshift(1)
    [2][3][7][1]
    Ok, after that, I call the shift function that will return the first offset in the array

    increased by one.

    Code:
    [2][3][7][1] <-- initial array
    
    print shift --> output: 2
    [ ][3][7][1]
    
    print shift --> output: 3
    [ ][ ][7][1]
    
    print shift --> output: 7
    [ ][ ][ ][1]
    Of course, there is a slow version of the shift function that will return the first offset in the array then do a real shifting (using loop).

    Code:
    [2][3][7][1] <-- initial array
    
    print shift --> output: 2
    [3][7][1][ ]
    
    print shift --> output: 3
    [7][1][ ][ ]
    
    print shift --> output: 7
    [1][ ][ ][ ]
    Nah, the problem is:

    I think I would prefer the first shift function because the speed.

    1. But from the algorithm above, is there a way to free certain block of memory?

    Code:
    print shift --> output: 3
    [ ][ ][ ][1]
    For example, I want to free the memory block index from 0 to 2.

    2. How about linked-listed queue? Is there a guarantee for the speed if we are using it to implementing queue?

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,211
    1. malloc() doesn't work like that. You allocate blocks of memory and you free() them exactly as you have allocated them. You're unable to change the blocks unless you realloc(), which doesn't seem to fit your design.
    2. A linked list can be a queue with relatively good performance if:
      1. You have a reference to the beginning of the queue, and can easily delete at the beginning of the list without any ridiculous shifting of the entire queue.
      2. You have a reference to the end of the queue and can easily insert at the end of the list. Otherwise insertion will be O(n).

  3. #3
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    So... *thinking*

    Its efficient to implement Stack if we use array and implement Queue if we use linked-list.

  4. #4
    Registered User
    Join Date
    Oct 2007
    Posts
    242
    Why would you want to implement a queue with an array? These generic collections (stack, queue, linked list, binary trees, ...) are useful, also because their size is dynamic.

  5. #5
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    Quote Originally Posted by audinue View Post
    So... *thinking*

    Its efficient to implement Stack if we use array and implement Queue if we use linked-list.
    If you use an array, you can make the buffer circular. That way you don't have to shift the array, you just decrement or increment the beginning and end pointers, handling wrap around correctly. You'd still have to copy the whole buffer over when it gets full, but you can use realloc() for that.

    This approach should be faster then a linked list if the correct capacity is given initially.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  6. #6
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    Why would you want to implement a queue with an array?
    Memory size used by array are quite smaller than linked list.
    If you use an array, you can make the buffer circular. That way you don't have to shift the array, you just decrement or increment the beginning and end pointers, handling wrap around correctly. You'd still have to copy the whole buffer over when it gets full, but you can use realloc() for that.
    I dont get it. Would you like to explain the design?

    However, my goal is designing an efficient deque or dequeue which could be used for good dynamic array manipulation.
    If I use linked-list, I will got trouble to get the element by index... >_< * confuse...
    Last edited by audinue; 07-19-2008 at 10:15 AM.

  7. #7
    Registered User
    Join Date
    Oct 2007
    Posts
    242
    Quote Originally Posted by audinue View Post
    Memory size used by array are quite smaller than linked list.
    How so? This is the same (if both array and linked list have the same number of elements)
    Last edited by eXeCuTeR; 07-19-2008 at 10:15 AM.

  8. #8
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    How so??

    Using linked-list:
    Code:
    typedef struct node
    {
       int data;
       node *next;
    } node;
    
    typedef struct
    {
       node *first;
    } stack;
    4 elements of linked-listed stack:
    [data, next][data, next][data, next][data, next] = 8 blocks

    Using array:
    Code:
    typedef struct
    {
       char *data; <-- the array
       size_t offset;
       size_t allocated;
    } stack;
    4 elements of array:
    [offset, allocated][data][data][data][data] = 6 blocks

    How so??
    Last edited by audinue; 07-19-2008 at 10:33 AM.

  9. #9
    Registered User
    Join Date
    Oct 2007
    Posts
    242
    Quote Originally Posted by audinue View Post
    How so??

    ...

    How so??
    Oops, I'm a fool, damn it.
    But you still have to consider that the number of elements in a linked list is flexible while an array is not (and the linked-list might take less memory than the array in some situations)
    Last edited by eXeCuTeR; 07-19-2008 at 10:41 AM.

  10. #10
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    eXeCuTeR: Would you like to give me some advice how to get element by index using linked list??

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    A queue (and stack) by definition needn't be indexable. Pretty much push and pop should be the only things that are required.

    As to implementing a queue as an array: perhaps you can postpone moving array contents forward to fill the unused space at the beginning of the array until you really need to (e.g when user tries to push an item and there is no more space left at the end of the array). That is, you wouldn't need to do it every-time something is popped, only occasionally when something is pushed.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  12. #12
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    anon! Thank you! You opened my eyes!

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    The problem description is a perfect description of when to use a circular buffer.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  14. #14
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    Quote Originally Posted by audinue View Post
    Memory size used by array are quite smaller than linked list.
    I dont get it. Would you like to explain the design?
    You have a buffer of size N. You have indexes for the first element of the queue, where you dequeue form, and the location where to enqueue the last element. You also need to store the size (or at least a boolean for if the queue is not empty).

    To enqueue, you first check if the queue is not full. Assuming it isn't, you copy the value into the array at the end index. Then increment end index, and modulo by N to get the new final index. The modulo ensure proper wrap around.

    To dequeue, you check if the queue is not empty. Assuming it isn't you just get the value at the start index. Then as with end index, increment it, and modulo by n.

    EDIT: or read the wiki link iMalc provided.
    Last edited by King Mir; 07-19-2008 at 02:55 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  15. #15
    Ugly C Lover audinue's Avatar
    Join Date
    Jun 2008
    Location
    Indonesia
    Posts
    489
    I'm a little bit stupid here King Mir, sorry. I still don't get it. -_-"?

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

Similar Threads

  1. lots of freeware
    By major_small in forum General Discussions
    Replies: 57
    Last Post: 05-28-2014, 04:42 PM
  2. Program that displays amount of free memory
    By trancedeejay in forum Linux Programming
    Replies: 3
    Last Post: 01-13-2006, 12:27 PM
  3. Bin packing problem....
    By 81N4RY_DR460N in forum C++ Programming
    Replies: 0
    Last Post: 08-01-2005, 05:20 AM
  4. Replies: 12
    Last Post: 06-24-2005, 04:27 PM
  5. Help needed with backtracking
    By sjalesho in forum C Programming
    Replies: 1
    Last Post: 11-09-2003, 05:28 PM

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