git.ozlabs.org Git - ccan/blob - ccan/deque/deque.c

   1 /* Licensed under Apache License v2.0 - see LICENSE file for details */
   2 #include "config.h"
   3 #include <assert.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6 #include "deque.h"
   7
   8 int deq_resize_(struct deq *q, unsigned n)
   9 {
  10         char *t;
  11
  12         assert(q && n > 0 && n >= q->len);
  13
  14         if (!(t = malloc(q->esz * n)))
  15                 return -1;
  16
  17         if (q->len) {
  18                 unsigned part1 = q->head + q->len <= q->cap ? q->len : q->cap - q->head;
  19                 unsigned part2 = q->len - part1;
  20                 memcpy(t, q->v + q->head * q->esz, q->esz * part1);
  21                 if (part2)
  22                         memcpy(t + q->esz * part1, q->v, q->esz * part2);
  23         }
  24         if (q->cap)
  25                 free(q->v);
  26
  27         q->v    = t;
  28         q->head = 0;
  29         q->tail = q->len;
  30         q->cap  = n;
  31
  32         return 0;
  33 }
  34
  35 int deq_op_(struct deq *q, enum deq_op op, unsigned *i)
  36 {
  37         assert(q && i);
  38         assert(op == DEQ_PUSH || op == DEQ_POP ||  op == DEQ_SHIFT || op == DEQ_UNSHIFT);
  39
  40         switch (op) {
  41         case DEQ_PUSH:
  42         case DEQ_UNSHIFT:
  43                 if (q->len == q->cap && deq_resize_(q, q->cap == 0 ? q->min : q->cap * 2) == -1)
  44                         return -1;
  45                 break;
  46         case DEQ_POP:
  47         case DEQ_SHIFT:
  48                 if (q->cap > q->min) {
  49                         if (q->shrink == DEQ_SHRINK_IF_EMPTY && q->len == 1 && deq_resize_(q, q->min) == -1)
  50                                 return -1;
  51                         if (q->shrink == DEQ_SHRINK_AT_20PCT && (q->len - 1) * 5 <= q->cap && deq_resize_(q, q->cap / 2) == -1)
  52                                 return -1;
  53                 }
  54                 if (q->len == 0)
  55                         return 0;
  56         }
  57
  58         switch (op) {
  59         case DEQ_PUSH:
  60                 *i = q->tail++;
  61                 q->tail  %= q->cap;
  62                 q->len++;
  63                 break;
  64         case DEQ_SHIFT:
  65                 *i = q->head++;
  66                 q->head %= q->cap;
  67                 q->len--;
  68                 break;
  69         case DEQ_POP:
  70                 q->tail = (q->tail == 0 ? q->cap : q->tail) - 1;
  71                 *i = q->tail;
  72                 q->len--;
  73                 break;
  74         case DEQ_UNSHIFT:
  75                 q->head = (q->head == 0 ? q->cap : q->head) - 1;
  76                 *i = q->head;
  77                 q->len++;
  78                 break;
  79         }
  80
  81         return 1;
  82 }
  83
  84 void deq_reset_(struct deq *q)
  85 {
  86         assert(q);
  87
  88         if (q->v)
  89                 free(q->v);
  90
  91         q->v = 0;
  92         q->head = q->tail = q->len = q->cap = 0;
  93 }