src/shl_ring.h

   1 /*
   2  * shl - Dynamic Array
   3  *
   4  * Copyright (c) 2011-2012 David Herrmann <dh.herrmann@googlemail.com>
   5  * Copyright (c) 2011 University of Tuebingen
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining
   8  * a copy of this software and associated documentation files
   9  * (the "Software"), to deal in the Software without restriction, including
  10  * without limitation the rights to use, copy, modify, merge, publish,
  11  * distribute, sublicense, and/or sell copies of the Software, and to
  12  * permit persons to whom the Software is furnished to do so, subject to
  13  * the following conditions:
  14  *
  15  * The above copyright notice and this permission notice shall be included
  16  * in all copies or substantial portions of the Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
  19  * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  21  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  22  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  23  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  24  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  25  */
  26
  27 /*
  28  * A circular memory ring implementation
  29  */
  30
  31 #ifndef SHL_RING_H
  32 #define SHL_RING_H
  33
  34 #include <stdbool.h>
  35 #include <stddef.h>
  36 #include <stdint.h>
  37 #include <stdlib.h>
  38
  39 #define SHL_RING_SIZE 512
  40
  41 struct shl_ring_entry {
  42         struct shl_ring_entry *next;
  43         size_t len;
  44         char buf[];
  45 };
  46
  47 struct shl_ring {
  48         struct shl_ring_entry *first;
  49         struct shl_ring_entry *last;
  50 };
  51
  52 static inline int shl_ring_new(struct shl_ring **out)
  53 {
  54         struct shl_ring *ring;
  55
  56         if (!out)
  57                 return -EINVAL;
  58
  59         ring = malloc(sizeof(*ring));
  60         if (!ring)
  61                 return -ENOMEM;
  62
  63         memset(ring, 0, sizeof(*ring));
  64
  65         *out = ring;
  66         return 0;
  67 }
  68
  69 static inline void shl_ring_free(struct shl_ring *ring)
  70 {
  71         struct shl_ring_entry *tmp;
  72
  73         if (!ring)
  74                 return;
  75
  76         while (ring->first) {
  77                 tmp = ring->first;
  78                 ring->first = tmp->next;
  79                 free(tmp);
  80         }
  81         free(ring);
  82 }
  83
  84 static inline bool shl_ring_is_empty(struct shl_ring *ring)
  85 {
  86         if (!ring)
  87                 return true;
  88
  89         return ring->first == NULL;
  90 }
  91
  92 static inline int shl_ring_write(struct shl_ring *ring, const char *val,
  93                                  size_t len)
  94 {
  95         struct shl_ring_entry *ent;
  96         size_t space, cp;
  97
  98         if (!ring || !val || !len)
  99                 return -EINVAL;
 100
 101 next:
 102         ent = ring->last;
 103         if (!ent || ent->len >= SHL_RING_SIZE) {
 104                 ent = malloc(sizeof(*ent) + SHL_RING_SIZE);
 105                 if (!ent)
 106                         return -ENOMEM;
 107
 108                 ent->len = 0;
 109                 ent->next = NULL;
 110                 if (ring->last)
 111                         ring->last->next = ent;
 112                 else
 113                         ring->first = ent;
 114                 ring->last = ent;
 115         }
 116
 117         space = SHL_RING_SIZE - ent->len;
 118         if (len >= space)
 119                 cp = space;
 120         else
 121                 cp = len;
 122
 123         memcpy(&ent->buf[ent->len], val, cp);
 124         ent->len += cp;
 125
 126         val = &val[cp];
 127         len -= cp;
 128         if (len > 0)
 129                 goto next;
 130
 131         return 0;
 132 }
 133
 134 static inline const char *shl_ring_peek(struct shl_ring *ring, size_t *len,
 135                                         size_t offset)
 136 {
 137         struct shl_ring_entry *iter;
 138
 139         if (!ring || !ring->first || !len) {
 140                 if (len)
 141                         *len = 0;
 142                 return NULL;
 143         }
 144
 145         iter = ring->first;
 146         while (iter->len <= offset) {
 147                 if (!iter->next) {
 148                         *len = 0;
 149                         return NULL;
 150                 }
 151
 152                 offset -= iter->len;
 153                 iter = iter->next;
 154         }
 155
 156         *len = ring->first->len - offset;
 157         return &ring->first->buf[offset];
 158 }
 159
 160 static inline void shl_ring_drop(struct shl_ring *ring, size_t len)
 161 {
 162         struct shl_ring_entry *ent;
 163
 164         if (!ring || !len)
 165                 return;
 166
 167 next:
 168         ent = ring->first;
 169         if (!ent)
 170                 return;
 171
 172         if (len >= ent->len) {
 173                 len -= ent->len;
 174                 ring->first = ent->next;
 175                 free(ent);
 176                 if (!ring->first)
 177                         ring->last = NULL;
 178
 179                 if (len)
 180                         goto next;
 181         } else {
 182                 memmove(ent->buf, &ent->buf[len], ent->len - len);
 183                 ent->len -= len;
 184         }
 185 }
 186
 187 static inline void shl_ring_flush(struct shl_ring *ring)
 188 {
 189         struct shl_ring_entry *tmp;
 190
 191         if (!ring)
 192                 return;
 193
 194         while (ring->first) {
 195                 tmp = ring->first;
 196                 ring->first = tmp->next;
 197                 free(tmp);
 198         }
 199         ring->last = NULL;
 200 }
 201
 202 #endif /* SHL_RING_H */