/src/augeas/src/ast.c

Source (jump to first uncovered line)
/*
 * ast.c: Support routines for put/get
 *
 * Copyright (C) 2008-2016 David Lutterkort
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
 *
 * Author: David Lutterkort <dlutter@redhat.com>
 */

#include <config.h>
#include <stdint.h>

#include "internal.h"
#include "memory.h"
#include "lens.h"

/* A dictionary that maps key to a list of (skel, dict) */
struct dict_entry {
    struct dict_entry *next;
    struct skel *skel;
    struct dict *dict;
};

/* Associates a KEY with a list of skel/dict pairs.

   Dicts are used in two phases: first they are constructed, through
   repeated calls to dict_append. In the second phase, items are looked up
   and removed from the dict.

   During construction, MARK points to the end of the list ENTRY. Once
   construction is done, MARK points to the head of that list, and ENTRY is
   moved towards the tail everytime an item is looked up.
*/
struct dict_node {
    char *key;
    struct dict_entry *entry; /* This will change as entries are looked up */
    struct dict_entry *mark;  /* Pointer to initial entry, will never change */
};

/* Nodes are kept sorted by their key, with NULL being smaller than any
   string */
struct dict {
    struct dict_node **nodes;
    uint32_t          size;
    uint32_t          used;
    bool              marked;
};

static const int dict_initial_size = 2;
static const int dict_max_expansion = 128;
static const uint32_t dict_max_size = (1<<24) - 1;

struct dict *make_dict(char *key, struct skel *skel, struct dict *subdict) {
    struct dict *dict = NULL;
    if (ALLOC(dict) < 0)
        goto error;
    if (ALLOC_N(dict->nodes, dict_initial_size) < 0)
        goto error;
    if (ALLOC(dict->nodes[0]) < 0)
        goto error;
    if (ALLOC(dict->nodes[0]->entry) < 0)
        goto error;

    dict->size = dict_initial_size;
    dict->used = 1;
    dict->nodes[0]->key = key;
    dict->nodes[0]->entry->skel = skel;
    dict->nodes[0]->entry->dict = subdict;
    dict->nodes[0]->mark = dict->nodes[0]->entry;

    return dict;
 error:
    if (dict->nodes) {
        if (dict->nodes[0])
            FREE(dict->nodes[0]->entry);
        FREE(dict->nodes[0]);
    }
    FREE(dict->nodes);
    FREE(dict);
    return NULL;
}

void free_dict(struct dict *dict) {
    if (dict == NULL)
        return;

    for (int i=0; i < dict->used; i++) {
        struct dict_node *node = dict->nodes[i];
        if (! dict->marked)
            node->mark = node->entry;
        while (node->mark != NULL) {
            struct dict_entry *del = node->mark;
            node->mark = del->next;
            free_skel(del->skel);
            free_dict(del->dict);
            free(del);
        }
        free(node->key);
        FREE(node);
    }
    FREE(dict->nodes);
    FREE(dict);
}

/* Return the position of KEY in DICT as an integer between 0 and
   DICT->USED.  If KEY is not in DICT, return a negative number P such that
   -(P + 1) is the position at which KEY must be inserted to keep the keys
   of the nodes in DICT sorted.
*/
static int dict_pos(struct dict *dict, const char *key) {
    if (key == NULL) {
        return (dict->nodes[0]->key == NULL) ? 0 : -1;
    }

    int l = dict->nodes[0]->key == NULL ? 1 : 0;
    int h = dict->used;
    while (l < h) {
        int m = (l + h)/2;
        int cmp = strcmp(dict->nodes[m]->key, key);
        if (cmp > 0)
            h = m;
        else if (cmp < 0)
            l = m + 1;
        else
            return m;
    }
    return -(l + 1);
}

static int dict_expand(struct dict *dict) {
    uint32_t size = dict->size;

    if (size == dict_max_size)
        return -1;
    if (size > dict_max_expansion)
        size += dict_max_expansion;
    else
        size *= 2;
    if (size > dict_max_size)
        size = dict_max_size;
    dict->size = size;
    return REALLOC_N(dict->nodes, dict->size);
}

