1/*************************************************** 2 * File name: dict.c 3 * 4 * Copyright (C) 2015, Broadcom Corporation. All Rights Reserved. 5 * 6 * Permission to use, copy, modify, and/or distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 13 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION 15 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 16 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 * 18 * First written on 03/08/2010 by Toni Homedes i Saun. 19 * 20 ***************************************************/ 21/** \file dict.c 22 */ 23/** \defgroup dict Simple Dictionnary 24 * 25 * \ingroup gigled Gigle Daemon 26 * 27 * \brief Simple key/value dictionary implementation 28 * 29 * Simples't possible implementation of a dictionary. Expected number of 30 * entries is very low (about 10~20) so emphasis has been given to simplicity 31 * to reduce risk 32 * 33 * The dictionnary is based on a single linked list and a head pointer. 34 * Elements are always unshifted at the front of the list; no order is kept. 35 * 36 * $Id: dict.c 298543 2011-11-24 01:30:47Z $ 37 */ 38/*@{*/ 39 40/*************************************************** 41* Include section 42***************************************************/ 43 44/* FILE-CSTYLED */ 45 46#include "dict.h" 47 48#include <errno.h> 49#include <stdio.h> 50#include <stdlib.h> 51#include <string.h> 52 53/*************************************************** 54 * Local Defines Section 55 ***************************************************/ 56 57/*************************************************** 58 * Local Constants Section 59 ***************************************************/ 60 61/*************************************************** 62 * Local Typedefs Section 63 ***************************************************/ 64 65/** \brief Dict list node 66 */ 67typedef struct s_dict_node { 68 struct s_dict_node *next; /**< \brief Pointer to next node of NULL if NIL */ 69 char * key; /**< \brief Pointer to malloc'ed key copy */ 70 char * value; /**< \brief Pointer to malloc'ed value copy */ 71} 72 t_dict_node; 73 74/*************************************************** 75 * Local Variables Section 76 ***************************************************/ 77 78/** This macro for easier rewriting */ 79#define Dict_head (*(t_dict_node **)dict) 80 81/************************************************** 82 * Function Prototype Section 83 * Add prototypes for all local functions defined 84 * in this file 85 ***************************************************/ 86static t_dict_node *DictInternalFind(dict_hdl_t dict, const char * const key); 87static void DictInternalFreeNode(t_dict_node ** const p); 88 89/*************************************************** 90 * Function Definition Section 91 * Define all public and local functions from now on 92 **************************************************/ 93 94/************************************************** 95 * Function name : static t_dict_node *DictInternalFind(const char * const key) 96 * Created by : Toni Homedes i Saun 97 * Date created : 03-08-2010 98 * Notes : Public function 99 * Restrictions (pre-conditions) 100 * Odd modes (post-conditions) 101 **************************************************/ 102/** \brief Searches for given key and returns pointer to the whole node 103 * 104 * \param[in] key Pointer to the key to search for 105 * 106 * \return Pointer to the found node or NULL if not 107 * 108 **************************************************/ 109static t_dict_node *DictInternalFind(const dict_hdl_t dict, const char * const key) 110{ 111 t_dict_node *p; 112 113 /* run over list looking for key */ 114 for (p = Dict_head; p; p = p->next) 115 if (!strcmp(key, p->key)) 116 break; 117 return p; 118} 119 120/************************************************** 121 * Function name : static void DictInternalFreeNode(t_dict_node ** const p) 122 * Created by : Toni Homedes i Saun 123 * Date created : 03-08-2010 124 * Notes : Public function 125 * Restrictions (pre-conditions) 126 * Odd modes (post-conditions) 127 **************************************************/ 128/** \brief Frees passed node and related mallocs and relinks list 129 * 130 * \param[in,out] p Pointer to the pointer holding node to delete 131 * 132 **************************************************/ 133static void DictInternalFreeNode(t_dict_node ** const p) 134{ 135 if (*p) 136 { 137 t_dict_node *tmp = (*p)->next; 138 free((*p)->key); 139 free((*p)->value); 140 free(*p); 141 *p = tmp; 142 } 143} 144 145/************************************************** 146 * Function name : dict_hdl_t DictNew(void) 147 * Created by : Toni Homedes i Saun 148 * Date created : 05-10-2010 149 * Notes : Public function 150 * Restrictions (pre-conditions) 151 * Odd modes (post-conditions) 152 **************************************************/ 153/** \brief Creates a new Dictionary 154 * 155 * \return New dictionnary handle 156 * 157 **************************************************/ 158dict_hdl_t DictNew(void) 159{ 160 t_dict_node * const *dict = malloc(sizeof (t_dict_node*)); 161 if (!dict) 162 { 163 perror("Can't get memory for dict handle"); 164 exit(EXIT_FAILURE); 165 } 166 Dict_head = NULL; 167 return (dict_hdl_t)dict; 168} 169 170/************************************************** 171 * Function name : static t_dict_node *DictInternalFind(const char * const key) 172 * Created by : Toni Homedes i Saun 173 * Date created : 03-08-2010 174 * Notes : Public function 175 * Restrictions (pre-conditions) 176 * Odd modes (post-conditions) 177 **************************************************/ 178/** \brief Searches for given key and returns pointer to the whole node 179 * 180 * \param[in] key Pointer to the key to search for 181 * 182 * \return Pointer to the found node or NULL if not 183 * 184 **************************************************/ 185void DictFree(dict_hdl_t dict) 186{ 187 if (dict) 188 DictDoEmpty(dict); 189 190 free((void *)dict); 191} 192 193/************************************************** 194 * Function name : void DictSet(const char * const key, const char * const 195 * value) 196 * Created by : Toni Homedes i Saun 197 * Date created : 03-08-2010 198 * Notes : Public function 199 * Restrictions (pre-conditions) 200 * Odd modes (post-conditions) 201 **************************************************/ 202/** \brief Sets given value in the dictionary 203 * 204 * \param[in] key Key to store 205 * \param[in] value Value to store 206 * 207 **************************************************/ 208void DictSet(const dict_hdl_t dict, const char * const key, const char * const 209 value) 210{ 211 t_dict_node *node = DictInternalFind(dict, key); 212 213 if (node) 214 { 215 if (strcmp(node->value, value)) 216 { 217 free(node->value); 218 node->value = strdup(value); 219 } 220 } 221 else 222 { 223 /* Inset new node in linked list */ 224 /* for this application we are assuming we'll never run out of memory */ 225 node = malloc(sizeof *node); 226 node->key = strdup(key); 227 node->value = strdup(value); 228 node->next = Dict_head; 229 Dict_head = node; 230 } 231} 232 233/************************************************** 234 * Function name : const char *DictGet(const char * const key) 235 * value) 236 * Created by : Toni Homedes i Saun 237 * Date created : 03-08-2010 238 * Notes : Public function 239 * Restrictions (pre-conditions) 240 * Odd modes (post-conditions) 241 **************************************************/ 242/** \brief Gets a key's value from the dictionnary 243 * 244 * \param[in] key Key to store 245 * 246 * \returns value if found or NULL if not 247 * 248 **************************************************/ 249const char *DictGet(const dict_hdl_t dict, const char * const key) 250{ 251 t_dict_node *node = DictInternalFind(dict, key); 252 return node ? node->value : NULL; 253} 254 255/************************************************** 256 * Function name : void DictDelete(const char * const key) 257 * Created by : Toni Homedes i Saun 258 * Date created : 03-08-2010 259 * Notes : Public function 260 * Restrictions (pre-conditions) 261 * Odd modes (post-conditions) 262 **************************************************/ 263/** \brief Deletes given value from the dictionary 264 * 265 * \param[in] key Key to delete 266 * 267 **************************************************/ 268void DictDelete(const dict_hdl_t dict, const char * const key) 269{ 270 t_dict_node **p; 271 272 /* run over list looking for key keeping a * to previous for relinking */ 273 for (p = &Dict_head; *p; p = &(*p)->next) 274 if (!strcmp(key, (*p)->key)) 275 break; 276 277 DictInternalFreeNode(p); 278} 279 280/************************************************** 281 * Function name : int DictIsEmpty(void) 282 * Created by : Toni Homedes i Saun 283 * Date created : 03-08-2010 284 * Notes : Public function 285 * Restrictions (pre-conditions) 286 * Odd modes (post-conditions) 287 **************************************************/ 288/** \brief Checks if the dictionary is empty 289 * 290 **************************************************/ 291int DictIsEmpty(const dict_hdl_t dict) 292{ 293 return NULL == Dict_head; 294} 295 296/************************************************** 297 * Function name : void DictDoEmpty(void) 298 * Created by : Toni Homedes i Saun 299 * Date created : 03-08-2010 300 * Notes : Public function 301 * Restrictions (pre-conditions) 302 * Odd modes (post-conditions) 303 **************************************************/ 304/** \brief Empties the dictionary 305 * 306 **************************************************/ 307void DictDoEmpty(const dict_hdl_t dict) 308{ 309 while (Dict_head) 310 { 311 DictInternalFreeNode(&Dict_head); 312 } 313} 314 315/************************************************** 316 * Function name : void DictMap(void (*fn)(const char *key, const char *value)) 317 * Created by : Toni Homedes i Saun 318 * Date created : 03-08-2010 319 * Notes : Public function 320 * Restrictions (pre-conditions) 321 * Odd modes (post-conditions) 322 **************************************************/ 323/** \brief Maps a function on all dictionary entries. Order is random. 324 * 325 * \param[in] fn Fucntion to be mapped 326 * 327 **************************************************/ 328void DictMap(const dict_hdl_t dict, void (*fn)(const char *key, const char *value)) 329{ 330 t_dict_node *p; 331 for (p = Dict_head; p; p = p->next) 332 fn(p->key, p->value); 333} 334 335/************************************************** 336 * Function name : dict_iterator_t DictIteratorNew(dict_hdl_t dict) 337 * value) 338 * Created by : Toni Homedes i Saun 339 * Date created : 06-10-2010 340 * Notes : Public function 341 * Restrictions (pre-conditions) 342 * Odd modes (post-conditions) 343 **************************************************/ 344/** \brief Create a new Dict Iterator 345 * 346 * \param[in] dict Dictionnary 347 * 348 **************************************************/ 349dict_iterator_t DictIteratorNew(dict_hdl_t dict) 350{ 351 t_dict_node ** const iterator = malloc(sizeof (t_dict_node*)); 352 if (!iterator) 353 { 354 perror("Can't get memory for iterator handle"); 355 exit(EXIT_FAILURE); 356 } 357 *iterator = Dict_head; 358 return (dict_iterator_t)iterator; 359} 360 361/************************************************** 362 * Function name : void DictSet(const char * const key, const char * const 363 * value) 364 * Created by : Toni Homedes i Saun 365 * Date created : 06-10-2010 366 * Notes : Public function 367 * Restrictions (pre-conditions) 368 * Odd modes (post-conditions) 369 **************************************************/ 370/** \brief Destroys given iterator 371 * 372 * \param[in] iterator Iterator to destroy 373 * 374 **************************************************/ 375void DictIteratorFree(dict_iterator_t iterator) 376{ 377 free((void *)iterator); 378} 379 380/************************************************** 381 * Function name : const char *DictIteratorKey(dict_iterator_t iterator) 382 * Created by : Toni Homedes i Saun 383 * Date created : 06-10-2010 384 * Notes : Public function 385 * Restrictions (pre-conditions) 386 * Odd modes (post-conditions) 387 **************************************************/ 388/** \brief Returns key for given iterator 389 * 390 * \param[in] iterator Iterator to use 391 * 392 **************************************************/ 393const char *DictIteratorKey(dict_iterator_t iterator) 394{ 395 t_dict_node **p = (t_dict_node **)iterator; 396 397 return *p ? (*p)->key : NULL; 398} 399 400/************************************************** 401 * Function name : void DictSet(const char * const key, const char * const 402 * value) 403 * Created by : Toni Homedes i Saun 404 * Date created : 06-10-2010 405 * Notes : Public function 406 * Restrictions (pre-conditions) 407 * Odd modes (post-conditions) 408 **************************************************/ 409/** \brief Advances given iterator 410 * 411 * \param[in] iterator Iterator to advance 412 * 413 **************************************************/ 414int DictIteratorAdvance(dict_iterator_t iterator) 415{ 416 t_dict_node **p = (t_dict_node **)iterator; 417 418 if (*p) 419 *p = (*p)->next; 420 421 return *p != NULL; 422} 423 424/*@}*/ 425