adk/tools/strmap.c

   1 /*
   2  *    strmap version 1.0.0
   3  *
   4  *    ANSI C hash table for strings.
   5  *
   6  *    strmap.c
   7  *
   8  *    Copyright (c) 2009 Per Ola Kristensson.
   9  *
  10  *    Per Ola Kristensson <pok21@cam.ac.uk>
  11  *    Inference Group, Department of Physics
  12  *    University of Cambridge
  13  *    Cavendish Laboratory
  14  *    JJ Thomson Avenue
  15  *    CB3 0HE Cambridge
  16  *    United Kingdom
  17  *
  18  *    strmap is free software: you can redistribute it and/or modify
  19  *    it under the terms of the GNU Lesser General Public License as published by
  20  *    the Free Software Foundation, either version 3 of the License, or
  21  *    (at your option) any later version.
  22  *
  23  *    strmap is distributed in the hope that it will be useful,
  24  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
  25  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  26  *    GNU Lesser General Public License for more details.
  27  *
  28  *    You should have received a copy of the GNU Lesser General Public License
  29  *    along with strmap.  If not, see <http://www.gnu.org/licenses/>.
  30  */
  31 #include "strmap.h"
  32
  33 typedef struct Pair Pair;
  34
  35 typedef struct Bucket Bucket;
  36
  37 struct Pair {
  38         char *key;
  39         char *value;
  40 };
  41
  42 struct Bucket {
  43         unsigned int count;
  44         Pair *pairs;
  45 };
  46
  47 struct StrMap {
  48         unsigned int count;
  49         Bucket *buckets;
  50 };
  51
  52 static Pair * get_pair(Bucket *bucket, const char *key);
  53 static unsigned long hash(const char *str);
  54
  55 StrMap * strmap_new(unsigned int capacity)
  56 {
  57         StrMap *map;
  58
  59         map = malloc(sizeof(StrMap));
  60         if (map == NULL) {
  61                 return NULL;
  62         }
  63         map->count = capacity;
  64         map->buckets = malloc(map->count * sizeof(Bucket));
  65         if (map->buckets == NULL) {
  66                 free(map);
  67                 return NULL;
  68         }
  69         memset(map->buckets, 0, map->count * sizeof(Bucket));
  70         return map;
  71 }
  72
  73 void strmap_delete(StrMap *map)
  74 {
  75         unsigned int i, j, n, m;
  76         Bucket *bucket;
  77         Pair *pair;
  78
  79         if (map == NULL) {
  80                 return;
  81         }
  82         n = map->count;
  83         bucket = map->buckets;
  84         i = 0;
  85         while (i < n) {
  86                 m = bucket->count;
  87                 pair = bucket->pairs;
  88                 j = 0;
  89                 while(j < m) {
  90                         free(pair->key);
  91                         free(pair->value);
  92                         pair++;
  93                         j++;
  94                 }
  95                 free(bucket->pairs);
  96                 bucket++;
  97                 i++;
  98         }
  99         free(map->buckets);
 100         free(map);
 101 }
 102
 103 int strmap_get(const StrMap *map, const char *key, char *out_buf, unsigned int n_out_buf)
 104 {
 105         unsigned int index;
 106         Bucket *bucket;
 107         Pair *pair;
 108
 109         if (map == NULL) {
 110                 return 0;
 111         }
 112         if (key == NULL) {
 113                 return 0;
 114         }
 115         index = hash(key) % map->count;
 116         bucket = &(map->buckets[index]);
 117         pair = get_pair(bucket, key);
 118         if (pair == NULL) {
 119                 return 0;
 120         }
 121         if (out_buf == NULL && n_out_buf == 0) {
 122                 return strlen(pair->value) + 1;
 123         }
 124         if (out_buf == NULL) {
 125                 return 0;
 126         }
 127         if (strlen(pair->value) >= n_out_buf) {
 128                 return 0;
 129         }
 130         strcpy(out_buf, pair->value);
 131         return 1;
 132 }
 133
 134 int strmap_exists(const StrMap *map, const char *key)
 135 {
 136         unsigned int index;
 137         Bucket *bucket;
 138         Pair *pair;
 139
 140         if (map == NULL) {
 141                 return 0;
 142         }
 143         if (key == NULL) {
 144                 return 0;
 145         }
 146         index = hash(key) % map->count;
 147         bucket = &(map->buckets[index]);
 148         pair = get_pair(bucket, key);
 149         if (pair == NULL) {
 150                 return 0;
 151         }
 152         return 1;
 153 }
 154
 155 int strmap_put(StrMap *map, const char *key, const char *value)
 156 {
 157         unsigned int key_len, value_len, index;
 158         Bucket *bucket;
 159         Pair *tmp_pairs, *pair;
 160         char *tmp_value;
 161         char *new_key, *new_value;
 162
 163         if (map == NULL) {
 164                 return 0;
 165         }
 166         if (key == NULL || value == NULL) {
 167                 return 0;
 168         }
 169         key_len = strlen(key);
 170         value_len = strlen(value);
 171         /* Get a pointer to the bucket the key string hashes to */
 172         index = hash(key) % map->count;
 173         bucket = &(map->buckets[index]);
 174         /* Check if we can handle insertion by simply replacing
 175          * an existing value in a key-value pair in the bucket.
 176          */
 177         if ((pair = get_pair(bucket, key)) != NULL) {
 178                 /* The bucket contains a pair that matches the provided key,
 179                  * change the value for that pair to the new value.
 180                  */
 181                 if (strlen(pair->value) < value_len) {
 182                         /* If the new value is larger than the old value, re-allocate
 183                          * space for the new larger value.
 184                          */
 185                         tmp_value = realloc(pair->value, (value_len + 1) * sizeof(char));
 186                         if (tmp_value == NULL) {
 187                                 return 0;
 188                         }
 189                         pair->value = tmp_value;
 190                 }
 191                 /* Copy the new value into the pair that matches the key */
 192                 strcpy(pair->value, value);
 193                 return 1;
 194         }
 195         /* Allocate space for a new key and value */
 196         new_key = malloc((key_len + 1) * sizeof(char));
 197         if (new_key == NULL) {
 198                 return 0;
 199         }
 200         new_value = malloc((value_len + 1) * sizeof(char));
 201         if (new_value == NULL) {
 202                 free(new_key);
 203                 return 0;
 204         }
 205         /* Create a key-value pair */
 206         if (bucket->count == 0) {
 207                 /* The bucket is empty, lazily allocate space for a single
 208                  * key-value pair.
 209                  */
 210                 bucket->pairs = malloc(sizeof(Pair));
 211                 if (bucket->pairs == NULL) {
 212                         free(new_key);
 213                         free(new_value);
 214                         return 0;
 215                 }
 216                 bucket->count = 1;
 217         }
 218         else {
 219                 /* The bucket wasn't empty but no pair existed that matches the provided
 220                  * key, so create a new key-value pair.
 221                  */
 222                 tmp_pairs = realloc(bucket->pairs, (bucket->count + 1) * sizeof(Pair));
 223                 if (tmp_pairs == NULL) {
 224                         free(new_key);
 225                         free(new_value);
 226                         return 0;
 227                 }
 228                 bucket->pairs = tmp_pairs;
 229                 bucket->count++;
 230         }
 231         /* Get the last pair in the chain for the bucket */
 232         pair = &(bucket->pairs[bucket->count - 1]);
 233         pair->key = new_key;
 234         pair->value = new_value;
 235         /* Copy the key and its value into the key-value pair */
 236         strcpy(pair->key, key);
 237         strcpy(pair->value, value);
 238         return 1;
 239 }
 240
 241 int strmap_get_count(const StrMap *map)
 242 {
 243         unsigned int i, j, n, m;
 244         unsigned int count;
 245         Bucket *bucket;
 246         Pair *pair;
 247
 248         if (map == NULL) {
 249                 return 0;
 250         }
 251         bucket = map->buckets;
 252         n = map->count;
 253         i = 0;
 254         count = 0;
 255         while (i < n) {
 256                 pair = bucket->pairs;
 257                 m = bucket->count;
 258                 j = 0;
 259                 while (j < m) {
 260                         count++;
 261                         pair++;
 262                         j++;
 263                 }
 264                 bucket++;
 265                 i++;
 266         }
 267         return count;
 268 }
 269
 270 int strmap_enum(const StrMap *map, strmap_enum_func enum_func, const void *obj)
 271 {
 272         unsigned int i, j, n, m;
 273         Bucket *bucket;
 274         Pair *pair;
 275
 276         if (map == NULL) {
 277                 return 0;
 278         }
 279         if (enum_func == NULL) {
 280                 return 0;
 281         }
 282         bucket = map->buckets;
 283         n = map->count;
 284         i = 0;
 285         while (i < n) {
 286                 pair = bucket->pairs;
 287                 m = bucket->count;
 288                 j = 0;
 289                 while (j < m) {
 290                         enum_func(pair->key, pair->value, obj);
 291                         pair++;
 292                         j++;
 293                 }
 294                 bucket++;
 295                 i++;
 296         }
 297         return 1;
 298 }
 299
 300 /*
 301  * Returns a pair from the bucket that matches the provided key,
 302  * or null if no such pair exist.
 303  */
 304 static Pair * get_pair(Bucket *bucket, const char *key)
 305 {
 306         unsigned int i, n;
 307         Pair *pair;
 308
 309         n = bucket->count;
 310         if (n == 0) {
 311                 return NULL;
 312         }
 313         pair = bucket->pairs;
 314         i = 0;
 315         while (i < n) {
 316                 if (pair->key != NULL && pair->value != NULL) {
 317                         if (strcmp(pair->key, key) == 0) {
 318                                 return pair;
 319                         }
 320                 }
 321                 pair++;
 322                 i++;
 323         }
 324         return NULL;
 325 }
 326
 327 /*
 328  * Returns a hash code for the provided string.
 329  */
 330 static unsigned long hash(const char *str)
 331 {
 332         unsigned long hash = 5381;
 333         int c;
 334         c = 0;
 335
 336         while (c == *str++) {
 337                 hash = ((hash << 5) + hash) + c;
 338         }
 339         return hash;
 340 }
 341
 342 /*
 343
 344                    GNU LESSER GENERAL PUBLIC LICENSE
 345                        Version 3, 29 June 2007
 346
 347  Copyright (C) 2007 Free Software Foundation, Inc. <http://fsf.org/>
 348  Everyone is permitted to copy and distribute verbatim copies
 349  of this license document, but changing it is not allowed.
 350
 351
 352   This version of the GNU Lesser General Public License incorporates
 353 the terms and conditions of version 3 of the GNU General Public
 354 License, supplemented by the additional permissions listed below.
 355
 356   0. Additional Definitions.
 357
 358   As used herein, "this License" refers to version 3 of the GNU Lesser
 359 General Public License, and the "GNU GPL" refers to version 3 of the GNU
 360 General Public License.
 361
 362   "The Library" refers to a covered work governed by this License,
 363 other than an Application or a Combined Work as defined below.
 364
 365   An "Application" is any work that makes use of an interface provided
 366 by the Library, but which is not otherwise based on the Library.
 367 Defining a subclass of a class defined by the Library is deemed a mode
 368 of using an interface provided by the Library.
 369
 370   A "Combined Work" is a work produced by combining or linking an
 371 Application with the Library.  The particular version of the Library
 372 with which the Combined Work was made is also called the "Linked
 373 Version".
 374
 375   The "Minimal Corresponding Source" for a Combined Work means the
 376 Corresponding Source for the Combined Work, excluding any source code
 377 for portions of the Combined Work that, considered in isolation, are
 378 based on the Application, and not on the Linked Version.
 379
 380   The "Corresponding Application Code" for a Combined Work means the
 381 object code and/or source code for the Application, including any data
 382 and utility programs needed for reproducing the Combined Work from the
 383 Application, but excluding the System Libraries of the Combined Work.
 384
 385   1. Exception to Section 3 of the GNU GPL.
 386
 387   You may convey a covered work under sections 3 and 4 of this License
 388 without being bound by section 3 of the GNU GPL.
 389
 390   2. Conveying Modified Versions.
 391
 392   If you modify a copy of the Library, and, in your modifications, a
 393 facility refers to a function or data to be supplied by an Application
 394 that uses the facility (other than as an argument passed when the
 395 facility is invoked), then you may convey a copy of the modified
 396 version:
 397
 398    a) under this License, provided that you make a good faith effort to
 399    ensure that, in the event an Application does not supply the
 400    function or data, the facility still operates, and performs
 401    whatever part of its purpose remains meaningful, or
 402
 403    b) under the GNU GPL, with none of the additional permissions of
 404    this License applicable to that copy.
 405
 406   3. Object Code Incorporating Material from Library Header Files.
 407
 408   The object code form of an Application may incorporate material from
 409 a header file that is part of the Library.  You may convey such object
 410 code under terms of your choice, provided that, if the incorporated
 411 material is not limited to numerical parameters, data structure
 412 layouts and accessors, or small macros, inline functions and templates
 413 (ten or fewer lines in length), you do both of the following:
 414
 415    a) Give prominent notice with each copy of the object code that the
 416    Library is used in it and that the Library and its use are
 417    covered by this License.
 418
 419    b) Accompany the object code with a copy of the GNU GPL and this license
 420    document.
 421
 422   4. Combined Works.
 423
 424   You may convey a Combined Work under terms of your choice that,
 425 taken together, effectively do not restrict modification of the
 426 portions of the Library contained in the Combined Work and reverse
 427 engineering for debugging such modifications, if you also do each of
 428 the following:
 429
 430    a) Give prominent notice with each copy of the Combined Work that
 431    the Library is used in it and that the Library and its use are
 432    covered by this License.
 433
 434    b) Accompany the Combined Work with a copy of the GNU GPL and this license
 435    document.
 436
 437    c) For a Combined Work that displays copyright notices during
 438    execution, include the copyright notice for the Library among
 439    these notices, as well as a reference directing the user to the
 440    copies of the GNU GPL and this license document.
 441
 442    d) Do one of the following:
 443
 444        0) Convey the Minimal Corresponding Source under the terms of this
 445        License, and the Corresponding Application Code in a form
 446        suitable for, and under terms that permit, the user to
 447        recombine or relink the Application with a modified version of
 448        the Linked Version to produce a modified Combined Work, in the
 449        manner specified by section 6 of the GNU GPL for conveying
 450        Corresponding Source.
 451
 452        1) Use a suitable shared library mechanism for linking with the
 453        Library.  A suitable mechanism is one that (a) uses at run time
 454        a copy of the Library already present on the user's computer
 455        system, and (b) will operate properly with a modified version
 456        of the Library that is interface-compatible with the Linked
 457        Version.
 458
 459    e) Provide Installation Information, but only if you would otherwise
 460    be required to provide such information under section 6 of the
 461    GNU GPL, and only to the extent that such information is
 462    necessary to install and execute a modified version of the
 463    Combined Work produced by recombining or relinking the
 464    Application with a modified version of the Linked Version. (If
 465    you use option 4d0, the Installation Information must accompany
 466    the Minimal Corresponding Source and Corresponding Application
 467    Code. If you use option 4d1, you must provide the Installation
 468    Information in the manner specified by section 6 of the GNU GPL
 469    for conveying Corresponding Source.)
 470
 471   5. Combined Libraries.
 472
 473   You may place library facilities that are a work based on the
 474 Library side by side in a single library together with other library
 475 facilities that are not Applications and are not covered by this
 476 License, and convey such a combined library under terms of your
 477 choice, if you do both of the following:
 478
 479    a) Accompany the combined library with a copy of the same work based
 480    on the Library, uncombined with any other library facilities,
 481    conveyed under the terms of this License.
 482
 483    b) Give prominent notice with the combined library that part of it
 484    is a work based on the Library, and explaining where to find the
 485    accompanying uncombined form of the same work.
 486
 487   6. Revised Versions of the GNU Lesser General Public License.
 488
 489   The Free Software Foundation may publish revised and/or new versions
 490 of the GNU Lesser General Public License from time to time. Such new
 491 versions will be similar in spirit to the present version, but may
 492 differ in detail to address new problems or concerns.
 493
 494   Each version is given a distinguishing version number. If the
 495 Library as you received it specifies that a certain numbered version
 496 of the GNU Lesser General Public License "or any later version"
 497 applies to it, you have the option of following the terms and
 498 conditions either of that published version or of any later version
 499 published by the Free Software Foundation. If the Library as you
 500 received it does not specify a version number of the GNU Lesser
 501 General Public License, you may choose any version of the GNU Lesser
 502 General Public License ever published by the Free Software Foundation.
 503
 504   If the Library as you received it specifies that a proxy can decide
 505 whether future versions of the GNU Lesser General Public License shall
 506 apply, that proxy's public statement of acceptance of any version is
 507 permanent authorization for you to choose that version for the
 508 Library.
 509
 510 */