int dict_append(struct dict **dict, struct dict *d2) {
    if (d2 == NULL)
        return 0;

    if (*dict == NULL) {
        *dict = d2;
        return 0;
    }

    struct dict *d1 = *dict;
    for (int i2 = 0; i2 < d2->used; i2++) {
        struct dict_node *n2 = d2->nodes[i2];
        int i1 = dict_pos(d1, n2->key);
        if (i1 < 0) {
            i1 = - i1 - 1;
            if (d1->size == d1->used) {
                if (dict_expand(d1) < 0)
                    return -1;
            }
            memmove(d1->nodes + i1 + 1, d1->nodes + i1,
                    sizeof(*d1->nodes) * (d1->used - i1));
            d1->nodes[i1] = n2;
            d1->used += 1;
        } else {
            struct dict_node *n1 = d1->nodes[i1];
            list_tail_cons(n1->entry, n1->mark, n2->entry);
            FREE(n2->key);
            FREE(n2);
        }
    }
    FREE(d2->nodes);
    FREE(d2);
    return 0;
}

void dict_lookup(const char *key, struct dict *dict,
                 struct skel **skel, struct dict **subdict) {
    *skel = NULL;
    *subdict = NULL;
    if (dict != NULL) {
        if (! dict->marked) {
            for (int i=0; i < dict->used; i++) {
                dict->nodes[i]->mark = dict->nodes[i]->entry;
            }
            dict->marked = 1;
        }
        int p = dict_pos(dict, key);
        if (p >= 0) {
            struct dict_node *node = dict->nodes[p];
            if (node->entry != NULL) {
                *skel = node->entry->skel;
                *subdict = node->entry->dict;
                node->entry = node->entry->next;
            }
        }
    }
}



/*
 * Local variables:
 *  indent-tabs-mode: nil
 *  c-indent-level: 4
 *  c-basic-offset: 4
 *  tab-width: 4
 * End:
 */

Coverage Report

Created: 2023-09-20 06:34

