positions.c

   1 #ifndef CGPERF_POSITIONS_C
   2 #define CGPERF_POSITIONS_C
   3 #include <stdbool.h>
   4 #include <stdlib.h>
   5 #include <stdio.h>
   6 #include <string.h>
   7 #include "c_fixing.h"
   8 #include "positions.h"
   9 /*------------------------------------------------------------------------------------------------*/
  10 #include "namespace/positions.h"
  11 /*------------------------------------------------------------------------------------------------*/
  12 /*{{{ pos_new */
  13 static struct Positions *pos_new(void)
  14 {
  15         struct Positions *t;
  16
  17         t = calloc(1, sizeof(*t));
  18         t->useall = false;
  19         t->size = 0;
  20         return t;
  21 }/*}}}*/
  22 /*{{{ pos_new_cpy */
  23 /* the copy constructor */
  24 static struct Positions *pos_new_cpy(struct Positions *src)
  25 {
  26         struct Positions *t;
  27
  28         t = malloc(sizeof(*t));
  29         memcpy(t, src, sizeof(struct Positions));
  30         return t;
  31 }/*}}}*/
  32 /*{{{ pos_del */
  33 static void pos_del(struct Positions *t)
  34 {
  35         free(t);
  36 }/*}}}*/
  37 /*{{{ pos_set_useall */
  38 static void pos_set_useall(struct Positions *t, bool useall)
  39 {
  40         t->useall = useall;
  41         if (useall) {
  42                 s32 *ptr;
  43                 s32 i;
  44                 /* The positions are 0, 1, ..., Positions_max_key_pos-1, in descending order */
  45                 t->size = POS_MAX_KEY_POS;
  46                 ptr = t->positions;
  47                 i = POS_MAX_KEY_POS - 1;
  48                 loop {
  49                         if (i < 0)
  50                                 break;
  51                         *ptr++ = i;
  52                         i--;
  53                 }
  54         }
  55 }/*}}}*/
  56 /*{{{ pos_sort */
  57 static bool pos_sort(struct Positions *t)
  58 {
  59         /*
  60          * Sorts the array in reverse order. Returns true if there are no duplicates, false
  61          * otherwise
  62          */
  63         bool duplicate_free;
  64         s32 *base;
  65         u32 len;
  66         u32 i;
  67
  68         if (t->useall)
  69                 return true;
  70         /* bubble sort */
  71         duplicate_free = true;
  72         base = t->positions;
  73         len = t->size;
  74
  75         i = 1;
  76         loop {
  77                 u32 j;
  78                 s32 tmp;
  79
  80                 if (i >= len)
  81                         break;
  82                 j = i;
  83                 tmp = base[j];
  84                 loop {
  85                         if ((j == 0) || (tmp < base[j - 1]))
  86                                 break;
  87                         base[j] = base[j - 1];
  88                         if (base[j] == tmp) /* oh no, a duplicate!!! */
  89                                 duplicate_free = false;
  90                         j--;
  91                 }
  92                 base[j] = tmp;
  93                 ++i;
  94         }
  95         return duplicate_free;
  96 }/*}}}*/
  97 /*{{{ pos_contains */
  98 /* assumes the array is in reverse order */
  99 static bool pos_contains(struct Positions *t, s32 pos)
 100 {
 101         u32 count;
 102         s32 *p;
 103
 104         count = t->size;
 105         p = t->positions + t->size - 1;
 106         loop {
 107                 if (count == 0)
 108                         break;
 109                 if (*p == pos)
 110                         return true;
 111                 if (*p > pos)
 112                         break;
 113                 p--;
 114                 count--;
 115         }
 116         return false;
 117 }/*}}}*/
 118 /*{{{ pos_remove */
 119 static void pos_remove(struct Positions *t, s32 pos)
 120 {
 121         u32 count;
 122
 123         pos_set_useall(t, false);
 124         count = t->size;
 125         if (count > 0) {
 126                 s32 *p;
 127
 128                 p = t->positions + t->size - 1;
 129                 if (*p == pos) {
 130                         (t->size)--;
 131                         return;
 132                 }
 133                 if (*p < pos) {
 134                         s32 prev;
 135
 136                         prev = *p;
 137                         loop {
 138                                 s32 curr;
 139
 140                                 p--;
 141                                 count--;
 142                                 if (count == 0)
 143                                         break;
 144                                 if (*p == pos) {
 145                                         *p = prev;
 146                                         (t->size)--;
 147                                         return;
 148                                 }
 149                                 if (*p > pos)
 150                                         break;
 151                                 curr = *p;
 152                                 *p = prev;
 153                                 prev = curr;
 154                         }
 155                 }
 156         }
 157         fprintf(stderr, "Positions::remove internal error: not found\n");
 158         exit(1);
 159 }/*}}}*/
 160 /*{{{ pos_add */
 161 /* assumes the array is in reverse order */
 162 static void pos_add(struct Positions *t, s32 pos)
 163 {
 164         u32 count;
 165         s32 *p;
 166
 167         pos_set_useall(t, false);
 168
 169         count = t->size;
 170         if (count == POS_MAX_SIZE) {
 171                 fprintf(stderr, "Positions_add internal error: overflow\n");
 172                 exit(1);
 173         }
 174         p = t->positions + t->size - 1;
 175         loop {
 176                 if (count == 0)
 177                         break;
 178                 if (*p == pos) {
 179                         fprintf(stderr, "Positions_add internal error: duplicate\n");
 180                         exit(1);
 181                 }
 182                 if (*p > pos)
 183                         break;
 184                 p[1] = p[0];
 185                 p--;
 186                 count--;
 187         }
 188         p[1] = pos;
 189         ++(t->size);
 190 }/*}}}*/
 191 /*{{{ pos_iterator */
 192 /*
 193  * creates an iterator, returning the positions in descending order, that apply to strings of length
 194  * <= maxlen.
 195  */
 196 static struct PositionIterator *pos_iterator(struct Positions *t, s32 maxlen)
 197 {
 198         return positer_new(t, maxlen);
 199 }/*}}}*/
 200 /*{{{ pos_iterator_all */
 201 /* creates an iterator, returning the positions in descending order */
 202 static struct PositionIterator *pos_iterator_all(struct Positions *t)
 203 {
 204         return positer_new_all(t);
 205 }/*}}}*/
 206 /*{{{ pos_reviterator */
 207 /* creates an iterator, returning the positions in ascending order */
 208 static struct PositionReverseIterator *pos_reviterator(struct Positions *t)
 209 {
 210         return posrevit_new(t);
 211 }/*}}}*/
 212 /*{{{ positer_new */
 213 /* initializes an iterator through POSITIONS, ignoring positions >= maxlen */
 214 static struct PositionIterator *positer_new(struct Positions *positions, s32 maxlen)
 215 {
 216         struct PositionIterator *t;
 217
 218         t = calloc(1, sizeof(*t));
 219         t->set = positions;
 220
 221         if (positions->useall) {
 222                 t->index = (maxlen <= (s32)POS_MAX_KEY_POS ? (s32)POS_MAX_KEY_POS - maxlen : 0);
 223         } else {
 224                 u32 index;
 225
 226                 index = 0;
 227                 loop {
 228                         if (index >= positions->size || positions->positions[index] < maxlen)
 229                                 break;
 230                         ++index;
 231                 }
 232                 t->index = index;
 233         }
 234         return t;
 235 }/*}}}*/
 236 /*{{{ positer_new_all */
 237 /* initializes an iterator through POSITIONS */
 238 static struct PositionIterator *positer_new_all(struct Positions *positions)
 239 {
 240         struct PositionIterator *t;
 241
 242         t = calloc(1, sizeof(*t));
 243         t->set = positions;
 244         return t;
 245 }/*}}}*/
 246 /*{{{ positer_remaining */
 247 /* returns the number of remaining positions, i.e. how often next() will return a value != EOS */
 248 static u32 positer_remaining(struct PositionIterator *t)
 249 {
 250         return t->set->size - t->index;
 251 }/*}}}*/
 252 /*{{{ positer_next */
 253 /* retrieves the next position, or EOS past the end */
 254 static s32 positer_next(struct PositionIterator *t)
 255 {
 256         s32 r;
 257
 258         r = t->index < t->set->size ? t->set->positions[t->index] : POSITER_EOS;
 259         ++(t->index);
 260         return r;
 261 }/*}}}*/
 262 /*{{{ positer_del */
 263 static void positer_del(struct PositionIterator *t)
 264 {
 265         free(t);
 266 }/*}}}*/
 267 /*{{{ posrevit_new */
 268 static struct PositionReverseIterator *posrevit_new(struct Positions *positions)
 269 {
 270         struct PositionReverseIterator *t;
 271
 272         t = calloc(1, sizeof(*t));
 273         t->set = positions;
 274         t->index = t->set->size;
 275         return t;
 276 }/*}}}*/
 277 /*{{{ posrevit_del */
 278 static void posrevit_del(struct PositionReverseIterator *t)
 279 {
 280         free(t);
 281 }/*}}}*/
 282 /*{{{ posrevit_next */
 283 /* retrieves the next position, or EOS past the end  */
 284 static s32 posrevit_next(struct PositionReverseIterator *t)
 285 {
 286         s32 r;
 287
 288         (t->index)--;
 289         r = (t->index > t->minindex ?  t->set->positions[t->index] : POSREVIT_EOS);
 290         return r;
 291 }
 292 /*}}}*/
 293 /*{{{ pos_cpy */
 294 /* _NOT_ the copy constructor */
 295 static void pos_cpy(struct Positions *d, struct Positions *s)
 296 {
 297         memcpy(d, s, sizeof(struct Positions));
 298 }/*}}}*/
 299 /*{{{ pos_print */
 300 static void pos_print(struct Positions *t)
 301 {
 302         bool first;
 303         bool seen_LASTCHAR;
 304         u32 count;
 305         s32 *p;
 306
 307         if (t->useall) {
 308                 printf ("*");
 309                 return;
 310         }
 311         first = true;
 312         seen_LASTCHAR = false;
 313         count = t->size;
 314         p = t->positions + t->size - 1;
 315         loop {
 316                 if (count == 0)
 317                         break;
 318                 count--;
 319                 if (*p == POS_LASTCHAR)
 320                         seen_LASTCHAR = true;
 321                 else {
 322                         if (!first)
 323                                 printf(",");
 324                         printf("%d", *p + 1);
 325                         if (count > 0 && p[-1] == *p + 1) {
 326                                 printf("-");
 327                                 loop {
 328                                         p--;
 329                                         count--;
 330                                         if (!(count > 0 && p[-1] == *p + 1))
 331                                                 break;
 332                                 }
 333                                 printf("%d", *p + 1);
 334                         }
 335                         first = false;
 336                 }
 337                 p--;
 338         }
 339         if (seen_LASTCHAR) {
 340                 if (!first)
 341                         printf(",");
 342                 printf("$");
 343         }
 344 }/*}}}*/
 345 /*------------------------------------------------------------------------------------------------*/
 346 #define EPILOG
 347 #include "namespace/positions.h"
 348 #undef EPILOG
 349 /*------------------------------------------------------------------------------------------------*/
 350 #endif