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

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