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(array *a, const char *key) { 124 size_t ndx; 125 force_assert(NULL != key); 126 127 if (ARRAY_NOT_FOUND != (ndx = array_get_index(a, key, strlen(key), NULL))) { 128 /* found, return it */ 129 return a->data[ndx]; 130 } 131 132 return NULL; 133 } 134 135 data_unset *array_extract_element(array *a, const char *key) { 136 size_t ndx, pos; 137 force_assert(NULL != key); 138 139 if (ARRAY_NOT_FOUND != (ndx = array_get_index(a, key, strlen(key), &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(hdrs, key))) { 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 void array_print_indent(int depth) { 289 int i; 290 for (i = 0; i < depth; i ++) { 291 fprintf(stdout, " "); 292 } 293 } 294 295 size_t array_get_max_key_length(array *a) { 296 size_t maxlen, i; 297 298 maxlen = 0; 299 for (i = 0; i < a->used; i ++) { 300 data_unset *du = a->data[i]; 301 size_t len = strlen(du->key->ptr); 302 303 if (len > maxlen) { 304 maxlen = len; 305 } 306 } 307 return maxlen; 308 } 309 310 int array_print(array *a, int depth) { 311 size_t i; 312 size_t maxlen; 313 int oneline = 1; 314 315 if (a->used > 5) { 316 oneline = 0; 317 } 318 for (i = 0; i < a->used && oneline; i++) { 319 data_unset *du = a->data[i]; 320 if (!du->is_index_key) { 321 oneline = 0; 322 break; 323 } 324 switch (du->type) { 325 case TYPE_INTEGER: 326 case TYPE_STRING: 327 case TYPE_COUNT: 328 break; 329 default: 330 oneline = 0; 331 break; 332 } 333 } 334 if (oneline) { 335 fprintf(stdout, "("); 336 for (i = 0; i < a->used; i++) { 337 data_unset *du = a->data[i]; 338 if (i != 0) { 339 fprintf(stdout, ", "); 340 } 341 du->print(du, depth + 1); 342 } 343 fprintf(stdout, ")"); 344 return 0; 345 } 346 347 maxlen = array_get_max_key_length(a); 348 fprintf(stdout, "(\n"); 349 for (i = 0; i < a->used; i++) { 350 data_unset *du = a->data[i]; 351 array_print_indent(depth + 1); 352 if (!du->is_index_key) { 353 int j; 354 355 if (i && (i % 5) == 0) { 356 fprintf(stdout, "# %zd\n", i); 357 array_print_indent(depth + 1); 358 } 359 fprintf(stdout, "\"%s\"", du->key->ptr); 360 for (j = maxlen - strlen(du->key->ptr); j > 0; j --) { 361 fprintf(stdout, " "); 362 } 363 fprintf(stdout, " => "); 364 } 365 du->print(du, depth + 1); 366 fprintf(stdout, ",\n"); 367 } 368 if (!(i && (i - 1 % 5) == 0)) { 369 array_print_indent(depth + 1); 370 fprintf(stdout, "# %zd\n", i); 371 } 372 array_print_indent(depth); 373 fprintf(stdout, ")"); 374 375 return 0; 376 } 377 378 #ifdef DEBUG_ARRAY 379 int main (int argc, char **argv) { 380 array *a; 381 data_string *ds; 382 data_count *dc; 383 384 UNUSED(argc); 385 UNUSED(argv); 386 387 a = array_init(); 388 389 ds = data_string_init(); 390 buffer_copy_string_len(ds->key, CONST_STR_LEN("abc")); 391 buffer_copy_string_len(ds->value, CONST_STR_LEN("alfrag")); 392 393 array_insert_unique(a, (data_unset *)ds); 394 395 ds = data_string_init(); 396 buffer_copy_string_len(ds->key, CONST_STR_LEN("abc")); 397 buffer_copy_string_len(ds->value, CONST_STR_LEN("hameplman")); 398 399 array_insert_unique(a, (data_unset *)ds); 400 401 ds = data_string_init(); 402 buffer_copy_string_len(ds->key, CONST_STR_LEN("123")); 403 buffer_copy_string_len(ds->value, CONST_STR_LEN("alfrag")); 404 405 array_insert_unique(a, (data_unset *)ds); 406 407 dc = data_count_init(); 408 buffer_copy_string_len(dc->key, CONST_STR_LEN("def")); 409 410 array_insert_unique(a, (data_unset *)dc); 411 412 dc = data_count_init(); 413 buffer_copy_string_len(dc->key, CONST_STR_LEN("def")); 414 415 array_insert_unique(a, (data_unset *)dc); 416 417 array_print(a, 0); 418 419 array_free(a); 420 421 fprintf(stderr, "%d\n", 422 buffer_caseless_compare(CONST_STR_LEN("Content-Type"), CONST_STR_LEN("Content-type"))); 423 424 return 0; 425 } 426 #endif 427