libds

a collection of simple data structures
Log | Files | Refs | LICENSE

vector.c (1834B)

      1 /* Vector implementation using a hashed-array tree */
      2 #include <stdlib.h>
      3 
      4 struct leaf {
      5 	void *data;
      6 };
      7 
      8 struct vector {
      9 	struct leaf **l;
     10 	size_t sz;
     11 	size_t ne;
     12 };
     13 
     14 static int
     15 grow(struct vector *v)
     16 {
     17 	struct leaf **tmp, *l;
     18 	size_t i, j, ne = 0;
     19 
     20 	tmp = calloc(v->sz * 2, sizeof(*tmp));
     21 	if (!tmp)
     22 		return -1;
     23 	for (i = 0; i < v->sz / 2; i++) {
     24 		tmp[i] = calloc(v->sz * 2, sizeof(**tmp));
     25 		if (!tmp[i]) {
     26 			while (i-- > 0)
     27 				free(tmp[i]);
     28 			free(tmp);
     29 			return -1;
     30 		}
     31 	}
     32 	for (i = 0; i < v->sz; i++) {
     33 		l = tmp[ne / (v->sz * 2)];
     34 		for (j = 0; j < v->sz; j++) {
     35 			l[ne % (v->sz * 2)].data = v->l[i][j].data;
     36 			ne++;
     37 		}
     38 		free(v->l[i]);
     39 	}
     40 	free(v->l);
     41 	v->l = tmp;
     42 	v->sz *= 2;
     43 	return 0;
     44 }
     45 
     46 struct vector *
     47 vector_init(void)
     48 {
     49 	struct vector *v;
     50 
     51 	v = calloc(1, sizeof(*v));
     52 	if (!v)
     53 		return NULL;
     54 	v->sz = 2;
     55 	v->l = calloc(v->sz, sizeof(*v->l));
     56 	if (!v->l) {
     57 		free(v);
     58 		return NULL;
     59 	}
     60 	return v;
     61 }
     62 
     63 void
     64 vector_free(struct vector *v)
     65 {
     66 	size_t i;
     67 
     68 	for (i = 0; i < v->sz; i++)
     69 		free(v->l[i]);
     70 	free(v->l);
     71 }
     72 
     73 size_t
     74 vector_add(struct vector *v, void *data)
     75 {
     76 	size_t index, offset;
     77 	struct leaf *l;
     78 
     79 	if (v->ne == v->sz * v->sz)
     80 		if (grow(v) < 0)
     81 			return -1;
     82 	index = v->ne / v->sz;
     83 	offset = v->ne % v->sz;
     84 	if (!v->l[index]) {
     85 		v->l[index] = calloc(v->sz, sizeof(**v->l));
     86 		if (!v->l[index])
     87 			return -1;
     88 	}
     89 	l = v->l[index];
     90 	l[offset].data = data;
     91 	return v->ne++;
     92 }
     93 
     94 void *
     95 vector_get(struct vector *v, size_t i)
     96 {
     97 	size_t index, offset;
     98 	struct leaf *l;
     99 
    100 	index = i / v->sz;
    101 	offset = i % v->sz;
    102 	if (v->l[index]) {
    103 		l = v->l[index];
    104 		return l[offset].data;
    105 	}
    106 	return NULL;
    107 }
    108 
    109 size_t
    110 vector_size(struct vector *v)
    111 {
    112 	return v->ne;
    113 }
    114 
    115 void
    116 vector_walk(struct vector *v, void (*cb)(struct vector *, void *))
    117 {
    118 	size_t i;
    119 
    120 	for (i = 0; i < v->ne; i++)
    121 		cb(v, v->l[i / v->sz][i % v->sz].data);
    122 }