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_clean(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         list->count = 0;
  76 }
  77
  78 void psi_plist_free(struct psi_plist *list) {
  79         psi_plist_clean(list);
  80         free(list);
  81 }
  82
  83 struct psi_plist *psi_plist_copy(struct psi_plist *list, void (*ctor)(void *))
  84 {
  85         size_t i;
  86         struct psi_plist *copy = calloc(1, sizeof(*list) + list->size + list->count * list->size);
  87
  88         *copy = *list;
  89         if (list->count) {
  90                 memcpy(copy->list, list->list, list->size * list->count);
  91         }
  92         if (ctor) {
  93                 for (i = 0; i < list->count; ++i) {
  94                         void *ptr = PLIST_ELE(copy, i);
  95                         ctor(ptr);
  96                 }
  97         }
  98         return copy;
  99 }
 100
 101 size_t psi_plist_count(struct psi_plist *list) {
 102         return list ? list->count : 0;
 103 }
 104
 105 void **psi_plist_eles(struct psi_plist *list) {
 106         return list ? list->list : NULL;
 107 }
 108
 109 struct psi_plist *psi_plist_add(struct psi_plist *list, void *ptr) {
 110         if (list && list->count) {
 111                 list = realloc(list, sizeof(*list) + list->size + list->count * list->size);
 112         }
 113         if (list) {
 114                 PLIST_CPY(list, PLIST_ELE(list, list->count++), ptr);
 115         }
 116         return list;
 117 }
 118
 119 struct psi_plist *psi_plist_add_r(struct psi_plist *list, size_t num_eles, void **eles) {
 120         if (list && list->count) {
 121                 list = realloc(list, sizeof(*list) + list->size + (num_eles + list->count) * list->size);
 122         }
 123         if (list) {
 124                 memcpy(PLIST_ELE(list, list->count), eles, num_eles * list->size);
 125                 list->count += num_eles;
 126         }
 127         return list;
 128 }
 129
 130 bool psi_plist_get(struct psi_plist *list, size_t index, void *ptr) {
 131         if (list && list->count > index) {
 132                 PLIST_CPY(list, ptr, PLIST_ELE(list, index));
 133                 return true;
 134         }
 135         return false;
 136 }
 137
 138 bool psi_plist_del(struct psi_plist *list, size_t index, void *ptr) {
 139         if (list && list->count > index) {
 140                 if (ptr) {
 141                         PLIST_CPY(list, ptr, PLIST_ELE(list, index));
 142                 }
 143                 if (--list->count > index) {
 144                         PLIST_MOV_REDUCE(list, index);
 145                 }
 146                 return true;
 147         }
 148         return false;
 149 }
 150
 151 bool psi_plist_del_r(struct psi_plist *list, size_t offset_start, size_t num_eles, void **eles) {
 152         if (list) {
 153                 size_t offset_end = offset_start + num_eles - 1;
 154
 155                 if (list->count <= offset_end) {
 156                         offset_end = list->count - 1;
 157                 }
 158                 if (offset_end >= offset_start) {
 159                         num_eles = 1 + offset_end - offset_start;
 160
 161                         if (eles) {
 162                                 memcpy(eles, PLIST_ELE(list, offset_start), num_eles * list->size);
 163                         }
 164                         assert(list->count >= num_eles);
 165                         if ((list->count -= num_eles)) {
 166                                 PLIST_MOV_REDUCE_EX(list, offset_start, num_eles);
 167                         }
 168                         return true;
 169                 }
 170         }
 171         return false;
 172 }
 173
 174 struct psi_plist *psi_plist_ins(struct psi_plist *list, size_t index, void *ptr) {
 175         size_t new_count;
 176
 177         if (list) {
 178                 new_count = MAX(list->count + 1, index);
 179                 if (new_count) {
 180                         list = realloc(list, sizeof(*list) + list->size + new_count * list->size);
 181                 }
 182                 if (list) {
 183                         PLIST_MOV_EXPAND(list, index);
 184                         PLIST_CPY(list, PLIST_ELE(list, index), ptr);
 185                         list->count = new_count;
 186                 }
 187         }
 188         return list;
 189 }
 190
 191 struct psi_plist *psi_plist_ins_r(struct psi_plist *list, size_t offset_start, size_t num_eles, void **eles) {
 192         size_t new_count;
 193
 194         if (list) {
 195                 new_count = MAX(offset_start, list->count) + num_eles;
 196                 if (new_count) {
 197                         list = realloc(list, sizeof(*list) + list->size + new_count * list->size);
 198                 }
 199                 if (list) {
 200                         size_t e;
 201
 202                         PLIST_MOV_EXPAND_EX(list, offset_start, num_eles);
 203                         for (e = 0; e < num_eles; ++e) {
 204                                 PLIST_CPY(list, PLIST_ELE(list, offset_start + e), &eles[e]);
 205                         }
 206                         list->count = new_count;
 207                 }
 208         }
 209         return list;
 210 }
 211
 212 bool psi_plist_shift(struct psi_plist *list, void *ptr) {
 213         if (list && list->count) {
 214                 if (ptr) {
 215                         PLIST_CPY(list, ptr, PLIST_ELE(list, 0));
 216                 }
 217                 if (--list->count) {
 218                         PLIST_MOV_REDUCE(list, 0);
 219                 }
 220                 return true;
 221         }
 222         return false;
 223 }
 224
 225 bool psi_plist_pop(struct psi_plist *list, void *ptr) {
 226         if (list && list->count) {
 227                 --list->count;
 228                 if (ptr) {
 229                         PLIST_CPY(list, ptr, PLIST_ELE(list, list->count));
 230                 }
 231                 return true;
 232         }
 233         return false;
 234 }
 235
 236 bool psi_plist_top(struct psi_plist *list, void *ptr) {
 237         if (list && list->count) {
 238                 PLIST_CPY(list, ptr, PLIST_ELE(list, list->count - 1));
 239                 return true;
 240         }
 241         return false;
 242 }
 243
 244
 245 static void swp_ptr(void *a, void *b) {
 246         void **_a = a, **_b = b, *_c;
 247
 248         _c = *_b;
 249         *_b = *_a;
 250         *_a = _c;
 251 }
 252
 253 void psi_plist_sort(struct psi_plist *list, compare_func_t cmp, swap_func_t swp) {
 254         if (!swp && list->size == sizeof(void *)) {
 255                 swp = swp_ptr;
 256         }
 257         assert(swp);
 258         zend_insert_sort((void *) list->list, list->count, list->size, cmp, swp);
 259 }