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