qdict.c

   1 /*
   2  * QDict Module
   3  *
   4  * Copyright (C) 2009 Red Hat Inc.
   5  *
   6  * Authors:
   7  *  Luiz Capitulino <lcapitulino@redhat.com>
   8  *
   9  * This work is licensed under the terms of the GNU LGPL, version 2.1 or later.
  10  * See the COPYING.LIB file in the top-level directory.
  11  */
  12
  13 #include "qint.h"
  14 #include "qfloat.h"
  15 #include "qdict.h"
  16 #include "qbool.h"
  17 #include "qstring.h"
  18 #include "qobject.h"
  19 #include "qemu-queue.h"
  20 #include "qemu-common.h"
  21
  22 static void qdict_destroy_obj(QObject *obj);
  23
  24 static const QType qdict_type = {
  25     .code = QTYPE_QDICT,
  26     .destroy = qdict_destroy_obj,
  27 };
  28
  29 /**
  30  * qdict_new(): Create a new QDict
  31  *
  32  * Return strong reference.
  33  */
  34 QDict *qdict_new(void)
  35 {
  36     QDict *qdict;
  37
  38     qdict = qemu_mallocz(sizeof(*qdict));
  39     QOBJECT_INIT(qdict, &qdict_type);
  40
  41     return qdict;
  42 }
  43
  44 /**
  45  * qobject_to_qdict(): Convert a QObject into a QDict
  46  */
  47 QDict *qobject_to_qdict(const QObject *obj)
  48 {
  49     if (qobject_type(obj) != QTYPE_QDICT)
  50         return NULL;
  51
  52     return container_of(obj, QDict, base);
  53 }
  54
  55 /**
  56  * tdb_hash(): based on the hash agorithm from gdbm, via tdb
  57  * (from module-init-tools)
  58  */
  59 static unsigned int tdb_hash(const char *name)
  60 {
  61     unsigned value;     /* Used to compute the hash value.  */
  62     unsigned   i;       /* Used to cycle through random values. */
  63
  64     /* Set the initial value from the key size. */
  65     for (value = 0x238F13AF * strlen(name), i=0; name[i]; i++)
  66         value = (value + (((const unsigned char *)name)[i] << (i*5 % 24)));
  67
  68     return (1103515243 * value + 12345);
  69 }
  70
  71 /**
  72  * alloc_entry(): allocate a new QDictEntry
  73  */
  74 static QDictEntry *alloc_entry(const char *key, QObject *value)
  75 {
  76     QDictEntry *entry;
  77
  78     entry = qemu_mallocz(sizeof(*entry));
  79     entry->key = qemu_strdup(key);
  80     entry->value = value;
  81
  82     return entry;
  83 }
  84
  85 /**
  86  * qdict_entry_value(): Return qdict entry value
  87  *
  88  * Return weak reference.
  89  */
  90 QObject *qdict_entry_value(const QDictEntry *entry)
  91 {
  92     return entry->value;
  93 }
  94
  95 /**
  96  * qdict_entry_key(): Return qdict entry key
  97  *
  98  * Return a *pointer* to the string, it has to be duplicated before being
  99  * stored.
 100  */
 101 const char *qdict_entry_key(const QDictEntry *entry)
 102 {
 103     return entry->key;
 104 }
 105
 106 /**
 107  * qdict_find(): List lookup function
 108  */
 109 static QDictEntry *qdict_find(const QDict *qdict,
 110                               const char *key, unsigned int bucket)
 111 {
 112     QDictEntry *entry;
 113
 114     QLIST_FOREACH(entry, &qdict->table[bucket], next)
 115         if (!strcmp(entry->key, key))
 116             return entry;
 117
 118     return NULL;
 119 }
 120
 121 /**
 122  * qdict_put_obj(): Put a new QObject into the dictionary
 123  *
 124  * Insert the pair 'key:value' into 'qdict', if 'key' already exists
 125  * its 'value' will be replaced.
 126  *
 127  * This is done by freeing the reference to the stored QObject and
 128  * storing the new one in the same entry.
 129  *
 130  * NOTE: ownership of 'value' is transferred to the QDict
 131  */
 132 void qdict_put_obj(QDict *qdict, const char *key, QObject *value)
 133 {
 134     unsigned int bucket;
 135     QDictEntry *entry;
 136
 137     bucket = tdb_hash(key) % QDICT_BUCKET_MAX;
 138     entry = qdict_find(qdict, key, bucket);
 139     if (entry) {
 140         /* replace key's value */
 141         qobject_decref(entry->value);
 142         entry->value = value;
 143     } else {
 144         /* allocate a new entry */
 145         entry = alloc_entry(key, value);
 146         QLIST_INSERT_HEAD(&qdict->table[bucket], entry, next);
 147         qdict->size++;
 148     }
 149 }
 150
 151 /**
 152  * qdict_get(): Lookup for a given 'key'
 153  *
 154  * Return a weak reference to the QObject associated with 'key' if
 155  * 'key' is present in the dictionary, NULL otherwise.
 156  */
 157 QObject *qdict_get(const QDict *qdict, const char *key)
 158 {
 159     QDictEntry *entry;
 160
 161     entry = qdict_find(qdict, key, tdb_hash(key) % QDICT_BUCKET_MAX);
 162     return (entry == NULL ? NULL : entry->value);
 163 }
 164
 165 /**
 166  * qdict_haskey(): Check if 'key' exists
 167  *
 168  * Return 1 if 'key' exists in the dict, 0 otherwise
 169  */
 170 int qdict_haskey(const QDict *qdict, const char *key)
 171 {
 172     unsigned int bucket = tdb_hash(key) % QDICT_BUCKET_MAX;
 173     return (qdict_find(qdict, key, bucket) == NULL ? 0 : 1);
 174 }
 175
 176 /**
 177  * qdict_size(): Return the size of the dictionary
 178  */
 179 size_t qdict_size(const QDict *qdict)
 180 {
 181     return qdict->size;
 182 }
 183
 184 /**
 185  * qdict_get_obj(): Get a QObject of a specific type
 186  */
 187 static QObject *qdict_get_obj(const QDict *qdict, const char *key,
 188                               qtype_code type)
 189 {
 190     QObject *obj;
 191
 192     obj = qdict_get(qdict, key);
 193     assert(obj != NULL);
 194     assert(qobject_type(obj) == type);
 195
 196     return obj;
 197 }
 198
 199 /**
 200  * qdict_get_double(): Get an number mapped by 'key'
 201  *
 202  * This function assumes that 'key' exists and it stores a
 203  * QFloat or QInt object.
 204  *
 205  * Return number mapped by 'key'.
 206  */
 207 double qdict_get_double(const QDict *qdict, const char *key)
 208 {
 209     QObject *obj = qdict_get(qdict, key);
 210
 211     assert(obj);
 212     switch (qobject_type(obj)) {
 213     case QTYPE_QFLOAT:
 214         return qfloat_get_double(qobject_to_qfloat(obj));
 215     case QTYPE_QINT:
 216         return qint_get_int(qobject_to_qint(obj));
 217     default:
 218         abort();
 219     }
 220 }
 221
 222 /**
 223  * qdict_get_int(): Get an integer mapped by 'key'
 224  *
 225  * This function assumes that 'key' exists and it stores a
 226  * QInt object.
 227  *
 228  * Return integer mapped by 'key'.
 229  */
 230 int64_t qdict_get_int(const QDict *qdict, const char *key)
 231 {
 232     QObject *obj = qdict_get_obj(qdict, key, QTYPE_QINT);
 233     return qint_get_int(qobject_to_qint(obj));
 234 }
 235
 236 /**
 237  * qdict_get_bool(): Get a bool mapped by 'key'
 238  *
 239  * This function assumes that 'key' exists and it stores a
 240  * QBool object.
 241  *
 242  * Return bool mapped by 'key'.
 243  */
 244 int qdict_get_bool(const QDict *qdict, const char *key)
 245 {
 246     QObject *obj = qdict_get_obj(qdict, key, QTYPE_QBOOL);
 247     return qbool_get_int(qobject_to_qbool(obj));
 248 }
 249
 250 /**
 251  * qdict_get_qlist(): Get the QList mapped by 'key'
 252  *
 253  * This function assumes that 'key' exists and it stores a
 254  * QList object.
 255  *
 256  * Return QList mapped by 'key'.
 257  */
 258 QList *qdict_get_qlist(const QDict *qdict, const char *key)
 259 {
 260     return qobject_to_qlist(qdict_get_obj(qdict, key, QTYPE_QLIST));
 261 }
 262
 263 /**
 264  * qdict_get_qdict(): Get the QDict mapped by 'key'
 265  *
 266  * This function assumes that 'key' exists and it stores a
 267  * QDict object.
 268  *
 269  * Return QDict mapped by 'key'.
 270  */
 271 QDict *qdict_get_qdict(const QDict *qdict, const char *key)
 272 {
 273     return qobject_to_qdict(qdict_get_obj(qdict, key, QTYPE_QDICT));
 274 }
 275
 276 /**
 277  * qdict_get_str(): Get a pointer to the stored string mapped
 278  * by 'key'
 279  *
 280  * This function assumes that 'key' exists and it stores a
 281  * QString object.
 282  *
 283  * Return pointer to the string mapped by 'key'.
 284  */
 285 const char *qdict_get_str(const QDict *qdict, const char *key)
 286 {
 287     QObject *obj = qdict_get_obj(qdict, key, QTYPE_QSTRING);
 288     return qstring_get_str(qobject_to_qstring(obj));
 289 }
 290
 291 /**
 292  * qdict_get_try_int(): Try to get integer mapped by 'key'
 293  *
 294  * Return integer mapped by 'key', if it is not present in
 295  * the dictionary or if the stored object is not of QInt type
 296  * 'def_value' will be returned.
 297  */
 298 int64_t qdict_get_try_int(const QDict *qdict, const char *key,
 299                           int64_t def_value)
 300 {
 301     QObject *obj;
 302
 303     obj = qdict_get(qdict, key);
 304     if (!obj || qobject_type(obj) != QTYPE_QINT)
 305         return def_value;
 306
 307     return qint_get_int(qobject_to_qint(obj));
 308 }
 309
 310 /**
 311  * qdict_get_try_bool(): Try to get a bool mapped by 'key'
 312  *
 313  * Return bool mapped by 'key', if it is not present in the
 314  * dictionary or if the stored object is not of QBool type
 315  * 'def_value' will be returned.
 316  */
 317 int qdict_get_try_bool(const QDict *qdict, const char *key, int def_value)
 318 {
 319     QObject *obj;
 320
 321     obj = qdict_get(qdict, key);
 322     if (!obj || qobject_type(obj) != QTYPE_QBOOL)
 323         return def_value;
 324
 325     return qbool_get_int(qobject_to_qbool(obj));
 326 }
 327
 328 /**
 329  * qdict_get_try_str(): Try to get a pointer to the stored string
 330  * mapped by 'key'
 331  *
 332  * Return a pointer to the string mapped by 'key', if it is not present
 333  * in the dictionary or if the stored object is not of QString type
 334  * NULL will be returned.
 335  */
 336 const char *qdict_get_try_str(const QDict *qdict, const char *key)
 337 {
 338     QObject *obj;
 339
 340     obj = qdict_get(qdict, key);
 341     if (!obj || qobject_type(obj) != QTYPE_QSTRING)
 342         return NULL;
 343
 344     return qstring_get_str(qobject_to_qstring(obj));
 345 }
 346
 347 /**
 348  * qdict_iter(): Iterate over all the dictionary's stored values.
 349  *
 350  * This function allows the user to provide an iterator, which will be
 351  * called for each stored value in the dictionary.
 352  */
 353 void qdict_iter(const QDict *qdict,
 354                 void (*iter)(const char *key, QObject *obj, void *opaque),
 355                 void *opaque)
 356 {
 357     int i;
 358     QDictEntry *entry;
 359
 360     for (i = 0; i < QDICT_BUCKET_MAX; i++) {
 361         QLIST_FOREACH(entry, &qdict->table[i], next)
 362             iter(entry->key, entry->value, opaque);
 363     }
 364 }
 365
 366 static QDictEntry *qdict_next_entry(const QDict *qdict, int first_bucket)
 367 {
 368     int i;
 369
 370     for (i = first_bucket; i < QDICT_BUCKET_MAX; i++) {
 371         if (!QLIST_EMPTY(&qdict->table[i])) {
 372             return QLIST_FIRST(&qdict->table[i]);
 373         }
 374     }
 375
 376     return NULL;
 377 }
 378
 379 /**
 380  * qdict_first(): Return first qdict entry for iteration.
 381  */
 382 const QDictEntry *qdict_first(const QDict *qdict)
 383 {
 384     return qdict_next_entry(qdict, 0);
 385 }
 386
 387 /**
 388  * qdict_next(): Return next qdict entry in an iteration.
 389  */
 390 const QDictEntry *qdict_next(const QDict *qdict, const QDictEntry *entry)
 391 {
 392     QDictEntry *ret;
 393
 394     ret = QLIST_NEXT(entry, next);
 395     if (!ret) {
 396         unsigned int bucket = tdb_hash(entry->key) % QDICT_BUCKET_MAX;
 397         ret = qdict_next_entry(qdict, bucket + 1);
 398     }
 399
 400     return ret;
 401 }
 402
 403 /**
 404  * qentry_destroy(): Free all the memory allocated by a QDictEntry
 405  */
 406 static void qentry_destroy(QDictEntry *e)
 407 {
 408     assert(e != NULL);
 409     assert(e->key != NULL);
 410     assert(e->value != NULL);
 411
 412     qobject_decref(e->value);
 413     qemu_free(e->key);
 414     qemu_free(e);
 415 }
 416
 417 /**
 418  * qdict_del(): Delete a 'key:value' pair from the dictionary
 419  *
 420  * This will destroy all data allocated by this entry.
 421  */
 422 void qdict_del(QDict *qdict, const char *key)
 423 {
 424     QDictEntry *entry;
 425
 426     entry = qdict_find(qdict, key, tdb_hash(key) % QDICT_BUCKET_MAX);
 427     if (entry) {
 428         QLIST_REMOVE(entry, next);
 429         qentry_destroy(entry);
 430         qdict->size--;
 431     }
 432 }
 433
 434 /**
 435  * qdict_destroy_obj(): Free all the memory allocated by a QDict
 436  */
 437 static void qdict_destroy_obj(QObject *obj)
 438 {
 439     int i;
 440     QDict *qdict;
 441
 442     assert(obj != NULL);
 443     qdict = qobject_to_qdict(obj);
 444
 445     for (i = 0; i < QDICT_BUCKET_MAX; i++) {
 446         QDictEntry *entry = QLIST_FIRST(&qdict->table[i]);
 447         while (entry) {
 448             QDictEntry *tmp = QLIST_NEXT(entry, next);
 449             QLIST_REMOVE(entry, next);
 450             qentry_destroy(entry);
 451             entry = tmp;
 452         }
 453     }
 454
 455     qemu_free(qdict);
 456 }