Annotation of embedaddon/lighttpd/src/array.c, revision 1.1
1.1 ! misho 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: unsigned int i;
! 134:
! 135: for (i = a->used; i < a->size; i++) {
! 136: if (a->data[i] && a->data[i]->type == t) {
! 137: ds = a->data[i];
! 138:
! 139: /* make empty slot at a->used for next insert */
! 140: a->data[i] = a->data[a->used];
! 141: a->data[a->used] = NULL;
! 142:
! 143: return ds;
! 144: }
! 145: }
! 146:
! 147: return NULL;
! 148: }
! 149:
! 150: void array_set_key_value(array *hdrs, const char *key, size_t key_len, const char *value, size_t val_len) {
! 151: data_string *ds_dst;
! 152:
! 153: if (NULL != (ds_dst = (data_string *)array_get_element(hdrs, key))) {
! 154: buffer_copy_string_len(ds_dst->value, value, val_len);
! 155: return;
! 156: }
! 157:
! 158: if (NULL == (ds_dst = (data_string *)array_get_unused_element(hdrs, TYPE_STRING))) {
! 159: ds_dst = data_string_init();
! 160: }
! 161:
! 162: buffer_copy_string_len(ds_dst->key, key, key_len);
! 163: buffer_copy_string_len(ds_dst->value, value, val_len);
! 164: array_insert_unique(hdrs, (data_unset *)ds_dst);
! 165: }
! 166:
! 167: /* replace or insert data, return the old one with the same key */
! 168: data_unset *array_replace(array *a, data_unset *du) {
! 169: int ndx;
! 170:
! 171: if (-1 == (ndx = array_get_index(a, du->key->ptr, du->key->used, NULL))) {
! 172: array_insert_unique(a, du);
! 173: return NULL;
! 174: } else {
! 175: data_unset *old = a->data[ndx];
! 176: a->data[ndx] = du;
! 177: return old;
! 178: }
! 179: }
! 180:
! 181: int array_insert_unique(array *a, data_unset *str) {
! 182: int ndx = -1;
! 183: int pos = 0;
! 184: size_t j;
! 185:
! 186: /* generate unique index if neccesary */
! 187: if (str->key->used == 0 || str->is_index_key) {
! 188: buffer_copy_long(str->key, a->unique_ndx++);
! 189: str->is_index_key = 1;
! 190: }
! 191:
! 192: /* try to find the string */
! 193: if (-1 != (ndx = array_get_index(a, str->key->ptr, str->key->used, &pos))) {
! 194: /* found, leave here */
! 195: if (a->data[ndx]->type == str->type) {
! 196: str->insert_dup(a->data[ndx], str);
! 197: } else {
! 198: SEGFAULT();
! 199: }
! 200: return 0;
! 201: }
! 202:
! 203: /* insert */
! 204:
! 205: if (a->used+1 > INT_MAX) {
! 206: /* we can't handle more then INT_MAX entries: see array_get_index() */
! 207: return -1;
! 208: }
! 209:
! 210: if (a->size == 0) {
! 211: a->size = 16;
! 212: a->data = malloc(sizeof(*a->data) * a->size);
! 213: a->sorted = malloc(sizeof(*a->sorted) * a->size);
! 214: assert(a->data);
! 215: assert(a->sorted);
! 216: for (j = a->used; j < a->size; j++) a->data[j] = NULL;
! 217: } else if (a->size == a->used) {
! 218: a->size += 16;
! 219: a->data = realloc(a->data, sizeof(*a->data) * a->size);
! 220: a->sorted = realloc(a->sorted, sizeof(*a->sorted) * a->size);
! 221: assert(a->data);
! 222: assert(a->sorted);
! 223: for (j = a->used; j < a->size; j++) a->data[j] = NULL;
! 224: }
! 225:
! 226: ndx = (int) a->used;
! 227:
! 228: /* make sure there is nothing here */
! 229: if (a->data[ndx]) a->data[ndx]->free(a->data[ndx]);
! 230:
! 231: a->data[a->used++] = str;
! 232:
! 233: if (pos != ndx &&
! 234: ((pos < 0) ||
! 235: buffer_caseless_compare(str->key->ptr, str->key->used, a->data[a->sorted[pos]]->key->ptr, a->data[a->sorted[pos]]->key->used) > 0)) {
! 236: pos++;
! 237: }
! 238:
! 239: /* move everything on step to the right */
! 240: if (pos != ndx) {
! 241: memmove(a->sorted + (pos + 1), a->sorted + (pos), (ndx - pos) * sizeof(*a->sorted));
! 242: }
! 243:
! 244: /* insert */
! 245: a->sorted[pos] = ndx;
! 246:
! 247: if (a->next_power_of_2 == (size_t)ndx) a->next_power_of_2 <<= 1;
! 248:
! 249: return 0;
! 250: }
! 251:
! 252: void array_print_indent(int depth) {
! 253: int i;
! 254: for (i = 0; i < depth; i ++) {
! 255: fprintf(stdout, " ");
! 256: }
! 257: }
! 258:
! 259: size_t array_get_max_key_length(array *a) {
! 260: size_t maxlen, i;
! 261:
! 262: maxlen = 0;
! 263: for (i = 0; i < a->used; i ++) {
! 264: data_unset *du = a->data[i];
! 265: size_t len = strlen(du->key->ptr);
! 266:
! 267: if (len > maxlen) {
! 268: maxlen = len;
! 269: }
! 270: }
! 271: return maxlen;
! 272: }
! 273:
! 274: int array_print(array *a, int depth) {
! 275: size_t i;
! 276: size_t maxlen;
! 277: int oneline = 1;
! 278:
! 279: if (a->used > 5) {
! 280: oneline = 0;
! 281: }
! 282: for (i = 0; i < a->used && oneline; i++) {
! 283: data_unset *du = a->data[i];
! 284: if (!du->is_index_key) {
! 285: oneline = 0;
! 286: break;
! 287: }
! 288: switch (du->type) {
! 289: case TYPE_INTEGER:
! 290: case TYPE_STRING:
! 291: case TYPE_COUNT:
! 292: break;
! 293: default:
! 294: oneline = 0;
! 295: break;
! 296: }
! 297: }
! 298: if (oneline) {
! 299: fprintf(stdout, "(");
! 300: for (i = 0; i < a->used; i++) {
! 301: data_unset *du = a->data[i];
! 302: if (i != 0) {
! 303: fprintf(stdout, ", ");
! 304: }
! 305: du->print(du, depth + 1);
! 306: }
! 307: fprintf(stdout, ")");
! 308: return 0;
! 309: }
! 310:
! 311: maxlen = array_get_max_key_length(a);
! 312: fprintf(stdout, "(\n");
! 313: for (i = 0; i < a->used; i++) {
! 314: data_unset *du = a->data[i];
! 315: array_print_indent(depth + 1);
! 316: if (!du->is_index_key) {
! 317: int j;
! 318:
! 319: if (i && (i % 5) == 0) {
! 320: fprintf(stdout, "# %zd\n", i);
! 321: array_print_indent(depth + 1);
! 322: }
! 323: fprintf(stdout, "\"%s\"", du->key->ptr);
! 324: for (j = maxlen - strlen(du->key->ptr); j > 0; j --) {
! 325: fprintf(stdout, " ");
! 326: }
! 327: fprintf(stdout, " => ");
! 328: }
! 329: du->print(du, depth + 1);
! 330: fprintf(stdout, ",\n");
! 331: }
! 332: if (!(i && (i - 1 % 5) == 0)) {
! 333: array_print_indent(depth + 1);
! 334: fprintf(stdout, "# %zd\n", i);
! 335: }
! 336: array_print_indent(depth);
! 337: fprintf(stdout, ")");
! 338:
! 339: return 0;
! 340: }
! 341:
! 342: #ifdef DEBUG_ARRAY
! 343: int main (int argc, char **argv) {
! 344: array *a;
! 345: data_string *ds;
! 346: data_count *dc;
! 347:
! 348: UNUSED(argc);
! 349: UNUSED(argv);
! 350:
! 351: a = array_init();
! 352:
! 353: ds = data_string_init();
! 354: buffer_copy_string_len(ds->key, CONST_STR_LEN("abc"));
! 355: buffer_copy_string_len(ds->value, CONST_STR_LEN("alfrag"));
! 356:
! 357: array_insert_unique(a, (data_unset *)ds);
! 358:
! 359: ds = data_string_init();
! 360: buffer_copy_string_len(ds->key, CONST_STR_LEN("abc"));
! 361: buffer_copy_string_len(ds->value, CONST_STR_LEN("hameplman"));
! 362:
! 363: array_insert_unique(a, (data_unset *)ds);
! 364:
! 365: ds = data_string_init();
! 366: buffer_copy_string_len(ds->key, CONST_STR_LEN("123"));
! 367: buffer_copy_string_len(ds->value, CONST_STR_LEN("alfrag"));
! 368:
! 369: array_insert_unique(a, (data_unset *)ds);
! 370:
! 371: dc = data_count_init();
! 372: buffer_copy_string_len(dc->key, CONST_STR_LEN("def"));
! 373:
! 374: array_insert_unique(a, (data_unset *)dc);
! 375:
! 376: dc = data_count_init();
! 377: buffer_copy_string_len(dc->key, CONST_STR_LEN("def"));
! 378:
! 379: array_insert_unique(a, (data_unset *)dc);
! 380:
! 381: array_print(a, 0);
! 382:
! 383: array_free(a);
! 384:
! 385: fprintf(stderr, "%d\n",
! 386: buffer_caseless_compare(CONST_STR_LEN("Content-Type"), CONST_STR_LEN("Content-type")));
! 387:
! 388: return 0;
! 389: }
! 390: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to array.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / lighttpd / src