current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote -3 down vote favorite

I have a FIFO queue of packets, which maintains:

  • Push index
  • Pop index
  • Count

I would like to assert my dequeuing algorithm:

if (push_index >= (count-i))
    pop_index = push_index-(count-i);
else
    pop_index = MAX_NUM_OF_PACKETS+push_index-(count-i);

Here is the code that I have used in order to test it:

#include <time.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_NUM_OF_PACKETS 8

int main()
{
    unsigned char push_index;
    unsigned char pop_index;
    unsigned char count;
    unsigned char i;

    int n;

    srand((unsigned int)time(NULL));

    for (n=0; n<100; n++)
    {
        push_index = (unsigned char)(rand()%MAX_NUM_OF_PACKETS);
        count = (unsigned char)(rand()%MAX_NUM_OF_PACKETS);
        printf("index = %u, count = %u:",push_index,count);
        for (i=0; i<count; i++)
        {
            if (push_index >= (count-i))
                pop_index = push_index-(count-i);
            else
                pop_index = MAX_NUM_OF_PACKETS+push_index-(count-i);
            printf(" %u",pop_index);
        }
        printf("\n");
    }

    return 0;
}

For the actual FIFO, you may assume that:

  • The maximum number of packets fits in 8 bits
  • The attributes (indexes and count) are thread-safe
share|improve this question
    
For the actual FIFO Is this example code or actual code? –  Mast Jul 3 at 8:36
    
@Mast: This code is for testing my dequeuing algorithm (described a few lines above it). Obviously, there is no threading issue here, as the indexes and the count are local variables. In the actual FIFO, those attributes are shared among different functions, and so they may be accessed by different threads during enqueue/dequeue operations. This is not a part of my question, so I figured that I should point it out. –  barak manos Jul 3 at 8:42
    
What exactly do you want a review on, that the tests cover your functionality? –  Emily L. Jul 3 at 12:42
    
@EmilyL.: Thank you. As I wrote at the beginning of the question, I would like to assert my dequeuing algorithm. The test is of less important to me, and I want to review the functionality itself: 1. Make sure that it is 100% correct. 2. Hear any improvement suggestion (simplification, etc). –  barak manos Jul 3 at 12:45

1 Answer 1

up vote 1 down vote

It looks like you're trying to reinvent the idea of "modulo" or "clock-face arithmetic":

  • MAX_NUM_OF_PACKETS means fifo_capacity
  • you're trying to take the quantity push_index - (count - i) modulo fifo_capacity

In C and C-like languages, this is spelled

pop_index = (push_index - (count - i)) % fifo_capacity;

You're worried about the case where (push_index - (count - i)) might be less than zero, in which case C doesn't define whether the modulus is positive or negative. The most common idiom to fix that problem is

int effective_pop_index = push_index - (count - i);
pop_index = (effective_pop_index + fifo_capacity) % fifo_capacity;

This is exactly what you came up with, except that you didn't know about the % operator.

A note on your English: You've said repeatedly that "I would like to assert my dequeuing algorithm." Unfortunately, the word assert does not have any English meaning that makes sense out of your statement. I think you meant "I would like to get some feedback on my algorithm.", or "Does anybody have any comments on my algorithm?".

Also, it's impossible to evaluate your dequeueing algorithm without also seeing your enqueueing algorithm. Of course we can guess what the latter looks like, but if I'm just going to guess, then I don't need to see any of your code, do I?

You should be aware that "%u" is the wrong format-specifier for unsigned char. You meant either printf("%hhu", pop_index), or else printf("%u", (unsigned int)pop_index). Without the explicit cast, pop_index will promote to int on most computer systems (undoubtedly including yours). (Which means that "%d" would also be pretty much correct.)

Also, you should be using int rather than unsigned char for all these quantities in the first place. All those (unsigned char) casts scattered throughout your code will at best not-hurt your program's performance; at worst they will inhibit compiler optimizations and slow things down. Remember, compilers tend to be really good at optimizing idiomatic, simple code, and not so good at optimizing weird, subtle code. Write your code as simply as possible, and the compiler will take care of the rest.

share|improve this answer
    
I don't want to use modulo because it effectively yields a division operation, and I'm running on a fixed-point processor. The compiler may opt it out when the operand is a power of 2 (as it is in my example - 8), but I wish not rely on that. –  barak manos Jul 5 at 8:24
1  
Use it. The compiler will perform strength reduction, and you'll save yourself a lot of headaches. To put it another way: You are currently programming in a perverse C-like language that lacks the % operator, and the best advice I can give to you is: Use C instead! It will save you a lot of time, plus, the C community is much bigger than the "barak's C-like language" community. –  Quuxplusone Jul 5 at 8:41
    
the C community is much bigger than the "barak's C-like language" community??? What kind of answer is that? And why have you down-voted the question (assuming that it was indeed you)? Such a long answer must imply that the question is in place!!! –  barak manos Jul 5 at 12:06
    
It wasn't me then, but it is now. :) –  Quuxplusone Jul 5 at 20:46
    
Right... And I suppose that it wasn't you who down-voted those other couple of random questions of mine either... –  barak manos Jul 5 at 20:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.