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 } 602