src/lib/cmdline_cirbuf.c

   1 /*-
   2  * Copyright (c) <2010>, Intel Corporation
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  *
  12  * - Redistributions in binary form must reproduce the above copyright
  13  *   notice, this list of conditions and the following disclaimer in
  14  *   the documentation and/or other materials provided with the
  15  *   distribution.
  16  *
  17  * - Neither the name of Intel Corporation nor the names of its
  18  *   contributors may be used to endorse or promote products derived
  19  *   from this software without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  27  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  28  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  30  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  31  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  32  * OF THE POSSIBILITY OF SUCH DAMAGE.
  33  */
  34
  35 /*
  36  * Copyright (c) 2009, Olivier MATZ <zer0@droids-corp.org>
  37  * All rights reserved.
  38  * Redistribution and use in source and binary forms, with or without
  39  * modification, are permitted provided that the following conditions are met:
  40  *
  41  *     * Redistributions of source code must retain the above copyright
  42  *       notice, this list of conditions and the following disclaimer.
  43  *     * Redistributions in binary form must reproduce the above copyright
  44  *       notice, this list of conditions and the following disclaimer in the
  45  *       documentation and/or other materials provided with the distribution.
  46  *     * Neither the name of the University of California, Berkeley nor the
  47  *       names of its contributors may be used to endorse or promote products
  48  *       derived from this software without specific prior written permission.
  49  *
  50  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ANY
  51  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  52  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  53  * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY
  54  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  55  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  56  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  57  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  58  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  59  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  60  */
  61
  62 #include <string.h>
  63 #include <errno.h>
  64
  65 #include "cmdline_cirbuf.h"
  66
  67
  68 void
  69 cirbuf_init(struct cirbuf *cbuf, char *buf, unsigned int start, unsigned int maxlen)
  70 {
  71         cbuf->maxlen = maxlen;
  72         cbuf->len = 0;
  73         cbuf->start = start;
  74         cbuf->end = start;
  75         cbuf->buf = buf;
  76 }
  77
  78 /* multiple add */
  79
  80 int
  81 cirbuf_add_buf_head(struct cirbuf *cbuf, const char *c, unsigned int n)
  82 {
  83         unsigned int e;
  84
  85         if (!n || n > CIRBUF_GET_FREELEN(cbuf))
  86                 return -EINVAL;
  87
  88         e = CIRBUF_IS_EMPTY(cbuf) ? 1 : 0;
  89
  90         if (n < cbuf->start + e) {
  91                 dprintf("s[%d] -> d[%d] (%d)\n", 0, cbuf->start - n + e, n);
  92                 memcpy(cbuf->buf + cbuf->start - n + e, c, n);
  93         }
  94         else {
  95                 dprintf("s[%d] -> d[%d] (%d)\n", + n - (cbuf->start + e), 0, cbuf->start + e);
  96                 dprintf("s[%d] -> d[%d] (%d)\n", cbuf->maxlen - n + (cbuf->start + e), 0, n - (cbuf->start + e));
  97                 memcpy(cbuf->buf, c  + n - (cbuf->start + e) , cbuf->start + e);
  98                 memcpy(cbuf->buf + cbuf->maxlen - n + (cbuf->start + e), c, n - (cbuf->start + e));
  99         }
 100         cbuf->len += n;
 101         cbuf->start += (cbuf->maxlen - n + e);
 102         cbuf->start %= cbuf->maxlen;
 103         return n;
 104 }
 105
 106 /* multiple add */
 107
 108 int
 109 cirbuf_add_buf_tail(struct cirbuf *cbuf, const char *c, unsigned int n)
 110 {
 111         unsigned int e;
 112
 113         if (!n || n > CIRBUF_GET_FREELEN(cbuf))
 114                 return -EINVAL;
 115
 116         e = CIRBUF_IS_EMPTY(cbuf) ? 1 : 0;
 117
 118         if (n < cbuf->maxlen - cbuf->end - 1 + e) {
 119                 dprintf("s[%d] -> d[%d] (%d)\n", 0, cbuf->end + !e, n);
 120                 memcpy(cbuf->buf + cbuf->end + !e, c, n);
 121         }
 122         else {
 123                 dprintf("s[%d] -> d[%d] (%d)\n", cbuf->end + !e, 0, cbuf->maxlen - cbuf->end - 1 + e);
 124                 dprintf("s[%d] -> d[%d] (%d)\n", cbuf->maxlen - cbuf->end - 1 + e, 0, n - cbuf->maxlen + cbuf->end + 1 - e);
 125                 memcpy(cbuf->buf + cbuf->end + !e, c, cbuf->maxlen - cbuf->end - 1 + e);
 126                 memcpy(cbuf->buf, c + cbuf->maxlen - cbuf->end - 1 + e, n - cbuf->maxlen + cbuf->end + 1 - e);
 127         }
 128         cbuf->len += n;
 129         cbuf->end += n - e;
 130         cbuf->end %= cbuf->maxlen;
 131         return n;
 132 }
 133
 134 /* add at head */
 135
 136 static inline void
 137 __cirbuf_add_head(struct cirbuf * cbuf, char c)
 138 {
 139         if (!CIRBUF_IS_EMPTY(cbuf)) {
 140                 cbuf->start += (cbuf->maxlen - 1);
 141                 cbuf->start %= cbuf->maxlen;
 142         }
 143         cbuf->buf[cbuf->start] = c;
 144         cbuf->len ++;
 145 }
 146
 147 int
 148 cirbuf_add_head_safe(struct cirbuf * cbuf, char c)
 149 {
 150         if (cbuf && !CIRBUF_IS_FULL(cbuf)) {
 151                 __cirbuf_add_head(cbuf, c);
 152                 return 0;
 153         }
 154         return -EINVAL;
 155 }
 156
 157 void
 158 cirbuf_add_head(struct cirbuf * cbuf, char c)
 159 {
 160         __cirbuf_add_head(cbuf, c);
 161 }
 162
 163 /* add at tail */
 164
 165 static inline void
 166 __cirbuf_add_tail(struct cirbuf * cbuf, char c)
 167 {
 168         if (!CIRBUF_IS_EMPTY(cbuf)) {
 169                 cbuf->end ++;
 170                 cbuf->end %= cbuf->maxlen;
 171         }
 172         cbuf->buf[cbuf->end] = c;
 173         cbuf->len ++;
 174 }
 175
 176 int
 177 cirbuf_add_tail_safe(struct cirbuf * cbuf, char c)
 178 {
 179         if (cbuf && !CIRBUF_IS_FULL(cbuf)) {
 180                 __cirbuf_add_tail(cbuf, c);
 181                 return 0;
 182         }
 183         return -EINVAL;
 184 }
 185
 186 void
 187 cirbuf_add_tail(struct cirbuf * cbuf, char c)
 188 {
 189         __cirbuf_add_tail(cbuf, c);
 190 }
 191
 192
 193 static inline void
 194 __cirbuf_shift_left(struct cirbuf *cbuf)
 195 {
 196         unsigned int i;
 197         char tmp = cbuf->buf[cbuf->start];
 198
 199         for (i=0 ; i<cbuf->len ; i++) {
 200                 cbuf->buf[(cbuf->start+i)%cbuf->maxlen] =
 201                         cbuf->buf[(cbuf->start+i+1)%cbuf->maxlen];
 202         }
 203         cbuf->buf[(cbuf->start-1+cbuf->maxlen)%cbuf->maxlen] = tmp;
 204         cbuf->start += (cbuf->maxlen - 1);
 205         cbuf->start %= cbuf->maxlen;
 206         cbuf->end += (cbuf->maxlen - 1);
 207         cbuf->end %= cbuf->maxlen;
 208 }
 209
 210 static inline void
 211 __cirbuf_shift_right(struct cirbuf *cbuf)
 212 {
 213         unsigned int i;
 214         char tmp = cbuf->buf[cbuf->end];
 215
 216         for (i=0 ; i<cbuf->len ; i++) {
 217                 cbuf->buf[(cbuf->end+cbuf->maxlen-i)%cbuf->maxlen] =
 218                         cbuf->buf[(cbuf->end+cbuf->maxlen-i-1)%cbuf->maxlen];
 219         }
 220         cbuf->buf[(cbuf->end+1)%cbuf->maxlen] = tmp;
 221         cbuf->start += 1;
 222         cbuf->start %= cbuf->maxlen;
 223         cbuf->end += 1;
 224         cbuf->end %= cbuf->maxlen;
 225 }
 226
 227 /* XXX we could do a better algorithm here... */
 228 void cirbuf_align_left(struct cirbuf * cbuf)
 229 {
 230         if (cbuf->start < cbuf->maxlen/2) {
 231                 while (cbuf->start != 0) {
 232                         __cirbuf_shift_left(cbuf);
 233                 }
 234         }
 235         else {
 236                 while (cbuf->start != 0) {
 237                         __cirbuf_shift_right(cbuf);
 238                 }
 239         }
 240 }
 241
 242 /* XXX we could do a better algorithm here... */
 243 void cirbuf_align_right(struct cirbuf * cbuf)
 244 {
 245         if (cbuf->start >= cbuf->maxlen/2) {
 246                 while (cbuf->end != cbuf->maxlen-1) {
 247                         __cirbuf_shift_left(cbuf);
 248                 }
 249         }
 250         else {
 251                 while (cbuf->start != cbuf->maxlen-1) {
 252                         __cirbuf_shift_right(cbuf);
 253                 }
 254         }
 255 }
 256
 257 /* buffer del */
 258
 259 int
 260 cirbuf_del_buf_head(struct cirbuf *cbuf, unsigned int size)
 261 {
 262         if (!size || size > CIRBUF_GET_LEN(cbuf))
 263                 return -EINVAL;
 264
 265         cbuf->len -= size;
 266         if (CIRBUF_IS_EMPTY(cbuf)) {
 267                 cbuf->start += size - 1;
 268                 cbuf->start %= cbuf->maxlen;
 269         }
 270         else {
 271                 cbuf->start += size;
 272                 cbuf->start %= cbuf->maxlen;
 273         }
 274         return 0;
 275 }
 276
 277 /* buffer del */
 278
 279 int
 280 cirbuf_del_buf_tail(struct cirbuf *cbuf, unsigned int size)
 281 {
 282         if (!size || size > CIRBUF_GET_LEN(cbuf))
 283                 return -EINVAL;
 284
 285         cbuf->len -= size;
 286         if (CIRBUF_IS_EMPTY(cbuf)) {
 287                 cbuf->end  += (cbuf->maxlen - size + 1);
 288                 cbuf->end %= cbuf->maxlen;
 289         }
 290         else {
 291                 cbuf->end  += (cbuf->maxlen - size);
 292                 cbuf->end %= cbuf->maxlen;
 293         }
 294         return 0;
 295 }
 296
 297 /* del at head */
 298
 299 static inline void
 300 __cirbuf_del_head(struct cirbuf * cbuf)
 301 {
 302         cbuf->len --;
 303         if (!CIRBUF_IS_EMPTY(cbuf)) {
 304                 cbuf->start ++;
 305                 cbuf->start %= cbuf->maxlen;
 306         }
 307 }
 308
 309 int
 310 cirbuf_del_head_safe(struct cirbuf * cbuf)
 311 {
 312         if (cbuf && !CIRBUF_IS_EMPTY(cbuf)) {
 313                 __cirbuf_del_head(cbuf);
 314                 return 0;
 315         }
 316         return -EINVAL;
 317 }
 318
 319 void
 320 cirbuf_del_head(struct cirbuf * cbuf)
 321 {
 322         __cirbuf_del_head(cbuf);
 323 }
 324
 325 /* del at tail */
 326
 327 static inline void
 328 __cirbuf_del_tail(struct cirbuf * cbuf)
 329 {
 330         cbuf->len --;
 331         if (!CIRBUF_IS_EMPTY(cbuf)) {
 332                 cbuf->end  += (cbuf->maxlen - 1);
 333                 cbuf->end %= cbuf->maxlen;
 334         }
 335 }
 336
 337 int
 338 cirbuf_del_tail_safe(struct cirbuf * cbuf)
 339 {
 340         if (cbuf && !CIRBUF_IS_EMPTY(cbuf)) {
 341                 __cirbuf_del_tail(cbuf);
 342                 return 0;
 343         }
 344         return -EINVAL;
 345 }
 346
 347 void
 348 cirbuf_del_tail(struct cirbuf * cbuf)
 349 {
 350         __cirbuf_del_tail(cbuf);
 351 }
 352
 353 /* convert to buffer */
 354
 355 int
 356 cirbuf_get_buf_head(struct cirbuf *cbuf, char *c, unsigned int size)
 357 {
 358         unsigned int n = (size < CIRBUF_GET_LEN(cbuf)) ? size : CIRBUF_GET_LEN(cbuf);
 359
 360         if (!n)
 361                 return 0;
 362
 363         if (cbuf->start <= cbuf->end) {
 364                 dprintf("s[%d] -> d[%d] (%d)\n", cbuf->start, 0, n);
 365                 memcpy(c, cbuf->buf + cbuf->start , n);
 366         }
 367         else {
 368                 dprintf("s[%d] -> d[%d] (%d)\n", cbuf->start, 0, cbuf->maxlen - cbuf->start);
 369                 dprintf("s[%d] -> d[%d] (%d)\n", 0, cbuf->maxlen - cbuf->start, n - cbuf->maxlen + cbuf->start);
 370                 memcpy(c, cbuf->buf + cbuf->start , cbuf->maxlen - cbuf->start);
 371                 memcpy(c + cbuf->maxlen - cbuf->start, cbuf->buf, n - cbuf->maxlen + cbuf->start);
 372         }
 373         return n;
 374 }
 375
 376 /* convert to buffer */
 377
 378 int
 379 cirbuf_get_buf_tail(struct cirbuf *cbuf, char *c, unsigned int size)
 380 {
 381         unsigned int n = (size < CIRBUF_GET_LEN(cbuf)) ? size : CIRBUF_GET_LEN(cbuf);
 382
 383         if (!n)
 384                 return 0;
 385
 386         if (cbuf->start <= cbuf->end) {
 387                 dprintf("s[%d] -> d[%d] (%d)\n", cbuf->end - n + 1, 0, n);
 388                 memcpy(c, cbuf->buf + cbuf->end - n + 1, n);
 389         }
 390         else {
 391                 dprintf("s[%d] -> d[%d] (%d)\n", 0,  cbuf->maxlen - cbuf->start, cbuf->end + 1);
 392                 dprintf("s[%d] -> d[%d] (%d)\n", cbuf->maxlen - n + cbuf->end + 1, 0, n - cbuf->end - 1);
 393
 394                 memcpy(c + cbuf->maxlen - cbuf->start, cbuf->buf, cbuf->end + 1);
 395                 memcpy(c, cbuf->buf + cbuf->maxlen - n + cbuf->end +1, n - cbuf->end - 1);
 396         }
 397         return n;
 398 }
 399
 400 /* get head or get tail */
 401
 402 char
 403 cirbuf_get_head(struct cirbuf * cbuf)
 404 {
 405         return cbuf->buf[cbuf->start];
 406 }
 407
 408 /* get head or get tail */
 409
 410 char
 411 cirbuf_get_tail(struct cirbuf * cbuf)
 412 {
 413         return cbuf->buf[cbuf->end];
 414 }
 415