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 #define PLIST_CPY_R(list, dest, src, num) memcpy((dest), (src), (num) * (list)->size)
  46 /* !!! adjust list->count prior reduction */
  47 #define PLIST_MOV_REDUCE(l, i) PLIST_MOV_REDUCE_EX(l, i, 1)
  48 #define PLIST_MOV_REDUCE_EX(l, i, n) memmove(PLIST_ELE(l, i), PLIST_ELE(l, (i) + (n)), (l)->size * ((l)->count - (i)))
  49 /* !!! adjust list->count after expansion */
  50 #define PLIST_MOV_EXPAND(l, i) PLIST_MOV_EXPAND_EX(l, i, 1)
  51 #define PLIST_MOV_EXPAND_EX(l, i, n) memmove(PLIST_ELE(l, (i) + (n)), PLIST_ELE(l, i), (l)->size * ((l)->count - (i)))
  52
  53 struct psi_plist *psi_plist_init(void (*dtor)(void *)) {
  54         return psi_plist_init_ex(0, dtor);
  55 }
  56 struct psi_plist *psi_plist_init_ex(size_t size, void (*dtor)(void *)) {
  57         struct psi_plist *list;
  58
  59         if (!size) {
  60                 size = sizeof(void*);
  61         }
  62
  63         list = pecalloc(1, sizeof(*list) + size, 1);
  64         list->size = size;
  65         list->dtor = dtor;
  66
  67         return list;
  68 }
  69
  70 void psi_plist_clean(struct psi_plist *list) {
  71         size_t i;
  72
  73         if (list) {
  74                 if (list->dtor) for (i = 0; i < list->count; ++i) {
  75                         list->dtor(PLIST_ELE(list, i));
  76                 }
  77                 list->count = 0;
  78         }
  79 }
  80
  81 void psi_plist_free(struct psi_plist *list) {
  82         if (list) {
  83                 psi_plist_clean(list);
  84                 free(list);
  85         }
  86 }
  87
  88 struct psi_plist *psi_plist_copy(struct psi_plist *list, void (*ctor)(void *))
  89 {
  90         size_t i;
  91         struct psi_plist *copy = pecalloc(1, sizeof(*list) + list->size + list->count * list->size, 1);
  92
  93         *copy = *list;
  94         if (list->count) {
  95                 memcpy(copy->list, list->list, list->size * list->count);
  96         }
  97         if (ctor) {
  98                 for (i = 0; i < list->count; ++i) {
  99                         void *ptr = PLIST_ELE(copy, i);
 100                         ctor(ptr);
 101                 }
 102         }
 103         return copy;
 104 }
 105
 106 size_t psi_plist_count(struct psi_plist *list) {
 107         return list ? list->count : 0;
 108 }
 109
 110 void **psi_plist_eles(struct psi_plist *list) {
 111         return list ? list->list : NULL;
 112 }
 113
 114 struct psi_plist *psi_plist_add(struct psi_plist *list, void *ptr) {
 115         if (list && list->count) {
 116                 list = safe_perealloc(list, list->count + 1, list->size, sizeof(*list), 1);
 117         }
 118         if (list) {
 119                 PLIST_CPY(list, PLIST_ELE(list, list->count++), ptr);
 120         }
 121         return list;
 122 }
 123
 124 struct psi_plist *psi_plist_add_r(struct psi_plist *list, size_t num_eles, void **eles) {
 125         if (list) {
 126                 list = safe_perealloc(list, list->count + num_eles + 1, list->size, sizeof(*list), 1);
 127         }
 128         if (list) {
 129                 memcpy(PLIST_ELE(list, list->count), eles, num_eles * list->size);
 130                 list->count += num_eles;
 131         }
 132         return list;
 133 }
 134
 135 bool psi_plist_get(struct psi_plist *list, size_t index, void *ptr) {
 136         if (list && list->count > index) {
 137                 PLIST_CPY(list, ptr, PLIST_ELE(list, index));
 138                 return true;
 139         }
 140         return false;
 141 }
 142
 143 bool psi_plist_unset(struct psi_plist *list, size_t index) {
 144         if (list && list->count > index) {
 145                 memset(PLIST_ELE(list, index), 0, list->size);
 146                 return true;
 147         }
 148         return false;
 149 }
 150
 151 bool psi_plist_set(struct psi_plist *list, size_t index, void *ptr) {
 152         if (list && list->count > index) {
 153                 PLIST_CPY(list, PLIST_ELE(list, index), ptr);
 154                 return true;
 155         }
 156         return false;
 157 }
 158
 159 bool psi_plist_del(struct psi_plist *list, size_t index, void *ptr) {
 160         if (list && list->count > index) {
 161                 if (ptr) {
 162                         PLIST_CPY(list, ptr, PLIST_ELE(list, index));
 163                 }
 164                 if (--list->count > index) {
 165                         PLIST_MOV_REDUCE(list, index);
 166                 }
 167                 return true;
 168         }
 169         return false;
 170 }
 171
 172 bool psi_plist_del_r(struct psi_plist *list, size_t offset_start, size_t num_eles, void **eles) {
 173         if (list) {
 174                 size_t offset_end = offset_start + num_eles - 1;
 175
 176                 if (list->count <= offset_end) {
 177                         offset_end = list->count - 1;
 178                 }
 179                 if (offset_end >= offset_start) {
 180                         num_eles = 1 + offset_end - offset_start;
 181
 182                         if (eles) {
 183                                 memcpy(eles, PLIST_ELE(list, offset_start), num_eles * list->size);
 184                         }
 185                         assert(list->count >= num_eles);
 186                         if ((list->count -= num_eles)) {
 187                                 PLIST_MOV_REDUCE_EX(list, offset_start, num_eles);
 188                         }
 189                         return true;
 190                 }
 191         }
 192         return false;
 193 }
 194
 195 struct psi_plist *psi_plist_ins(struct psi_plist *list, size_t index, void *ptr) {
 196         size_t new_count;
 197
 198         if (list) {
 199                 new_count = MAX(list->count + 1, index);
 200                 if (new_count) {
 201                         list = safe_perealloc(list, new_count + 1, list->size, sizeof(*list), 1);
 202                 }
 203                 if (list) {
 204                         PLIST_MOV_EXPAND(list, index);
 205                         PLIST_CPY(list, PLIST_ELE(list, index), ptr);
 206                         list->count = new_count;
 207                 }
 208         }
 209         return list;
 210 }
 211
 212 struct psi_plist *psi_plist_ins_r(struct psi_plist *list, size_t offset_start, size_t num_eles, void **eles) {
 213         size_t new_count;
 214
 215         if (list) {
 216                 new_count = MAX(offset_start, list->count) + num_eles;
 217                 if (new_count) {
 218                         list = safe_perealloc(list, new_count + 1, list->size, sizeof(*list), 1);
 219                 }
 220                 if (list) {
 221                         PLIST_MOV_EXPAND_EX(list, offset_start, num_eles);
 222                         PLIST_CPY_R(list, PLIST_ELE(list, offset_start), eles, num_eles);
 223                         list->count = new_count;
 224                 }
 225         }
 226         return list;
 227 }
 228
 229 bool psi_plist_shift(struct psi_plist *list, void *ptr) {
 230         if (list && list->count) {
 231                 if (ptr) {
 232                         PLIST_CPY(list, ptr, PLIST_ELE(list, 0));
 233                 }
 234                 if (--list->count) {
 235                         PLIST_MOV_REDUCE(list, 0);
 236                 }
 237                 return true;
 238         }
 239         return false;
 240 }
 241
 242 bool psi_plist_pop(struct psi_plist *list, void *ptr) {
 243         if (list && list->count) {
 244                 --list->count;
 245                 if (ptr) {
 246                         PLIST_CPY(list, ptr, PLIST_ELE(list, list->count));
 247                 }
 248                 return true;
 249         }
 250         return false;
 251 }
 252
 253 bool psi_plist_top(struct psi_plist *list, void *ptr) {
 254         if (list && list->count) {
 255                 PLIST_CPY(list, ptr, PLIST_ELE(list, list->count - 1));
 256                 return true;
 257         }
 258         return false;
 259 }
 260
 261
 262 static void swp_ptr(void *a, void *b) {
 263         void **_a = a, **_b = b, *_c;
 264
 265         _c = *_b;
 266         *_b = *_a;
 267         *_a = _c;
 268 }
 269
 270 void psi_plist_sort(struct psi_plist *list, compare_func_t cmp, swap_func_t swp) {
 271         if (!swp && list->size == sizeof(void *)) {
 272                 swp = swp_ptr;
 273         }
 274         assert(swp);
 275         zend_insert_sort((void *) list->list, list->count, list->size, cmp, swp);
 276 }