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