XML CO527 Anonymous Questions and Answers Keyword Index

This page provides a keyword index to questions and answers. Clicking on a keyword will take you to a page containing all questions and answers for that keyword, grouped by year.

To submit a question, use the anonymous questions page. You may find the keyword index and/or top-level index useful for locating past questions and answers.

Keyword reference for circular-queue

Question 28 (2011):

Submission reference: IN2136

I'm having problems searching through the array of requests. Please can you explain how the circular buffer and the modulo operator work?

Answer 28:

Quite a few people have stumbled over this one — the modulo operator ("%" in Java and C) produces, basically, the remainder after division. Its primary use in code is to cause a wrapping-around effect, which is how it is used in the context of the circular buffer. For example, assume we start with an empty buffer:

  H
+---+---+---+---+---+---+
|   |   |   |   |   |   |  (head=0, tail=0, size=0)
+---+---+---+---+---+---+
  T

Then, the high-level calls blockread a couple of times which causes various things to be added to the buffer, and "head" and "size" updated accordingly:

              H
+---+---+---+---+---+---+
| 5 | 10| 2 |   |   |   |  (head=3, tail=0, size=3)
+---+---+---+---+---+---+
  T

Now lets assume some things get removed from the tail position (as the disk goes idle and is able to service them):

              H
+---+---+---+---+---+---+
|   |   | 2 |   |   |   |  (head=3, tail=2, size=1)
+---+---+---+---+---+---+
          T

Up to this point, things are looking quite sensible, and it's not hard to see that "size" is just "head" minus "tail". Lets assume some more things get added:

                      H
+---+---+---+---+---+---+
|   |   | 2 | 1 | 7 |   |  (head=5, tail=2, size=3)
+---+---+---+---+---+---+
          T

And still everything is sensible, "size" is still "head" minus "tail". However, when the next thing gets added, something different happens:

  H
+---+---+---+---+---+---+
|   |   | 2 | 1 | 7 | 4 |  (head=0, tail=2, size=4)
+---+---+---+---+---+---+
          T

The "head" pointer has wrapped around back to the beginning of the array, as it clearly should, since this is where the next empty slot is. However, it is no longer the case that "size" is "head" minus "tail" (clearly 4 <> 0-2). To get the wrap-around, there are two ways you can code it:

    head++;
    if (head == length) {
        head = 0;
    }

Or:

    head++;
    head = head % length;

The second of which is a bit more succinct, and could be shortened to just:

    head = (head + 1) % length;

which is what the code actually has in places. If something else gets added to the buffer, we'd get:

      H
+---+---+---+---+---+---+
| 3 |   | 2 | 1 | 7 | 4 |  (head=1, tail=2, size=5)
+---+---+---+---+---+---+
          T

Whilst the "size" equals "head" minus "tail" idea is broken when "head" is numerically less-than "tail", it is the case that: "size" equals ("head" minus "tail") modulo "length". If some entries then get removed from the buffer, we'd have:

      H
+---+---+---+---+---+---+
| 3 |   |   |   | 7 | 4 |  (head=1, tail=4, size=3)
+---+---+---+---+---+---+
                  T

And when "tail" reaches the end, it wraps around in the same way as "head" did.

Having wrap-around like this is convenient for efficiency, instead of shuffling array elements around or reallocating/copying the contents each time. Alternatively a linked-list would have done just as nicely (same ease of adding and removing things) however, a linked-list requires a bit more code to implement.

A particular problem I've seen some people have is iterating over the contents of the array. Given the pictures above, something like:

    for (int i=0; i<size; i++) {
        ...
    }

Is going to break, since you'd be accessing:

      H
+---+---+---+---+---+---+
|=3=|= =|= =|   | 7 | 4 |  (head=1, tail=4, size=3)
+---+---+---+---+---+---+
                  T

So whilst the first element (index 0) is valid, the next two are not! Something else I've seen people code is this:

    for (int i=tail; i<size; i++) {
        ...
    }

This won't work either, particular in this case since "tail" is 4 and "size" is 3, so the loop condition is false from the start. Another variation that won't work:

    for (int i=tail; i<head; i++) {
        ...
    }

Since, in the above, "tail" is 4 and "head" is 1, so no looping ever occurs. Logically, the number of iterations must be equal to the number of entries in the buffer (which is what "size" tracks), so it's easiest to go from zero and loop over these directly. However, the value used to index the array must be suitable adjusted to wrap-around in the same way. A naive implementation would be something like:

    for (int i=tail; i<(tail + size); i++) {
        ...
    }

But this will break in some cases, since you'd be accessing these elements:

      H
+---+---+---+---+---+---+
| 3 |   |   |   |=7=|=4=|= =   (head=1, tail=4, size=3)
+---+---+---+---+---+---+
                  T

Where the last one doesn't exist! In Java you'd get an ArrayIndexOutOfBoundsException; in C you'd get a crash and/or undefined behaviour. The correct way to iterate through the contents of the circular buffer is like this:

    for (int n=0; n<size; n++) {
        int i=(n+tail) % length;

        ...
    }

Or if you prefer:

    for (int j=tail; j<(tail + size); j++) {
        int i = j % length;

        ...
    }

Or you could be quite nasty and cater explicitly for the case where "head" has wrapped around, but "tail" hasn't yet (but this is not good programming practice!):

    if (head < tail) {
        // head must have wrapped around!

        // deal with back-half of array.
        for (int i=tail; i<length; i++) {
            ...
        }

        // and then the front-half.
        for (int i=0; i<head; i++) {
            ...
        }
    } else {
        // normal, full or empty
        for (int i=tail; i<head; i++) {
            ...
        }
     }

Whilst code such as this does work, it's far from pretty and results in large amounts of duplicated code.

Keywords: assess4-1112 , circular-queue

Referrers: Question 28 (2015) , Question 52 (2015) , Question 16 (2012) , Question 31 (2011)