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