· 8 years ago · Jun 07, 2018, 12:02 PM
1/*Modified by Olle Stenlund
2 * Original code was was table.c which was written by Niclas Borlin and
3 * Adam Dahlgren Lindström.
4 * Version: 2
5 * Date: 06.06.2018
6 * CAS : <olst0018@student.umu.se>
7 * CS-ID : <tfy14osd>
8 */
9
10#include <stdlib.h>
11#include <stdio.h>
12#include <string.h>
13#include "table.h"
14#include "array_1d.h"
15
16/*Purpose: Implementation of table.c with the use of arrays. The code is
17 * written/modified by Olle Stenlund (2018). Includes the functions and
18 * tools to properly create a table with the use of arrays and has the
19 * ability to free all allocated memory after its destruction.
20 * */
21
22
23/*
24 * Implementation of a generic table for the "Datastructures and
25 * algorithms" courses at the Department of Computing Science, Umea
26 * University.
27 *
28 * Duplicates are handled by inspect and remove.
29 *
30 * Authors: Niclas Borlin (niclas@cs.umu.se)
31 * Adam Dahlgren Lindstrom (dali@cs.umu.se)
32 *
33 * Based on earlier code by: Johan Eliasson (johane@cs.umu.se).
34 *
35 * Version information:
36 * 2018-02-06: v1.0, first public version.
37 */
38
39
40/*Elements*/
41const int sizeMax = 80000;
42
43struct table {
44 array_1d *entries;
45 compare_function *key_cmp_func;
46 free_function key_free_func;
47 free_function value_free_func;
48 int elementCounter;
49};
50
51struct table_entry{
52 void *key;
53 void *value;
54};
55
56
57
58// ===========INTERNAL FUNCTION IMPLEMENTATIONS============
59
60/**
61 * table_empty() - Create an empty table. Sets elementCounter to 0.
62 * @key_cmp_func: A pointer to a function to be used to compare keys.
63 * @key_free_func: A pointer to a function (or NULL) to be called to
64 * de-allocate memory for keys on remove/kill.
65 * @value_free_func: A pointer to a function (or NULL) to be called to
66 * de-allocate memory for values on remove/kill.
67 *
68 * Return: Pointer to a new table.
69 */
70table *table_empty(compare_function *key_cmp_func,
71 free_function key_free_func,
72 free_function value_free_func){
73 table*t = calloc(sizeof (table),1);
74 //Creates the array
75 t->entries=array_1d_create(0, sizeMax, free);
76
77 // Store the key compare function and key/value free functions.
78 t->key_cmp_func = key_cmp_func;
79 t->key_free_func = key_free_func;
80 t->value_free_func = value_free_func;
81 t->elementCounter = 0;
82 return t;
83}
84
85
86/**
87 * table_is_empty() - Check if a table is empty.
88 * @table: Table to check.
89 *
90 * Return: True if table contains no key/value pairs, false otherwise.
91 */
92bool table_is_empty(const table *t) {
93 int k = 0;
94
95 while(k <= t->elementCounter){
96 if(array_1d_has_value(t->entries,k)){
97 return 0;
98 }
99 k++;
100 }
101 return 1;
102
103}
104
105
106/**
107 * table_insert() - Add a key/value pair to a table.
108 * @table: Table to manipulate.
109 * @key: A pointer to the key value.
110 * @value: A pointer to the value value.
111 *
112 * Insert the key/value pair into the table. If there exists a duplicate,
113 * the function will overwrite the value which shares the same key with
114 * the new value inserted.
115 *
116 * Returns: Nothing.
117 */
118void table_insert(table *t, void *key, void *value) {
119 struct table_entry *entry=malloc(sizeof(struct table_entry));
120 entry->key = key;
121 entry->value = value;
122 int k = 0;
123
124
125 while(k <= t->elementCounter){
126 struct table_entry *i = array_1d_inspect_value(t->entries,k);
127 if(!array_1d_has_value(t->entries,k)){
128 array_1d_set_value(t->entries,entry,t->elementCounter);
129 t->elementCounter++;
130 return;
131 }
132 if (t->key_cmp_func(i->key,key)==0){
133 if(t->key_free_func!=NULL)
134 t->key_free_func(i->key);
135 if(t->value_free_func!=NULL)
136 t->value_free_func(i->value);
137 array_1d_set_value(t->entries,entry,k);
138 return;
139 }
140 k++;
141 }
142}
143/**
144 * table_lookup() - Look up a given key in a table.
145 * @table: Table to inspect.
146 * @key: Key to look up.
147 *
148 * Return: The value corresponding to a given key, or NULL if the key
149 * is not found in the table. If the table contains duplicate keys,
150 * the value that was latest inserted will be returned.
151 */
152void *table_lookup(const table *t, const void *key) {
153 int *examineValue = NULL;
154 int k = t->elementCounter;
155
156 while(k >= 0){
157 struct table_entry *i = array_1d_inspect_value(t->entries,k);
158 if (array_1d_has_value(t->entries,k) && t->key_cmp_func(i->key,key)==0){
159 examineValue = i->value;
160 return examineValue;
161 }
162 k--;
163 }
164 return NULL;
165}
166
167
168/**
169 * table_remove() - Remove a key/value pair in the table.
170 * @table: Table to manipulate.
171 * @key: Key for which to remove pair.
172 *
173 * Any matching duplicates will be removed. Will call any free
174 * functions set for keys/values. Does nothing if key is not found in
175 * the table.
176 *
177 * Returns: Nothing.
178 */
179void table_remove(table *t, const void *key) {
180
181 int k = 0;
182
183 while(k <= t->elementCounter){
184 struct table_entry *i = array_1d_inspect_value(t->entries,k);
185 if(i != NULL){
186 if (t->key_cmp_func(i->key,key)==0){
187 if(t->key_free_func!=NULL)
188 t->key_free_func(i->key);
189 if(t->value_free_func!=NULL)
190 t->value_free_func(i->value);
191 if(k != t->elementCounter-1){
192 i=array_1d_inspect_value(t->entries,t->elementCounter-1);
193 struct table_entry *i2 = malloc(sizeof(struct table_entry));
194 memmove(i2,i,sizeof(struct table_entry));
195 array_1d_set_value(t->entries,i2,k);
196 array_1d_set_value(t->entries, NULL, t->elementCounter-1);
197 }
198 else {
199 array_1d_set_value(t->entries, NULL, k);
200 }
201 t->elementCounter--;
202 return;
203 }
204 }
205 k++;
206 }
207}
208
209
210
211
212
213
214/*
215 * table_kill() - Destroy a table.
216 * @table: Table to destroy.
217 *
218 * Return all dynamic memory used by the table and its elements. If a
219 * free_func was registered for keys and/or values at table creation,
220 * it is called each element to free any user-allocated memory
221 * occupied by the element values.
222 *
223 * Returns: Nothing.
224 */
225void table_kill(table *t){
226 int k = 0;
227
228 while (k <= t->elementCounter) {
229 struct table_entry *i = array_1d_inspect_value(t->entries,k);
230 if(i != NULL){
231 if(t->key_free_func!=NULL)
232 t->key_free_func(i->key);
233 if(t->value_free_func!=NULL)
234 t->value_free_func(i->value);
235 array_1d_set_value(t->entries,NULL,k);
236 }
237 k++;
238 }
239 array_1d_kill(t->entries);
240 free(t);
241}
242
243
244void table_print(const table *t, inspect_callback_pair print_func)
245{
246struct table_entry *i;
247int k = 0;
248
249 while (k <= t->elementCounter) {
250 i = array_1d_inspect_value(t->entries,k);
251 print_func(i->key, i->value);
252 k++;
253 }
254}