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