1: /* -*- mode: C; c-file-style: "gnu" -*- */
    2: /* dbus-hash.c Generic hash table utility (internal to D-Bus implementation)
    3:  * 
    4:  * Copyright (C) 2002  Red Hat, Inc.
    5:  * Copyright (c) 1991-1993 The Regents of the University of California.
    6:  * Copyright (c) 1994 Sun Microsystems, Inc.
    7:  * 
    8:  * Hash table implementation based on generic/tclHash.c from the Tcl
    9:  * source code. The original Tcl license applies to portions of the
   10:  * code from tclHash.c; the Tcl license follows this standad D-Bus 
   11:  * license information.
   12:  *
   13:  * Licensed under the Academic Free License version 2.1
   14:  * 
   15:  * This program is free software; you can redistribute it and/or modify
   16:  * it under the terms of the GNU General Public License as published by
   17:  * the Free Software Foundation; either version 2 of the License, or
   18:  * (at your option) any later version.
   19:  *
   20:  * This program is distributed in the hope that it will be useful,
   21:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   22:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   23:  * GNU General Public License for more details.
   24:  * 
   25:  * You should have received a copy of the GNU General Public License
   26:  * along with this program; if not, write to the Free Software
   27:  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   28:  *
   29:  */
   30: /* 
   31:  * The following copyright applies to code from the Tcl distribution.
   32:  *
   33:  * Copyright (c) 1991-1993 The Regents of the University of California.
   34:  * Copyright (c) 1994 Sun Microsystems, Inc.
   35:  *
   36:  * This software is copyrighted by the Regents of the University of
   37:  * California, Sun Microsystems, Inc., Scriptics Corporation, and
   38:  * other parties.  The following terms apply to all files associated
   39:  * with the software unless explicitly disclaimed in individual files.
   40:  * 
   41:  * The authors hereby grant permission to use, copy, modify,
   42:  * distribute, and license this software and its documentation for any
   43:  * purpose, provided that existing copyright notices are retained in
   44:  * all copies and that this notice is included verbatim in any
   45:  * distributions. No written agreement, license, or royalty fee is
   46:  * required for any of the authorized uses.  Modifications to this
   47:  * software may be copyrighted by their authors and need not follow
   48:  * the licensing terms described here, provided that the new terms are
   49:  * clearly indicated on the first page of each file where they apply.
   50:  * 
   51:  * IN NO EVENT SHALL THE AUTHORS OR DISTRIBUTORS BE LIABLE TO ANY
   52:  * PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
   53:  * DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION,
   54:  * OR ANY DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED
   55:  * OF THE POSSIBILITY OF SUCH DAMAGE.
   56:  * 
   57:  * THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
   58:  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
   59:  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, AND
   60:  * NON-INFRINGEMENT.  THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS,
   61:  * AND THE AUTHORS AND DISTRIBUTORS HAVE NO OBLIGATION TO PROVIDE
   62:  * MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
   63:  * 
   64:  * GOVERNMENT USE: If you are acquiring this software on behalf of the
   65:  * U.S. government, the Government shall have only "Restricted Rights"
   66:  * in the software and related documentation as defined in the Federal
   67:  * Acquisition Regulations (FARs) in Clause 52.227.19 (c) (2).  If you
   68:  * are acquiring the software on behalf of the Department of Defense,
   69:  * the software shall be classified as "Commercial Computer Software"
   70:  * and the Government shall have only "Restricted Rights" as defined
   71:  * in Clause 252.227-7013 (c) (1) of DFARs.  Notwithstanding the
   72:  * foregoing, the authors grant the U.S. Government and others acting
   73:  * in its behalf permission to use and distribute the software in
   74:  * accordance with the terms specified in this license.
   75:  */
   76: 
   77: #include "dbus-hash.h"
   78: #include "dbus-internals.h"
   79: #include "dbus-mempool.h"
   80: 
   81: /**
   82:  * @defgroup DBusHashTable Hash table
   83:  * @ingroup  DBusInternals
   84:  * @brief DBusHashTable data structure
   85:  *
   86:  * Types and functions related to DBusHashTable.
   87:  */
   88: 
   89: /**
   90:  * @defgroup DBusHashTableInternals Hash table implementation details
   91:  * @ingroup  DBusInternals
   92:  * @brief DBusHashTable implementation details
   93:  *
   94:  * The guts of DBusHashTable.
   95:  *
   96:  * @{
   97:  */
   98: 
   99: /**
  100:  * When there are this many entries per bucket, on average, rebuild
  101:  * the hash table to make it larger.
  102:  */
  103: #define REBUILD_MULTIPLIER  3
  104: 
  105: /**
  106:  * Takes a preliminary integer hash value and produces an index into a
  107:  * hash tables bucket list.  The idea is to make it so that
  108:  * preliminary values that are arbitrarily similar will end up in
  109:  * different buckets.  The hash function was taken from a
  110:  * random-number generator. (This is used to hash integers.)
  111:  *
  112:  * The down_shift drops off the high bits of the hash index, and
  113:  * decreases as we increase the number of hash buckets (to keep more
  114:  * range in the hash index). The mask also strips high bits and strips
  115:  * fewer high bits as the number of hash buckets increases.
  116:  * I don't understand two things: why is the initial downshift 28
  117:  * to keep 4 bits when the initial mask is 011 to keep 2 bits,
  118:  * and why do we have both a mask and a downshift?
  119:  * 
  120:  */
  121: #define RANDOM_INDEX(table, i) \
  122:     (((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
  123: 
  124: /**
  125:  * Initial number of buckets in hash table (hash table statically
  126:  * allocates its buckets for this size and below).
  127:  * The initial mask has to be synced to this.
  128:  */
  129: #define DBUS_SMALL_HASH_TABLE 4
  130: 
  131: /**
  132:  * Typedef for DBusHashEntry
  133:  */
  134: typedef struct DBusHashEntry DBusHashEntry;
  135: 
  136: /**
  137:  * @brief Internal representation of a hash entry.
  138:  * 
  139:  * A single entry (key-value pair) in the hash table.
  140:  * Internal to hash table implementation.
  141:  */
  142: struct DBusHashEntry
  143: {
  144:   DBusHashEntry *next;    /**< Pointer to next entry in this
  145:                            * hash bucket, or #NULL for end of
  146:                            * chain.
  147:                            */
  148:   void *key;              /**< Hash key */
  149:   void *value;            /**< Hash value */
  150: };
  151: 
  152: /**
  153:  * Function used to find and optionally create a hash entry.
  154:  */
  155: typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable        *table,
  156:                                                   void                 *key,
  157:                                                   dbus_bool_t           create_if_not_found,
  158:                                                   DBusHashEntry      ***bucket,
  159:                                                   DBusPreallocatedHash *preallocated);
  160: 
  161: /**
  162:  * @brief Internals of DBusHashTable.
  163:  * 
  164:  * Hash table internals. Hash tables are opaque objects, they must be
  165:  * used via accessor functions.
  166:  */
  167: struct DBusHashTable {
  168:   int refcount;                       /**< Reference count */
  169:   
  170:   DBusHashEntry **buckets;            /**< Pointer to bucket array.  Each
  171:                                        * element points to first entry in
  172:                                        * bucket's hash chain, or #NULL.
  173:                                        */
  174:   DBusHashEntry *static_buckets[DBUS_SMALL_HASH_TABLE];
  175:                                        /**< Bucket array used for small tables
  176:                                         * (to avoid mallocs and frees).
  177:                                         */
  178:   int n_buckets;                       /**< Total number of buckets allocated
  179:                                         * at **buckets.
  180:                                         */
  181:   int n_entries;                       /**< Total number of entries present
  182:                                         * in table.
  183:                                         */
  184:   int hi_rebuild_size;                 /**< Enlarge table when n_entries gets
  185:                                         * to be this large.
  186:                                         */
  187:   int lo_rebuild_size;                 /**< Shrink table when n_entries gets
  188:                                         * below this.
  189:                                         */
  190:   int down_shift;                      /**< Shift count used in hashing
  191:                                         * function.  Designed to use high-
  192:                                         * order bits of randomized keys.
  193:                                         */
  194:   int mask;                            /**< Mask value used in hashing
  195:                                         * function.
  196:                                         */
  197:   DBusHashType key_type;               /**< Type of keys used in this table */
  198: 
  199: 
  200:   DBusFindEntryFunction find_function; /**< Function for finding entries */
  201: 
  202:   DBusFreeFunction free_key_function;   /**< Function to free keys */
  203:   DBusFreeFunction free_value_function; /**< Function to free values */
  204: 
  205:   DBusMemPool *entry_pool;              /**< Memory pool for hash entries */
  206: };
  207: 
  208: /** 
  209:  * @brief Internals of DBusHashIter.
  210:  */
  211: typedef struct
  212: {
  213:   DBusHashTable *table;     /**< Pointer to table containing entry. */
  214:   DBusHashEntry **bucket;   /**< Pointer to bucket that points to
  215:                              * first entry in this entry's chain:
  216:                              * used for deleting the entry.
  217:                              */
  218:   DBusHashEntry *entry;      /**< Current hash entry */
  219:   DBusHashEntry *next_entry; /**< Next entry to be iterated onto in current bucket */
  220:   int next_bucket;           /**< index of next bucket */
  221:   int n_entries_on_init;     /**< used to detect table resize since initialization */
  222: } DBusRealHashIter;
  223: 
  224: static DBusHashEntry* find_direct_function      (DBusHashTable          *table,
  225:                                                  void                   *key,
  226:                                                  dbus_bool_t             create_if_not_found,
  227:                                                  DBusHashEntry        ***bucket,
  228:                                                  DBusPreallocatedHash   *preallocated);
  229: static DBusHashEntry* find_string_function      (DBusHashTable          *table,
  230:                                                  void                   *key,
  231:                                                  dbus_bool_t             create_if_not_found,
  232:                                                  DBusHashEntry        ***bucket,
  233:                                                  DBusPreallocatedHash   *preallocated);
  234: #ifdef DBUS_BUILD_TESTS
  235: static DBusHashEntry* find_two_strings_function (DBusHashTable          *table,
  236:                                                  void                   *key,
  237:                                                  dbus_bool_t             create_if_not_found,
  238:                                                  DBusHashEntry        ***bucket,
  239:                                                  DBusPreallocatedHash   *preallocated);
  240: #endif
  241: static unsigned int   string_hash               (const char             *str);
  242: #ifdef DBUS_BUILD_TESTS
  243: static unsigned int   two_strings_hash          (const char             *str);
  244: #endif
  245: static void           rebuild_table             (DBusHashTable          *table);
  246: static DBusHashEntry* alloc_entry               (DBusHashTable          *table);
  247: static void           remove_entry              (DBusHashTable          *table,
  248:                                                  DBusHashEntry         **bucket,
  249:                                                  DBusHashEntry          *entry);
  250: static void           free_entry                (DBusHashTable          *table,
  251:                                                  DBusHashEntry          *entry);
  252: static void           free_entry_data           (DBusHashTable          *table,
  253:                                                  DBusHashEntry          *entry);
  254: 
  255: 
  256: /** @} */
  257: 
  258: /**
  259:  * @addtogroup DBusHashTable
  260:  * @{
  261:  */
  262: 
  263: /**
  264:  * @typedef DBusHashIter
  265:  *
  266:  * Public opaque hash table iterator object.
  267:  */
  268: 
  269: /**
  270:  * @typedef DBusHashTable
  271:  *
  272:  * Public opaque hash table object.
  273:  */
  274: 
  275: /**
  276:  * @typedef DBusHashType
  277:  *
  278:  * Indicates the type of a key in the hash table.
  279:  */
  280: 
  281: /**
  282:  * Constructs a new hash table. Should be freed with
  283:  * _dbus_hash_table_unref(). If memory cannot be
  284:  * allocated for the hash table, returns #NULL.
  285:  *
  286:  * @param type the type of hash key to use.
  287:  * @param key_free_function function to free hash keys.
  288:  * @param value_free_function function to free hash values.
  289:  * @returns a new DBusHashTable or #NULL if no memory.
  290:  */
  291: DBusHashTable*
  292: _dbus_hash_table_new (DBusHashType     type,
  293:                       DBusFreeFunction key_free_function,
  294:                       DBusFreeFunction value_free_function)
  295: {
  296:   DBusHashTable *table;
  297:   DBusMemPool *entry_pool;
  298:   
  299:   table = dbus_new0 (DBusHashTable, 1);
  300:   if (table == NULL)
  301:     return NULL;
  302: 
  303:   entry_pool = _dbus_mem_pool_new (sizeof (DBusHashEntry), TRUE);
  304:   if (entry_pool == NULL)
  305:     {
  306:       dbus_free (table);
  307:       return NULL;
  308:     }
  309:   
  310:   table->refcount = 1;
  311:   table->entry_pool = entry_pool;
  312:   
  313:   _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
  314:   
  315:   table->buckets = table->static_buckets;  
  316:   table->n_buckets = DBUS_SMALL_HASH_TABLE;
  317:   table->n_entries = 0;
  318:   table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
  319:   table->lo_rebuild_size = 0;
  320:   table->down_shift = 28;
  321:   table->mask = 3;
  322:   table->key_type = type;
  323: 
  324:   _dbus_assert (table->mask < table->n_buckets);
  325:   
  326:   switch (table->key_type)
  327:     {
  328:     case DBUS_HASH_INT:
  329:     case DBUS_HASH_POINTER:
  330:     case DBUS_HASH_ULONG:
  331:       table->find_function = find_direct_function;
  332:       break;
  333:     case DBUS_HASH_STRING:
  334:       table->find_function = find_string_function;
  335:       break;
  336:     case DBUS_HASH_TWO_STRINGS:
  337: #ifdef DBUS_BUILD_TESTS
  338:       table->find_function = find_two_strings_function;
  339: #endif
  340:       break;
  341:     default:
  342:       _dbus_assert_not_reached ("Unknown hash table type");
  343:       break;
  344:     }
  345: 
  346:   table->free_key_function = key_free_function;
  347:   table->free_value_function = value_free_function;
  348: 
  349:   return table;
  350: }
  351: 
  352: 
  353: /**
  354:  * Increments the reference count for a hash table.
  355:  *
  356:  * @param table the hash table to add a reference to.
  357:  * @returns the hash table.
  358:  */
  359: DBusHashTable *
  360: _dbus_hash_table_ref (DBusHashTable *table)
  361: {
  362:   table->refcount += 1;
  363:   
  364:   return table;
  365: }
  366: 
  367: /**
  368:  * Decrements the reference count for a hash table,
  369:  * freeing the hash table if the count reaches zero.
  370:  *
  371:  * @param table the hash table to remove a reference from.
  372:  */
  373: void
  374: _dbus_hash_table_unref (DBusHashTable *table)
  375: {
  376:   table->refcount -= 1;
  377: 
  378:   if (table->refcount == 0)
  379:     {
  380: #if 0
  381:       DBusHashEntry *entry;
  382:       DBusHashEntry *next;
  383:       int i;
  384: 
  385:       /* Free the entries in the table. */
  386:       for (i = 0; i < table->n_buckets; i++)
  387:         {
  388:           entry = table->buckets[i];
  389:           while (entry != NULL)
  390:             {
  391:               next = entry->next;
  392: 
  393:               free_entry (table, entry);
  394:               
  395:               entry = next;
  396:             }
  397:         }
  398: #else
  399:       DBusHashEntry *entry;
  400:       int i;
  401: 
  402:       /* Free the entries in the table. */
  403:       for (i = 0; i < table->n_buckets; i++)
  404:         {
  405:           entry = table->buckets[i];
  406:           while (entry != NULL)
  407:             {
  408:               free_entry_data (table, entry);
  409:               
  410:               entry = entry->next;
  411:             }
  412:         }
  413:       /* We can do this very quickly with memory pools ;-) */
  414:       _dbus_mem_pool_free (table->entry_pool);
  415: #endif
  416:       
  417:       /* Free the bucket array, if it was dynamically allocated. */
  418:       if (table->buckets != table->static_buckets)
  419:         dbus_free (table->buckets);
  420: 
  421:       dbus_free (table);
  422:     }
  423: }
  424: 
  425: /**
  426:  * Removed all entries from a hash table.
  427:  *
  428:  * @param table the hash table to remove all entries from.
  429:  */
  430: void
  431: _dbus_hash_table_remove_all (DBusHashTable *table)
  432: {
  433:   DBusHashIter iter;
  434:   _dbus_hash_iter_init (table, &iter);
  435:   while (_dbus_hash_iter_next (&iter))
  436:     {
  437:       _dbus_hash_iter_remove_entry(&iter);
  438:     }
  439: }
  440: 
  441: static DBusHashEntry*
  442: alloc_entry (DBusHashTable *table)
  443: {
  444:   DBusHashEntry *entry;
  445: 
  446:   entry = _dbus_mem_pool_alloc (table->entry_pool);
  447:   
  448:   return entry;
  449: }
  450: 
  451: static void
  452: free_entry_data (DBusHashTable  *table,
  453:                  DBusHashEntry  *entry)
  454: {
  455:   if (table->free_key_function)
  456:     (* table->free_key_function) (entry->key);
  457:   if (table->free_value_function)
  458:     (* table->free_value_function) (entry->value);
  459: }
  460: 
  461: static void
  462: free_entry (DBusHashTable  *table,
  463:             DBusHashEntry  *entry)
  464: {
  465:   free_entry_data (table, entry);
  466:   _dbus_mem_pool_dealloc (table->entry_pool, entry);
  467: }
  468: 
  469: static void
  470: remove_entry (DBusHashTable  *table,
  471:               DBusHashEntry **bucket,
  472:               DBusHashEntry  *entry)
  473: {
  474:   _dbus_assert (table != NULL);
  475:   _dbus_assert (bucket != NULL);
  476:   _dbus_assert (*bucket != NULL);  
  477:   _dbus_assert (entry != NULL);
  478:   
  479:   if (*bucket == entry)
  480:     *bucket = entry->next;
  481:   else
  482:     {
  483:       DBusHashEntry *prev;
  484:       prev = *bucket;
  485: 
  486:       while (prev->next != entry)
  487:         prev = prev->next;      
  488:       
  489:       _dbus_assert (prev != NULL);
  490: 
  491:       prev->next = entry->next;
  492:     }
  493:   
  494:   table->n_entries -= 1;
  495:   free_entry (table, entry);
  496: }
  497: 
  498: /**
  499:  * Initializes a hash table iterator. To iterate over all entries in a
  500:  * hash table, use the following code (the printf assumes a hash
  501:  * from strings to strings obviously):
  502:  *
  503:  * @code
  504:  * DBusHashIter iter;
  505:  *
  506:  * _dbus_hash_iter_init (table, &iter);
  507:  * while (_dbus_hash_iter_next (&iter))
  508:  *   {
  509:  *      printf ("The first key is %s and value is %s\n",
  510:  *              _dbus_hash_iter_get_string_key (&iter),
  511:  *              _dbus_hash_iter_get_value (&iter));
  512:  *   }
  513:  * 
  514:  * 
  515:  * @endcode
  516:  *
  517:  * The iterator is initialized pointing "one before" the first hash
  518:  * entry. The first call to _dbus_hash_iter_next() moves it onto
  519:  * the first valid entry or returns #FALSE if the hash table is
  520:  * empty. Subsequent calls move to the next valid entry or return
  521:  * #FALSE if there are no more entries.
  522:  *
  523:  * Note that it is guaranteed to be safe to remove a hash entry during
  524:  * iteration, but it is not safe to add a hash entry.
  525:  * 
  526:  * @param table the hash table to iterate over.
  527:  * @param iter the iterator to initialize.
  528:  */
  529: void
  530: _dbus_hash_iter_init (DBusHashTable *table,
  531:                       DBusHashIter  *iter)
  532: {
  533:   DBusRealHashIter *real;
  534:   
  535:   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
  536:   
  537:   real = (DBusRealHashIter*) iter;
  538: 
  539:   real->table = table;
  540:   real->bucket = NULL;
  541:   real->entry = NULL;
  542:   real->next_entry = NULL;
  543:   real->next_bucket = 0;
  544:   real->n_entries_on_init = table->n_entries;
  545: }
  546: 
  547: /**
  548:  * Move the hash iterator forward one step, to the next hash entry.
  549:  * The documentation for _dbus_hash_iter_init() explains in more
  550:  * detail.
  551:  *
  552:  * @param iter the iterator to move forward.
  553:  * @returns #FALSE if there are no more entries to move to.
  554:  */
  555: dbus_bool_t
  556: _dbus_hash_iter_next (DBusHashIter  *iter)
  557: {
  558:   DBusRealHashIter *real;
  559:   
  560:   _dbus_assert (sizeof (DBusHashIter) == sizeof (DBusRealHashIter));
  561:   
  562:   real = (DBusRealHashIter*) iter;
  563: 
  564:   /* if this assertion failed someone probably added hash entries
  565:    * during iteration, which is bad.
  566:    */
  567:   _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
  568:   
  569:   /* Remember that real->entry may have been deleted */
  570:   
  571:   while (real->next_entry == NULL)
  572:     {
  573:       if (real->next_bucket >= real->table->n_buckets)
  574:         {
  575:           /* invalidate iter and return false */
  576:           real->entry = NULL;
  577:           real->table = NULL;
  578:           real->bucket = NULL;
  579:           return FALSE;
  580:         }
  581: 
  582:       real->bucket = &(real->table->buckets[real->next_bucket]);
  583:       real->next_entry = *(real->bucket);
  584:       real->next_bucket += 1;
  585:     }
  586: 
  587:   _dbus_assert (real->next_entry != NULL);
  588:   _dbus_assert (real->bucket != NULL);
  589:   
  590:   real->entry = real->next_entry;
  591:   real->next_entry = real->entry->next;
  592:   
  593:   return TRUE;
  594: }
  595: 
  596: /**
  597:  * Removes the current entry from the hash table.
  598:  * If a key_free_function or value_free_function
  599:  * was provided to _dbus_hash_table_new(),
  600:  * frees the key and/or value for this entry.
  601:  *
  602:  * @param iter the hash table iterator.
  603:  */
  604: void
  605: _dbus_hash_iter_remove_entry (DBusHashIter *iter)
  606: {
  607:   DBusRealHashIter *real;
  608: 
  609:   real = (DBusRealHashIter*) iter;
  610: 
  611:   _dbus_assert (real->table != NULL);
  612:   _dbus_assert (real->entry != NULL);
  613:   _dbus_assert (real->bucket != NULL);
  614:   
  615:   remove_entry (real->table, real->bucket, real->entry);
  616: 
  617:   real->entry = NULL; /* make it crash if you try to use this entry */
  618: }
  619: