Search code examples
cdata-structurescircular-buffer

Circular buffer implementation in C


I have found pseudo code on how to implement a circular buffer.

// Producer.
while (true) {
  /* produce item v */
  while ((in+1)%n == out)
    /* Wait. */;
  b[in] = v;
  in = (in + 1) % n
}

// Consumer.
while (true) {
  while (in == out)
    /* Wait. */;
  w = b[out];
  out = (out + 1) % n;
  /* Consume item w. */
}

What I don't understand is the "Consume item w." comment, because I think that with w = b[out]; we are consuming w, aren't we?


Solution

  • With

    w = b[out];
    

    You only grab a copy of the item to be consumed. With

    out = (out + 1) % n;
    

    You advance the index of the item to be consumed, thereby preventing it from being referenced again.

    In a manner, multiple calls to w = b[out]; don't actually consume the buffer's slot, it just accesses it; while out = (out + 1) % n; prevents further access of that item. Preventing further access of the buffer item is the strongest definition of the term "consume the item" that I can think of.