src/transport.c
changeset 95 546e631421b9
parent 94 9ec29aa10b58
child 96 fe4931a0413b
     1.1 --- a/src/transport.c	Mon Mar 09 23:20:08 2015 +0100
     1.2 +++ b/src/transport.c	Tue Mar 10 15:23:46 2015 +0100
     1.3 @@ -193,6 +193,360 @@
     1.4      return bloblist_add(bloblist->next, blob, size, mime_type, file_name);
     1.5  }
     1.6  
     1.7 +DYNAMIC_API stringpair_t * new_stringpair(const char *key, const char *value)
     1.8 +{
     1.9 +    stringpair_t *pair = NULL;
    1.10 +
    1.11 +    assert(key);
    1.12 +    assert(value),
    1.13 +
    1.14 +    pair = calloc(1, sizeof(stringpair_t));
    1.15 +    assert(pair);
    1.16 +    if (pair == NULL)
    1.17 +        goto enomem;
    1.18 +
    1.19 +    pair->key = strdup(key);
    1.20 +    assert(pair->key);
    1.21 +    if (pair->key == NULL)
    1.22 +        goto enomem;
    1.23 +
    1.24 +    pair->value = strdup(value);
    1.25 +    assert(pair->value);
    1.26 +    if (pair->value == NULL)
    1.27 +        goto enomem;
    1.28 +
    1.29 +    return pair;
    1.30 +
    1.31 +enomem:
    1.32 +    free_stringpair(pair);
    1.33 +    return NULL;
    1.34 +}
    1.35 +
    1.36 +DYNAMIC_API void free_stringpair(stringpair_t * pair)
    1.37 +{
    1.38 +    if (pair) {
    1.39 +        free(pair->key);
    1.40 +        free(pair->value);
    1.41 +        free(pair);
    1.42 +    }
    1.43 +}
    1.44 +
    1.45 +DYNAMIC_API stringpair_t * stringpair_dup(const stringpair_t *src)
    1.46 +{
    1.47 +    assert(src);
    1.48 +    return new_stringpair(src->key, src->value);
    1.49 +}
    1.50 +
    1.51 +DYNAMIC_API stringpair_map_t * new_stringpair_map(const stringpair_t *pair)
    1.52 +{
    1.53 +    stringpair_map_t *map = NULL;
    1.54 +
    1.55 +    map = calloc(1, sizeof(stringpair_map_t));
    1.56 +    assert(map);
    1.57 +    if (map == NULL)
    1.58 +        goto enomem;
    1.59 +
    1.60 +    if (pair) {
    1.61 +        map->pair = stringpair_dup(pair);
    1.62 +        if (map->pair == NULL)
    1.63 +            goto enomem;
    1.64 +    }
    1.65 +
    1.66 +    return map;
    1.67 +
    1.68 +enomem:
    1.69 +    free_stringpair_map(map);
    1.70 +    return NULL;
    1.71 +}
    1.72 +
    1.73 +DYNAMIC_API void free_stringpair_map(stringpair_map_t *map)
    1.74 +{
    1.75 +    if (map) {
    1.76 +        free_stringpair_map(map->left);
    1.77 +        free_stringpair_map(map->right);
    1.78 +        free_stringpair(map->pair);
    1.79 +        free(map);
    1.80 +    }
    1.81 +}
    1.82 +
    1.83 +static stringpair_map_t * _stringpair_map_dup(
    1.84 +        const stringpair_map_t *src,
    1.85 +        stringpair_map_t *parent
    1.86 +    )
    1.87 +{
    1.88 +    stringpair_map_t *map = NULL;   
    1.89 +
    1.90 +    assert(src);
    1.91 +
    1.92 +    map = new_stringpair_map(src->pair);
    1.93 +    if (map == NULL)
    1.94 +        goto enomem;
    1.95 +
    1.96 +    map->color = src->color;
    1.97 +
    1.98 +    if (src->left) {
    1.99 +        map->left = _stringpair_map_dup(src->left, map);
   1.100 +        if (map->left == NULL)
   1.101 +            goto enomem;
   1.102 +    }
   1.103 +
   1.104 +    if (src->right) {
   1.105 +        map->right = _stringpair_map_dup(src->right, map);
   1.106 +        if (map->right == NULL)
   1.107 +            goto enomem;
   1.108 +    }
   1.109 +
   1.110 +    map->parent_ref = parent;
   1.111 +
   1.112 +    return map;
   1.113 +
   1.114 +enomem:
   1.115 +    free_stringpair_map(map);
   1.116 +    return NULL;
   1.117 +}
   1.118 +
   1.119 +DYNAMIC_API stringpair_map_t * stringpair_map_dup(const stringpair_map_t *src)
   1.120 +{
   1.121 +    return _stringpair_map_dup(src, NULL);
   1.122 +}
   1.123 +
   1.124 +static bool stringpair_map_is_leave(const stringpair_map_t *node)
   1.125 +{
   1.126 +    assert(node);
   1.127 +    return node->left == NULL && node->right == NULL;
   1.128 +}
   1.129 +
   1.130 +DYNAMIC_API stringpair_map_t * stringpair_map_find(
   1.131 +        stringpair_map_t *map,
   1.132 +        const char *key
   1.133 +    )
   1.134 +{
   1.135 +    int c;
   1.136 +
   1.137 +    assert(key);
   1.138 +
   1.139 +    if (map == NULL || map->pair == NULL) // empty map
   1.140 +        return NULL;
   1.141 +
   1.142 +    c = strcmp(map->pair->key, key);
   1.143 +
   1.144 +    if (c == 0)
   1.145 +        return map;
   1.146 +    else if (c < 0)
   1.147 +        return stringpair_map_find(map->left, key);
   1.148 +    else
   1.149 +        return stringpair_map_find(map->right, key);
   1.150 +}
   1.151 +
   1.152 +static stringpair_map_t * stringpair_map_grandparent(stringpair_map_t *node)
   1.153 +{
   1.154 +    assert(node);
   1.155 +
   1.156 +    if (node->parent_ref == NULL)
   1.157 +        return NULL;
   1.158 +
   1.159 +    return node->parent_ref->parent_ref;
   1.160 +}
   1.161 +
   1.162 +static stringpair_map_t * stringpair_map_uncle(stringpair_map_t *node)
   1.163 +{
   1.164 +    assert(stringpair_map_grandparent(node));
   1.165 +
   1.166 +    if (node->parent_ref == stringpair_map_grandparent(node)->left)
   1.167 +        return stringpair_map_grandparent(node)->right;
   1.168 +    else
   1.169 +        return stringpair_map_grandparent(node)->left;
   1.170 +}
   1.171 +
   1.172 +static stringpair_map_t * _stringpair_map_add(
   1.173 +        stringpair_map_t *map,
   1.174 +        stringpair_t * pair
   1.175 +    )
   1.176 +{
   1.177 +    int c;
   1.178 +
   1.179 +    assert(map);
   1.180 +    assert(pair);
   1.181 +
   1.182 +    if (map->pair == NULL) {
   1.183 +        map->pair = stringpair_dup(pair);
   1.184 +        if (map->pair == NULL)
   1.185 +            return NULL;
   1.186 +        return map;
   1.187 +    }
   1.188 +
   1.189 +    assert(map->pair->key);
   1.190 +    assert(pair->key);
   1.191 +
   1.192 +    c = strcmp(map->pair->key, pair->key);
   1.193 +    if (c == 0) {
   1.194 +        free(map->pair->value);
   1.195 +
   1.196 +        assert(pair->value);
   1.197 +
   1.198 +        map->pair->value = strdup(pair->value);
   1.199 +        assert(map->pair->value);
   1.200 +        if (map->pair->value == NULL)
   1.201 +            return NULL;
   1.202 +    }
   1.203 +    else if (c < 0) {
   1.204 +        if (map->left == NULL) {
   1.205 +            map->left = new_stringpair_map(pair);
   1.206 +            if (map->left)
   1.207 +                return NULL;
   1.208 +            map = map->left;
   1.209 +        }
   1.210 +        else {
   1.211 +            map = _stringpair_map_add(map->left, pair);
   1.212 +        }
   1.213 +    }
   1.214 +    else {
   1.215 +        if (map->right == NULL) {
   1.216 +            map->right = new_stringpair_map(pair);
   1.217 +            if (map->right)
   1.218 +                return NULL;
   1.219 +            map = map->right;
   1.220 +        }
   1.221 +        else {
   1.222 +            map = _stringpair_map_add(map->right, pair);
   1.223 +        }
   1.224 +    }
   1.225 +
   1.226 +    return map;
   1.227 +}
   1.228 +
   1.229 +static void stringpair_map_rotate_left(stringpair_map_t *l)
   1.230 +{
   1.231 +    stringpair_map_t * _parent;
   1.232 +    stringpair_map_t * _r;
   1.233 +
   1.234 +    assert(l);
   1.235 +    assert(l->parent_ref);
   1.236 +    assert(l->right);
   1.237 +
   1.238 +    _parent = l->parent_ref;
   1.239 +    _r = l->right;
   1.240 +
   1.241 +    l->right = _r->left;
   1.242 +    _r->left = l;
   1.243 +
   1.244 +    if (_parent->left == l)
   1.245 +        _parent->left = _r;
   1.246 +    else
   1.247 +        _parent->right = _r;
   1.248 +}
   1.249 +
   1.250 +static void stringpair_map_rotate_right(stringpair_map_t *r)
   1.251 +{
   1.252 +    stringpair_map_t * _parent;
   1.253 +    stringpair_map_t * _l;
   1.254 +
   1.255 +    assert(r);
   1.256 +    assert(r->parent_ref);
   1.257 +    assert(r->left);
   1.258 +
   1.259 +    _parent = r->parent_ref;
   1.260 +    _l = r->left;
   1.261 +
   1.262 +    r->left = _l->right;
   1.263 +    _l->right = r;
   1.264 +
   1.265 +    if (_parent->left == r)
   1.266 +        _parent->left = _l;
   1.267 +    else
   1.268 +        _parent->right = _l;
   1.269 +}
   1.270 +
   1.271 +static void stringpair_map_case5(stringpair_map_t *map)
   1.272 +{
   1.273 +    map->parent_ref->color = rbt_black;
   1.274 +    stringpair_map_grandparent(map)->color = rbt_red;
   1.275 +    if (map == map->parent_ref->left &&
   1.276 +            map->parent_ref == stringpair_map_grandparent(map)->left) {
   1.277 +        stringpair_map_rotate_right(stringpair_map_grandparent(map));
   1.278 +    }
   1.279 +    else {
   1.280 +        assert(map == map->parent_ref->right &&
   1.281 +                map->parent_ref == stringpair_map_grandparent(map)->right);
   1.282 +        stringpair_map_rotate_left(stringpair_map_grandparent(map));
   1.283 +    }
   1.284 +}
   1.285 +
   1.286 +static void stringpair_map_case4(stringpair_map_t *map)
   1.287 +{
   1.288 +    if (map == map->parent_ref->right &&
   1.289 +            map->parent_ref == stringpair_map_grandparent(map)->left) {
   1.290 +        stringpair_map_rotate_left(map->parent_ref);
   1.291 +        map = map->left;
   1.292 +    }
   1.293 +    else if (map == map->parent_ref->left &&
   1.294 +            map->parent_ref == stringpair_map_grandparent(map)->right) {
   1.295 +        stringpair_map_rotate_right(map->parent_ref);
   1.296 +        map = map->right;
   1.297 +    }
   1.298 +
   1.299 +    stringpair_map_case5(map);
   1.300 +}
   1.301 +
   1.302 +static void stringpair_map_case1(stringpair_map_t *map);
   1.303 +
   1.304 +static void stringpair_map_case3(stringpair_map_t *map)
   1.305 +{
   1.306 +    if (stringpair_map_uncle(map) != NULL &&
   1.307 +            stringpair_map_uncle(map)->color == rbt_red) {
   1.308 +        map->parent_ref->color = rbt_black;
   1.309 +        stringpair_map_uncle(map)->color = rbt_black;
   1.310 +        stringpair_map_grandparent(map)->color = rbt_red;
   1.311 +
   1.312 +        stringpair_map_case1(stringpair_map_grandparent(map));
   1.313 +    }
   1.314 +    else {
   1.315 +        stringpair_map_case4(map);
   1.316 +    }
   1.317 +}
   1.318 +
   1.319 +static void stringpair_map_case2(stringpair_map_t *map)
   1.320 +{
   1.321 +    if (map->parent_ref->color == rbt_black)
   1.322 +        return;
   1.323 +    else
   1.324 +        stringpair_map_case3(map);
   1.325 +}
   1.326 +
   1.327 +static void stringpair_map_case1(stringpair_map_t *map)
   1.328 +{
   1.329 +    assert(map);
   1.330 +
   1.331 +    if (map->parent_ref == NULL)
   1.332 +        map->color = rbt_black;
   1.333 +    else
   1.334 +        stringpair_map_case2(map);
   1.335 +}
   1.336 +
   1.337 +static void stringpair_map_repair(stringpair_map_t *map)
   1.338 +{
   1.339 +    stringpair_map_case1(map);
   1.340 +}
   1.341 +
   1.342 +DYNAMIC_API stringpair_map_t * stringpair_map_add(
   1.343 +        stringpair_map_t *map,
   1.344 +        stringpair_t * pair
   1.345 +    )
   1.346 +{
   1.347 +    stringpair_map_t * _map = NULL;
   1.348 +
   1.349 +    assert(map);
   1.350 +    assert(pair);
   1.351 +
   1.352 +    _map = _stringpair_map_add(map, pair);
   1.353 +    if (_map == NULL)
   1.354 +        return NULL;
   1.355 +
   1.356 +    stringpair_map_repair(_map);
   1.357 +
   1.358 +    return _map;
   1.359 +}
   1.360 +
   1.361  DYNAMIC_API message *new_message(
   1.362          PEP_msg_direction dir,
   1.363          pEp_identity *from,