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