src/array.c

   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