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