Talk:Circular buffer

The template queue's IsFull function is incorrect. Notice it is identical to IsEmpty(), only advancing the tail before doing a check. Consider: Q::Resize(2); Q::Enqueue(T); Q::Enqueue(T); The second enqueue will throw as IsFull reports true (tail=1, +1 & mask = head == true) — Preceding unsigned comment added by 98.232.107.82 (talk) 23:09, 12 June 2011 (UTC)

history

When was the ring buffer invented or first publicly discussed or first mentioned in an academic paper or first used in an actual operating system? 209.252.104.131 (talk) 10:47, 16 March 2008 (UTC) ring buffer has been invented by Alblas Hans (pe1ayx) publicly made in 1993-1995 in linux kernel source tree in /drivers/char/scc.c under the name buffer pool concept and ring buffer chain. copyricht by none gnu use —Preceding unsigned comment added by 83.101.55.202 (talk) 15:35, 3 October 2010 (UTC)

no mention of additional overheads

one still has to always check before a read or a write if the read pointer and a write pointer overlap.

this is never needed incase of a simple write ->read->write buffer a simple write->read->write kind of buffer works sequentially and simply does not let one write to the buffer is someone has not read what is already written because it assumes buffer_size=max message size and simply keeps check of whether the buffer is read or not.

incoherence between 2 paragraphs

In Circular buffer mechanics paragraph, it says that the start pointer points to the start of valid data and the end pointer points to the end of valid data. So, in my understanding, and according to the figures:

• 1 element buffer: start = end
• Full buffer: start = (end+1)%size
• Free buffer: not defined since we have no "valid data", but we can suppose that start = end too.

In the following paragraph Difficulties, a full buffer is represented with start = end. This is the same for the free buffer. We can suppose that the rule is different in this paragraph: the start pointer points to the start of valid data and the end pointer points to the next element after the end of valid data (if any). If there is no valid data, start = end.

Did I miss something ? —Preceding unsigned comment added by 84.14.106.33 (talk) 14:45, August 27, 2007 (UTC)

You didn't miss anything, the Circular buffer mechanics paragraph is incorrect, the first pointer will point to the first element to be read, and the second pointer will point to the first element to be written. I'm going to try to remember this when I have some time to correct the diagrams and fix it. 70.230.2.66 (talk) 23:24, 10 March 2008 (UTC)

I agree with 70.230.2.66. The classic implementation has a "read pointer" and a "write pointer".

The "write pointer" points to the location where the next element will be written, which is (in general) just past the newest element (most recently written element) in the buffer.

The "write pointer" always points to an empty slot in the buffer, except in the special case where the buffer is completely full. The point of the "Always Keep One Byte Open" variant is to eliminate this special case.

• 1 element in buffer: (read pointer + 1)%size == write pointer

When we have 1 element in the buffer, and then we read that element (incrementing the read pointer just as we always do), then we inevitably get:

• Free buffer: read pointer == write pointer

--68.0.124.33 (talk) 18:59, 14 January 2009 (UTC)

Buffer border

In Circular buffer mechanics it talks about a "buffer border". What is the buffer border and when can it be "read over"? 137.44.2.188 (talk) 09:51, 9 April 2008 (UTC)

 I rewrote the sentence about a "buffer border" to hopefully make it more clear. Maybe the 'clarify' notice can be removed?  Shervinemami (talk) 18:50, 1 July 2010 (UTC)

round robin archive

The RRDtool currently mentions a "a round-robin archive (RRA).", and the brief description reminds me of a circular buffer. Is "round-robin archive" an exact synonym for "circular buffer", or some specific variant of a circular buffer? Or is it something significantly different? --68.0.124.33 (talk) 00:49, 15 January 2009 (UTC)

Used Buffer space

When checking to see how much space is used in the buffer, needing to be read (The space between the write and read pointers) could you not just use another variable, incrementing it as you write something, and decrementing it as you read something? For example, once it is initialized, the buffer is empty therefore your variable would = 0. But once you write, say 3 bytes, with out reading something, the variable would than = 3. And again after reading 2 bytes, that same variable would equal 1, effectively indicating that there is one byte remaining to be read in the buffer. This eliminates the need for any crazy algorithms for when your write pointer has wrapped around before you read pointer has. —Preceding unsigned comment added by 205.250.74.174 (talk) 23:15, 17 June 2009 (UTC)

