kernel/util/circular.c

0001 /*                    The Quest Operating System
0002  *  Copyright (C) 2005-2010  Richard West, Boston University
0003  *
0004  *  This program is free software: you can redistribute it and/or modify
0005  *  it under the terms of the GNU General Public License as published by
0006  *  the Free Software Foundation, either version 3 of the License, or
0007  *  (at your option) any later version.
0008  *
0009  *  This program is distributed in the hope that it will be useful,
0010  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
0011  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0012  *  GNU General Public License for more details.
0013  *
0014  *  You should have received a copy of the GNU General Public License
0015  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
0016  */
0017
0018 #include "arch/i386.h"
0019 #include "sched/sched.h"
0020 #include "util/circular.h"
0021
0022 static inline void
0023 circular_lock (circular *c)
0024 {
0025   spinlock_lock (&c->lock);
0026 }
0027
0028 static inline void
0029 circular_unlock (circular *c)
0030 {
0031   spinlock_unlock (&c->lock);
0032 }
0033
0034 /* Insert an element of any size into the circular buffer.  If buffer
0035  * is full, check if CIRCULAR_FLAG_NOWAIT is set.  If so, return -1,
0036  * else block. */
0037 static sint32
0038 generic_circular_insert (circular *c, void *elt, uint32 flags)
0039 {
0040   sint32 ret;
0041
0042   circular_lock (c);
0043
0044   while (c->cur_count == c->num_elts) {
0045     if (flags & CIRCULAR_FLAG_NOWAIT) {
0046       ret = -1;
0047       goto finish;
0048     } else {
0049       /* place on waitqueue */
0050       queue_append (&c->ins_waitq, str ());
0051       circular_unlock (c);
0052       schedule ();              /* block */
0053       circular_lock (c);
0054     }
0055   }
0056
0057   /* copy the elt into the insertion point and advance the insertion
0058    * pointer to the next slot. */
0059   memcpy (c->insert_ptr, elt, c->elt_size);
0060   c->insert_ptr += c->elt_size;
0061   if (c->insert_ptr >= c->buffer_end)
0062     c->insert_ptr = c->buffer;
0063   ret = ++c->cur_count;
0064   wakeup_queue (&c->rem_waitq);
0065
0066  finish:
0067   circular_unlock (c);
0068   return ret;
0069 }
0070
0071 /* Remove an element of any size from the circular buffer and copy to
0072  * the pointer out_elt.  If buffer is empty, check if
0073  * CIRCULAR_FLAG_NOWAIT is set.  If so, return -1, else block. */
0074 static sint32
0075 generic_circular_remove (circular *c, void *out_elt, uint32 flags)
0076 {
0077   sint32 ret;
0078
0079   circular_lock (c);
0080
0081   while (c->cur_count == 0) {
0082     if (flags & CIRCULAR_FLAG_NOWAIT) {
0083       ret = -1;
0084       goto finish;
0085     } else {
0086       /* place on waitqueue */
0087       queue_append (&c->rem_waitq, str ());
0088       circular_unlock (c);
0089       schedule ();              /* block */
0090       circular_lock (c);
0091     }
0092   }
0093
0094   /* copy from the removal point into out_elt and advance the removal
0095    * pointer to the next slot. */
0096   memcpy (out_elt, c->remove_ptr, c->elt_size);
0097   c->remove_ptr += c->elt_size;
0098   if (c->remove_ptr >= c->buffer_end)
0099     c->remove_ptr = c->buffer;
0100   ret = --c->cur_count;
0101   wakeup_queue (&c->ins_waitq);
0102
0103  finish:
0104   circular_unlock (c);
0105   return ret;
0106 }
0107
0108 /* Instead of templates, use explicit element size parameter. */
0109
0110 void
0111 circular_init (circular *c, void *buffer, sint32 num_elts, sint32 elt_size)
0112 {
0113   c->buffer     = buffer;
0114   c->insert_ptr = buffer;
0115   c->remove_ptr = buffer;
0116   c->buffer_end = buffer + num_elts * elt_size;
0117   c->num_elts   = num_elts;
0118   c->elt_size   = elt_size;
0119   c->cur_count  = 0;
0120   /* Leave possibility of specialized routines being used here. */
0121   c->insert     = generic_circular_insert;
0122   c->remove     = generic_circular_remove;
0123   spinlock_init (&c->lock);
0124   c->ins_waitq  = 0;
0125   c->rem_waitq  = 0;
0126 }
0127
0128 /*
0129  * Local Variables:
0130  * indent-tabs-mode: nil
0131  * mode: C
0132  * c-file-style: "gnu"
0133  * c-basic-offset: 2
0134  * End:
0135  */
0136
0137 /* vi: set et sw=2 sts=2: */