map/map.c - GCC Code Coverage Report

Directory:	../replacer/
Coverage:	low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%

	Coverage	Exec / Excl / Total
Lines:	86.8%	118 / 0 / 136
Functions:	92.9%	13 / 0 / 14
Branches:	70.6%	48 / 0 / 68

    map/map.c
    
        Line
        Branch
        Exec
        Source
      
        /**
      
         * Copyright (c) 2014 rxi
      
         *
      
         * This library is free software; you can redistribute it and/or modify it
      
         * under the terms of the MIT license. See LICENSE for details.
      
         */
      
        #include <stdlib.h>
      
        #include <string.h>
      
        #include "map.h"
      
        #include "unit_test_common.h"
      
        struct map_node_t {
      
          unsigned hash;
      
          void *value;
      
          map_node_t *next;
      
          /* char key[]; */
      
          /* char value[]; */
      
        };
      
        15568
        static unsigned map_hash(const char *str) {
      
          // Limiting hashed length to 16 barely affects hash uniqueness,
      
          // but speeds up hash function a lot
      
        15568
          unsigned limit = 16;
      
        15568
          unsigned hash  = 5381;
      
          4/4✓ Branch 4 → 5 taken 259172 times.
✓ Branch 4 → 6 taken 868 times.
✓ Branch 5 → 3 taken 244472 times.
✓ Branch 5 → 6 taken 14700 times.

        260040
          while (*str && (limit--)) {
      
        244472
            hash = ((hash << 5) + hash) ^ *str++;
      
          }
      
        15568
          return hash;
      
        }
      
        4495
        static map_node_t *map_newnode(const char *key, void *value, int vsize) {
      
          map_node_t *node;
      
        4495
          int ksize   = strlen(key) + 1;
      
        4495
          int voffset = ksize + ((sizeof(void *) - ksize) % sizeof(void *));
      
        4495
          node        = malloc(sizeof(*node) + voffset + vsize);
      
          1/2✗ Branch 3 → 4 not taken.
✓ Branch 3 → 5 taken 4495 times.

        4495
          if (!node)
      
        ✗
            return NULL;
      
        4495
          memcpy(node + 1, key, ksize);
      
        4495
          node->hash  = map_hash(key);
      
        4495
          node->value = ((char *)(node + 1)) + voffset;
      
        4495
          memcpy(node->value, value, vsize);
      
        4495
          return node;
      
        }
      
        20052
        static int map_bucketidx(map_base_t *m, unsigned hash) {
      
          /* If the implementation is changed to allow a non-power-of-2 bucket count,
      
           * the line below should be changed to use mod instead of AND */
      
        20052
          return hash & (m->nbuckets - 1);
      
        }
      
        9124
        static void map_addnode(map_base_t *m, map_node_t *node) {
      
        9124
          int n         = map_bucketidx(m, node->hash);
      
        9124
          node->next    = m->buckets[n];
      
        9124
          m->buckets[n] = node;
      
        9124
        }
      
        263
        static int map_resize(map_base_t *m, int nbuckets) {
      
          map_node_t *nodes, *node, *next;
      
          map_node_t **buckets;
      
          int i;
      
          /* Chain all nodes together */
      
        263
          nodes = NULL;
      
        263
          i     = m->nbuckets;
      
          2/2✓ Branch 7 → 3 taken 4629 times.
✓ Branch 7 → 8 taken 263 times.

        4892
          while (i--) {
      
        4629
            node = (m->buckets)[i];
      
          2/2✓ Branch 5 → 4 taken 4629 times.
✓ Branch 5 → 6 taken 4629 times.

        9258
            while (node) {
      
        4629
              next       = node->next;
      
        4629
              node->next = nodes;
      
        4629
              nodes      = node;
      
        4629
              node       = next;
      
            }
      
          }
      
          /* Reset buckets */
      
        263
          buckets = realloc(m->buckets, sizeof(*m->buckets) * nbuckets);
      
          1/2✓ Branch 9 → 10 taken 263 times.
✗ Branch 9 → 11 not taken.

        263
          if (buckets != NULL) {
      
        263
            m->buckets  = buckets;
      
        263
            m->nbuckets = nbuckets;
      
          }
      
          1/2✓ Branch 11 → 12 taken 263 times.
✗ Branch 11 → 16 not taken.

        263
          if (m->buckets) {
      
        263
            memset(m->buckets, 0, sizeof(*m->buckets) * m->nbuckets);
      
            /* Re-add nodes to buckets */
      
        263
            node = nodes;
      
          2/2✓ Branch 15 → 13 taken 4629 times.
✓ Branch 15 → 16 taken 263 times.

        4892
            while (node) {
      
        4629
              next = node->next;
      
        4629
              map_addnode(m, node);
      
        4629
              node = next;
      
            }
      
          }
      
          /* Return error code if realloc() failed */
      
          1/2✗ Branch 16 → 17 not taken.
✓ Branch 16 → 18 taken 263 times.

        263
          return (buckets == NULL) ? -1 : 0;
      
        }
      
        11073
        static map_node_t **map_getref(map_base_t *m, const char *key) {
      
        11073
          unsigned hash = map_hash(key);
      
          map_node_t **next;
      
          2/2✓ Branch 3 → 4 taken 10928 times.
✓ Branch 3 → 11 taken 145 times.

        11073
          if (m->nbuckets > 0) {
      
        10928
            next = &m->buckets[map_bucketidx(m, hash)];
      
          2/2✓ Branch 10 → 6 taken 6013709 times.
✓ Branch 10 → 11 taken 4636 times.

        6018345
            while (*next) {
      
          4/4✓ Branch 6 → 7 taken 6013499 times.
✓ Branch 6 → 9 taken 210 times.
✓ Branch 7 → 8 taken 6292 times.
✓ Branch 7 → 9 taken 6007207 times.

        6013709
              if ((*next)->hash == hash && !strcmp((char *)(*next + 1), key)) {
      
        6292
                return next;
      
              }
      
        6007417
              next = &(*next)->next;
      
            }
      
          }
      
        4781
          return NULL;
      
        }
      
        184
        void map_deinit_(map_base_t *m) {
      
          map_node_t *next, *node;
      
          int i;
      
        184
          i = m->nbuckets;
      
          2/2✓ Branch 8 → 3 taken 4708 times.
✓ Branch 8 → 9 taken 184 times.

        4892
          while (i--) {
      
        4708
            node = m->buckets[i];
      
          2/2✓ Branch 6 → 4 taken 273 times.
✓ Branch 6 → 7 taken 4708 times.

        4981
            while (node) {
      
        273
              next = node->next;
      
        273
              free(node);
      
        273
              node = next;
      
            }
      
          }
      
        184
          free(m->buckets);
      
          /* map_deinit_() makes blank state object:
      
           * that redefines map_deinit_() as idempotent func and avoids crash
      
           * on subsequent map_set_, map_increment_int_ (though, by cost of possible
      
           * memory leak) */
      
        184
          memset(m, 0, sizeof(*m));
      
        184
        }
      
        353
        void *map_get_(map_base_t *m, const char *key) {
      
        353
          map_node_t **next = map_getref(m, key);
      
          2/2✓ Branch 3 → 4 taken 67 times.
✓ Branch 3 → 5 taken 286 times.

        353
          return next ? (*next)->value : NULL;
      
        }
      
        6490
        int map_set_(map_base_t *m, const char *key, void *value, int vsize) {
      
          int n, err;
      
          map_node_t **next, *node;
      
          /* Find & replace existing node */
      
        6490
          next = map_getref(m, key);
      
          2/2✓ Branch 3 → 4 taken 2001 times.
✓ Branch 3 → 5 taken 4489 times.

        6490
          if (next) {
      
        2001
            memcpy((*next)->value, value, vsize);
      
        2001
            return 0;
      
          }
      
          /* Add new node */
      
        4489
          node = map_newnode(key, value, vsize);
      
          1/2✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 4489 times.

        4489
          if (node == NULL)
      
        ✗
            goto fail;
      
          2/2✓ Branch 8 → 9 taken 257 times.
✓ Branch 8 → 15 taken 4232 times.

        4489
          if (m->nnodes >= m->nbuckets) {
      
          2/2✓ Branch 9 → 10 taken 178 times.
✓ Branch 9 → 11 taken 79 times.

        257
            n   = (m->nbuckets > 0) ? (m->nbuckets << 1) : 1;
      
        257
            err = map_resize(m, n);
      
          1/2✗ Branch 13 → 14 not taken.
✓ Branch 13 → 15 taken 257 times.

        257
            if (err)
      
        ✗
              goto fail;
      
          }
      
        4489
          map_addnode(m, node);
      
        4489
          m->nnodes++;
      
        4489
          return 0;
      
        ✗
        fail:
      
        ✗
          if (node)
      
        ✗
            free(node);
      
        ✗
          return -1;
      
        }
      
        8
        int map_increment_int_(map_base_t *m, const char *key, int vsize) {
      
          int n, err;
      
          map_node_t **next, *node;
      
          /* Find & replace existing node */
      
        8
          next = map_getref(m, key);
      
          2/2✓ Branch 3 → 4 taken 2 times.
✓ Branch 3 → 5 taken 6 times.

        8
          if (next) {
      
        2
            int *ptr = (int *)(*next)->value;
      
        2
            *ptr     = *ptr + 1;
      
        2
            return 0;
      
          }
      
          /* Add new node */
      
        6
          int tmp = 1;
      
        6
          node    = map_newnode(key, &tmp, vsize);
      
          1/2✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 6 times.

        6
          if (node == NULL)
      
        ✗
            goto fail;
      
          1/2✓ Branch 8 → 9 taken 6 times.
✗ Branch 8 → 15 not taken.

        6
          if (m->nnodes >= m->nbuckets) {
      
          1/2✓ Branch 9 → 10 taken 6 times.
✗ Branch 9 → 11 not taken.

        6
            n   = (m->nbuckets > 0) ? (m->nbuckets << 1) : 1;
      
        6
            err = map_resize(m, n);
      
          1/2✗ Branch 13 → 14 not taken.
✓ Branch 13 → 15 taken 6 times.

        6
            if (err)
      
        ✗
              goto fail;
      
          }
      
        6
          map_addnode(m, node);
      
        6
          m->nnodes++;
      
        6
          return 0;
      
        ✗
        fail:
      
        ✗
          if (node)
      
        ✗
            free(node);
      
        ✗
          return -1;
      
        }
      
        4222
        void map_remove_(map_base_t *m, const char *key) {
      
          map_node_t *node;
      
        4222
          map_node_t **next = map_getref(m, key);
      
          1/2✓ Branch 3 → 4 taken 4222 times.
✗ Branch 3 → 6 not taken.

        4222
          if (next) {
      
        4222
            node  = *next;
      
        4222
            *next = (*next)->next;
      
        4222
            free(node);
      
        4222
            m->nnodes--;
      
          }
      
        4222
        }
      
        4335
        map_iter_t map_iter_(void) {
      
          map_iter_t iter;
      
        4335
          iter.bucketidx = -1;
      
        4335
          iter.node      = NULL;
      
        4335
          return iter;
      
        }
      
        4335
        const char *map_next_(map_base_t *m, map_iter_t *iter) {
      
          1/2✓ Branch 2 → 3 taken 4335 times.
✗ Branch 2 → 4 not taken.

        4335
          if (iter->node) {
      
        ✗
            iter->node = iter->node->next;
      
        ✗
            if (iter->node == NULL)
      
        ✗
              goto nextBucket;
      
          }
      
          else {
      
        4335
          nextBucket:
      
            do {
      
          2/2✓ Branch 7 → 8 taken 119 times.
✓ Branch 7 → 9 taken 6279000 times.

        6279119
              if (++iter->bucketidx >= m->nbuckets) {
      
        119
                return NULL;
      
              }
      
        6279000
              iter->node = m->buckets[iter->bucketidx];
      
          2/2✓ Branch 9 → 10 taken 6274784 times.
✓ Branch 9 → 11 taken 4216 times.

        6279000
            } while (iter->node == NULL);
      
          }
      
        4216
          return (char *)(iter->node + 1);
      
        }
      
        ✗
        void *map_value_(map_iter_t *iter) {
      
        ✗
          return iter->node != NULL ? iter->node->value : NULL;
      
        }

