Circular buffer - logic difficulty

This is a discussion on Circular buffer - logic difficulty within the C Programming forums, part of the General Programming Boards category; I have written a get_buffer function that will not allow the buffer to be read if the buffer is empty. ...

  1. #1
    Registered User
    Join Date
    Aug 2009
    Posts
    70

    Circular buffer - logic difficulty

    I have written a get_buffer function that will not allow the buffer to be read if the buffer is empty. However, i am having difficulty doing the logic for the requirement of disallowing the buffer to be read when the buffer is at it's minimum fill level.

    Code:
    void init_buffer(bufferQueue *b, int min, int max)
    {
            b = malloc(sizeof(bufferQueue));
            b->buffer_array = malloc(max*sizeof(int));
            b->in = 0;
            b->out = 0;
            b->min_buffer_size = min;
            b->max_buffer_size = max;
    }
    
    bufferQueue *destroy_buffer(bufferQueue *b)
    {
            free(b);
            return b;
    }
    
    void put_buffer(bufferQueue *b, int v)
    {
            if((b->in+1)%b->max_buffer_size == b->out)
            {
                    //semWait(sem);
            }
    
            b->buffer_array[b->in] = v;
            b->in = (b->in+1)%b->max_buffer_size;
            }
    
    int get_buffer(bufferQueue *b)
    {
            if(b->in == b->out)
            {
                    return;
                    //semWait(sem);
            }
            return b->buffer_array[b->out];
            b->out = (b->out+1)%b->max_buffer_size;
    }
    Last edited by erasm; 10-05-2009 at 12:52 PM.

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,239
    Without some kind of special trick, it's impossible to tell the difference between a circular queue being completely full vs. completely empty. This is one of the classic difficulties of circular queues.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  3. #3
    Registered User
    Join Date
    Sep 2009
    Posts
    6
    I'm assuming you have a threaded-like environment, with fork or pthread_create...

    Your problem is also known as "the busy barber", or "the sleepy barber", a classical subject of computer sciences.

    You need to use two semaphores to handle the critical region, one to avoid consumers of reading empty buffers and another one to stop producers to insert anything when the buffer's full.

    This is a piece of a code I used in a c++ class used for synching multithreads... I just do not control whether the buffer's full or not, I simply don't mind (I just check the memory consumption, but buffer's level is always low in my program)

    Code:
     
    void Produce(Item *t) {
       down_mutex(); // enter critical region
          _buffer.put_buffer(t); // produce on your circular buffer
          is_empty=false;
          _count++;  //any check for is_full would be done here!
        up_mutex(); 
        up_empty (); // release customers waiting when buffer's empty
    }
    
    and the consumer:
    Item * Consume () {
        Item * ret;
        down_empty(); // go sleep if ain't no messages, up_empty releases!!
        down_mutex();  // enter RC
          ret = get_buffer(); // consume
          if (--_count==0) is_empty=true;  // down_empty controls
        up_mutex(); 
        return ret;
      }
    Now, just rewrite it using semaphores... follows the supressed functions.

    Code:
     
     void down_mutex() { pthread_mutex_lock(&mutex); }
      void up_mutex() { pthread_mutex_unlock(&mutex); }
    
      void down_empty() { while(is_empty) pthread_cond_wait(&empty, &mutex); up_mutex(); }
      void up_empty() { pthread_cond_signal(&empty); }
    
      void down_full()  { while(is_full) pthread_cond_wait(&full, &mutex); up_mutex(); }
      void up_full()  { pthread_cond_signal(&full); }
    Good luck!

    yezaim

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Function call from another .c module
    By Ali.B in forum C Programming
    Replies: 14
    Last Post: 08-03-2009, 11:45 AM
  2. buffer contents swapping
    By daluu in forum C++ Programming
    Replies: 7
    Last Post: 10-14-2004, 02:34 PM
  3. Console Screen Buffer
    By GaPe in forum Windows Programming
    Replies: 0
    Last Post: 02-06-2003, 04:15 AM
  4. Circular Logic
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 10-15-2001, 08:10 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21