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