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,
  96                         cbuf->start + e);
  97                 dprintf("s[%d] -> d[%d] (%d)\n", cbuf->maxlen - n +
  98                         (cbuf->start + e), 0, n - (cbuf->start + e));
  99                 memcpy(cbuf->buf, c  + n - (cbuf->start + e) , cbuf->start + e);
 100                 memcpy(cbuf->buf + cbuf->maxlen - n + (cbuf->start + e), c,
 101                        n - (cbuf->start + e));
 102         }
 103         cbuf->len += n;
 104         cbuf->start += (cbuf->maxlen - n + e);
 105         cbuf->start %= cbuf->maxlen;
 106         return n;
 107 }
 108
 109 /* multiple add */
 110
 111 int
 112 cirbuf_add_buf_tail(struct cirbuf *cbuf, const char *c, unsigned int n)
 113 {
 114         unsigned int e;
 115
 116         if (!n || n > CIRBUF_GET_FREELEN(cbuf))
 117                 return -EINVAL;
 118
 119         e = CIRBUF_IS_EMPTY(cbuf) ? 1 : 0;
 120
 121         if (n < cbuf->maxlen - cbuf->end - 1 + e) {
 122                 dprintf("s[%d] -> d[%d] (%d)\n", 0, cbuf->end + !e, n);
 123                 memcpy(cbuf->buf + cbuf->end + !e, c, n);
 124         }
 125         else {
 126                 dprintf("s[%d] -> d[%d] (%d)\n", cbuf->end + !e, 0,
 127                         cbuf->maxlen - cbuf->end - 1 + e);
 128                 dprintf("s[%d] -> d[%d] (%d)\n", cbuf->maxlen - cbuf->end - 1 +
 129                         e, 0, n - cbuf->maxlen + cbuf->end + 1 - e);
 130                 memcpy(cbuf->buf + cbuf->end + !e, c, cbuf->maxlen -
 131                        cbuf->end - 1 + e);
 132                 memcpy(cbuf->buf, c + cbuf->maxlen - cbuf->end - 1 + e,
 133                        n - cbuf->maxlen + cbuf->end + 1 - e);
 134         }
 135         cbuf->len += n;
 136         cbuf->end += n - e;
 137         cbuf->end %= cbuf->maxlen;
 138         return n;
 139 }
 140
 141 /* add at head */
 142
 143 static inline void
 144 __cirbuf_add_head(struct cirbuf * cbuf, char c)
 145 {
 146         if (!CIRBUF_IS_EMPTY(cbuf)) {
 147                 cbuf->start += (cbuf->maxlen - 1);
 148                 cbuf->start %= cbuf->maxlen;
 149         }
 150         cbuf->buf[cbuf->start] = c;
 151         cbuf->len ++;
 152 }
 153
 154 int
 155 cirbuf_add_head_safe(struct cirbuf * cbuf, char c)
 156 {
 157         if (cbuf && !CIRBUF_IS_FULL(cbuf)) {
 158                 __cirbuf_add_head(cbuf, c);
 159                 return 0;
 160         }
 161         return -EINVAL;
 162 }
 163
 164 void
 165 cirbuf_add_head(struct cirbuf * cbuf, char c)
 166 {
 167         __cirbuf_add_head(cbuf, c);
 168 }
 169
 170 /* add at tail */
 171
 172 static inline void
 173 __cirbuf_add_tail(struct cirbuf * cbuf, char c)
 174 {
 175         if (!CIRBUF_IS_EMPTY(cbuf)) {
 176                 cbuf->end ++;
 177                 cbuf->end %= cbuf->maxlen;
 178         }
 179         cbuf->buf[cbuf->end] = c;
 180         cbuf->len ++;
 181 }
 182
 183 int
 184 cirbuf_add_tail_safe(struct cirbuf * cbuf, char c)
 185 {
 186         if (cbuf && !CIRBUF_IS_FULL(cbuf)) {
 187                 __cirbuf_add_tail(cbuf, c);
 188                 return 0;
 189         }
 190         return -EINVAL;
 191 }
 192
 193 void
 194 cirbuf_add_tail(struct cirbuf * cbuf, char c)
 195 {
 196         __cirbuf_add_tail(cbuf, c);
 197 }
 198
 199
 200 static inline void
 201 __cirbuf_shift_left(struct cirbuf *cbuf)
 202 {
 203         unsigned int i;
 204         char tmp = cbuf->buf[cbuf->start];
 205
 206         for (i=0 ; i<cbuf->len ; i++) {
 207                 cbuf->buf[(cbuf->start+i)%cbuf->maxlen] =
 208                         cbuf->buf[(cbuf->start+i+1)%cbuf->maxlen];
 209         }
 210         cbuf->buf[(cbuf->start-1+cbuf->maxlen)%cbuf->maxlen] = tmp;
 211         cbuf->start += (cbuf->maxlen - 1);
 212         cbuf->start %= cbuf->maxlen;
 213         cbuf->end += (cbuf->maxlen - 1);
 214         cbuf->end %= cbuf->maxlen;
 215 }
 216
 217 static inline void
 218 __cirbuf_shift_right(struct cirbuf *cbuf)
 219 {
 220         unsigned int i;
 221         char tmp = cbuf->buf[cbuf->end];
 222
 223         for (i=0 ; i<cbuf->len ; i++) {
 224                 cbuf->buf[(cbuf->end+cbuf->maxlen-i)%cbuf->maxlen] =
 225                         cbuf->buf[(cbuf->end+cbuf->maxlen-i-1)%cbuf->maxlen];
 226         }
 227         cbuf->buf[(cbuf->end+1)%cbuf->maxlen] = tmp;
 228         cbuf->start += 1;
 229         cbuf->start %= cbuf->maxlen;
 230         cbuf->end += 1;
 231         cbuf->end %= cbuf->maxlen;
 232 }
 233
 234 /* XXX we could do a better algorithm here... */
 235 void cirbuf_align_left(struct cirbuf * cbuf)
 236 {
 237         if (cbuf->start < cbuf->maxlen/2) {
 238                 while (cbuf->start != 0) {
 239                         __cirbuf_shift_left(cbuf);
 240                 }
 241         }
 242         else {
 243                 while (cbuf->start != 0) {
 244                         __cirbuf_shift_right(cbuf);
 245                 }
 246         }
 247 }
 248
 249 /* XXX we could do a better algorithm here... */
 250 void cirbuf_align_right(struct cirbuf * cbuf)
 251 {
 252         if (cbuf->start >= cbuf->maxlen/2) {
 253                 while (cbuf->end != cbuf->maxlen-1) {
 254                         __cirbuf_shift_left(cbuf);
 255                 }
 256         }
 257         else {
 258                 while (cbuf->start != cbuf->maxlen-1) {
 259                         __cirbuf_shift_right(cbuf);
 260                 }
 261         }
 262 }
 263
 264 /* buffer del */
 265
 266 int
 267 cirbuf_del_buf_head(struct cirbuf *cbuf, unsigned int size)
 268 {
 269         if (!size || size > CIRBUF_GET_LEN(cbuf))
 270                 return -EINVAL;
 271
 272         cbuf->len -= size;
 273         if (CIRBUF_IS_EMPTY(cbuf)) {
 274                 cbuf->start += size - 1;
 275                 cbuf->start %= cbuf->maxlen;
 276         }
 277         else {
 278                 cbuf->start += size;
 279                 cbuf->start %= cbuf->maxlen;
 280         }
 281         return 0;
 282 }
 283
 284 /* buffer del */
 285
 286 int
 287 cirbuf_del_buf_tail(struct cirbuf *cbuf, unsigned int size)
 288 {
 289         if (!size || size > CIRBUF_GET_LEN(cbuf))
 290                 return -EINVAL;
 291
 292         cbuf->len -= size;
 293         if (CIRBUF_IS_EMPTY(cbuf)) {
 294                 cbuf->end  += (cbuf->maxlen - size + 1);
 295                 cbuf->end %= cbuf->maxlen;
 296         }
 297         else {
 298                 cbuf->end  += (cbuf->maxlen - size);
 299                 cbuf->end %= cbuf->maxlen;
 300         }
 301         return 0;
 302 }
 303
 304 /* del at head */
 305
 306 static inline void
 307 __cirbuf_del_head(struct cirbuf * cbuf)
 308 {
 309         cbuf->len --;
 310         if (!CIRBUF_IS_EMPTY(cbuf)) {
 311                 cbuf->start ++;
 312                 cbuf->start %= cbuf->maxlen;
 313         }
 314 }
 315
 316 int
 317 cirbuf_del_head_safe(struct cirbuf * cbuf)
 318 {
 319         if (cbuf && !CIRBUF_IS_EMPTY(cbuf)) {
 320                 __cirbuf_del_head(cbuf);
 321                 return 0;
 322         }
 323         return -EINVAL;
 324 }
 325
 326 void
 327 cirbuf_del_head(struct cirbuf * cbuf)
 328 {
 329         __cirbuf_del_head(cbuf);
 330 }
 331
 332 /* del at tail */
 333
 334 static inline void
 335 __cirbuf_del_tail(struct cirbuf * cbuf)
 336 {
 337         cbuf->len --;
 338         if (!CIRBUF_IS_EMPTY(cbuf)) {
 339                 cbuf->end  += (cbuf->maxlen - 1);
 340                 cbuf->end %= cbuf->maxlen;
 341         }
 342 }
 343
 344 int
 345 cirbuf_del_tail_safe(struct cirbuf * cbuf)
 346 {
 347         if (cbuf && !CIRBUF_IS_EMPTY(cbuf)) {
 348                 __cirbuf_del_tail(cbuf);
 349                 return 0;
 350         }
 351         return -EINVAL;
 352 }
 353
 354 void
 355 cirbuf_del_tail(struct cirbuf * cbuf)
 356 {
 357         __cirbuf_del_tail(cbuf);
 358 }
 359
 360 /* convert to buffer */
 361
 362 int
 363 cirbuf_get_buf_head(struct cirbuf *cbuf, char *c, unsigned int size)
 364 {
 365         unsigned int n;
 366
 367         n = (size < CIRBUF_GET_LEN(cbuf)) ? size : CIRBUF_GET_LEN(cbuf);
 368
 369         if (!n)
 370                 return 0;
 371
 372         if (cbuf->start <= cbuf->end) {
 373                 dprintf("s[%d] -> d[%d] (%d)\n", cbuf->start, 0, n);
 374                 memcpy(c, cbuf->buf + cbuf->start , n);
 375         }
 376         else {
 377                 dprintf("s[%d] -> d[%d] (%d)\n", cbuf->start, 0,
 378                         cbuf->maxlen - cbuf->start);
 379                 dprintf("s[%d] -> d[%d] (%d)\n", 0,cbuf->maxlen - cbuf->start,
 380                         n - cbuf->maxlen + cbuf->start);
 381                 memcpy(c, cbuf->buf + cbuf->start , cbuf->maxlen - cbuf->start);
 382                 memcpy(c + cbuf->maxlen - cbuf->start, cbuf->buf,
 383                        n - cbuf->maxlen + cbuf->start);
 384         }
 385         return n;
 386 }
 387
 388 /* convert to buffer */
 389
 390 int
 391 cirbuf_get_buf_tail(struct cirbuf *cbuf, char *c, unsigned int size)
 392 {
 393         unsigned int n;
 394
 395         n = (size < CIRBUF_GET_LEN(cbuf)) ? size : CIRBUF_GET_LEN(cbuf);
 396
 397         if (!n)
 398                 return 0;
 399
 400         if (cbuf->start <= cbuf->end) {
 401                 dprintf("s[%d] -> d[%d] (%d)\n", cbuf->end - n + 1, 0, n);
 402                 memcpy(c, cbuf->buf + cbuf->end - n + 1, n);
 403         }
 404         else {
 405                 dprintf("s[%d] -> d[%d] (%d)\n", 0,
 406                         cbuf->maxlen - cbuf->start, cbuf->end + 1);
 407                 dprintf("s[%d] -> d[%d] (%d)\n",
 408                         cbuf->maxlen - n + cbuf->end + 1, 0, n - cbuf->end - 1);
 409
 410                 memcpy(c + cbuf->maxlen - cbuf->start,
 411                        cbuf->buf, cbuf->end + 1);
 412                 memcpy(c, cbuf->buf + cbuf->maxlen - n + cbuf->end +1,
 413                        n - cbuf->end - 1);
 414         }
 415         return n;
 416 }
 417
 418 /* get head or get tail */
 419
 420 char
 421 cirbuf_get_head(struct cirbuf * cbuf)
 422 {
 423         return cbuf->buf[cbuf->start];
 424 }
 425
 426 /* get head or get tail */
 427
 428 char
 429 cirbuf_get_tail(struct cirbuf * cbuf)
 430 {
 431         return cbuf->buf[cbuf->end];
 432 }
 433