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