C# Example

I find the C# example distinctly uninformative and overly verbose. While perhaps it shows good design, it doesn't illustrate the subject matter any better than the other two C examples. I'm removing it for now. SiegeLord (talk) 18:33, 13 September 2010 (UTC)

Full/Empty Buffer Distinction

Another solution not mentioned in the article is to have an additional boolean variable. When an element is inserted, it is set to true, and when an element is removed, it is set to false. If the indices are equal and the variable is true, the buffer is full. If the indices are equal and the varaible is false, the buffer is empty. Platypus1130 (talk) 21:58, 30 January 2011 (UTC)

Full implementation?

Is it really useful to have two full implementations of a ring buffer? Wouldn't it be better to just have some pseudo code? This is an encyclopedia, not a pastebin, is it not? —Preceding unsigned comment added by 142.244.143.199 (talk) 17:22, 12 April 2011 (UTC)

Agreed, it's currently quite unencyclopaedic. See below a simpler C implementation which I think works as an easy-to-understand example without being too C-specific. I suggest replacing the whole "Difficulties section" using this as a starting point. Thoughts? HoboBen (talk) 20:05, 20 April 2011 (UTC) Edit: spoke too soon, there's a bug in my RetrieveFromQueue function where start==end when it's full. Needs to be fixed first. HoboBen (talk) 21:05, 21 April 2011 (UTC)

Fixed. HoboBen (talk) 16:06, 22 April 2011 (UTC)

#define BUFFER_SIZE 256

item *buffer[BUFFER_SIZE];
int start = 0;
int end = 0
int active = 0;

void PushToQueue(item *p)
{
    buffer[end] = p;
    end = (end + 1) % BUFFER_SIZE;

    if (active < BUFFER_SIZE)
    {
        active++;
    } else {
        /* Move start to next-oldest */
        start = (start + 1) % BUFFER_SIZE;
    }
}

item *RetrieveFromQueue(void)
{
    item *p;

    if (!active) { return NULL; }

    p = buffer[start];
    start = (start + 1) % BUFFER_SIZE;

    active--;
    return p;
}

Can we please get consensus on replacing the current C examples with this alternative? Agree, disagree, or suggest modifications below. HoboBen (talk) 12:58, 27 July 2011 (UTC)

Java Implementation

A while back, I added the following external link:

CircularArrayList for Java - a Java implementation of a circular buffer

This is a link to a page on my own website. I know that under some circumstances this is allowed if there is consensus that the link is a useful addition to the article. But alas, I have a bit of a history for linking to my site, and after I became a bit pushy in a discussion elsewhere, the links were (understandably) removed. To save you some time, I should mention that I have been made very aware of the WP guidelines that are frowning upon me. I stand on nothing except IAR and a sure conviction that the article is better off with the link than without it. Some points to note:

• The article does not, as it stands, have a link to a Java implementation.
• CircularArrayList plugs something of a hole in the Java Collections Framework. Some readers may come to the article specifically looking for this (as I did, originally).
• Its minimalism makes it 10 times shorter than the shortest currently externally linked implementation (in any language).

(until they disappeared during the course of the discussion) --Tennenrishin (talk) 22:55, 13 August 2011 (UTC)

• It is probably the only production-ready implementation supporting Java generic element types that is available on the web.

I have learned my lesson about pushing when there is potential for COI, but I believe there is rather an alignment of interest (even though the only interest I derive from my website is satisfaction). Would you consider the case for restoring the link, based purely on the merits of its inclusion? (Those essays listed in IAR make for some really good reading :) --Tennenrishin (talk) 15:55, 13 July 2011 (UTC)

I don't see how a link to yet another implementation would add to an encyclopedic understanding of this type of data structure. - MrOllie (talk) 20:59, 13 July 2011 (UTC)

Thank you for explaining why you removed the link, MrOllie. If you were a reader that is familiar only/mainly with Java, would you then? --Tennenrishin (talk) 21:53, 22 July 2011 (UTC)

Does anyone have a position to offer on this matter? I would like to restore the link if it is in the interest of the article. --Tennenrishin (talk) 21:10, 12 August 2011 (UTC)

