Re: circular buffer
> Hello, > > I'm trying to understand and implement FIFO. I found two reference examples > on the Internet: <ring buffer example snipped> > ex.2 > struct fifo_node { > struct fifo_node *next; > value_type value; > }; > > What I don't understand is why to add the 'next' pointer in the structure, > thus making linked list? I think you need to say more. Without the 'next' pointer, what good would the structure be? You could make an array of them and use it like the ring buffer example but then why have the value in a structure at all? The 'next' pointer is to make a linked list to (presumably) store the queued items. -- Ben. |
|
Re: circular buffer
> > I'm trying to understand and implement FIFO. I found two reference > examples on the Internet: Very simple. FIFO stands for "first in, first out", i.e. a queue. -- <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt> <http://www.securityfocus.com/columnists/423> <http://www.aaxnet.com/editor/edit043.html> <http://kadaitcha.cx/vista/dogsbreakfast/index.html> cbfalconer at maineline dot net -- Posted via a free Usenet account from |
|
Re: circular buffer
> "Ben Bacarisse" <> wrote in message > news: >> >> I think you need to say more. Without the 'next' pointer, what good >> would the structure be? You could make an array of them and use it >> like the ring buffer example but then why have the value in a >> structure at all? > > Why not just hold an array and head/tail counters in the structure. That's fine, as long as you know in advance that you won't need to make the ring buffer larger at runtime. You might not. -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 email: rjh at the above domain, - www. |
|
Re: circular buffer
> .... snip ... > > I seem to realize your point. The linked list of FIFO nodes lets > us to have 'rubber' queue, of flexible size. But then we don't > have markers of head and tail, what to do with that? For a FIFO you don't need both. Just keep a pointer to the tail. One step malloc and add item; one step extract item, use and free. node *push(T item, node *stack) { node *temp; if (temp = malloc(sizeof *temp)) { temp.item = item; stack->next = temp; } return temp; } T pop(node * stack) { node *temp; T value; temp = stack; stack = stack>-next; value = temp->item; free temp; return value; } ..... while (whatever) stack = push(something, stack); ..... while (foo) value = pop(stack); I have omitted full and empty checks. Also #includes. -- <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt> <http://www.securityfocus.com/columnists/423> <http://www.aaxnet.com/editor/edit043.html> <http://kadaitcha.cx/vista/dogsbreakfast/index.html> cbfalconer at maineline dot net -- Posted via a free Usenet account from |
|
Re: circular buffer
wrote: >Roman Mashak wrote: >> I seem to realize your point. The linked list of FIFO nodes lets us to have >> 'rubber' queue, of flexible size. But then we don't have markers of head and >> tail, what to do with that? > >The linked list implementation of a FIFO would probably have two user-defined >types. One for the nodes, like you suggested: > > struct fifo_node { > struct fifo_node *next; > value_type value; > }; > >And one that represents the entire FIFO: > > struct fifo_queue { > struct fifo_node *head; > struct fifo_node *tail; > }; > > >Alternately, it is less efficient, but you can simply store the >head of the queue and find the tail when you need it by traversing >the list. (That's not very practical; it's just to prove that you >don't HAVE to store both.) A somewhat better scheme is to link the tail to the head and store the tail, making it a circular singly linked list. Inserts are done after the tail (yielding a new tail) and deletes delete the successor of the tail. An advanatage is that you don't need to introduce another data structure; the tail is just another fifo_node. |
|
circular buffer
I'm trying to understand and implement FIFO. I found two reference examples on the Internet: ex.1 #define BUFSIZE 32 struct ring_buffer { char buf[BUFSIZE]; int head, tail; }; typedef struct ring_buffer ring_buffer; Further functions added: init buffer, add to tail of buffer etc. This is quite clear. ex.2 struct fifo_node { struct fifo_node *next; value_type value; }; What I don't understand is why to add the 'next' pointer in the structure, thus making linked list? -- Best regards, Roman |
|
Re: circular buffer
Roman Mashak wrote:
> I seem to realize your point. The linked list of FIFO nodes lets us to have > 'rubber' queue, of flexible size. But then we don't have markers of head and > tail, what to do with that? The linked list implementation of a FIFO would probably have two user-defined types. One for the nodes, like you suggested: struct fifo_node { struct fifo_node *next; value_type value; }; And one that represents the entire FIFO: struct fifo_queue { struct fifo_node *head; struct fifo_node *tail; }; Alternately, it is less efficient, but you can simply store the head of the queue and find the tail when you need it by traversing the list. (That's not very practical; it's just to prove that you don't HAVE to store both.) - Logan |
|
Re: circular buffer
CBFalconer <> writes:
> Roman Mashak wrote: >> > ... snip ... >> >> I seem to realize your point. The linked list of FIFO nodes lets >> us to have 'rubber' queue, of flexible size. But then we don't >> have markers of head and tail, what to do with that? > > For a FIFO you don't need both. Just keep a pointer to the tail. > One step malloc and add item; one step extract item, use and free. FIFO == queue FIFO != stack LIFO == stack -- Ben Pfaff |
|
Re: circular buffer
CBFalconer <> writes:
> Roman Mashak wrote: >> > ... snip ... >> >> I seem to realize your point. The linked list of FIFO nodes lets >> us to have 'rubber' queue, of flexible size. But then we don't >> have markers of head and tail, what to do with that? > > For a FIFO you don't need both. No indeed you don't (though there is nothing wrong with doing it that way). > Just keep a pointer to the tail. > One step malloc and add item; one step extract item, use and free. But now you post code for A LIFO. > node *push(T item, node *stack) { > node *temp; > > if (temp = malloc(sizeof *temp)) { > temp.item = item; > stack->next = temp; > } > return temp; > } > > T pop(node * stack) { > node *temp; > T value; > > temp = stack; stack = stack>-next; > value = temp->item; > free temp; > return value; > } > > ..... > while (whatever) stack = push(something, stack); > ..... > while (foo) value = pop(stack); > > I have omitted full and empty checks. Also #includes. That is not C is it? Looks a little odd (apart from all the typos). If pop can (meaningfully) modify its parameter, why make push return a new stack? I'd use the same style for both functions. -- Ben. |
|
Re: circular buffer
Ben Pfaff wrote:
> CBFalconer <> writes: >> Roman Mashak wrote: >>> >> ... snip ... >>> >>> I seem to realize your point. The linked list of FIFO nodes lets >>> us to have 'rubber' queue, of flexible size. But then we don't >>> have markers of head and tail, what to do with that? >> >> For a FIFO you don't need both. Just keep a pointer to the tail. >> One step malloc and add item; one step extract item, use and free. > > FIFO == queue > FIFO != stack > LIFO == stack Woops. I knew all that. Just got carried away :-) -- <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt> <http://www.securityfocus.com/columnists/423> <http://www.aaxnet.com/editor/edit043.html> <http://kadaitcha.cx/vista/dogsbreakfast/index.html> cbfalconer at maineline dot net -- Posted via a free Usenet account from |
Linear Mode
