src/array.c

   1 #include "first.h"
   2
   3 #include "array.h"
   4 #include "buffer.h"
   5
   6 #include <string.h>
   7 #include <stdlib.h>
   8 #include <limits.h>
   9
  10 #include <errno.h>
  11 #include <assert.h>
  12
  13 #define ARRAY_NOT_FOUND ((size_t)(-1))
  14
  15 array *array_init(void) {
  16         array *a;
  17
  18         a = calloc(1, sizeof(*a));
  19         force_assert(a);
  20
  21         return a;
  22 }
  23
  24 array *array_init_array(array *src) {
  25         size_t i;
  26         array *a = array_init();
  27
  28         if (0 == src->size) return a;
  29
  30         a->used = src->used;
  31         a->size = src->size;
  32         a->unique_ndx = src->unique_ndx;
  33
  34         a->data = malloc(sizeof(*src->data) * src->size);
  35         force_assert(NULL != a->data);
  36         for (i = 0; i < src->size; i++) {
  37                 if (src->data[i]) a->data[i] = src->data[i]->fn->copy(src->data[i]);
  38                 else a->data[i] = NULL;
  39         }
  40
  41         a->sorted = malloc(sizeof(*src->sorted) * src->size);
  42         force_assert(NULL != a->sorted);
  43         memcpy(a->sorted, src->sorted, sizeof(*src->sorted) * src->size);
  44         return a;
  45 }
  46
  47 void array_free(array *a) {
  48         size_t i;
  49         if (!a) return;
  50
  51         for (i = 0; i < a->size; i++) {
  52                 if (a->data[i]) a->data[i]->fn->free(a->data[i]);
  53         }
  54
  55         if (a->data) free(a->data);
  56         if (a->sorted) free(a->sorted);
  57
  58         free(a);
  59 }
  60
  61 void array_reset(array *a) {
  62         size_t i;
  63         if (!a) return;
  64
  65         for (i = 0; i < a->used; i++) {
  66                 a->data[i]->fn->reset(a->data[i]);
  67                 a->data[i]->is_index_key = 0;
  68         }
  69
  70         a->used = 0;
  71         a->unique_ndx = 0;
  72 }
  73
  74 void array_reset_data_strings(array *a) {
  75         if (!a) return;
  76
  77         for (size_t i = 0; i < a->used; ++i) {
  78                 data_string * const ds = (data_string *)a->data[i];
  79                 /*force_assert(ds->type == TYPE_STRING);*/
  80                 ds->is_index_key = 0;
  81                 buffer_reset(ds->key);
  82                 buffer_reset(ds->value);
  83         }
  84
  85         a->used = 0;
  86         a->unique_ndx = 0;
  87 }
  88
  89 data_unset *array_pop(array *a) {
  90         data_unset *du;
  91
  92         force_assert(a->used != 0);
  93
  94         a->used --;
  95         du = a->data[a->used];
  96         force_assert(a->sorted[a->used] == a->used); /* only works on "simple" lists */
  97         a->data[a->used] = NULL;
  98
  99         return du;
 100 }
 101
 102 __attribute_pure__
 103 static int array_caseless_compare(const char * const a, const char * const b, const size_t len) {
 104     for (size_t i = 0; i < len; ++i) {
 105         unsigned int ca = ((unsigned char *)a)[i];
 106         unsigned int cb = ((unsigned char *)b)[i];
 107         if (ca == cb) continue;
 108
 109         /* always lowercase for transitive results */
 110         if (ca >= 'A' && ca <= 'Z') ca |= 32;
 111         if (cb >= 'A' && cb <= 'Z') cb |= 32;
 112
 113         if (ca == cb) continue;
 114         return (int)(ca - cb);
 115     }
 116     return 0;
 117 }
 118
 119 __attribute_pure__
 120 static int array_keycmp(const char *a, size_t alen, const char *b, size_t blen) {
 121     return alen < blen ? -1 : alen > blen ? 1 : array_caseless_compare(a, b, blen);
 122 }
 123
 124 /* returns index of element or ARRAY_NOT_FOUND
 125  * if rndx != NULL it stores the position in a->sorted[] where the key needs
 126  * to be inserted
 127  */
 128 static size_t array_get_index(const array *a, const char *key, size_t keylen, size_t *rndx) {
 129         /* invariant: [lower-1] < key < [upper]
 130          * "virtual elements": [-1] = -INFTY, [a->used] = +INFTY
 131          * also an invariant: 0 <= lower <= upper <= a->used
 132          */
 133         size_t lower = 0, upper = a->used;
 134         force_assert(upper <= SSIZE_MAX); /* (lower + upper) can't overflow */
 135
 136         while (lower != upper) {
 137                 size_t probe = (lower + upper) / 2;
 138                 const buffer *b = a->data[a->sorted[probe]]->key;
 139                 int cmp = array_keycmp(key, keylen, CONST_BUF_LEN(b));
 140
 141                 if (cmp == 0) {
 142                         /* found */
 143                         if (rndx) *rndx = probe;
 144                         return a->sorted[probe];
 145                 } else if (cmp < 0) {
 146                         /* key < [probe] */
 147                         upper = probe; /* still: lower <= upper */
 148                 } else {
 149                         /* key > [probe] */
 150                         lower = probe + 1; /* still: lower <= upper */
 151                 }
 152         }
 153
 154         /* not found: [lower-1] < key < [upper] = [lower] ==> insert at [lower] */
 155         if (rndx) *rndx = lower;
 156         return ARRAY_NOT_FOUND;
 157 }
 158
 159 data_unset *array_get_element_klen(const array *a, const char *key, size_t klen) {
 160         size_t ndx;
 161         force_assert(NULL != key);
 162
 163         if (ARRAY_NOT_FOUND != (ndx = array_get_index(a, key, klen, NULL))) {
 164                 /* found, return it */
 165                 return a->data[ndx];
 166         }
 167
 168         return NULL;
 169 }
 170
 171 data_unset *array_extract_element_klen(array *a, const char *key, size_t klen) {
 172         size_t ndx, pos;
 173         force_assert(NULL != key);
 174
 175         if (ARRAY_NOT_FOUND != (ndx = array_get_index(a, key, klen, &pos))) {
 176                 /* found */
 177                 const size_t last_ndx = a->used - 1;
 178                 data_unset *entry = a->data[ndx];
 179
 180                 /* now we need to swap it with the last element (if it isn't already the last element) */
 181                 if (ndx != last_ndx) {
 182                         /* to swap we also need to modify the index in a->sorted - find pos of last_elem there */
 183                         size_t last_elem_pos;
 184                         /* last element must be present at the expected position */
 185                         force_assert(last_ndx == array_get_index(a, CONST_BUF_LEN(a->data[last_ndx]->key), &last_elem_pos));
 186
 187                         /* move entry from last_ndx to ndx */
 188                         a->data[ndx] = a->data[last_ndx];
 189                         a->data[last_ndx] = NULL;
 190
 191                         /* fix index entry for moved entry */
 192                         a->sorted[last_elem_pos] = ndx;
 193                 } else {
 194                         a->data[ndx] = NULL;
 195                 }
 196
 197                 /* remove entry in a->sorted: move everything after pos one step to the left */
 198                 if (pos != last_ndx) {
 199                         memmove(a->sorted + pos, a->sorted + pos + 1, (last_ndx - pos) * sizeof(*a->sorted));
 200                 }
 201                 a->sorted[last_ndx] = ARRAY_NOT_FOUND;
 202                 --a->used;
 203
 204                 return entry;
 205         }
 206
 207         return NULL;
 208 }
 209
 210 static data_unset *array_get_unused_element(array *a, data_type_t t) {
 211         data_unset *ds = NULL;
 212         unsigned int i;
 213
 214         for (i = a->used; i < a->size; i++) {
 215                 if (a->data[i] && a->data[i]->type == t) {
 216                         ds = a->data[i];
 217
 218                         /* make empty slot at a->used for next insert */
 219                         a->data[i] = a->data[a->used];
 220                         a->data[a->used] = NULL;
 221
 222                         return ds;
 223                 }
 224         }
 225
 226         return NULL;
 227 }
 228
 229 void array_set_key_value(array *hdrs, const char *key, size_t key_len, const char *value, size_t val_len) {
 230         data_string *ds;
 231
 232         if (NULL != (ds = (data_string *)array_get_element_klen(hdrs, key, key_len))) {
 233                 buffer_copy_string_len(ds->value, value, val_len);
 234                 return;
 235         }
 236
 237         array_insert_key_value(hdrs, key, key_len, value, val_len);
 238 }
 239
 240 void array_insert_key_value(array *hdrs, const char *key, size_t key_len, const char *value, size_t val_len) {
 241         data_string *ds;
 242
 243         if (NULL == (ds = (data_string *)array_get_unused_element(hdrs, TYPE_STRING))) {
 244                 ds = data_string_init();
 245         }
 246
 247         buffer_copy_string_len(ds->key, key, key_len);
 248         buffer_copy_string_len(ds->value, value, val_len);
 249         array_insert_unique(hdrs, (data_unset *)ds);
 250 }
 251
 252 void array_insert_value(array *hdrs, const char *value, size_t val_len) {
 253         data_string *ds;
 254
 255         if (NULL == (ds = (data_string *)array_get_unused_element(hdrs, TYPE_STRING))) {
 256                 ds = data_string_init();
 257         }
 258
 259         buffer_copy_string_len(ds->value, value, val_len);
 260         array_insert_unique(hdrs, (data_unset *)ds);
 261 }
 262
 263 int * array_get_int_ptr(array *a, const char *k, size_t klen) {
 264         data_integer *di = (data_integer *)array_get_element_klen(a, k, klen);
 265
 266         if (NULL == di) {
 267                 di = (data_integer *)array_get_unused_element(a, TYPE_INTEGER);
 268                 if (NULL == di) di = data_integer_init();
 269                 buffer_copy_string_len(di->key, k, klen);
 270                 array_insert_unique(a, (data_unset *)di);
 271         }
 272
 273         return &di->value;
 274 }
 275
 276 /* if entry already exists return pointer to existing entry, otherwise insert entry and return NULL */
 277 static data_unset **array_find_or_insert(array *a, data_unset *entry) {
 278         size_t ndx, pos, j;
 279
 280         /* generate unique index if neccesary */
 281         if (buffer_is_empty(entry->key) || entry->is_index_key) {
 282                 buffer_copy_int(entry->key, a->unique_ndx++);
 283                 entry->is_index_key = 1;
 284                 force_assert(0 != a->unique_ndx); /* must not wrap or we'll get problems */
 285         }
 286
 287         /* try to find the entry */
 288         if (ARRAY_NOT_FOUND != (ndx = array_get_index(a, CONST_BUF_LEN(entry->key), &pos))) {
 289                 /* found collision, return it */
 290                 return &a->data[ndx];
 291         }
 292
 293         /* insert */
 294
 295         /* there couldn't possibly be enough memory to store so many entries */
 296         force_assert(a->used + 1 <= SSIZE_MAX);
 297
 298         if (a->size == a->used) {
 299                 a->size  += 16;
 300                 a->data   = realloc(a->data,   sizeof(*a->data)   * a->size);
 301                 a->sorted = realloc(a->sorted, sizeof(*a->sorted) * a->size);
 302                 force_assert(a->data);
 303                 force_assert(a->sorted);
 304                 for (j = a->used; j < a->size; j++) a->data[j] = NULL;
 305         }
 306
 307         ndx = a->used;
 308
 309         /* make sure there is nothing here */
 310         if (a->data[ndx]) a->data[ndx]->fn->free(a->data[ndx]);
 311
 312         a->data[a->used++] = entry;
 313
 314         /* move everything one step to the right */
 315         if (pos != ndx) {
 316                 memmove(a->sorted + (pos + 1), a->sorted + (pos), (ndx - pos) * sizeof(*a->sorted));
 317         }
 318
 319         /* insert */
 320         a->sorted[pos] = ndx;
 321
 322         return NULL;
 323 }
 324
 325 /* replace or insert data (free existing entry) */
 326 void array_replace(array *a, data_unset *entry) {
 327         data_unset **old;
 328
 329         force_assert(NULL != entry);
 330         if (NULL != (old = array_find_or_insert(a, entry))) {
 331                 force_assert(*old != entry);
 332                 (*old)->fn->free(*old);
 333                 *old = entry;
 334         }
 335 }
 336
 337 void array_insert_unique(array *a, data_unset *entry) {
 338         data_unset **old;
 339
 340         force_assert(NULL != entry);
 341         if (NULL != (old = array_find_or_insert(a, entry))) {
 342                 force_assert((*old)->type == entry->type);
 343                 entry->fn->insert_dup(*old, entry);
 344         }
 345 }
 346
 347 int array_is_vlist(array *a) {
 348         for (size_t i = 0; i < a->used; ++i) {
 349                 data_unset *du = a->data[i];
 350                 if (!du->is_index_key || du->type != TYPE_STRING) return 0;
 351         }
 352         return 1;
 353 }
 354
 355 int array_is_kvany(array *a) {
 356         for (size_t i = 0; i < a->used; ++i) {
 357                 data_unset *du = a->data[i];
 358                 if (du->is_index_key) return 0;
 359         }
 360         return 1;
 361 }
 362
 363 int array_is_kvarray(array *a) {
 364         for (size_t i = 0; i < a->used; ++i) {
 365                 data_unset *du = a->data[i];
 366                 if (du->is_index_key || du->type != TYPE_ARRAY) return 0;
 367         }
 368         return 1;
 369 }
 370
 371 int array_is_kvstring(array *a) {
 372         for (size_t i = 0; i < a->used; ++i) {
 373                 data_unset *du = a->data[i];
 374                 if (du->is_index_key || du->type != TYPE_STRING) return 0;
 375         }
 376         return 1;
 377 }
 378
 379 /* array_match_*() routines follow very similar pattern, but operate on slightly
 380  * different data: array key/value, prefix/suffix match, case-insensitive or not
 381  * While these could be combined into fewer routines with flags to modify the
 382  * behavior, the interface distinctions are useful to add clarity to the code,
 383  * and the specialized routines run slightly faster */
 384
 385 data_unset *
 386 array_match_key_prefix_klen (const array * const a, const char * const s, const size_t slen)
 387 {
 388     for (size_t i = 0; i < a->used; ++i) {
 389         const buffer * const key = a->data[i]->key;
 390         const size_t klen = buffer_string_length(key);
 391         if (klen <= slen && 0 == memcmp(s, key->ptr, klen))
 392             return a->data[i];
 393     }
 394     return NULL;
 395 }
 396
 397 data_unset *
 398 array_match_key_prefix_nc_klen (const array * const a, const char * const s, const size_t slen)
 399 {
 400     for (size_t i = 0; i < a->used; ++i) {
 401         const buffer * const key = a->data[i]->key;
 402         const size_t klen = buffer_string_length(key);
 403         if (klen <= slen && buffer_eq_icase_ssn(s, key->ptr, klen))
 404             return a->data[i];
 405     }
 406     return NULL;
 407 }
 408
 409 data_unset *
 410 array_match_key_prefix (const array * const a, const buffer * const b)
 411 {
 412     return array_match_key_prefix_klen(a, CONST_BUF_LEN(b));
 413 }
 414
 415 data_unset *
 416 array_match_key_prefix_nc (const array * const a, const buffer * const b)
 417 {
 418     return array_match_key_prefix_nc_klen(a, CONST_BUF_LEN(b));
 419 }
 420
 421 const buffer *
 422 array_match_value_prefix (const array * const a, const buffer * const b)
 423 {
 424     const size_t blen = buffer_string_length(b);
 425
 426     for (size_t i = 0; i < a->used; ++i) {
 427         const buffer * const value = ((data_string *)a->data[i])->value;
 428         const size_t vlen = buffer_string_length(value);
 429         if (vlen <= blen && 0 == memcmp(b->ptr, value->ptr, vlen))
 430             return value;
 431     }
 432     return NULL;
 433 }
 434
 435 const buffer *
 436 array_match_value_prefix_nc (const array * const a, const buffer * const b)
 437 {
 438     const size_t blen = buffer_string_length(b);
 439
 440     for (size_t i = 0; i < a->used; ++i) {
 441         const buffer * const value = ((data_string *)a->data[i])->value;
 442         const size_t vlen = buffer_string_length(value);
 443         if (vlen <= blen && buffer_eq_icase_ssn(b->ptr, value->ptr, vlen))
 444             return value;
 445     }
 446     return NULL;
 447 }
 448
 449 data_unset *
 450 array_match_key_suffix (const array * const a, const buffer * const b)
 451 {
 452     const size_t blen = buffer_string_length(b);
 453     const char * const end = b->ptr + blen;
 454
 455     for (size_t i = 0; i < a->used; ++i) {
 456         const buffer * const key = a->data[i]->key;
 457         const size_t klen = buffer_string_length(key);
 458         if (klen <= blen && 0 == memcmp(end - klen, key->ptr, klen))
 459             return a->data[i];
 460     }
 461     return NULL;
 462 }
 463
 464 data_unset *
 465 array_match_key_suffix_nc (const array * const a, const buffer * const b)
 466 {
 467     const size_t blen = buffer_string_length(b);
 468     const char * const end = b->ptr + blen;
 469
 470     for (size_t i = 0; i < a->used; ++i) {
 471         const buffer * const key = a->data[i]->key;
 472         const size_t klen = buffer_string_length(key);
 473         if (klen <= blen && buffer_eq_icase_ssn(end - klen, key->ptr, klen))
 474             return a->data[i];
 475     }
 476     return NULL;
 477 }
 478
 479 const buffer *
 480 array_match_value_suffix (const array * const a, const buffer * const b)
 481 {
 482     const size_t blen = buffer_string_length(b);
 483     const char * const end = b->ptr + blen;
 484
 485     for (size_t i = 0; i < a->used; ++i) {
 486         const buffer * const value = ((data_string *)a->data[i])->value;
 487         const size_t vlen = buffer_string_length(value);
 488         if (vlen <= blen && 0 == memcmp(end - vlen, value->ptr, vlen))
 489             return value;
 490     }
 491     return NULL;
 492 }
 493
 494 const buffer *
 495 array_match_value_suffix_nc (const array * const a, const buffer * const b)
 496 {
 497     const size_t blen = buffer_string_length(b);
 498     const char * const end = b->ptr + blen;
 499
 500     for (size_t i = 0; i < a->used; ++i) {
 501         const buffer * const value = ((data_string *)a->data[i])->value;
 502         const size_t vlen = buffer_string_length(value);
 503         if (vlen <= blen && buffer_eq_icase_ssn(end - vlen, value->ptr, vlen))
 504             return value;
 505     }
 506     return NULL;
 507 }
 508
 509 data_unset *
 510 array_match_path_or_ext (const array * const a, const buffer * const b)
 511 {
 512     const size_t blen = buffer_string_length(b);
 513
 514     for (size_t i = 0; i < a->used; ++i) {
 515         /* check extension in the form "^/path" or ".ext$" */
 516         const buffer * const key = a->data[i]->key;
 517         const size_t klen = buffer_string_length(key);
 518         if (klen <= blen
 519             && 0 == memcmp((*(key->ptr) == '/' ? b->ptr : b->ptr + blen - klen),
 520                            key->ptr, klen))
 521             return a->data[i];
 522     }
 523     return NULL;
 524 }
 525
 526
 527
 528
 529
 530 #include <stdio.h>
 531
 532 void array_print_indent(int depth) {
 533         int i;
 534         for (i = 0; i < depth; i ++) {
 535                 fprintf(stdout, "    ");
 536         }
 537 }
 538
 539 size_t array_get_max_key_length(array *a) {
 540         size_t maxlen, i;
 541
 542         maxlen = 0;
 543         for (i = 0; i < a->used; i ++) {
 544                 data_unset *du = a->data[i];
 545                 size_t len = buffer_string_length(du->key);
 546
 547                 if (len > maxlen) {
 548                         maxlen = len;
 549                 }
 550         }
 551         return maxlen;
 552 }
 553
 554 int array_print(array *a, int depth) {
 555         size_t i;
 556         size_t maxlen;
 557         int oneline = 1;
 558
 559         if (a->used > 5) {
 560                 oneline = 0;
 561         }
 562         for (i = 0; i < a->used && oneline; i++) {
 563                 data_unset *du = a->data[i];
 564                 if (!du->is_index_key) {
 565                         oneline = 0;
 566                         break;
 567                 }
 568                 switch (du->type) {
 569                         case TYPE_INTEGER:
 570                         case TYPE_STRING:
 571                                 break;
 572                         default:
 573                                 oneline = 0;
 574                                 break;
 575                 }
 576         }
 577         if (oneline) {
 578                 fprintf(stdout, "(");
 579                 for (i = 0; i < a->used; i++) {
 580                         data_unset *du = a->data[i];
 581                         if (i != 0) {
 582                                 fprintf(stdout, ", ");
 583                         }
 584                         du->fn->print(du, depth + 1);
 585                 }
 586                 fprintf(stdout, ")");
 587                 return 0;
 588         }
 589
 590         maxlen = array_get_max_key_length(a);
 591         fprintf(stdout, "(\n");
 592         for (i = 0; i < a->used; i++) {
 593                 data_unset *du = a->data[i];
 594                 array_print_indent(depth + 1);
 595                 if (!du->is_index_key) {
 596                         int j;
 597
 598                         if (i && (i % 5) == 0) {
 599                                 fprintf(stdout, "# %zu\n", i);
 600                                 array_print_indent(depth + 1);
 601                         }
 602                         fprintf(stdout, "\"%s\"", du->key->ptr);
 603                         for (j = maxlen - buffer_string_length(du->key); j > 0; j--) {
 604                                 fprintf(stdout, " ");
 605                         }
 606                         fprintf(stdout, " => ");
 607                 }
 608                 du->fn->print(du, depth + 1);
 609                 fprintf(stdout, ",\n");
 610         }
 611         if (!(i && (i - 1 % 5) == 0)) {
 612                 array_print_indent(depth + 1);
 613                 fprintf(stdout, "# %zu\n", i);
 614         }
 615         array_print_indent(depth);
 616         fprintf(stdout, ")");
 617
 618         return 0;
 619 }