git.m6w6.name Git - m6w6/ext-psi/blob - src/plist.c

   1 /*******************************************************************************
   2  Copyright (c) 2016, Michael Wallner <mike@php.net>.
   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 are met:
   7
   8      * Redistributions of source code must retain the above copyright notice,
   9        this list of conditions and the following disclaimer.
  10      * Redistributions in binary form must reproduce the above copyright
  11        notice, this list of conditions and the following disclaimer in the
  12        documentation and/or other materials provided with the distribution.
  13
  14  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  15  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  17  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
  18  FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  20  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  21  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  22  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24 *******************************************************************************/
  25
  26 #include "php_psi_stdinc.h"
  27
  28 #include "plist.h"
  29
  30 struct psi_plist {
  31         size_t size;
  32         size_t count;
  33         void (*dtor)(void *);
  34         void *list[0];
  35 };
  36
  37 #define PLIST_ELE(l, i) (((char *)(l)->list) + (l)->size * (i))
  38 #define PLIST_CPY(list, dest, src) do { \
  39         if (list->size == sizeof(void *)) { \
  40                 *(void **)(dest) = *(void **)(src); \
  41         } else { \
  42                 memcpy(dest, src, list->size); \
  43         } \
  44 } while (0)
  45 /* !!! adjust list->count prior reduction */
  46 #define PLIST_MOV_REDUCE(l, i) PLIST_MOV_REDUCE_EX(l, i, 1)
  47 #define PLIST_MOV_REDUCE_EX(l, i, n) memmove(PLIST_ELE(l, i), PLIST_ELE(l, i + n), (l)->size * ((l)->count - i))
  48 /* !!! adjust list->count after expansion */
  49 #define PLIST_MOV_EXPAND(l, i) PLIST_MOV_EXPAND_EX(l, i, 1)
  50 #define PLIST_MOV_EXPAND_EX(l, i, n) memmove(PLIST_ELE(l, i + n), PLIST_ELE(l, i), (l)->size * ((l)->count - i))
  51
  52 struct psi_plist *psi_plist_init(void (*dtor)(void *)) {
  53         return psi_plist_init_ex(0, dtor);
  54 }
  55 struct psi_plist *psi_plist_init_ex(size_t size, void (*dtor)(void *)) {
  56         struct psi_plist *list;
  57
  58         if (!size) {
  59                 size = sizeof(void*);
  60         }
  61
  62         list = calloc(1, sizeof(*list) + size);
  63         list->size = size;
  64         list->dtor = dtor;
  65
  66         return list;
  67 }
  68
  69 void psi_plist_free(struct psi_plist *list) {
  70         size_t i;
  71
  72         if (list->dtor) for (i = 0; i < list->count; ++i) {
  73                 list->dtor(PLIST_ELE(list, i));
  74         }
  75         free(list);
  76 }
  77
  78 struct psi_plist *psi_plist_copy(struct psi_plist *list, void (*ctor)(void *))
  79 {
  80         size_t i;
  81         struct psi_plist *copy = calloc(1, sizeof(*list) + list->size + list->count * list->size);
  82
  83         *copy = *list;
  84         if (list->count) {
  85                 memcpy(copy->list, list->list, list->size * list->count);
  86         }
  87         if (ctor) {
  88                 for (i = 0; i < list->count; ++i) {
  89                         void *ptr = PLIST_ELE(copy, i);
  90                         ctor(ptr);
  91                 }
  92         }
  93         return copy;
  94 }
  95
  96 size_t psi_plist_count(struct psi_plist *list) {
  97         return list ? list->count : 0;
  98 }
  99
 100 void **psi_plist_eles(struct psi_plist *list) {
 101         return list ? list->list : NULL;
 102 }
 103
 104 struct psi_plist *psi_plist_add(struct psi_plist *list, void *ptr) {
 105         if (list && list->count) {
 106                 list = realloc(list, sizeof(*list) + list->size + list->count * list->size);
 107         }
 108         if (list) {
 109                 PLIST_CPY(list, PLIST_ELE(list, list->count++), ptr);
 110         }
 111         return list;
 112 }
 113
 114 struct psi_plist *psi_plist_add_r(struct psi_plist *list, size_t num_eles, void **eles) {
 115         if (list && list->count) {
 116                 list = realloc(list, sizeof(*list) + list->size + (num_eles + list->count) * list->size);
 117         }
 118         if (list) {
 119                 memcpy(PLIST_ELE(list, list->count), eles, num_eles * list->size);
 120                 list->count += num_eles;
 121         }
 122         return list;
 123 }
 124
 125 bool psi_plist_get(struct psi_plist *list, size_t index, void *ptr) {
 126         if (list && list->count > index) {
 127                 PLIST_CPY(list, ptr, PLIST_ELE(list, index));
 128                 return true;
 129         }
 130         return false;
 131 }
 132
 133 bool psi_plist_del(struct psi_plist *list, size_t index, void *ptr) {
 134         if (list && list->count > index) {
 135                 if (ptr) {
 136                         PLIST_CPY(list, ptr, PLIST_ELE(list, index));
 137                 }
 138                 if (--list->count > index) {
 139                         PLIST_MOV_REDUCE(list, index);
 140                 }
 141                 return true;
 142         }
 143         return false;
 144 }
 145
 146 bool psi_plist_del_r(struct psi_plist *list, size_t offset_start, size_t num_eles, void **eles) {
 147         if (list) {
 148                 size_t offset_end = offset_start + num_eles - 1;
 149
 150                 if (list->count <= offset_end) {
 151                         offset_end = list->count - 1;
 152                 }
 153                 if (offset_end >= offset_start) {
 154                         num_eles = 1 + offset_end - offset_start;
 155
 156                         if (eles) {
 157                                 memcpy(eles, PLIST_ELE(list, offset_start), num_eles * list->size);
 158                         }
 159
 160                         if ((list->count -= num_eles)) {
 161                                 PLIST_MOV_REDUCE_EX(list, offset_start, num_eles);
 162                         }
 163                         return true;
 164                 }
 165         }
 166         return false;
 167 }
 168
 169 struct psi_plist *psi_plist_ins(struct psi_plist *list, size_t index, void *ptr) {
 170         size_t new_count = MAX(list->count + 1, index);
 171
 172         if (list && new_count) {
 173                 list = realloc(list, sizeof(*list) + list->size + new_count * list->size);
 174         }
 175         if (list) {
 176                 PLIST_MOV_EXPAND(list, index);
 177                 PLIST_CPY(list, PLIST_ELE(list, index), ptr);
 178                 list->count = new_count;
 179         }
 180         return list;
 181 }
 182
 183 struct psi_plist *psi_plist_ins_r(struct psi_plist *list, size_t offset_start, size_t num_eles, void **eles) {
 184         size_t new_count = MAX(offset_start, list->count) + num_eles;
 185
 186         if (list && new_count) {
 187                 list = realloc(list, sizeof(*list) + list->size + new_count * list->size);
 188         }
 189         if (list) {
 190                 size_t e;
 191
 192                 PLIST_MOV_EXPAND_EX(list, offset_start, num_eles);
 193                 for (e = 0; e < num_eles; ++e) {
 194                         PLIST_CPY(list, PLIST_ELE(list, offset_start + e), &eles[e]);
 195                 }
 196                 list->count = new_count;
 197         }
 198         return list;
 199 }
 200
 201 bool psi_plist_shift(struct psi_plist *list, void *ptr) {
 202         if (list && list->count) {
 203                 if (ptr) {
 204                         PLIST_CPY(list, ptr, PLIST_ELE(list, 0));
 205                 }
 206                 if (--list->count) {
 207                         PLIST_MOV_REDUCE(list, 0);
 208                 }
 209                 return true;
 210         }
 211         return false;
 212 }
 213
 214 bool psi_plist_pop(struct psi_plist *list, void *ptr) {
 215         if (list && list->count) {
 216                 --list->count;
 217                 if (ptr) {
 218                         PLIST_CPY(list, ptr, PLIST_ELE(list, list->count));
 219                 }
 220                 return true;
 221         }
 222         return false;
 223 }
 224
 225 bool psi_plist_top(struct psi_plist *list, void *ptr) {
 226         if (list && list->count) {
 227                 PLIST_CPY(list, ptr, PLIST_ELE(list, list->count - 1));
 228                 return true;
 229         }
 230         return false;
 231 }
 232
 233
 234 static void swp_ptr(void *a, void *b) {
 235         void **_a = a, **_b = b, *_c;
 236
 237         _c = *_b;
 238         *_b = *_a;
 239         *_a = _c;
 240 }
 241
 242 void psi_plist_sort(struct psi_plist *list, compare_func_t cmp, swap_func_t swp) {
 243         if (!swp && list->size == sizeof(void *)) {
 244                 swp = swp_ptr;
 245         }
 246         assert(swp);
 247         zend_insert_sort((void *) list->list, list->count, list->size, cmp, swp);
 248 }