I'll make myself more clear: Please do not restore the link, it is not helpful nor is it consistent with WP:EL. - MrOllie (talk) 21:11, 12 August 2011 (UTC)

MrOllie, why do you say the link is not helpful? --Tennenrishin (talk) 16:01, 13 August 2011 (UTC)

We already have three implementations in the article. We don't need to duplicate that ad nauseam for additional platforms and programming languages in the external links. It's not educational. - MrOllie (talk) 16:27, 13 August 2011 (UTC)

1. Indeed, the article has about 450 lines of low-level code for C readers. What is wrong with adding one line to the article for Java readers?

2. If you don't care about languages, you would find this brief high-level implementation much more educational than any number of low-level implementations, because Java affords more abstraction than C. (I am trying to trust that you have actually looked at the link.)

3. Even if one imagines it is not "educational", it is still helpful. See 2nd and 4th bullets in the original post. An encyclopedia is a reference work.

4. Regarding "duplicating ad nauseam for additional languages": C and Java are by far the two most popular languages.

5. Regarding "duplicating ad nauseam for additional platforms": Actually, Java would be the one language where you don't have to worry about that. --Tennenrishin (talk) 07:14, 18 August 2011 (UTC)

MrOllie, if you still think the link is not helpful, please help me understand. --Tennenrishin (talk) 10:58, 29 August 2011 (UTC)

It would appear that you have changed your view, MrOllie. If this is true, thank you for being unbiased.--Tennenrishin (talk) 14:24, 5 September 2011 (UTC)

I have not changed my view, so I removed the link you added based on the lack of consensus demonstrated on this talk page and because of the guidelines in WP:EL. Please do not continue to add links to your own website. Thanks. - MrOllie (talk) 14:33, 5 September 2011 (UTC)

MrOllie, why is the link not helpful, in your view?--Tennenrishin (talk) 07:33, 6 September 2011 (UTC)

We already have implementations in the article which it duplicates. WP:ELNO point one says that we only include sites that will provide unique content that cannot otherwise be included. I find your arguments that it is different because one is Java and one is C++ to be unconvincing. - MrOllie (talk) 14:45, 6 September 2011 (UTC)

If you really believe the implementations are similar, please take a moment to compare them. It will also help you to understand my arguments. --Tennenrishin (talk) 21:23, 6 September 2011 (UTC)

I have reviewed your site and fully understand your arguments. Nonetheless, I disagree with them. - MrOllie (talk) 12:53, 7 September 2011 (UTC)

Do you refuse to explain why you disagree? --Tennenrishin (talk) 13:11, 7 September 2011 (UTC)

(If they are a little overwhelming I can summarize the most important ones for you.) --Tennenrishin (talk) 13:39, 7 September 2011 (UTC)

Fine, from your numbered list above: 1), It's a problem because it does not comply with the external links guidelines. 2) This argument compares apples and oranges: an implementation in the article vs an external link to your site. 3) This argument does not appear to be grounded in Wikipedia policy. 'Helpful' is not a criteria for link inclusion. 4) This argument does not appear to be grounded in Wikipedia policy. 5) This argument does not appear to be grounded in Wikipedia policy. - MrOllie (talk) 13:55, 7 September 2011 (UTC)

Please explain why you disagree that the link is helpful. I have now asked 5 times.

Also, since you have mistaken that numbered list of responses, let me help you identify the arguments throughout the discussion:

• A. Many readers are familiar with Java, but not with C. That segment of readers would find the link very helpful if not indispensable.
• B. The linked implementation is at a completely different level of abstraction compared to the article's implementation. In other words, it does away with many implementation details (pointers, #defines, typedefs, pointers to pointers! etc.) that only serve to obscure the concept being explained by the article. For this reason, even readers that are familiar with both languages would find the Java implementation adds considerable educational value.
• C. A ready-to-go Java implementation is, obviously, ideal information for readers looking to implement a circular buffer in Java. (And this happens often, for a reason explained in my original post.)

I believe any one of the above arguments is enough to prove that the link is helpful. I am a reasonable man:) I will not try to save face if I see your POV is valid. But with the views you claim to be holding, I'm finding it hard to believe you even know Java. (No offence - just an appeal for reasonableness.) --Tennenrishin (talk) 16:07, 7 September 2011 (UTC)

