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