Line	Count	Source (jump to first uncovered line)
1		/*
2		* ast.c: Support routines for put/get
3		*
4		* Copyright (C) 2008-2016 David Lutterkort
5		*
6		* This library is free software; you can redistribute it and/or
7		* modify it under the terms of the GNU Lesser General Public
8		* License as published by the Free Software Foundation; either
9		* version 2.1 of the License, or (at your option) any later version.
10		*
11		* This library is distributed in the hope that it will be useful,
12		* but WITHOUT ANY WARRANTY; without even the implied warranty of
13		* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14		* Lesser General Public License for more details.
15		*
16		* You should have received a copy of the GNU Lesser General Public
17		* License along with this library; if not, write to the Free Software
18		* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19		*
20		* Author: David Lutterkort <dlutter@redhat.com>
21		*/
22
23		#include <config.h>
24		#include <stdint.h>
25
26		#include "internal.h"
27		#include "memory.h"
28		#include "lens.h"
29
30		/* A dictionary that maps key to a list of (skel, dict) */
31		struct dict_entry {
32		struct dict_entry *next;
33		struct skel *skel;
34		struct dict *dict;
35		};
36
37		/* Associates a KEY with a list of skel/dict pairs.
38
39		Dicts are used in two phases: first they are constructed, through
40		repeated calls to dict_append. In the second phase, items are looked up
41		and removed from the dict.
42
43		During construction, MARK points to the end of the list ENTRY. Once
44		construction is done, MARK points to the head of that list, and ENTRY is
45		moved towards the tail everytime an item is looked up.
46		*/
47		struct dict_node {
48		char *key;
49		struct dict_entry entry; / This will change as entries are looked up */
50		struct dict_entry mark; / Pointer to initial entry, will never change */
51		};
52
53		/* Nodes are kept sorted by their key, with NULL being smaller than any
54		string */
55		struct dict {
56		struct dict_node **nodes;
57		uint32_t size;
58		uint32_t used;
59		bool marked;
60		};
61
62		static const int dict_initial_size = 2;
63		static const int dict_max_expansion = 128;
64		static const uint32_t dict_max_size = (1<<24) - 1;
65
66	0	struct dict make_dict(char key, struct skel skel, struct dict subdict) {
67	0	struct dict *dict = NULL;
68	0	if (ALLOC(dict) < 0)
69	0	goto error;
70	0	if (ALLOC_N(dict->nodes, dict_initial_size) < 0)
71	0	goto error;
72	0	if (ALLOC(dict->nodes[0]) < 0)
73	0	goto error;
74	0	if (ALLOC(dict->nodes[0]->entry) < 0)
75	0	goto error;
76
77	0	dict->size = dict_initial_size;
78	0	dict->used = 1;
79	0	dict->nodes[0]->key = key;
80	0	dict->nodes[0]->entry->skel = skel;
81	0	dict->nodes[0]->entry->dict = subdict;
82	0	dict->nodes[0]->mark = dict->nodes[0]->entry;
83
84	0	return dict;
85	0	error:
86	0	if (dict->nodes) {
87	0	if (dict->nodes[0])
88	0	FREE(dict->nodes[0]->entry);
89	0	FREE(dict->nodes[0]);
90	0	}
91	0	FREE(dict->nodes);
92	0	FREE(dict);
93	0	return NULL;
94	0	}
95
96	0	void free_dict(struct dict *dict) {
97	0	if (dict == NULL)
98	0	return;
99
100	0	for (int i=0; i < dict->used; i++) {
101	0	struct dict_node *node = dict->nodes[i];
102	0	if (! dict->marked)
103	0	node->mark = node->entry;
104	0	while (node->mark != NULL) {
105	0	struct dict_entry *del = node->mark;
106	0	node->mark = del->next;
107	0	free_skel(del->skel);
108	0	free_dict(del->dict);
109	0	free(del);
110	0	}
111	0	free(node->key);
112	0	FREE(node);
113	0	}
114	0	FREE(dict->nodes);
115	0	FREE(dict);
116	0	}
117
118		/* Return the position of KEY in DICT as an integer between 0 and
119		DICT->USED. If KEY is not in DICT, return a negative number P such that
120		-(P + 1) is the position at which KEY must be inserted to keep the keys
121		of the nodes in DICT sorted.
122		*/
123	0	static int dict_pos(struct dict dict, const char key) {
124	0	if (key == NULL) {
125	0	return (dict->nodes[0]->key == NULL) ? 0 : -1;
126	0	}
127
128	0	int l = dict->nodes[0]->key == NULL ? 1 : 0;
129	0	int h = dict->used;
130	0	while (l < h) {
131	0	int m = (l + h)/2;
132	0	int cmp = strcmp(dict->nodes[m]->key, key);
133	0	if (cmp > 0)
134	0	h = m;
135	0	else if (cmp < 0)
136	0	l = m + 1;
137	0	else
138	0	return m;
139	0	}
140	0	return -(l + 1);
141	0	}
142
143	0	static int dict_expand(struct dict *dict) {
144	0	uint32_t size = dict->size;
145
146	0	if (size == dict_max_size)
147	0	return -1;
148	0	if (size > dict_max_expansion)
149	0	size += dict_max_expansion;
150	0	else
151	0	size *= 2;
152	0	if (size > dict_max_size)
153	0	size = dict_max_size;
154	0	dict->size = size;
155	0	return REALLOC_N(dict->nodes, dict->size);
156	0	}
157
158	0	int dict_append(struct dict *dict, struct dict d2) {
159	0	if (d2 == NULL)
160	0	return 0;
161
162	0	if (*dict == NULL) {
163	0	*dict = d2;
164	0	return 0;
165	0	}
166
167	0	struct dict d1 = dict;
168	0	for (int i2 = 0; i2 < d2->used; i2++) {
169	0	struct dict_node *n2 = d2->nodes[i2];
170	0	int i1 = dict_pos(d1, n2->key);
171	0	if (i1 < 0) {
172	0	i1 = - i1 - 1;
173	0	if (d1->size == d1->used) {
174	0	if (dict_expand(d1) < 0)
175	0	return -1;
176	0	}
177	0	memmove(d1->nodes + i1 + 1, d1->nodes + i1,
178	0	sizeof(d1->nodes) (d1->used - i1));
179	0	d1->nodes[i1] = n2;
180	0	d1->used += 1;
181	0	} else {
182	0	struct dict_node *n1 = d1->nodes[i1];
183	0	list_tail_cons(n1->entry, n1->mark, n2->entry);
184	0	FREE(n2->key);
185	0	FREE(n2);
186	0	}
187	0	}
188	0	FREE(d2->nodes);
189	0	FREE(d2);
190	0	return 0;
191	0	}
192
193		void dict_lookup(const char key, struct dict dict,
194	0	struct skel skel, struct dict subdict) {
195	0	*skel = NULL;
196	0	*subdict = NULL;
197	0	if (dict != NULL) {
198	0	if (! dict->marked) {
199	0	for (int i=0; i < dict->used; i++) {
200	0	dict->nodes[i]->mark = dict->nodes[i]->entry;
201	0	}
202	0	dict->marked = 1;
203	0	}
204	0	int p = dict_pos(dict, key);
205	0	if (p >= 0) {
206	0	struct dict_node *node = dict->nodes[p];
207	0	if (node->entry != NULL) {
208	0	*skel = node->entry->skel;
209	0	*subdict = node->entry->dict;
210	0	node->entry = node->entry->next;
211	0	}
212	0	}
213	0	}
214	0	}
215
216
217
218		/*
219		* Local variables:
220		* indent-tabs-mode: nil
221		* c-indent-level: 4
222		* c-basic-offset: 4
223		* tab-width: 4
224		* End:
225		*/