Please try to stick to the external links guidelines. None of what you are arguing seems to have much relation to them. Perhaps your fundamental disconnect is that you think the purpose of Wikipedia is to provide helpful links to readers. It is not. In fact Wikipedia is specifically not supposed to serve as a directory of external links. Perhaps you should add your link to a site which is supposed to be a directory, such as dmoz.org. Please don't mistake my refusal to engage with you on whether Java is better than C++ with ignorance of Java, I can assure you that I am familiar with both languages. - MrOllie (talk) 16:20, 7 September 2011 (UTC)

Guidelines are guidelines. The overruling question is whether the link improves WP or not. For most of this discussion, my quest has been to understand why you say the link is not helpful, in the face of three arguments (each of which seem undeniably compelling to me). This is the 6th time I ask.

If, on the other hand, you have now realized that the link is helpful, but you want to remove it despite its helpfulness, just because it violates guidelines, then please say so, because that is a different argument entirely. --Tennenrishin (talk)

The link is not helpful in the context of this Wikipedia article. It is not surprising that you find your own arguments compelling, or that you think it is a good site, it is your site and presumably you would not have put it up if you didn't think it was good. This is a large part of why we have the guideline on conflict of interest, which discourages siteowners from linking their sites. - MrOllie (talk) 03:55, 8 September 2011 (UTC)

So, in spite of arguments A, B and C above, the link is not helpful, because of who added it? Am I interpreting your response correctly? --Tennenrishin (talk) 11:46, 8 September 2011 (UTC)

No, that is incorrect. I have repeated my reasoning a couple of times above. I am really not interested in repeating myself again. - MrOllie (talk) 12:13, 8 September 2011 (UTC)

There is no need to repeat yourself. Just explain why you say the link is not helpful, or point me to where you have explained this already. Let me break the question down for you:

• Why is argument A invalid?
• Why is argument B invalid?
• Why is argument C invalid?

Alternatively, if you no longer wish to dispute that the link is helpful, but insist on its removal despite its helpfulness (for reasons such as WP:COI or WP:EL), then please say so. --Tennenrishin (talk) 13:26, 8 September 2011 (UTC)

I have brought this up at the noticeboard for external links to gain more input. - MrOllie (talk) 14:58, 8 September 2011 (UTC)

The link is not appropriate, per WP:EL and WP:COI. "Helpfulness" isn't much of an argument. OhNoitsJamie ^Talk 15:01, 8 September 2011 (UTC)

"Helpful" in the sense that the link constitutes a significant improvement to the article. I believe that this claim is supported by arguments A, B and C above, independently. The case I make stands or falls by them, but so far, they have not been addressed or acknowledged. --Tennenrishin (talk) 15:54, 8 September 2011 (UTC)

(Following up from the noticeboard request...) I agree with MrOllie and Ohnoitsjamie - it's code in a different language with little explanation. It's heavily redundant with the content of this article, so it should not be added to the list.

Please see arguments A, B and C. --Tennenrishin (talk) 07:44, 9 September 2011 (UTC)

Similarly, I'd remove the first link, http://c2.com/cgi/wiki?CircularBuffer , from the list as well. --Ronz (talk) 15:18, 8 September 2011 (UTC)

Regarding your request for "someone with Java experience" to come over; I've been writing Java since 1997, and I've already given you my opinion. I suggest stepping away from the deceased equine. OhNoitsJamie ^Talk 16:59, 8 September 2011 (UTC)

Your stated opinion appears to suggest that you agree the link is helpful, but that its helpfulness should be ignored. Is this true? --Tennenrishin (talk) 07:44, 9 September 2011 (UTC)

As to the arguments: taken to their logical conclusions, they would justify links to examples in every possible language - not even remotely appropriate. The other aspect of the arguments is that the article does not make the issue clear enough - but that's actually an argument for improving the article, not for going against WP:EL. --- Barek (talk • contribs) - 17:13, 8 September 2011 (UTC)

Thank you. You are the very first one to allude to the arguments I have raised.

• "they would justify links to examples in every possible language": All the arguments (A, B and C) are conditional on the wide popularity of Java. Java is the most, or the second most popular language, I'm not sure which.
• "but that's actually an argument for improving the article": My claim is that the link improves the article. That does not preclude the possibility that there is a different way to improve the article more. --Tennenrishin (talk) 19:40, 8 September 2011 (UTC)

