1 #include "first.h" 2 3 #include "array.h" 4 #include "buffer.h" 5 6 #include <string.h> 7 #include <stdio.h> 8 #include <stdlib.h> 9 #include <limits.h> 10 11 #include <errno.h> 12 #include <assert.h> 13 14 #define ARRAY_NOT_FOUND ((size_t)(-1)) 15 16 array *array_init(void) { 17 array *a; 18 19 a = calloc(1, sizeof(*a)); 20 force_assert(a); 21 22 return a; 23 } 24 25 array *array_init_array(array *src) { 26 size_t i; 27 array *a = array_init(); 28 29 if (0 == src->size) return a; 30 31 a->used = src->used; 32 a->size = src->size; 33 a->unique_ndx = src->unique_ndx; 34 35 a->data = malloc(sizeof(*src->data) * src->size); 36 force_assert(NULL != a->data); 37 for (i = 0; i < src->size; i++) { 38 if (src->data[i]) a->data[i] = src->data[i]->copy(src->data[i]); 39 else a->data[i] = NULL; 40 } 41 42 a->sorted = malloc(sizeof(*src->sorted) * src->size); 43 force_assert(NULL != a->sorted); 44 memcpy(a->sorted, src->sorted, sizeof(*src->sorted) * src->size); 45 return a; 46 } 47 48 void array_free(array *a) { 49 size_t i; 50 if (!a) return; 51 52 for (i = 0; i < a->size; i++) { 53 if (a->data[i]) a->data[i]->free(a->data[i]); 54 } 55 56 if (a->data) free(a->data); 57 if (a->sorted) free(a->sorted); 58 59 free(a); 60 } 61 62 void array_reset(array *a) { 63 size_t i; 64 if (!a) return; 65 66 for (i = 0; i < a->used; i++) { 67 a->data[i]->reset(a->data[i]); 68 } 69 70 a->used = 0; 71 a->unique_ndx = 0; 72 } 73 74 data_unset *array_pop(array *a) { 75 data_unset *du; 76 77 force_assert(a->used != 0); 78 79 a->used --; 80 du = a->data[a->used]; 81 force_assert(a->sorted[a->used] == a->used); /* only works on "simple" lists */ 82 a->data[a->used] = NULL; 83 84 return du; 85 } 86 87 /* returns index of element or ARRAY_NOT_FOUND 88 * if rndx != NULL it stores the position in a->sorted[] where the key needs 89 * to be inserted 90 */ 91 static size_t array_get_index(array *a, const char *key, size_t keylen, size_t *rndx) { 92 /* invariant: [lower-1] < key < [upper] 93 * "virtual elements": [-1] = -INFTY, [a->used] = +INFTY 94 * also an invariant: 0 <= lower <= upper <= a->used 95 */ 96 size_t lower = 0, upper = a->used; 97 force_assert(upper <= SSIZE_MAX); /* (lower + upper) can't overflow */ 98 99 while (lower != upper) { 100 size_t probe = (lower + upper) / 2; 101 int cmp = buffer_caseless_compare(key, keylen, CONST_BUF_LEN(a->data[a->sorted[probe]]->key)); 102 assert(lower < upper); /* from loop invariant (lower <= upper) + (lower != upper) */ 103 assert((lower <= probe) && (probe < upper)); /* follows from lower < upper */ 104 105 if (cmp == 0) { 106 /* found */ 107 if (rndx) *rndx = probe; 108 return a->sorted[probe]; 109 } else if (cmp < 0) { 110 /* key < [probe] */ 111 upper = probe; /* still: lower <= upper */ 112 } else { 113 /* key > [probe] */ 114 lower = probe + 1; /* still: lower <= upper */ 115 } 116 } 117 118 /* not found: [lower-1] < key < [upper] = [lower] ==> insert at [lower] */ 119 if (rndx) *rndx = lower; 120 return ARRAY_NOT_FOUND; 121 } 122 123 data_unset *array_get_element_klen(array *a, const char *key, size_t klen) { 124 size_t ndx; 125 force_assert(NULL != key); 126 127 if (ARRAY_NOT_FOUND != (ndx = array_get_index(a, key, klen, NULL))) { 128 /* found, return it */ 129 return a->data[ndx]; 130 } 131 132 return NULL; 133 } 134 135 data_unset *array_extract_element_klen(array *a, const char *key, size_t klen) { 136 size_t ndx, pos; 137 force_assert(NULL != key); 138 139 if (ARRAY_NOT_FOUND != (ndx = array_get_index(a, key, klen, &pos))) { 140 /* found */ 141 const size_t last_ndx = a->used - 1; 142 data_unset *entry = a->data[ndx]; 143 144 /* now we need to swap it with the last element (if it isn't already the last element) */ 145 if (ndx != last_ndx) { 146 /* to swap we also need to modify the index in a->sorted - find pos of last_elem there */ 147 size_t last_elem_pos; 148 /* last element must be present at the expected position */ 149 force_assert(last_ndx == array_get_index(a, CONST_BUF_LEN(a->data[last_ndx]->key), &last_elem_pos)); 150 151 /* move entry from last_ndx to ndx */ 152 a->data[ndx] = a->data[last_ndx]; 153 a->data[last_ndx] = NULL; 154 155 /* fix index entry for moved entry */ 156 a->sorted[last_elem_pos] = ndx; 157 } else { 158 a->data[ndx] = NULL; 159 } 160 161 /* remove entry in a->sorted: move everything after pos one step to the left */ 162 if (pos != last_ndx) { 163 memmove(a->sorted + pos, a->sorted + pos + 1, (last_ndx - pos) * sizeof(*a->sorted)); 164 } 165 a->sorted[last_ndx] = ARRAY_NOT_FOUND; 166 --a->used; 167 168 return entry; 169 } 170 171 return NULL; 172 } 173 174 data_unset *array_get_unused_element(array *a, data_type_t t) { 175 data_unset *ds = NULL; 176 unsigned int i; 177 178 for (i = a->used; i < a->size; i++) { 179 if (a->data[i] && a->data[i]->type == t) { 180 ds = a->data[i]; 181 182 /* make empty slot at a->used for next insert */ 183 a->data[i] = a->data[a->used]; 184 a->data[a->used] = NULL; 185 186 return ds; 187 } 188 } 189 190 return NULL; 191 } 192 193 void array_set_key_value(array *hdrs, const char *key, size_t key_len, const char *value, size_t val_len) { 194 data_string *ds_dst; 195 196 if (NULL != (ds_dst = (data_string *)array_get_element_klen(hdrs, key, key_len))) { 197 buffer_copy_string_len(ds_dst->value, value, val_len); 198 return; 199 } 200 201 if (NULL == (ds_dst = (data_string *)array_get_unused_element(hdrs, TYPE_STRING))) { 202 ds_dst = data_string_init(); 203 } 204 205 buffer_copy_string_len(ds_dst->key, key, key_len); 206 buffer_copy_string_len(ds_dst->value, value, val_len); 207 array_insert_unique(hdrs, (data_unset *)ds_dst); 208 } 209 210 /* if entry already exists return pointer to existing entry, otherwise insert entry and return NULL */ 211 static data_unset **array_find_or_insert(array *a, data_unset *entry) { 212 size_t ndx, pos, j; 213 214 /* generate unique index if neccesary */ 215 if (buffer_is_empty(entry->key) || entry->is_index_key) { 216 buffer_copy_int(entry->key, a->unique_ndx++); 217 entry->is_index_key = 1; 218 force_assert(0 != a->unique_ndx); /* must not wrap or we'll get problems */ 219 } 220 221 /* try to find the entry */ 222 if (ARRAY_NOT_FOUND != (ndx = array_get_index(a, CONST_BUF_LEN(entry->key), &pos))) { 223 /* found collision, return it */ 224 return &a->data[ndx]; 225 } 226 227 /* insert */ 228 229 /* there couldn't possibly be enough memory to store so many entries */ 230 force_assert(a->used + 1 <= SSIZE_MAX); 231 232 if (a->size == 0) { 233 a->size = 16; 234 a->data = malloc(sizeof(*a->data) * a->size); 235 a->sorted = malloc(sizeof(*a->sorted) * a->size); 236 force_assert(a->data); 237 force_assert(a->sorted); 238 for (j = a->used; j < a->size; j++) a->data[j] = NULL; 239 } else if (a->size == a->used) { 240 a->size += 16; 241 a->data = realloc(a->data, sizeof(*a->data) * a->size); 242 a->sorted = realloc(a->sorted, sizeof(*a->sorted) * a->size); 243 force_assert(a->data); 244 force_assert(a->sorted); 245 for (j = a->used; j < a->size; j++) a->data[j] = NULL; 246 } 247 248 ndx = a->used; 249 250 /* make sure there is nothing here */ 251 if (a->data[ndx]) a->data[ndx]->free(a->data[ndx]); 252 253 a->data[a->used++] = entry; 254 255 /* move everything one step to the right */ 256 if (pos != ndx) { 257 memmove(a->sorted + (pos + 1), a->sorted + (pos), (ndx - pos) * sizeof(*a->sorted)); 258 } 259 260 /* insert */ 261 a->sorted[pos] = ndx; 262 263 return NULL; 264 } 265 266 /* replace or insert data (free existing entry) */ 267 void array_replace(array *a, data_unset *entry) { 268 data_unset **old; 269 270 force_assert(NULL != entry); 271 if (NULL != (old = array_find_or_insert(a, entry))) { 272 force_assert(*old != entry); 273 (*old)->free(*old); 274 *old = entry; 275 } 276 } 277 278 void array_insert_unique(array *a, data_unset *entry) { 279 data_unset **old; 280 281 force_assert(NULL != entry); 282 if (NULL != (old = array_find_or_insert(a, entry))) { 283 force_assert((*old)->type == entry->type); 284 entry->insert_dup(*old, entry); 285 } 286 } 287 288 int array_is_vlist(array *a) { 289 for (size_t i = 0; i < a->used; ++i) { 290 data_unset *du = a->data[i]; 291 if (!du->is_index_key || du->type != TYPE_STRING) return 0; 292 } 293 return 1; 294 } 295 296 int array_is_kvany(array *a) { 297 for (size_t i = 0; i < a->used; ++i) { 298 data_unset *du = a->data[i]; 299 if (du->is_index_key) return 0; 300 } 301 return 1; 302 } 303 304 int array_is_kvarray(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_ARRAY) return 0; 308 } 309 return 1; 310 } 311 312 int array_is_kvstring(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 || du->type != TYPE_STRING) return 0; 316 } 317 return 1; 318 } 319 320 void array_print_indent(int depth) { 321 int i; 322 for (i = 0; i < depth; i ++) { 323 fprintf(stdout, " "); 324 } 325 } 326 327 size_t array_get_max_key_length(array *a) { 328 size_t maxlen, i; 329 330 maxlen = 0; 331 for (i = 0; i < a->used; i ++) { 332 data_unset *du = a->data[i]; 333 size_t len = buffer_string_length(du->key); 334 335 if (len > maxlen) { 336 maxlen = len; 337 } 338 } 339 return maxlen; 340 } 341 342 int array_print(array *a, int depth) { 343 size_t i; 344 size_t maxlen; 345 int oneline = 1; 346 347 if (a->used > 5) { 348 oneline = 0; 349 } 350 for (i = 0; i < a->used && oneline; i++) { 351 data_unset *du = a->data[i]; 352 if (!du->is_index_key) { 353 oneline = 0; 354 break; 355 } 356 switch (du->type) { 357 case TYPE_INTEGER: 358 case TYPE_STRING: 359 break; 360 default: 361 oneline = 0; 362 break; 363 } 364 } 365 if (oneline) { 366 fprintf(stdout, "("); 367 for (i = 0; i < a->used; i++) { 368 data_unset *du = a->data[i]; 369 if (i != 0) { 370 fprintf(stdout, ", "); 371 } 372 du->print(du, depth + 1); 373 } 374 fprintf(stdout, ")"); 375 return 0; 376 } 377 378 maxlen = array_get_max_key_length(a); 379 fprintf(stdout, "(\n"); 380 for (i = 0; i < a->used; i++) { 381 data_unset *du = a->data[i]; 382 array_print_indent(depth + 1); 383 if (!du->is_index_key) { 384 int j; 385 386 if (i && (i % 5) == 0) { 387 fprintf(stdout, "# %zu\n", i); 388 array_print_indent(depth + 1); 389 } 390 fprintf(stdout, "\"%s\"", du->key->ptr); 391 for (j = maxlen - buffer_string_length(du->key); j > 0; j--) { 392 fprintf(stdout, " "); 393 } 394 fprintf(stdout, " => "); 395 } 396 du->print(du, depth + 1); 397 fprintf(stdout, ",\n"); 398 } 399 if (!(i && (i - 1 % 5) == 0)) { 400 array_print_indent(depth + 1); 401 fprintf(stdout, "# %zu\n", i); 402 } 403 array_print_indent(depth); 404 fprintf(stdout, ")"); 405 406 return 0; 407 } 408 409 #ifdef DEBUG_ARRAY 410 int main (int argc, char **argv) { 411 array *a; 412 data_string *ds; 413 414 UNUSED(argc); 415 UNUSED(argv); 416 417 a = array_init(); 418 419 ds = data_string_init(); 420 buffer_copy_string_len(ds->key, CONST_STR_LEN("abc")); 421 buffer_copy_string_len(ds->value, CONST_STR_LEN("alfrag")); 422 423 array_insert_unique(a, (data_unset *)ds); 424 425 ds = data_string_init(); 426 buffer_copy_string_len(ds->key, CONST_STR_LEN("abc")); 427 buffer_copy_string_len(ds->value, CONST_STR_LEN("hameplman")); 428 429 array_insert_unique(a, (data_unset *)ds); 430 431 ds = data_string_init(); 432 buffer_copy_string_len(ds->key, CONST_STR_LEN("123")); 433 buffer_copy_string_len(ds->value, CONST_STR_LEN("alfrag")); 434 435 array_insert_unique(a, (data_unset *)ds); 436 437 array_print(a, 0); 438 439 array_free(a); 440 441 fprintf(stderr, "%d\n", 442 buffer_caseless_compare(CONST_STR_LEN("Content-Type"), CONST_STR_LEN("Content-type"))); 443 444 return 0; 445 } 446 #endif 447