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