1 #include "array.h" 2 #include "buffer.h" 3 4 #include <string.h> 5 #include <stdio.h> 6 #include <stdlib.h> 7 #include <limits.h> 8 9 #include <errno.h> 10 #include <assert.h> 11 12 array *array_init(void) { 13 array *a; 14 15 a = calloc(1, sizeof(*a)); 16 force_assert(a); 17 18 a->next_power_of_2 = 1; 19 20 return a; 21 } 22 23 array *array_init_array(array *src) { 24 size_t i; 25 array *a = array_init(); 26 27 if (0 == src->size) return a; 28 29 a->used = src->used; 30 a->size = src->size; 31 a->next_power_of_2 = src->next_power_of_2; 32 a->unique_ndx = src->unique_ndx; 33 34 a->data = malloc(sizeof(*src->data) * src->size); 35 for (i = 0; i < src->size; i++) { 36 if (src->data[i]) a->data[i] = src->data[i]->copy(src->data[i]); 37 else a->data[i] = NULL; 38 } 39 40 a->sorted = malloc(sizeof(*src->sorted) * src->size); 41 memcpy(a->sorted, src->sorted, sizeof(*src->sorted) * src->size); 42 return a; 43 } 44 45 void array_free(array *a) { 46 size_t i; 47 if (!a) return; 48 49 if (!a->is_weakref) { 50 for (i = 0; i < a->size; i++) { 51 if (a->data[i]) a->data[i]->free(a->data[i]); 52 } 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 if (!a->is_weakref) { 66 for (i = 0; i < a->used; i++) { 67 a->data[i]->reset(a->data[i]); 68 } 69 } 70 71 a->used = 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 a->data[a->used] = NULL; 82 83 return du; 84 } 85 86 static int array_get_index(array *a, const char *key, size_t keylen, int *rndx) { 87 int ndx = -1; 88 int i, pos = 0; 89 90 if (key == NULL) return -1; 91 92 /* try to find the string */ 93 for (i = pos = a->next_power_of_2 / 2; ; i >>= 1) { 94 int cmp; 95 96 if (pos < 0) { 97 pos += i; 98 } else if (pos >= (int)a->used) { 99 pos -= i; 100 } else { 101 cmp = buffer_caseless_compare(key, keylen, CONST_BUF_LEN(a->data[a->sorted[pos]]->key)); 102 103 if (cmp == 0) { 104 /* found */ 105 ndx = a->sorted[pos]; 106 break; 107 } else if (cmp < 0) { 108 pos -= i; 109 } else { 110 pos += i; 111 } 112 } 113 if (i == 0) break; 114 } 115 116 if (rndx) *rndx = pos; 117 118 return ndx; 119 } 120 121 data_unset *array_get_element(array *a, const char *key) { 122 int ndx; 123 124 if (-1 != (ndx = array_get_index(a, key, strlen(key), NULL))) { 125 /* found, leave here */ 126 127 return a->data[ndx]; 128 } 129 130 return NULL; 131 } 132 133 data_unset *array_get_unused_element(array *a, data_type_t t) { 134 data_unset *ds = NULL; 135 unsigned int i; 136 137 for (i = a->used; i < a->size; i++) { 138 if (a->data[i] && a->data[i]->type == t) { 139 ds = a->data[i]; 140 141 /* make empty slot at a->used for next insert */ 142 a->data[i] = a->data[a->used]; 143 a->data[a->used] = NULL; 144 145 return ds; 146 } 147 } 148 149 return NULL; 150 } 151 152 void array_set_key_value(array *hdrs, const char *key, size_t key_len, const char *value, size_t val_len) { 153 data_string *ds_dst; 154 155 if (NULL != (ds_dst = (data_string *)array_get_element(hdrs, key))) { 156 buffer_copy_string_len(ds_dst->value, value, val_len); 157 return; 158 } 159 160 if (NULL == (ds_dst = (data_string *)array_get_unused_element(hdrs, TYPE_STRING))) { 161 ds_dst = data_string_init(); 162 } 163 164 buffer_copy_string_len(ds_dst->key, key, key_len); 165 buffer_copy_string_len(ds_dst->value, value, val_len); 166 array_insert_unique(hdrs, (data_unset *)ds_dst); 167 } 168 169 /* replace or insert data, return the old one with the same key */ 170 data_unset *array_replace(array *a, data_unset *du) { 171 int ndx; 172 173 force_assert(NULL != du); 174 if (-1 == (ndx = array_get_index(a, CONST_BUF_LEN(du->key), NULL))) { 175 array_insert_unique(a, du); 176 return NULL; 177 } else { 178 data_unset *old = a->data[ndx]; 179 a->data[ndx] = du; 180 return old; 181 } 182 } 183 184 int array_insert_unique(array *a, data_unset *str) { 185 int ndx = -1; 186 int pos = 0; 187 size_t j; 188 189 /* generate unique index if neccesary */ 190 if (buffer_is_empty(str->key) || str->is_index_key) { 191 buffer_copy_int(str->key, a->unique_ndx++); 192 str->is_index_key = 1; 193 } 194 195 /* try to find the string */ 196 if (-1 != (ndx = array_get_index(a, CONST_BUF_LEN(str->key), &pos))) { 197 /* found, leave here */ 198 if (a->data[ndx]->type == str->type) { 199 str->insert_dup(a->data[ndx], str); 200 } else { 201 SEGFAULT(); 202 } 203 return 0; 204 } 205 206 /* insert */ 207 208 if (a->used+1 > INT_MAX) { 209 /* we can't handle more then INT_MAX entries: see array_get_index() */ 210 return -1; 211 } 212 213 if (a->size == 0) { 214 a->size = 16; 215 a->data = malloc(sizeof(*a->data) * a->size); 216 a->sorted = malloc(sizeof(*a->sorted) * a->size); 217 force_assert(a->data); 218 force_assert(a->sorted); 219 for (j = a->used; j < a->size; j++) a->data[j] = NULL; 220 } else if (a->size == a->used) { 221 a->size += 16; 222 a->data = realloc(a->data, sizeof(*a->data) * a->size); 223 a->sorted = realloc(a->sorted, sizeof(*a->sorted) * a->size); 224 force_assert(a->data); 225 force_assert(a->sorted); 226 for (j = a->used; j < a->size; j++) a->data[j] = NULL; 227 } 228 229 ndx = (int) a->used; 230 231 /* make sure there is nothing here */ 232 if (a->data[ndx]) a->data[ndx]->free(a->data[ndx]); 233 234 a->data[a->used++] = str; 235 236 if (pos != ndx && 237 ((pos < 0) || 238 buffer_caseless_compare(CONST_BUF_LEN(str->key), CONST_BUF_LEN(a->data[a->sorted[pos]]->key)) > 0)) { 239 pos++; 240 } 241 242 /* move everything on step to the right */ 243 if (pos != ndx) { 244 memmove(a->sorted + (pos + 1), a->sorted + (pos), (ndx - pos) * sizeof(*a->sorted)); 245 } 246 247 /* insert */ 248 a->sorted[pos] = ndx; 249 250 if (a->next_power_of_2 == (size_t)ndx) a->next_power_of_2 <<= 1; 251 252 return 0; 253 } 254 255 void array_print_indent(int depth) { 256 int i; 257 for (i = 0; i < depth; i ++) { 258 fprintf(stdout, " "); 259 } 260 } 261 262 size_t array_get_max_key_length(array *a) { 263 size_t maxlen, i; 264 265 maxlen = 0; 266 for (i = 0; i < a->used; i ++) { 267 data_unset *du = a->data[i]; 268 size_t len = strlen(du->key->ptr); 269 270 if (len > maxlen) { 271 maxlen = len; 272 } 273 } 274 return maxlen; 275 } 276 277 int array_print(array *a, int depth) { 278 size_t i; 279 size_t maxlen; 280 int oneline = 1; 281 282 if (a->used > 5) { 283 oneline = 0; 284 } 285 for (i = 0; i < a->used && oneline; i++) { 286 data_unset *du = a->data[i]; 287 if (!du->is_index_key) { 288 oneline = 0; 289 break; 290 } 291 switch (du->type) { 292 case TYPE_INTEGER: 293 case TYPE_STRING: 294 case TYPE_COUNT: 295 break; 296 default: 297 oneline = 0; 298 break; 299 } 300 } 301 if (oneline) { 302 fprintf(stdout, "("); 303 for (i = 0; i < a->used; i++) { 304 data_unset *du = a->data[i]; 305 if (i != 0) { 306 fprintf(stdout, ", "); 307 } 308 du->print(du, depth + 1); 309 } 310 fprintf(stdout, ")"); 311 return 0; 312 } 313 314 maxlen = array_get_max_key_length(a); 315 fprintf(stdout, "(\n"); 316 for (i = 0; i < a->used; i++) { 317 data_unset *du = a->data[i]; 318 array_print_indent(depth + 1); 319 if (!du->is_index_key) { 320 int j; 321 322 if (i && (i % 5) == 0) { 323 fprintf(stdout, "# %zd\n", i); 324 array_print_indent(depth + 1); 325 } 326 fprintf(stdout, "\"%s\"", du->key->ptr); 327 for (j = maxlen - strlen(du->key->ptr); j > 0; j --) { 328 fprintf(stdout, " "); 329 } 330 fprintf(stdout, " => "); 331 } 332 du->print(du, depth + 1); 333 fprintf(stdout, ",\n"); 334 } 335 if (!(i && (i - 1 % 5) == 0)) { 336 array_print_indent(depth + 1); 337 fprintf(stdout, "# %zd\n", i); 338 } 339 array_print_indent(depth); 340 fprintf(stdout, ")"); 341 342 return 0; 343 } 344 345 #ifdef DEBUG_ARRAY 346 int main (int argc, char **argv) { 347 array *a; 348 data_string *ds; 349 data_count *dc; 350 351 UNUSED(argc); 352 UNUSED(argv); 353 354 a = array_init(); 355 356 ds = data_string_init(); 357 buffer_copy_string_len(ds->key, CONST_STR_LEN("abc")); 358 buffer_copy_string_len(ds->value, CONST_STR_LEN("alfrag")); 359 360 array_insert_unique(a, (data_unset *)ds); 361 362 ds = data_string_init(); 363 buffer_copy_string_len(ds->key, CONST_STR_LEN("abc")); 364 buffer_copy_string_len(ds->value, CONST_STR_LEN("hameplman")); 365 366 array_insert_unique(a, (data_unset *)ds); 367 368 ds = data_string_init(); 369 buffer_copy_string_len(ds->key, CONST_STR_LEN("123")); 370 buffer_copy_string_len(ds->value, CONST_STR_LEN("alfrag")); 371 372 array_insert_unique(a, (data_unset *)ds); 373 374 dc = data_count_init(); 375 buffer_copy_string_len(dc->key, CONST_STR_LEN("def")); 376 377 array_insert_unique(a, (data_unset *)dc); 378 379 dc = data_count_init(); 380 buffer_copy_string_len(dc->key, CONST_STR_LEN("def")); 381 382 array_insert_unique(a, (data_unset *)dc); 383 384 array_print(a, 0); 385 386 array_free(a); 387 388 fprintf(stderr, "%d\n", 389 buffer_caseless_compare(CONST_STR_LEN("Content-Type"), CONST_STR_LEN("Content-type"))); 390 391 return 0; 392 } 393 #endif 394