You seem to have missed my point. The purpose of Wikipedia is to provide content, not an internet directory. The link does not improve the article, it expands a link directory. If the article is unclear, that's a reason to improve the article content, not to expand the link directory. --- Barek (talk • contribs) - 21:18, 8 September 2011 (UTC)

WP is not a link directory. Nonetheless, WP articles have helpful external links.

Implementations have inimitable ability to define the concept unambiguously, but easily "overload" the reader with lots of lines of code. That is why there have been complaints on this page about the amount of code in the article. The link discretely puts that extra helpfulness (see A, B, C, D below) within the reader's reach, but out of the reader's face. --Tennenrishin (talk) 09:06, 9 September 2011 (UTC)

Allow me to repeat the arguments, and summarize my position for the benefit of any newcomers. (B2 and D were added now)

• A. Many readers are familiar with Java, but not with C. That segment of readers would find the link very helpful if not indispensable.
• B1. The linked implementation is at a completely different level of abstraction compared to the article's implementation. In other words, it does away with many implementation details (pointers, code-structure, #defines, typedefs, pointers to pointers! etc.) that obscure the concept in question.
• B2. The linked implementation is a self-contained module implementing a very widely recognized interface from JCF. A pre-understood interface gives many readers a substantial head-start in assimilating it mentally (or in a project), because the circular buffer is decoupled from its context at no cost in generality.
• B. For reasons B1 and B2, even readers that are familiar with both languages would find the Java implementation adds considerable educational value.
• C. A ready-to-go Java implementation is, obviously, ideal reference information for readers looking to implement a circular buffer in Java. (And this happens often, for reasons explained in bullets 2 and 4 of my original post.)
• D. The main distinguishing feature (even though it is not a defining feature) of a circular buffer over a linked list, is its potential support for random access. Readers interested in this particular feature will find that the link implements it neatly, under the same widely recognized interface. (Working this optional functionality into the C implementation would incur some cost in clarity and article length.)

Now, my claim is that each of A, B, C and D point to a significant improvement in the WP article. --Tennenrishin (talk) 19:40, 8 September 2011 (UTC)

A, B, C and D have not been disputed anywhere in this entire discussion so far. Does anyone disagree? --Tennenrishin (talk) 11:22, 9 September 2011 (UTC)

I suggest everyone cease participating in this tiresome discussion. Wikipedia is not a court of law. There are three editors who are telling you the same thing; the link is not appropriate. There is no burden of proof that must be established to exclude a link. Policy backed by simple consensus is sufficient. OhNoitsJamie ^Talk 15:12, 9 September 2011 (UTC)

I am sorry that the discussion has been tiresome. Actually, in my original post, I said I wouldn't push, but one thing led to another... and I kept thinking a breakthrough is around the corner. I should have stopped a long time ago.

I have been quite stubborn, and I owe you all an explanation. But words are tiresome...

Helpless helpful external link

--Tennenrishin (talk) 22:41, 9 September 2011 (UTC)

That's pretty damned funny! Sorry if I was a bit gruff about the whole bit. It's just that I've had many, many, many similar discussions. Thanks for having a good sense of humor about it! OhNoitsJamie ^Talk 22:45, 9 September 2011 (UTC)

It's okay :) I just wish I hadn't waited so long before making my words into a picture. Tennenrishin (talk) 10:31, 2 January 2012 (UTC)

Removal of Implementations

I'm a little surprised to see my Bip Buffer article removed from here (not that I added it, but I was quite honored that it was linked). It was removed during removal of specific implementations... except it's not an actual implementation per se - it's a variant algorithm which provides nearly the efficiency of a regular circular buffer, but with reduced overhead for reading data in chunks; it ensures that all chunks read are contiguous.Fleetingshadow (talk) 22:15, 7 September 2011 (UTC)

MrOllie, this is collateral damage from our discussion above. Is there anything I can say to make you restore these links? --Tennenrishin (talk) 08:46, 8 September 2011 (UTC)

Regardless of the quality of such articles and ideas, Wikipedia needs to be consistent with its No Original Research policy. There are plenty of great venues for advancing new code paradigms/data structures/algorithms, etc. This just isn't the place for it. 02:48, 10 September 2011 (UTC)