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_del(struct psi_plist *list, size_t index, void *ptr) {
 152         if (list && list->count > index) {
 153                 if (ptr) {
 154                         PLIST_CPY(list, ptr, PLIST_ELE(list, index));
 155                 }
 156                 if (--list->count > index) {
 157                         PLIST_MOV_REDUCE(list, index);
 158                 }
 159                 return true;
 160         }
 161         return false;
 162 }
 163
 164 bool psi_plist_del_r(struct psi_plist *list, size_t offset_start, size_t num_eles, void **eles) {
 165         if (list) {
 166                 size_t offset_end = offset_start + num_eles - 1;
 167
 168                 if (list->count <= offset_end) {
 169                         offset_end = list->count - 1;
 170                 }
 171                 if (offset_end >= offset_start) {
 172                         num_eles = 1 + offset_end - offset_start;
 173
 174                         if (eles) {
 175                                 memcpy(eles, PLIST_ELE(list, offset_start), num_eles * list->size);
 176                         }
 177                         assert(list->count >= num_eles);
 178                         if ((list->count -= num_eles)) {
 179                                 PLIST_MOV_REDUCE_EX(list, offset_start, num_eles);
 180                         }
 181                         return true;
 182                 }
 183         }
 184         return false;
 185 }
 186
 187 struct psi_plist *psi_plist_ins(struct psi_plist *list, size_t index, void *ptr) {
 188         size_t new_count;
 189
 190         if (list) {
 191                 new_count = MAX(list->count + 1, index);
 192                 if (new_count) {
 193                         list = safe_perealloc(list, new_count + 1, list->size, sizeof(*list), 1);
 194                 }
 195                 if (list) {
 196                         PLIST_MOV_EXPAND(list, index);
 197                         PLIST_CPY(list, PLIST_ELE(list, index), ptr);
 198                         list->count = new_count;
 199                 }
 200         }
 201         return list;
 202 }
 203
 204 struct psi_plist *psi_plist_ins_r(struct psi_plist *list, size_t offset_start, size_t num_eles, void **eles) {
 205         size_t new_count;
 206
 207         if (list) {
 208                 new_count = MAX(offset_start, list->count) + num_eles;
 209                 if (new_count) {
 210                         list = safe_perealloc(list, new_count + 1, list->size, sizeof(*list), 1);
 211                 }
 212                 if (list) {
 213                         PLIST_MOV_EXPAND_EX(list, offset_start, num_eles);
 214                         PLIST_CPY_R(list, PLIST_ELE(list, offset_start), eles, num_eles);
 215                         list->count = new_count;
 216                 }
 217         }
 218         return list;
 219 }
 220
 221 bool psi_plist_shift(struct psi_plist *list, void *ptr) {
 222         if (list && list->count) {
 223                 if (ptr) {
 224                         PLIST_CPY(list, ptr, PLIST_ELE(list, 0));
 225                 }
 226                 if (--list->count) {
 227                         PLIST_MOV_REDUCE(list, 0);
 228                 }
 229                 return true;
 230         }
 231         return false;
 232 }
 233
 234 bool psi_plist_pop(struct psi_plist *list, void *ptr) {
 235         if (list && list->count) {
 236                 --list->count;
 237                 if (ptr) {
 238                         PLIST_CPY(list, ptr, PLIST_ELE(list, list->count));
 239                 }
 240                 return true;
 241         }
 242         return false;
 243 }
 244
 245 bool psi_plist_top(struct psi_plist *list, void *ptr) {
 246         if (list && list->count) {
 247                 PLIST_CPY(list, ptr, PLIST_ELE(list, list->count - 1));
 248                 return true;
 249         }
 250         return false;
 251 }
 252
 253
 254 static void swp_ptr(void *a, void *b) {
 255         void **_a = a, **_b = b, *_c;
 256
 257         _c = *_b;
 258         *_b = *_a;
 259         *_a = _c;
 260 }
 261
 262 void psi_plist_sort(struct psi_plist *list, compare_func_t cmp, swap_func_t swp) {
 263         if (!swp && list->size == sizeof(void *)) {
 264                 swp = swp_ptr;
 265         }
 266         assert(swp);
 267         zend_insert_sort((void *) list->list, list->count, list->size, cmp, swp);
 268 }