Line	Branch	Exec	Source
1			/**
2			* Copyright (c) 2014 rxi
3			*
4			* This library is free software; you can redistribute it and/or modify it
5			* under the terms of the MIT license. See LICENSE for details.
6			*/
7
8			#include <stdlib.h>
9			#include <string.h>
10			#include "map.h"
11
12			#include "unit_test_common.h"
13
14			struct map_node_t {
15			unsigned hash;
16			void *value;
17			map_node_t *next;
18			/* char key[]; */
19			/* char value[]; */
20			};
21
22		15568	static unsigned map_hash(const char *str) {
23			// Limiting hashed length to 16 barely affects hash uniqueness,
24			// but speeds up hash function a lot
25		15568	unsigned limit = 16;
26		15568	unsigned hash = 5381;
27	4/4 ✓ Branch 4 → 5 taken 259172 times. ✓ Branch 4 → 6 taken 868 times. ✓ Branch 5 → 3 taken 244472 times. ✓ Branch 5 → 6 taken 14700 times.	260040	while (*str && (limit--)) {
28		244472	hash = ((hash << 5) + hash) ^ *str++;
29			}
30		15568	return hash;
31			}
32
33		4495	static map_node_t map_newnode(const char key, void *value, int vsize) {
34			map_node_t *node;
35		4495	int ksize = strlen(key) + 1;
36		4495	int voffset = ksize + ((sizeof(void ) - ksize) % sizeof(void ));
37		4495	node = malloc(sizeof(*node) + voffset + vsize);
38	1/2 ✗ Branch 3 → 4 not taken. ✓ Branch 3 → 5 taken 4495 times.	4495	if (!node)
39		✗	return NULL;
40		4495	memcpy(node + 1, key, ksize);
41		4495	node->hash = map_hash(key);
42		4495	node->value = ((char *)(node + 1)) + voffset;
43		4495	memcpy(node->value, value, vsize);
44		4495	return node;
45			}
46
47		20052	static int map_bucketidx(map_base_t *m, unsigned hash) {
48			/* If the implementation is changed to allow a non-power-of-2 bucket count,
49			* the line below should be changed to use mod instead of AND */
50		20052	return hash & (m->nbuckets - 1);
51			}
52
53		9124	static void map_addnode(map_base_t m, map_node_t node) {
54		9124	int n = map_bucketidx(m, node->hash);
55		9124	node->next = m->buckets[n];
56		9124	m->buckets[n] = node;
57		9124	}
58
59		263	static int map_resize(map_base_t *m, int nbuckets) {
60			map_node_t nodes, node, *next;
61			map_node_t **buckets;
62			int i;
63			/* Chain all nodes together */
64		263	nodes = NULL;
65		263	i = m->nbuckets;
66	2/2 ✓ Branch 7 → 3 taken 4629 times. ✓ Branch 7 → 8 taken 263 times.	4892	while (i--) {
67		4629	node = (m->buckets)[i];
68	2/2 ✓ Branch 5 → 4 taken 4629 times. ✓ Branch 5 → 6 taken 4629 times.	9258	while (node) {
69		4629	next = node->next;
70		4629	node->next = nodes;
71		4629	nodes = node;
72		4629	node = next;
73			}
74			}
75			/* Reset buckets */
76		263	buckets = realloc(m->buckets, sizeof(m->buckets) nbuckets);
77	1/2 ✓ Branch 9 → 10 taken 263 times. ✗ Branch 9 → 11 not taken.	263	if (buckets != NULL) {
78		263	m->buckets = buckets;
79		263	m->nbuckets = nbuckets;
80			}
81	1/2 ✓ Branch 11 → 12 taken 263 times. ✗ Branch 11 → 16 not taken.	263	if (m->buckets) {
82		263	memset(m->buckets, 0, sizeof(m->buckets) m->nbuckets);
83			/* Re-add nodes to buckets */
84		263	node = nodes;
85	2/2 ✓ Branch 15 → 13 taken 4629 times. ✓ Branch 15 → 16 taken 263 times.	4892	while (node) {
86		4629	next = node->next;
87		4629	map_addnode(m, node);
88		4629	node = next;
89			}
90			}
91			/* Return error code if realloc() failed */
92	1/2 ✗ Branch 16 → 17 not taken. ✓ Branch 16 → 18 taken 263 times.	263	return (buckets == NULL) ? -1 : 0;
93			}
94
95		11073	static map_node_t *map_getref(map_base_t m, const char *key) {
96		11073	unsigned hash = map_hash(key);
97			map_node_t **next;
98	2/2 ✓ Branch 3 → 4 taken 10928 times. ✓ Branch 3 → 11 taken 145 times.	11073	if (m->nbuckets > 0) {
99		10928	next = &m->buckets[map_bucketidx(m, hash)];
100	2/2 ✓ Branch 10 → 6 taken 6013709 times. ✓ Branch 10 → 11 taken 4636 times.	6018345	while (*next) {
101	4/4 ✓ Branch 6 → 7 taken 6013499 times. ✓ Branch 6 → 9 taken 210 times. ✓ Branch 7 → 8 taken 6292 times. ✓ Branch 7 → 9 taken 6007207 times.	6013709	if ((next)->hash == hash && !strcmp((char )(*next + 1), key)) {
102		6292	return next;
103			}
104		6007417	next = &(*next)->next;
105			}
106			}
107		4781	return NULL;
108			}
109
110		184	void map_deinit_(map_base_t *m) {
111			map_node_t next, node;
112			int i;
113		184	i = m->nbuckets;
114	2/2 ✓ Branch 8 → 3 taken 4708 times. ✓ Branch 8 → 9 taken 184 times.	4892	while (i--) {
115		4708	node = m->buckets[i];
116	2/2 ✓ Branch 6 → 4 taken 273 times. ✓ Branch 6 → 7 taken 4708 times.	4981	while (node) {
117		273	next = node->next;
118		273	free(node);
119		273	node = next;
120			}
121			}
122		184	free(m->buckets);
123
124			/* map_deinit_() makes blank state object:
125			* that redefines map_deinit_() as idempotent func and avoids crash
126			* on subsequent map_set_, map_increment_int_ (though, by cost of possible
127			* memory leak) */
128		184	memset(m, 0, sizeof(*m));
129		184	}
130
131		353	void map_get_(map_base_t m, const char *key) {
132		353	map_node_t **next = map_getref(m, key);
133	2/2 ✓ Branch 3 → 4 taken 67 times. ✓ Branch 3 → 5 taken 286 times.	353	return next ? (*next)->value : NULL;
134			}
135
136		6490	int map_set_(map_base_t m, const char key, void *value, int vsize) {
137			int n, err;
138			map_node_t *next, node;
139			/* Find & replace existing node */
140		6490	next = map_getref(m, key);
141	2/2 ✓ Branch 3 → 4 taken 2001 times. ✓ Branch 3 → 5 taken 4489 times.	6490	if (next) {
142		2001	memcpy((*next)->value, value, vsize);
143		2001	return 0;
144			}
145			/* Add new node */
146		4489	node = map_newnode(key, value, vsize);
147	1/2 ✗ Branch 6 → 7 not taken. ✓ Branch 6 → 8 taken 4489 times.	4489	if (node == NULL)
148		✗	goto fail;
149	2/2 ✓ Branch 8 → 9 taken 257 times. ✓ Branch 8 → 15 taken 4232 times.	4489	if (m->nnodes >= m->nbuckets) {
150	2/2 ✓ Branch 9 → 10 taken 178 times. ✓ Branch 9 → 11 taken 79 times.	257	n = (m->nbuckets > 0) ? (m->nbuckets << 1) : 1;
151		257	err = map_resize(m, n);
152	1/2 ✗ Branch 13 → 14 not taken. ✓ Branch 13 → 15 taken 257 times.	257	if (err)
153		✗	goto fail;
154			}
155		4489	map_addnode(m, node);
156		4489	m->nnodes++;
157		4489	return 0;
158		✗	fail:
159		✗	if (node)
160		✗	free(node);
161		✗	return -1;
162			}
163
164		8	int map_increment_int_(map_base_t m, const char key, int vsize) {
165			int n, err;
166			map_node_t *next, node;
167			/* Find & replace existing node */
168		8	next = map_getref(m, key);
169	2/2 ✓ Branch 3 → 4 taken 2 times. ✓ Branch 3 → 5 taken 6 times.	8	if (next) {
170		2	int ptr = (int )(*next)->value;
171		2	ptr = ptr + 1;
172		2	return 0;
173			}
174			/* Add new node */
175		6	int tmp = 1;
176		6	node = map_newnode(key, &tmp, vsize);
177	1/2 ✗ Branch 6 → 7 not taken. ✓ Branch 6 → 8 taken 6 times.	6	if (node == NULL)
178		✗	goto fail;
179	1/2 ✓ Branch 8 → 9 taken 6 times. ✗ Branch 8 → 15 not taken.	6	if (m->nnodes >= m->nbuckets) {
180	1/2 ✓ Branch 9 → 10 taken 6 times. ✗ Branch 9 → 11 not taken.	6	n = (m->nbuckets > 0) ? (m->nbuckets << 1) : 1;
181		6	err = map_resize(m, n);
182	1/2 ✗ Branch 13 → 14 not taken. ✓ Branch 13 → 15 taken 6 times.	6	if (err)
183		✗	goto fail;
184			}
185		6	map_addnode(m, node);
186		6	m->nnodes++;
187		6	return 0;
188		✗	fail:
189		✗	if (node)
190		✗	free(node);
191		✗	return -1;
192			}
193
194		4222	void map_remove_(map_base_t m, const char key) {
195			map_node_t *node;
196		4222	map_node_t **next = map_getref(m, key);
197	1/2 ✓ Branch 3 → 4 taken 4222 times. ✗ Branch 3 → 6 not taken.	4222	if (next) {
198		4222	node = *next;
199		4222	next = (next)->next;
200		4222	free(node);
201		4222	m->nnodes--;
202			}
203		4222	}
204
205		4335	map_iter_t map_iter_(void) {
206			map_iter_t iter;
207		4335	iter.bucketidx = -1;
208		4335	iter.node = NULL;
209		4335	return iter;
210			}
211
212		4335	const char map_next_(map_base_t m, map_iter_t *iter) {
213	1/2 ✓ Branch 2 → 3 taken 4335 times. ✗ Branch 2 → 4 not taken.	4335	if (iter->node) {
214		✗	iter->node = iter->node->next;
215		✗	if (iter->node == NULL)
216		✗	goto nextBucket;
217			}
218			else {
219		4335	nextBucket:
220			do {
221	2/2 ✓ Branch 7 → 8 taken 119 times. ✓ Branch 7 → 9 taken 6279000 times.	6279119	if (++iter->bucketidx >= m->nbuckets) {
222		119	return NULL;
223			}
224		6279000	iter->node = m->buckets[iter->bucketidx];
225	2/2 ✓ Branch 9 → 10 taken 6274784 times. ✓ Branch 9 → 11 taken 4216 times.	6279000	} while (iter->node == NULL);
226			}
227		4216	return (char *)(iter->node + 1);
228			}
229
230		✗	void map_value_(map_iter_t iter) {
231		✗	return iter->node != NULL ? iter->node->value : NULL;
232			}
233