Annotation of gpl/axl/src/axl_hash.c, revision 1.1
1.1 ! misho 1: /*
! 2: * LibAxl: Another XML library
! 3: * Copyright (C) 2006 Advanced Software Production Line, S.L.
! 4: *
! 5: * This program is free software; you can redistribute it and/or
! 6: * modify it under the terms of the GNU Lesser General Public License
! 7: * as published by the Free Software Foundation; either version 2.1 of
! 8: * the License, or (at your option) any later version.
! 9: *
! 10: * This program is distributed in the hope that it will be useful,
! 11: * but WITHOUT ANY WARRANTY; without even the implied warranty of
! 12: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
! 13: * GNU Lesser General Public License for more details.
! 14: *
! 15: * You should have received a copy of the GNU Lesser General Public
! 16: * License along with this program; if not, write to the Free
! 17: * Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
! 18: * 02111-1307 USA
! 19: *
! 20: * You may find a copy of the license under this software is released
! 21: * at COPYING file. This is LGPL software: you are welcome to
! 22: * develop proprietary applications using this library without any
! 23: * royalty or fee but returning back any change, improvement or
! 24: * addition in the form of source code, project image, documentation
! 25: * patches, etc.
! 26: *
! 27: * For commercial support on build XML enabled solutions contact us:
! 28: *
! 29: * Postal address:
! 30: * Advanced Software Production Line, S.L.
! 31: * Edificio Alius A, Oficina 102,
! 32: * C/ Antonio Suarez Nº 10,
! 33: * Alcalá de Henares 28802 Madrid
! 34: * Spain
! 35: *
! 36: * Email address:
! 37: * info@aspl.es - http://www.aspl.es/xml
! 38: */
! 39: #include <axl_hash.h>
! 40: #include <axl_factory.h>
! 41: #include <axl_log.h>
! 42:
! 43: #define LOG_DOMAIN "axl-hash"
! 44:
! 45: /**
! 46: * \defgroup axl_hash_module Axl Hash: A hash table used by Axl Library
! 47: */
! 48:
! 49: /**
! 50: * \addtogroup axl_hash_module
! 51: * @{
! 52: */
! 53:
! 54: typedef struct _axlHashNode axlHashNode;
! 55:
! 56: struct _axlHashNode {
! 57: /* the key stored and the destroy function */
! 58: axlPointer key;
! 59: axlDestroyFunc key_destroy;
! 60:
! 61: /* the data stored and the destroy function */
! 62: axlPointer data;
! 63: axlDestroyFunc data_destroy;
! 64:
! 65: /* a pointer to the next item */
! 66: axlHashNode * next;
! 67: };
! 68:
! 69: struct _axlHash {
! 70: /* the hash function */
! 71: axlHashFunc hash;
! 72: axlEqualFunc equal;
! 73:
! 74: /* the hash table, implemented using chaining for collition
! 75: * resolution. */
! 76: axlHashNode ** table;
! 77:
! 78: /* factory to allocate nodes */
! 79: axlFactory * factory;
! 80:
! 81: /* stored items in the hash */
! 82: int items;
! 83:
! 84: /* the hash size */
! 85: int hash_size;
! 86:
! 87: /* steps: how many slots are allocated when the hash is
! 88: * resized */
! 89: int step;
! 90: };
! 91:
! 92: /**
! 93: * @internal Implementation of the axl hash cursor.
! 94: */
! 95: struct _axlHashCursor {
! 96: /* a pointer to the hash */
! 97: axlHash * hash;
! 98:
! 99: /* a pointer to the node inside the hash (current value) */
! 100: axlHashNode * node;
! 101:
! 102: /* the value if the index being accessed by the node
! 103: * pointed (current value) */
! 104: int index;
! 105: };
! 106:
! 107: /**
! 108: * @brief Public hash implementation for keys that are strings.
! 109: *
! 110: * @param _key The string key to hash.
! 111: *
! 112: * @return A value associated to the key.
! 113: */
! 114: unsigned int axl_hash_string (axlPointer _key)
! 115: {
! 116: /* never is received a NULL value at this function, so, don't
! 117: * check it */
! 118: int g, h = 0;
! 119: char * key = _key;
! 120:
! 121: /* hashing taken from the Red Dragon book!! */
! 122: while (*key) {
! 123: h = (h << 4) + *key;
! 124: if ((g = h & 0xF0000000) != 0) {
! 125: h ^= g >> 24;
! 126: h ^= g;
! 127: }
! 128:
! 129: ++ key;
! 130: } /* end while */
! 131:
! 132: /* return the value */
! 133: return h;
! 134: }
! 135:
! 136: /**
! 137: * @brief Common equal hash function associated to \ref
! 138: * axl_hash_string that allows to check two keys to be equal,
! 139: * conforming to the results expected by the hash (\ref axlHash).
! 140: *
! 141: * @param keya The key to compare.
! 142: *
! 143: * @param keyb The other key to compare.
! 144: *
! 145: * @return 0 if both strings are equal and any other else value when
! 146: * they differs.
! 147: */
! 148: int axl_hash_equal_string (axlPointer keya,
! 149: axlPointer keyb)
! 150: {
! 151: char * _keya = keya;
! 152: char * _keyb = keyb;
! 153: int i = 0;
! 154:
! 155: while (_keya [i] != 0 && _keyb [i] != 0) {
! 156:
! 157: /* check values */
! 158: if (_keya [i] != _keyb [i])
! 159: return 1;
! 160:
! 161: /* update the iterator */
! 162: i++;
! 163: } /* end while */
! 164:
! 165: /* check that both string ends at the same point */
! 166: if (_keya [i] != 0 || _keyb [i] != 0)
! 167: return 1;
! 168:
! 169: /* both keys are equal */
! 170: return 0;
! 171: }
! 172:
! 173: /**
! 174: * @brief Convenience hashing function to store keys that are
! 175: * integers.
! 176: *
! 177: * @param key The key that is supported to contain a int value stored
! 178: * using \ref INT_TO_PTR.
! 179: *
! 180: * @return The index in the hash where is located the associated data.
! 181: */
! 182: unsigned int axl_hash_int (axlPointer key)
! 183: {
! 184: int value = PTR_TO_INT (key);
! 185:
! 186: return (unsigned int) value;
! 187: }
! 188:
! 189: /**
! 190: * @brief Convenience hash function to compare two keys that holds
! 191: * integers values.
! 192: *
! 193: * @param keya The first key to compare.
! 194: * @param keyb The second key to compare.
! 195: *
! 196: * @return 0 if both keys are equal, 1 if not.
! 197: */
! 198: int axl_hash_equal_int (axlPointer keya,
! 199: axlPointer keyb)
! 200: {
! 201: /* return if both keys containing int values are equal */
! 202: return (PTR_TO_INT (keya) == PTR_TO_INT(keyb)) ? 0 : 1;
! 203: }
! 204:
! 205:
! 206: /**
! 207: * @internal Internal lookup function, returns the hole hash node.
! 208: *
! 209: * @param hash The hash where the lookup will be performed.
! 210: *
! 211: * @param key The key that is being looked up.
! 212: *
! 213: * @return The axlHashNode reference or NULL if not found.
! 214: */
! 215: axlHashNode * __axl_hash_internal_lookup (axlHash * hash, axlPointer key)
! 216: {
! 217: axlHashNode * node;
! 218:
! 219: axl_return_val_if_fail (hash, NULL);
! 220:
! 221: /* get the node at the provided position */
! 222: if (hash->hash_size == 0)
! 223: return NULL;
! 224: node = hash->table [hash->hash (key) % hash->hash_size];
! 225:
! 226: /* node not found */
! 227: if (node == NULL)
! 228: return NULL;
! 229:
! 230: /* check for equal keys */
! 231: if (hash->equal (node->key, key) == 0)
! 232: return node;
! 233:
! 234: while (node->next != NULL) {
! 235: /* seems we have more nodes */
! 236: node = node->next;
! 237:
! 238: /* check for equal keys */
! 239: if (hash->equal (node->key, key) == 0)
! 240: return node;
! 241: } /* end */
! 242:
! 243: /* node not found */
! 244: return NULL;
! 245: }
! 246:
! 247: /**
! 248: * @brief Creates a new hash table using the function provided as
! 249: * hashing function.
! 250: *
! 251: * The hash function (\ref axlHashFunc) allows the hash table to
! 252: * distribute values across the table while performing inserts
! 253: * operation but it is also used while getting data from the table.
! 254: *
! 255: * A second function is required (\ref axlEqualFunc) to resolve
! 256: * internal table conflicts while placing data that are indexed using
! 257: * the same value generated by \ref axlHashFunc. This hash
! 258: * implementation store items at the giving position using a linked
! 259: * list (Chaining collition resolution). Knowing this, an external
! 260: * function is required to compare items to ensure they are selected
! 261: * properly.
! 262: *
! 263: * This hash accept any kind of key and values to be stored as long as
! 264: * the provided functions returns different identifiers to store
! 265: * items. However, because the common use of a hash is to store data
! 266: * using strings as keys two functions are provided by default to
! 267: * create a string index hash table: \ref axl_hash_equal_string and
! 268: * \ref axl_hash_string.
! 269: *
! 270: * \code
! 271: * // create a string indexed hash
! 272: * axlHash * hash = axl_hash_new (axl_hash_string, axl_hash_equal_string);
! 273: * \endcode
! 274: *
! 275: * Additionally, two functions are provided to create hash containing
! 276: * integer values as keys: \ref axl_hash_int and \ref axl_hash_equal_int.
! 277: *
! 278: * Once the hash is created the following functions must be used to
! 279: * store data:
! 280: *
! 281: * - \ref axl_hash_insert
! 282: * - \ref axl_hash_insert_full
! 283: *
! 284: * Then, use the following function to get data associated to the
! 285: * provided key.
! 286: *
! 287: * - \ref axl_hash_get
! 288: *
! 289: * Finally, you can use the following functions to either remove items
! 290: * from the hash and to completely deallocate the memory used by the
! 291: * hash and all of its data:
! 292: *
! 293: * - \ref axl_hash_remove
! 294: * - \ref axl_hash_free
! 295: *
! 296: *
! 297: * @param hash The hashing function to be used for this table.
! 298: *
! 299: * @param equal The equal function used by the hash to actually check
! 300: * that two stored items are equal (using the key value)
! 301: *
! 302: * @return A newly created hash table that is deallocated by using \ref axl_hash_free.
! 303: */
! 304: axlHash * axl_hash_new (axlHashFunc hash, axlEqualFunc equal)
! 305: {
! 306: /* call to full implementation */
! 307: return axl_hash_new_full (hash, equal, 10);
! 308: }
! 309:
! 310: /**
! 311: * @brief The function works the same way like \ref axl_hash_new, but
! 312: * provides a way to configure how many unit are allocated on hash
! 313: * resizing operations.
! 314: *
! 315: * See \ref axl_hash_new for more information. That function uses a
! 316: * default step value equal to 10.
! 317: *
! 318: * @param hash The hashing function to be used for this table.
! 319: *
! 320: * @param equal The equal function used by the hash to actually check
! 321: * that two stored items are equal (using the key value)
! 322: *
! 323: * @param step The number of empty new slots to allocate once the hash
! 324: * must be resized.
! 325: *
! 326: * @return A newly created hash table that is deallocated by using \ref axl_hash_free.
! 327: */
! 328: axlHash * axl_hash_new_full (axlHashFunc hash,
! 329: axlEqualFunc equal,
! 330: int step)
! 331: {
! 332: /* create the hash */
! 333: axlHash * result;
! 334:
! 335: result = axl_new (axlHash, 1);
! 336: result->factory = axl_factory_create (sizeof (axlHashNode));
! 337: result->hash = hash;
! 338: result->equal = equal;
! 339: result->step = step;
! 340:
! 341: /* return the hash table created */
! 342: return result;
! 343: }
! 344:
! 345: /**
! 346: * @brief Inserts a key index value into the provided hash table.
! 347: *
! 348: * The function will store the data provided on the hash setting no
! 349: * destroy function for the key and the data stored. See \ref
! 350: * axl_hash_insert_full for more details.
! 351: *
! 352: * <b>NOTE:</b> The insert operation will replace a previously
! 353: * inserted item with the same key. If no item is found, and insert
! 354: * will take place, otherwise previous item is replaced calling to the
! 355: * key destroy and data destroy defined.
! 356: *
! 357: * @param hash The hash table where the insert operation will be
! 358: * produced.
! 359: *
! 360: * @param key The key to store in the hash table. If the key is found,
! 361: * previous data is replaced, storing this new key and the value
! 362: * provided.
! 363: *
! 364: * @param data The data to store associated to the provided key.
! 365: */
! 366: void axl_hash_insert (axlHash * hash,
! 367: axlPointer key,
! 368: axlPointer data)
! 369: {
! 370: /* call to the full implementation */
! 371: axl_hash_insert_full (hash, key, NULL, data, NULL);
! 372:
! 373: /* nothing more to do */
! 374: return;
! 375: }
! 376:
! 377: /**
! 378: * @internal Function used to create the node that will be stored in
! 379: * the hash.
! 380: */
! 381: #define __axl_hash_create_node(factory, node, key, key_destroy, data, data_destroy)\
! 382: node = axl_factory_get (factory);\
! 383: node->key = key;\
! 384: node->key_destroy = key_destroy;\
! 385: node->data = data;\
! 386: node->data_destroy = data_destroy;
! 387:
! 388: /**
! 389: * @internal Function that performs the hash insertion for the
! 390: * selected node.
! 391: */
! 392: #define __axl_hash_insert_node(_pos,_hash,_key,_node,_increase)\
! 393: _pos = (_hash->hash (_key)) % _hash->hash_size;\
! 394: _node->next = _hash->table [_pos];\
! 395: _hash->table [pos] = _node;\
! 396: if (_increase)\
! 397: _hash->items++;
! 398:
! 399: /**
! 400: * @brief Inserts a key value into the provided hash table, allowing
! 401: * to provide deallocation functions for the key and the data to be
! 402: * stored.
! 403: *
! 404: * <b>NOTE:</b> The insert operation will replace a previously
! 405: * inserted item with the same key. If no item is found, an insert
! 406: * will take place, otherwise previous item is replaced calling to the
! 407: * key destroy and data destroy functions defined.
! 408: *
! 409: * @param hash The hash table where the data will be added.
! 410: *
! 411: * @param key The key to store in the hash table. If the key is found,
! 412: * previous data is replaced, storing this new key and the value
! 413: * provided.
! 414: *
! 415: * @param key_destroy An optional destroy function that will be called
! 416: * to deallocate the key provided.
! 417: *
! 418: * @param data The data to store associated to the provided key.
! 419: *
! 420: * @param data_destroy An optional destroy function that will be
! 421: * called to deallocate the data provided.
! 422: */
! 423: void axl_hash_insert_full (axlHash * hash,
! 424: axlPointer key,
! 425: axlDestroyFunc key_destroy,
! 426: axlPointer data,
! 427: axlDestroyFunc data_destroy)
! 428: {
! 429: int pos = 0;
! 430: axlHashNode * node = NULL;
! 431: axlHashNode * aux = NULL;
! 432: int iterator = 0;
! 433:
! 434: /* check incoming data */
! 435: axl_return_if_fail (hash);
! 436:
! 437: /* check the really basic case where the hash has no data
! 438: * stored yet. */
! 439: if (hash->hash_size == 0) {
! 440: /* allocate memory for the hash */
! 441: hash->table = axl_new (axlHashNode *, hash->step);
! 442: hash->hash_size = hash->step;
! 443:
! 444: /* create the node to store */
! 445: __axl_hash_create_node (hash->factory, node, key, key_destroy, data, data_destroy);
! 446:
! 447: /* insert the node into the hash */
! 448: __axl_hash_insert_node (pos, hash, key, node, axl_true);
! 449:
! 450: return;
! 451: }
! 452:
! 453: /* now check for a more complex case */
! 454: node = __axl_hash_internal_lookup (hash, key);
! 455:
! 456: /* if the node is not found and the hash size can't hold more items, expand it and rehash */
! 457: if ((hash->hash_size == hash->items) && (node == NULL)) {
! 458: /* seems we need to rehash items, reallocating enough
! 459: * memory */
! 460:
! 461: /* before allocating more memory, extract all items to
! 462: * be reallocated */
! 463: iterator = 0;
! 464: node = NULL;
! 465: while (iterator < hash->hash_size) {
! 466:
! 467: /* check for content */
! 468: if (hash->table[iterator] != NULL) {
! 469: /* check if node has been initialized,
! 470: * and set it to the first position */
! 471: if (node == NULL) {
! 472: /* configure init node position */
! 473: node = hash->table[iterator];
! 474:
! 475: /* and last aux position */
! 476: aux = node;
! 477: while (aux->next != NULL) {
! 478: /* update reference */
! 479: aux = aux->next;
! 480: }
! 481:
! 482: } else {
! 483: /* make aux to point to the next list */
! 484: aux->next = hash->table[iterator];
! 485:
! 486: /* and while the last item is not
! 487: * reached, move aux to point to the
! 488: * last item of the chain */
! 489: while (aux->next != NULL) {
! 490: /* update reference */
! 491: aux = aux->next;
! 492: }
! 493: }
! 494: } /* end if */
! 495:
! 496: /* update the iterator */
! 497: iterator++;
! 498: }
! 499:
! 500: /* now we have in node a complete list of items
! 501: * stored, allocate more memory and rehash */
! 502: hash->hash_size += hash->step;
! 503: hash->table = realloc (hash->table, sizeof (axlHashNode *) * (hash->hash_size));
! 504:
! 505: /* clear the table */
! 506: memset (hash->table, 0, sizeof (axlHashNode*) * (hash->hash_size));
! 507:
! 508: /* for each item inside the list rehash it */
! 509: while (node != NULL) {
! 510: /* store next item to rehash in aux */
! 511: aux = node->next;
! 512:
! 513: /* insert the node into the hash */
! 514: __axl_hash_insert_node (pos, hash, node->key, node, axl_false);
! 515:
! 516: /* update the reference */
! 517: node = aux;
! 518: } /* end while */
! 519:
! 520: /* clear node reference */
! 521: node = NULL;
! 522: } /* rehashing if end */
! 523:
! 524: /* we have enough space to store the item create the
! 525: node to store */
! 526: if (node == NULL) {
! 527: /* create a new node */
! 528: __axl_hash_create_node (hash->factory, node, key, key_destroy, data, data_destroy);
! 529:
! 530: /* insert the node into the hash as usual */
! 531: __axl_hash_insert_node (pos, hash, key, node, axl_true);
! 532: } else {
! 533: /* don't create a node, replace previous content and use new content */
! 534: if (node->key_destroy != NULL) {
! 535: node->key_destroy (node->key);
! 536: }
! 537: if (node->data_destroy != NULL) {
! 538: node->data_destroy (node->data);
! 539: }
! 540:
! 541: /* now use new data */
! 542: node->key = key;
! 543: node->key_destroy = key_destroy;
! 544: node->data = data;
! 545: node->data_destroy = data_destroy;
! 546: }
! 547:
! 548: /* nothing more man!! */
! 549: return;
! 550: }
! 551:
! 552: /**
! 553: * @internal Function that supports axl_hash_remove and
! 554: * axl_hash_delete.
! 555: *
! 556: * The function returns axl_true if an item was removed due to the call
! 557: * done.
! 558: */
! 559: axl_bool __axl_hash_remove_common (axlHash * hash,
! 560: axlPointer key,
! 561: axl_bool remove)
! 562: {
! 563: axlHashNode * node;
! 564: axlHashNode * aux;
! 565: int pos;
! 566:
! 567: axl_return_val_if_fail (hash, axl_false);
! 568:
! 569: /* do not perform any operation if the hash is empty */
! 570: if (hash->hash_size == 0)
! 571: return axl_false;
! 572:
! 573: /* get the node at the provided position */
! 574: pos = (hash->hash (key)) % hash->hash_size;
! 575: node = hash->table [pos];
! 576:
! 577: /* node not found */
! 578: if (node == NULL)
! 579: return axl_false;
! 580:
! 581: /* check for equal keys */
! 582: if (hash->equal (node->key, key) == 0) {
! 583: /* set that no items are available at the provided
! 584: * position */
! 585: hash->table [pos] = node->next;
! 586:
! 587: remove_element:
! 588: /* key destruction is defined */
! 589: if (node->key_destroy != NULL && remove)
! 590: node->key_destroy (node->key);
! 591:
! 592: /* if data destruction is defined */
! 593: if (node->data_destroy != NULL && remove)
! 594: node->data_destroy (node->data);
! 595:
! 596: /* decreases elements found */
! 597: hash->items--;
! 598:
! 599: /* delete the node */
! 600: axl_factory_release_spare (hash->factory, node);
! 601: /* axl_free (node); */
! 602:
! 603: /* element destroyed, nothing more to do around
! 604: * here */
! 605: return axl_true;
! 606: }
! 607:
! 608: /* seems we have more nodes */
! 609: while (node->next != NULL) {
! 610: /* store a reference to the current node (which will
! 611: * be the previous on next sentences) */
! 612: aux = node;
! 613:
! 614: /* update the reference to the next node */
! 615: node = node->next;
! 616:
! 617: /* check for equal keys */
! 618: if (hash->equal (node->key, key) == 0) {
! 619: /* make previous node to point to the next
! 620: * element of the following node */
! 621: aux->next = node->next;
! 622:
! 623: goto remove_element;
! 624: }
! 625: } /* end */
! 626:
! 627: /* no item was found on the hash */
! 628: return axl_false;
! 629: }
! 630:
! 631: /**
! 632: * @brief Allows to remove the selected pair key/value on the provided
! 633: * hash table.
! 634: *
! 635: * The function will remevo the item but it will not resize the table
! 636: * due to it. The function will call to the key destroy and data
! 637: * destroy function if they were defined at the insertion time (\ref
! 638: * axl_hash_insert_full).
! 639: *
! 640: *
! 641: * @param hash The hash table where the removal operation will be
! 642: * performed.
! 643: *
! 644: * @param key The key to lookup to be removed.
! 645: *
! 646: * @return The function returns axl_true if the item was removed,
! 647: * otherwise axl_false is returned. If the function returns axl_true, it means
! 648: * the object was stored in the hash before calling to remove it.
! 649: */
! 650: axl_bool axl_hash_remove (axlHash * hash,
! 651: axlPointer key)
! 652: {
! 653: /* call common implementation deleting data with destroy
! 654: * functions defined */
! 655: return __axl_hash_remove_common (hash, key, axl_true);
! 656: }
! 657:
! 658: /**
! 659: * @brief Allows to remove the selected pair key/value on the provided
! 660: * hash table, without calling to destroy functions.
! 661: *
! 662: * The function will remove the item but it will not resize the table
! 663: * due to it. The function will NOT call to the key destroy and data
! 664: * destroy function if they were defined at the insertion time (\ref
! 665: * axl_hash_insert_full).
! 666: *
! 667: *
! 668: * @param hash The hash table where the removal operation will be
! 669: * performed.
! 670: *
! 671: * @param key The key to lookup to be removed.
! 672: *
! 673: * @return The function returns axl_true if the item was removed
! 674: * (deallocation functions aren't called), otherwise axl_false is
! 675: * returned. If the function returns axl_true, it means the object was
! 676: * stored in the hash before calling to remove.
! 677: */
! 678: axl_bool axl_hash_delete (axlHash * hash,
! 679: axlPointer key)
! 680: {
! 681: /* call common implementation, without calling destroy
! 682: * functions defined */
! 683: return __axl_hash_remove_common (hash, key, axl_false);
! 684: }
! 685:
! 686: /**
! 687: * @brief Allows to get the content associated to the key provided
! 688: * inside the hash provided.
! 689: *
! 690: * @param hash The hash table where the lookup will be performed.
! 691: *
! 692: * @param key The key to use to retrieve the information.
! 693: *
! 694: * @return NULL or the associated data to the key provided. The
! 695: * function will also return a NULL value if provided a NULL hash
! 696: * reference or a NULL key reference.
! 697: */
! 698: axlPointer axl_hash_get (axlHash * hash,
! 699: axlPointer key)
! 700: {
! 701: axlHashNode * node;
! 702:
! 703: axl_return_val_if_fail (hash, NULL);
! 704:
! 705: /* check for empty hash to return NULL directly */
! 706: if (hash->items == 0)
! 707: return NULL;
! 708:
! 709: /* lookup using internal function */
! 710: node = __axl_hash_internal_lookup (hash, key);
! 711:
! 712: /* return the content or NULL if not defined the node */
! 713: if (node != NULL)
! 714: return node->data;
! 715: return NULL;
! 716: }
! 717:
! 718: /**
! 719: * @internal
! 720: *
! 721: * Common implementation for both foreach functions: axl_hash_foreach
! 722: * and axl_hash_foreach2.
! 723: */
! 724: void __axl_hash_foreach (axlHash * hash,
! 725: axlHashForeachFunc func,
! 726: axlHashForeachFunc2 func2,
! 727: axlHashForeachFunc3 func3,
! 728: axlHashForeachFunc4 func4,
! 729: axlPointer user_data,
! 730: axlPointer user_data2,
! 731: axlPointer user_data3,
! 732: axlPointer user_data4)
! 733: {
! 734:
! 735: int iterator = 0;
! 736: axlHashNode * node;
! 737:
! 738: /* perform some basic checks */
! 739: axl_return_if_fail (hash);
! 740:
! 741: /* foreach item row inside the hash table */
! 742: while (iterator < hash->hash_size) {
! 743:
! 744: /* check for content */
! 745: if (hash->table[iterator] != NULL) {
! 746: /* get the first item inside the table */
! 747: node = hash->table[iterator];
! 748:
! 749: do {
! 750: /* check for one user defined pointer
! 751: * foreach: notify the item found */
! 752: if (func != NULL && func (node->key, node->data, user_data)) {
! 753: /* user have decided to stop */
! 754: return;
! 755: } /* end if */
! 756:
! 757: /* check for two user defined pointers
! 758: * notify the item found */
! 759: if (func2 != NULL && func2 (node->key, node->data, user_data, user_data2)) {
! 760: /* user have decided to stop */
! 761: return;
! 762: } /* end if */
! 763:
! 764: /* check for three user defined pointers
! 765: * notify the item found */
! 766: if (func3 != NULL && func3 (node->key, node->data, user_data, user_data2, user_data3)) {
! 767: /* user have decided to stop */
! 768: return;
! 769: } /* end if */
! 770:
! 771: /* check for four user defined
! 772: * pointers notify the item found */
! 773: if (func4 != NULL && func4 (node->key, node->data, user_data, user_data2, user_data3, user_data4)) {
! 774: /* user have decided to stop */
! 775: return;
! 776: } /* end if */
! 777:
! 778: /* next item inside the same collition
! 779: * position */
! 780: node = node->next;
! 781:
! 782: /* while the next item is not null,
! 783: * keep on iterating */
! 784: } while (node != NULL);
! 785:
! 786: } /* end if */
! 787:
! 788: /* update the iterator */
! 789: iterator++;
! 790:
! 791: } /* end while */
! 792:
! 793: return;
! 794: }
! 795:
! 796: /**
! 797: * @brief Performs a foreach operation over all items stored in the
! 798: * hash provided.
! 799: *
! 800: * The function provided (<b>func</b>) will be called passing in the
! 801: * item found, and the data provided (third argument).
! 802: *
! 803: * Because the \ref axlHashForeachFunc function is used, \ref axl_true must be
! 804: * returned to stop the foreach process. In the case all items must be
! 805: * visited, \ref axl_false must be returned in any case.
! 806: *
! 807: * @param hash The hash table where the iteration process will take
! 808: * place.
! 809: *
! 810: * @param func The function to call for each item found.
! 811: *
! 812: * @param user_data User defined data to be passed in to the function callback along with the item found.
! 813: */
! 814: void axl_hash_foreach (axlHash * hash,
! 815: axlHashForeachFunc func,
! 816: axlPointer user_data)
! 817:
! 818: {
! 819:
! 820: /* perform the foreach operation using common support */
! 821: __axl_hash_foreach (hash,
! 822: /* foreach function */
! 823: func, NULL, NULL, NULL,
! 824: /* user defined data */
! 825: user_data, NULL, NULL, NULL);
! 826:
! 827: return;
! 828: }
! 829:
! 830: /**
! 831: * @brief Allows to perform a foreach operation providing two user
! 832: * defined pointer to be passed to the foreach function for each item
! 833: * found.
! 834: *
! 835: * This function works like \ref axl_hash_foreach function but support
! 836: * two user defined pointers. See \ref axl_hash_foreach for more information.
! 837: *
! 838: * @param hash The hash where the iteration will be performed.
! 839: *
! 840: * @param func The foreach function that will be called for all nodes
! 841: * found passed in both pointers defined along with the key value and
! 842: * the value associated.
! 843: *
! 844: * @param user_data User defined data to be passed to the foreach
! 845: * function.
! 846: *
! 847: * @param user_data2 Second User defined data to be passed to the
! 848: * foreach function.
! 849: */
! 850: void axl_hash_foreach2 (axlHash * hash,
! 851: axlHashForeachFunc2 func,
! 852: axlPointer user_data,
! 853: axlPointer user_data2)
! 854:
! 855: {
! 856: /* perform the foreach operation using common support */
! 857: __axl_hash_foreach (hash,
! 858: /* foreach function */
! 859: NULL, func, NULL, NULL,
! 860: /* user defined data */
! 861: user_data, user_data2, NULL, NULL);
! 862:
! 863: return;
! 864: }
! 865:
! 866: /**
! 867: * @brief Three user defined pointers foreach function over a hash.
! 868: *
! 869: * See \ref axl_hash_foreach2 and \ref axl_hash_foreach3 for more
! 870: * information.
! 871: *
! 872: * @param hash The hash where the foreach operation will take place.
! 873: *
! 874: * @param func The function to be called for each item found in the
! 875: * hash.
! 876: *
! 877: * @param user_data The user defined pointer to be configured in the
! 878: * hash.
! 879: *
! 880: * @param user_data2 Second user defined pointer to be configured in
! 881: * the hash.
! 882: *
! 883: * @param user_data3 Third user defined pointer to be configured in
! 884: * the hash.
! 885: */
! 886: void axl_hash_foreach3 (axlHash * hash,
! 887: axlHashForeachFunc3 func,
! 888: axlPointer user_data,
! 889: axlPointer user_data2,
! 890: axlPointer user_data3)
! 891: {
! 892: /* perform the foreach operation using common support */
! 893: __axl_hash_foreach (hash,
! 894: /* foreach function */
! 895: NULL, NULL, func, NULL,
! 896: /* user defined data */
! 897: user_data, user_data2, user_data3, NULL);
! 898: }
! 899:
! 900: /**
! 901: * @brief Four user defined pointers foreach function over a hash.
! 902: *
! 903: * See \ref axl_hash_foreach2 and \ref axl_hash_foreach3 for more
! 904: * information.
! 905: *
! 906: * @param hash The hash where the foreach operation will take place.
! 907: *
! 908: * @param func The function to be called for each item found in the
! 909: * hash.
! 910: *
! 911: * @param user_data The user defined pointer to be configured in the
! 912: * hash.
! 913: *
! 914: * @param user_data2 Second user defined pointer to be configured in
! 915: * the hash.
! 916: *
! 917: * @param user_data3 Third user defined pointer to be configured in
! 918: * the hash.
! 919: *
! 920: * @param user_data4 Forth user defined pointer to be configured in
! 921: * the hash.
! 922: */
! 923: void axl_hash_foreach4 (axlHash * hash,
! 924: axlHashForeachFunc4 func,
! 925: axlPointer user_data,
! 926: axlPointer user_data2,
! 927: axlPointer user_data3,
! 928: axlPointer user_data4)
! 929: {
! 930: /* perform the foreach operation using common support */
! 931: __axl_hash_foreach (hash,
! 932: /* foreach functions */
! 933: NULL, NULL, NULL, func,
! 934: /* user defined data */
! 935: user_data, user_data2, user_data3, user_data4);
! 936: }
! 937:
! 938: /**
! 939: * @brief Allows to check if the provided key is found on the given
! 940: * hash table.
! 941: *
! 942: * The function allows to get if the key is found on the table pretty
! 943: * much the behaviour that we could get using the following:
! 944: * \code
! 945: * // just compare if the provided key returns some value
! 946: * axl_bool value = (axl_hash_get (hash, "key2") != NULL);
! 947: * \endcode
! 948: *
! 949: * However it could happen that the value associated to the key, which
! 950: * already exists, is a NULL pointer, making previous comparation to
! 951: * not work in all cases. This function allows to check for the
! 952: * existance of a key and its associated data no mather what is the
! 953: * value of the associated data.
! 954: *
! 955: * @param hash The hash table to check for a key value.
! 956: * @param key The key to check for its existance.
! 957: *
! 958: * @return axl_true if the key is found, otherwise axl_false is returned.
! 959: */
! 960: axl_bool axl_hash_exists (axlHash * hash,
! 961: axlPointer key)
! 962: {
! 963: /* check if the hash is provided without loggin an error */
! 964: return (__axl_hash_internal_lookup (hash, key) != NULL);
! 965: }
! 966:
! 967: /**
! 968: * @internal function for axl_hash_copy.
! 969: */
! 970: axl_bool __axl_hash_copy_foreach (axlPointer key,
! 971: axlPointer data,
! 972: /* user defined pointers */
! 973: axlPointer user_data, /* hash */
! 974: axlPointer user_data2, /* result */
! 975: axlPointer user_data3, /* key_copy */
! 976: axlPointer user_data4) /* value_copy */
! 977: {
! 978: /* get a reference to the received data */
! 979: axlHash * hash = user_data;
! 980: axlHash * result = user_data2;
! 981: axlHashItemCopy key_copy = user_data3;
! 982: axlHashItemCopy value_copy = user_data4;
! 983:
! 984: /* additional variables */
! 985: axlHashNode * node;
! 986:
! 987: /* get node to copy */
! 988: node = hash->table [(hash->hash (key)) % hash->hash_size];
! 989:
! 990: /* check this is the node to copy */
! 991: while (node != NULL) {
! 992: if (hash->equal (node->key, key) == 0)
! 993: break;
! 994:
! 995: /* it isn't the node looked up */
! 996: node = node->next;
! 997: } /* end while */
! 998:
! 999: /* copy */
! 1000: axl_hash_insert_full (result,
! 1001: /* insert the key and its destroy function. */
! 1002: key_copy (node->key, node->key_destroy, node->data, node->data_destroy), node->key_destroy,
! 1003: /* insert data and its destroy function. */
! 1004: value_copy (node->key, node->key_destroy, node->data, node->data_destroy), node->data_destroy);
! 1005:
! 1006: /* make the foreach process to continue until the last element */
! 1007: return axl_false;
! 1008: }
! 1009:
! 1010: /**
! 1011: * @brief Allows to copy the provided hash, providing the copy
! 1012: * function used to duplicate key and value items stored.
! 1013: *
! 1014: * The function are optional, so, if they are null, the same value is
! 1015: * stored in the hash (for the key and the value). In this case, if
! 1016: * the source hash has defined destroy function for either key or
! 1017: * values, they will not be configured in the returning hash.
! 1018: *
! 1019: * If function are provided, \ref axl_hash_copy will use it to get a
! 1020: * duplicated version for either the key or the value. In this case,
! 1021: * if the source hash has defined the destroy function either for the
! 1022: * key or the value, it will be configured in the returning hash.
! 1023: *
! 1024: * @param hash The \ref axlHash that will work as data source.
! 1025: *
! 1026: * @param key_copy The function to be used to duplicate keys.
! 1027: *
! 1028: * @param value_copy The function used to duplicate values.
! 1029: *
! 1030: * @return A newly allocated reference to a \ref axlHash containing
! 1031: * all values from the source hash. The function will fail if the hash
! 1032: * provided is a null reference or copy functions aren't provided.
! 1033: */
! 1034: axlHash * axl_hash_copy (axlHash * hash,
! 1035: axlHashItemCopy key_copy,
! 1036: axlHashItemCopy value_copy)
! 1037: {
! 1038: axlHash * result;
! 1039:
! 1040: /* return if the hash reference is null */
! 1041: axl_return_val_if_fail (hash, NULL);
! 1042: axl_return_val_if_fail (key_copy, NULL);
! 1043: axl_return_val_if_fail (value_copy, NULL);
! 1044:
! 1045: /* create the hash */
! 1046: result = axl_hash_new_full (hash->hash,
! 1047: hash->equal,
! 1048: /* make initial step to be equal
! 1049: * to the current hash size copied
! 1050: * to avoid resizing operations
! 1051: * during the foreach. */
! 1052: hash->items);
! 1053: /* restore step */
! 1054: result->step = hash->step;
! 1055:
! 1056: /* check empty hash value */
! 1057: if (hash->hash_size == 0)
! 1058: return result;
! 1059:
! 1060: /* copy all items */
! 1061: axl_hash_foreach4 (hash, __axl_hash_copy_foreach, hash, result, key_copy, value_copy);
! 1062:
! 1063:
! 1064: /* return created hash */
! 1065: return result;
! 1066: }
! 1067:
! 1068: /**
! 1069: * @brief Returns the number of items already stored on the provided
! 1070: * hash.
! 1071: *
! 1072: * @param hash The hash that is being requested for the number of
! 1073: * indexed data items.
! 1074: *
! 1075: * @return The number of items or -1 if it fails.
! 1076: */
! 1077: int axl_hash_items (axlHash * hash)
! 1078: {
! 1079: axl_return_val_if_fail (hash, -1);
! 1080:
! 1081: /* return current items stored */
! 1082: return hash->items;
! 1083: }
! 1084:
! 1085: /**
! 1086: * @brief Allows to get the amount of items that could store the hash
! 1087: * without allocating more additional memory.
! 1088: *
! 1089: * @param hash The hash that is being requested to return its items
! 1090: * capacity (key + value) pair.
! 1091: *
! 1092: * @return The capacity or -1 if the reference received is null.
! 1093: */
! 1094: int axl_hash_capacity (axlHash * hash)
! 1095: {
! 1096: axl_return_val_if_fail (hash, -1);
! 1097: /* return current capacity */
! 1098: return hash->hash_size;
! 1099: }
! 1100:
! 1101: /**
! 1102: * @internal Shows current hash status to the console.
! 1103: *
! 1104: * The function is only useful for internal hash module purposes. It
! 1105: * shows the numbers of items stored, the table size, the number of
! 1106: * collitions, etc.
! 1107: *
! 1108: * @param hash The hash where the status is requested.
! 1109: */
! 1110: void axl_hash_show_status (axlHash * hash)
! 1111: {
! 1112: /* use full implementation */
! 1113: axl_hash_show_status_full (hash, NULL);
! 1114:
! 1115: return;
! 1116: }
! 1117:
! 1118: /**
! 1119: * @internal Shows current hash content to the console using the
! 1120: * provided function to show the hash content.
! 1121: *
! 1122: * @param hash The hash that is requested to show its content.
! 1123: *
! 1124: * @param show_item The function to be used to show the content.
! 1125: */
! 1126: void axl_hash_show_status_full (axlHash * hash,
! 1127: axlHashPrintKeyData show_item)
! 1128: {
! 1129: axlHashNode * node;
! 1130: int iterator;
! 1131: int count;
! 1132: axl_return_if_fail (hash);
! 1133:
! 1134: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "axl hash table status:");
! 1135: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "table size: %d items: %d step: %d",
! 1136: hash->hash_size, hash->items, hash->step);
! 1137: /* get the number of empty blocks */
! 1138: iterator = 0;
! 1139: count = 0;
! 1140: while (iterator < hash->hash_size) {
! 1141: /* empty item found */
! 1142: if (hash->table[iterator] == NULL) {
! 1143: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "empty cell at: %d", iterator);
! 1144: count++;
! 1145: }
! 1146:
! 1147: /* update iterator */
! 1148: iterator++;
! 1149: }
! 1150: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "number of empty cells: %d", count);
! 1151:
! 1152: /* get the number properly used cells (no collitions) */
! 1153: iterator = 0;
! 1154: count = 0;
! 1155: while (iterator < hash->hash_size) {
! 1156: /* empty item found */
! 1157: node = hash->table[iterator];
! 1158: if (node != NULL && node->next == NULL) {
! 1159: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "properly used cell at: %d", iterator);
! 1160: count++;
! 1161:
! 1162: if (show_item != NULL) {
! 1163: show_item (node->key, node->data);
! 1164: }
! 1165: }
! 1166:
! 1167: /* update iterator */
! 1168: iterator++;
! 1169: }
! 1170: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "number of properly used cells (no collition): %d", count);
! 1171:
! 1172: /* get the number of collitioned cells */
! 1173: iterator = 0;
! 1174: count = 0;
! 1175: while (iterator < hash->hash_size) {
! 1176: /* empty item found */
! 1177: node = hash->table[iterator];
! 1178: if (node != NULL && node->next != NULL) {
! 1179: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "collitioned cell at: %d", iterator);
! 1180: count++;
! 1181: }
! 1182:
! 1183: /* for each node show the content */
! 1184: while ((show_item) != NULL && (node != NULL)) {
! 1185: if (show_item != NULL) {
! 1186: show_item (node->key, node->data);
! 1187: }
! 1188:
! 1189: /* update to the next node */
! 1190: node = node->next;
! 1191: }
! 1192:
! 1193: /* update iterator */
! 1194: iterator++;
! 1195: }
! 1196: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "number of collitioned cells: %d", count);
! 1197:
! 1198:
! 1199:
! 1200: return;
! 1201: }
! 1202:
! 1203: /**
! 1204: * @brief Allows to deallocate the hash provided.
! 1205: *
! 1206: * @param hash The hash to deallocate.
! 1207: */
! 1208: void axl_hash_free (axlHash * hash)
! 1209: {
! 1210: int iterator = 0;
! 1211: axlHashNode * node;
! 1212: axlHashNode * aux;
! 1213:
! 1214: /* do not perform any operation if a null reference is
! 1215: * received */
! 1216: if (hash == NULL)
! 1217: return;
! 1218:
! 1219: /* release the hash table */
! 1220: if (hash->table != NULL) {
! 1221:
! 1222: /* first release all nodes inside */
! 1223: while (iterator < hash->hash_size) {
! 1224: node = hash->table[iterator];
! 1225: if (node != NULL) {
! 1226: do {
! 1227: /* key destruction is defined */
! 1228: if (node->key_destroy != NULL)
! 1229: node->key_destroy (node->key);
! 1230:
! 1231: /* if data destruction is defined */
! 1232: if (node->data_destroy != NULL)
! 1233: node->data_destroy (node->data);
! 1234:
! 1235: /* check data */
! 1236: aux = node;
! 1237: node = node->next;
! 1238:
! 1239: /* while more nodes */
! 1240: } while (node != NULL);
! 1241: } /* end if */
! 1242:
! 1243: /* update the iterator */
! 1244: iterator++;
! 1245: } /* end while */
! 1246:
! 1247: /* now release the table */
! 1248: axl_free (hash->table);
! 1249: } /* end if */
! 1250:
! 1251: /* free factory */
! 1252: axl_factory_free (hash->factory);
! 1253:
! 1254: /* now release the hash itself */
! 1255: axl_free (hash);
! 1256:
! 1257: /* nothing more to free */
! 1258: return;
! 1259: }
! 1260:
! 1261: /**
! 1262: * @internal Function that allows to get how many spare internal hash
! 1263: * nodes we can store.
! 1264: */
! 1265: int __axl_hash_spare_max (axlHash * hash)
! 1266: {
! 1267: return axl_factory_spare_max (hash->factory);
! 1268: }
! 1269:
! 1270: /**
! 1271: * @internal Function that allows to get how many spare internal hash
! 1272: * nodes are actually stored.
! 1273: */
! 1274: int __axl_hash_spare_next (axlHash * hash)
! 1275: {
! 1276: return axl_factory_spare_next (hash->factory);
! 1277: }
! 1278:
! 1279: /* @} */
! 1280:
! 1281: /**
! 1282: * \defgroup axl_hash_cursor_module Axl Hash Cursor: Iterator support for the Axl Hash
! 1283: */
! 1284:
! 1285: /* init the cursor */
! 1286: void __axl_hash_cursor_init (axlHashCursor * cursor, axl_bool first)
! 1287: {
! 1288: /* pointer to a hash node (basic atom holding key and value) */
! 1289: axlHashNode * node = NULL;
! 1290:
! 1291: if (first) {
! 1292: /* configure first */
! 1293: cursor->index = 0;
! 1294:
! 1295: /* foreach element inside the hash, check the first value */
! 1296: while (cursor->index < cursor->hash->hash_size) {
! 1297: /* check the table at the current position */
! 1298: node = cursor->hash->table[cursor->index];
! 1299: if (node != NULL) {
! 1300: /* first node found, store it */
! 1301: cursor->node = node;
! 1302: break;
! 1303: } /* end if */
! 1304:
! 1305: /* node not found, go next position */
! 1306: cursor->index++;
! 1307: } /* end while */
! 1308: } else {
! 1309: /* find last value */
! 1310: cursor->index = cursor->hash->hash_size - 1;
! 1311: cursor->node = NULL;
! 1312: while (cursor->index > 0) {
! 1313: /* check the table at the current position */
! 1314: node = cursor->hash->table[cursor->index];
! 1315: if (node != NULL) {
! 1316: /* find last entry filled, now find
! 1317: * last entry in the same index */
! 1318: while (node->next != NULL)
! 1319: node = node->next;
! 1320:
! 1321: /* configure it */
! 1322: cursor->node = node;
! 1323: break;
! 1324: } /* end if */
! 1325:
! 1326: /* node not found, go next position */
! 1327: cursor->index--;
! 1328: } /* end while */
! 1329: } /* end if */
! 1330:
! 1331: /* if the node wasn't found, reset index */
! 1332: if (node == NULL)
! 1333: cursor->index = 0;
! 1334:
! 1335: /* cursor initialized */
! 1336: return;
! 1337: }
! 1338:
! 1339: /**
! 1340: * \addtogroup axl_hash_cursor_module
! 1341: * @{
! 1342: */
! 1343:
! 1344: /**
! 1345: * @brief Allows to get a cursor to iterate the hash in a linear and
! 1346: * efficient way.
! 1347: *
! 1348: * The \ref axlHashCursor could be used to iterate an \ref axlHash in
! 1349: * an efficient way because it stores current state (position), hiding
! 1350: * all module details. Then using the following functions you can
! 1351: * modify the state (current position to get):
! 1352: *
! 1353: * - \ref axl_hash_cursor_first
! 1354: * - \ref axl_hash_cursor_last
! 1355: * - \ref axl_hash_cursor_next
! 1356: *
! 1357: * Finally, the following functions are provided to get the data stored at a
! 1358: * particular position, pointed by the current status of the cursor:
! 1359: *
! 1360: * - \ref axl_hash_cursor_get_key (returns the key of the current position)
! 1361: * - \ref axl_hash_cursor_get_value (returns the value of the current position)
! 1362: *
! 1363: * You are allowed to remove elements from the hash (\ref axlHash)
! 1364: * having a cursor created (\ref axlHashCursor), using \ref
! 1365: * axl_hash_cursor_remove.
! 1366: *
! 1367: * Here is an example:
! 1368: * \code
! 1369: * axlPointer key;
! 1370: * axlPointer value;
! 1371: * axlHashCursor * cursor;
! 1372: *
! 1373: * // create the cursor
! 1374: * cursor = axl_hash_cursor_new (hash);
! 1375: *
! 1376: * // while there are more elements
! 1377: * while (axl_hash_cursor_has_item (cursor)) {
! 1378: *
! 1379: * // get the value and key
! 1380: * value = axl_hash_cursor_get_key (cursor);
! 1381: * value = axl_hash_cursor_get_value (cursor);
! 1382: *
! 1383: * // get the next
! 1384: * axl_hash_cursor_next (cursor);
! 1385: *
! 1386: * }
! 1387: *
! 1388: * // free the cursor
! 1389: * axl_hash_cursor_free (cursor);
! 1390: * \endcode
! 1391: *
! 1392: * @param hash The hash that the new cursor (\ref axlHashCursor) will
! 1393: * provide access.
! 1394: *
! 1395: * @return A newly created \ref axlHashCursor used to iterate the
! 1396: * hash. Once finished you must call to \ref axl_hash_cursor_free.
! 1397: */
! 1398: axlHashCursor * axl_hash_cursor_new (axlHash * hash)
! 1399: {
! 1400: axlHashCursor * cursor;
! 1401:
! 1402: axl_return_val_if_fail (hash, NULL);
! 1403:
! 1404: /* create the cursor */
! 1405: cursor = axl_new (axlHashCursor, 1);
! 1406:
! 1407: /* initial configuration */
! 1408: cursor->hash = hash;
! 1409:
! 1410: /* init the cursor */
! 1411: __axl_hash_cursor_init (cursor, axl_true);
! 1412:
! 1413: /* return cursor */
! 1414: return cursor;
! 1415: }
! 1416:
! 1417: /**
! 1418: * @brief Allows to configure the cursor to point to the first item of
! 1419: * the hash (if there are any).
! 1420: *
! 1421: * @param cursor The cursor that is required to be configured to point the first item.
! 1422: */
! 1423: void axl_hash_cursor_first (axlHashCursor * cursor)
! 1424: {
! 1425: axl_return_if_fail (cursor);
! 1426:
! 1427: /* init the cursor at the initial state */
! 1428: __axl_hash_cursor_init (cursor, axl_true);
! 1429:
! 1430: return;
! 1431: }
! 1432:
! 1433: /**
! 1434: * @brief Allows to configure the cursor to point to the last item of
! 1435: * the hash (if there are any).
! 1436: *
! 1437: * @param cursor The cursor that is required to be configured to point
! 1438: * to the last item.
! 1439: */
! 1440: void axl_hash_cursor_last (axlHashCursor * cursor)
! 1441: {
! 1442: axl_return_if_fail (cursor);
! 1443:
! 1444: /* init the cursor at the initial state, selecting the last
! 1445: * node */
! 1446: __axl_hash_cursor_init (cursor, axl_false);
! 1447:
! 1448: return;
! 1449: }
! 1450:
! 1451: /**
! 1452: * @brief Allows to configure the cursor to point to the next item of
! 1453: * the hash (if there are any).
! 1454: *
! 1455: * @param cursor The cursor that is required to be configured to point
! 1456: * to the next item.
! 1457: */
! 1458: void axl_hash_cursor_next (axlHashCursor * cursor)
! 1459: {
! 1460: axl_return_if_fail (cursor);
! 1461:
! 1462: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "getting next element at the cursor");
! 1463:
! 1464: /* check if the current node is null and do nothing if nothing
! 1465: * is found */
! 1466: if (cursor->node == NULL) {
! 1467: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "no nodes found....");
! 1468: return;
! 1469: }
! 1470:
! 1471: /* basic case, the item is found in the same level */
! 1472: if (cursor->node->next != NULL) {
! 1473: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "getting next node....");
! 1474: /* configure new current node */
! 1475: cursor->node = cursor->node->next;
! 1476:
! 1477: return;
! 1478: } /* end if */
! 1479:
! 1480: /* node not found, go next position */
! 1481: cursor->index++;
! 1482:
! 1483: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "updating and checking next index: %d (hash: %d)....",
! 1484: cursor->index, cursor->hash->hash_size);
! 1485:
! 1486: /* check if we have reached the phisical limit of the hash */
! 1487: if (cursor->index >= cursor->hash->hash_size) {
! 1488: cursor->node = NULL;
! 1489: return;
! 1490: }
! 1491:
! 1492: /* seems next is null, see in other positions */
! 1493: while (cursor->index < cursor->hash->hash_size) {
! 1494:
! 1495: /* check the table at the current position */
! 1496: cursor->node = cursor->hash->table[cursor->index];
! 1497: if (cursor->node != NULL) {
! 1498: /* node found, stop! */
! 1499: break;
! 1500: } /* end if */
! 1501:
! 1502: /* node not found, go next position */
! 1503: cursor->index++;
! 1504: } /* end while */
! 1505:
! 1506: /* nothing to be done */
! 1507: return;
! 1508: }
! 1509:
! 1510: /**
! 1511: * @brief Allows to check if there are more elements next to the
! 1512: * current element pointed by the cursor.
! 1513: *
! 1514: * @param cursor The cursor that is required to return if there are
! 1515: * next items.
! 1516: *
! 1517: * @return \ref axl_true if more items are found, otherwise \ref axl_false is
! 1518: * returned.
! 1519: */
! 1520: axl_bool axl_hash_cursor_has_next (axlHashCursor * cursor)
! 1521: {
! 1522: int iterator;
! 1523: axl_return_val_if_fail (cursor, axl_false);
! 1524:
! 1525: /* check basic case */
! 1526: if (cursor->node != NULL && cursor->node->next != NULL) {
! 1527: __axl_log (LOG_DOMAIN, AXL_LEVEL_DEBUG, "next is defined..");
! 1528: return axl_true;
! 1529: }
! 1530:
! 1531: /* seems next is null, see in other positions */
! 1532: iterator = cursor->index + 1;
! 1533: while (iterator < cursor->hash->hash_size) {
! 1534: /* check the table at the current position */
! 1535: if (cursor->hash->table[iterator] != NULL)
! 1536: return axl_true;
! 1537:
! 1538: /* node not found, go next position */
! 1539: iterator++;
! 1540: } /* end while */
! 1541:
! 1542: return axl_false;
! 1543: }
! 1544:
! 1545: /**
! 1546: * @brief Allows to know if the current position has items.
! 1547: *
! 1548: * @param cursor The cursor pointing to a particular element inside
! 1549: * the hash (or not).
! 1550: *
! 1551: * @return \ref axl_true if the hash that is iterated can return data at
! 1552: * the current position, otherwise \ref axl_false is returned.
! 1553: */
! 1554: axl_bool axl_hash_cursor_has_item (axlHashCursor * cursor)
! 1555: {
! 1556: axl_return_val_if_fail (cursor, axl_false);
! 1557:
! 1558: /* return axl_true if there are a item selected */
! 1559: return (cursor->node != NULL);
! 1560: }
! 1561:
! 1562: /**
! 1563: * @brief Allows to remove current element pointed by the cursor,
! 1564: * maintainig internal state of the cursor, calling to the destroy
! 1565: * function associated in the hash.
! 1566: *
! 1567: * The function will call to the destroy function asociated to the
! 1568: * hash.
! 1569: *
! 1570: * @param cursor The cursor pointing to the item inside the hash that
! 1571: * must be removed.
! 1572: */
! 1573: void axl_hash_cursor_remove (axlHashCursor * cursor)
! 1574: {
! 1575: axlHashNode * node;
! 1576:
! 1577: axl_return_if_fail (cursor);
! 1578:
! 1579: /* if current cursor is pointing nowhere, just do nothing */
! 1580: if (cursor->node == NULL)
! 1581: return;
! 1582:
! 1583: /* remember node */
! 1584: node = cursor->node->next;
! 1585:
! 1586: /* remove node selected */
! 1587: axl_hash_remove (cursor->hash, cursor->node->key);
! 1588:
! 1589: /* configure next item */
! 1590: cursor->node = node;
! 1591: if (cursor->node == NULL) {
! 1592: while (cursor->index < cursor->hash->hash_size) {
! 1593: /* check the table at the current position */
! 1594: if (cursor->hash->table[cursor->index] != NULL) {
! 1595: /* configure the next node */
! 1596: cursor->node = cursor->hash->table[cursor->index];
! 1597: return;
! 1598: }
! 1599:
! 1600: /* node not found, go next position */
! 1601: cursor->index++;
! 1602: } /* end while */
! 1603: } /* end if */
! 1604:
! 1605: return;
! 1606: }
! 1607:
! 1608: /**
! 1609: * @brief Allows to get current value at the current cursor state.
! 1610: *
! 1611: * @param cursor The cursor that will be used to return the data
! 1612: * located at the hash, using cursor current state.
! 1613: */
! 1614: axlPointer axl_hash_cursor_get_value (axlHashCursor * cursor)
! 1615: {
! 1616: axl_return_val_if_fail (cursor, NULL);
! 1617:
! 1618: /* nothing to return if current is NULL */
! 1619: if (cursor->node == NULL)
! 1620: return NULL;
! 1621:
! 1622: /* return data */
! 1623: return cursor->node->data;
! 1624: }
! 1625:
! 1626: /**
! 1627: * @brief Allows to get current key at the current cursor state.
! 1628: *
! 1629: * @param cursor The cursor that will be used to return the data
! 1630: * located at the hash, using cursor current state.
! 1631: */
! 1632: axlPointer axl_hash_cursor_get_key (axlHashCursor * cursor)
! 1633: {
! 1634: axl_return_val_if_fail (cursor, NULL);
! 1635:
! 1636: /* nothing to return if current is NULL */
! 1637: if (cursor->node == NULL)
! 1638: return NULL;
! 1639:
! 1640: /* return key pointer */
! 1641: return cursor->node->key;
! 1642: }
! 1643:
! 1644: /**
! 1645: * @brief Allows to get the reference to the hash that is associated
! 1646: * to the cursor received.
! 1647: *
! 1648: * @param cursor The cursor that is required to return the hash associated.
! 1649: *
! 1650: * @return A reference to the hash being iterated or NULL if fails.
! 1651: */
! 1652: axlHash * axl_hash_cursor_hash (axlHashCursor * cursor)
! 1653: {
! 1654: /* check incoming cursor */
! 1655: axl_return_val_if_fail (cursor, NULL);
! 1656:
! 1657: /* return the hash */
! 1658: return cursor->hash;
! 1659: }
! 1660:
! 1661: /**
! 1662: * @brief Deallocates memory used by the cursor.
! 1663: *
! 1664: * @param cursor The cursor to be deallocated.
! 1665: */
! 1666: void axl_hash_cursor_free (axlHashCursor * cursor)
! 1667: {
! 1668: axl_return_if_fail (cursor);
! 1669:
! 1670: /* free the cursor */
! 1671: axl_free (cursor);
! 1672:
! 1673: return;
! 1674: }
! 1675:
! 1676:
! 1677: /* @} */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to axl_hash.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / gpl / axl / src