Lines Matching refs:table
2 /* dbus-hash.c Generic hash table utility (internal to D-Bus implementation)
8 * Hash table implementation based on generic/tclHash.c from the Tcl
83 * @defgroup DBusHashTable Hash table
91 * @defgroup DBusHashTableInternals Hash table implementation details
102 * the hash table to make it larger.
122 #define RANDOM_INDEX(table, i) \
123 (((((intptr_t) (i))*1103515245) >> (table)->down_shift) & (table)->mask)
126 * Initial number of buckets in hash table (hash table statically
140 * A single entry (key-value pair) in the hash table.
141 * Internal to hash table implementation.
156 typedef DBusHashEntry* (* DBusFindEntryFunction) (DBusHashTable *table,
165 * Hash table internals. Hash tables are opaque objects, they must be
183 * in table.
185 int hi_rebuild_size; /**< Enlarge table when n_entries gets
188 int lo_rebuild_size; /**< Shrink table when n_entries gets
198 DBusHashType key_type; /**< Type of keys used in this table */
214 DBusHashTable *table; /**< Pointer to table containing entry. */
222 int n_entries_on_init; /**< used to detect table resize since initialization */
227 static DBusHashEntry* find_direct_function (DBusHashTable *table,
232 static DBusHashEntry* find_string_function (DBusHashTable *table,
238 static void rebuild_table (DBusHashTable *table);
239 static DBusHashEntry* alloc_entry (DBusHashTable *table);
240 static void remove_entry (DBusHashTable *table,
243 static void free_entry (DBusHashTable *table,
245 static void free_entry_data (DBusHashTable *table,
259 * Public opaque hash table iterator object.
265 * Public opaque hash table object.
271 * Indicates the type of a key in the hash table.
275 * Constructs a new hash table. Should be freed with
277 * allocated for the hash table, returns #NULL.
289 DBusHashTable *table;
292 table = dbus_new0 (DBusHashTable, 1);
293 if (table == NULL)
299 dbus_free (table);
303 table->refcount = 1;
304 table->entry_pool = entry_pool;
306 _dbus_assert (DBUS_SMALL_HASH_TABLE == _DBUS_N_ELEMENTS (table->static_buckets));
308 table->buckets = table->static_buckets;
309 table->n_buckets = DBUS_SMALL_HASH_TABLE;
310 table->n_entries = 0;
311 table->hi_rebuild_size = DBUS_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
312 table->lo_rebuild_size = 0;
313 table->down_shift = 28;
314 table->mask = 3;
315 table->key_type = type;
317 _dbus_assert (table->mask < table->n_buckets);
319 switch (table->key_type)
323 table->find_function = find_direct_function;
326 table->find_function = find_string_function;
329 _dbus_assert_not_reached ("Unknown hash table type");
333 table->free_key_function = key_free_function;
334 table->free_value_function = value_free_function;
336 return table;
341 * Increments the reference count for a hash table.
343 * @param table the hash table to add a reference to.
344 * @returns the hash table.
347 _dbus_hash_table_ref (DBusHashTable *table)
349 table->refcount += 1;
351 return table;
355 * Decrements the reference count for a hash table,
356 * freeing the hash table if the count reaches zero.
358 * @param table the hash table to remove a reference from.
361 _dbus_hash_table_unref (DBusHashTable *table)
363 table->refcount -= 1;
365 if (table->refcount == 0)
372 /* Free the entries in the table. */
373 for (i = 0; i < table->n_buckets; i++)
375 entry = table->buckets[i];
380 free_entry (table, entry);
389 /* Free the entries in the table. */
390 for (i = 0; i < table->n_buckets; i++)
392 entry = table->buckets[i];
395 free_entry_data (table, entry);
401 _dbus_mem_pool_free (table->entry_pool);
405 if (table->buckets != table->static_buckets)
406 dbus_free (table->buckets);
408 dbus_free (table);
413 * Removed all entries from a hash table.
415 * @param table the hash table to remove all entries from.
418 _dbus_hash_table_remove_all (DBusHashTable *table)
421 _dbus_hash_iter_init (table, &iter);
429 alloc_entry (DBusHashTable *table)
433 entry = _dbus_mem_pool_alloc (table->entry_pool);
439 free_entry_data (DBusHashTable *table,
442 if (table->free_key_function)
443 (* table->free_key_function) (entry->key);
444 if (table->free_value_function)
445 (* table->free_value_function) (entry->value);
449 free_entry (DBusHashTable *table,
452 free_entry_data (table, entry);
453 _dbus_mem_pool_dealloc (table->entry_pool, entry);
457 remove_entry (DBusHashTable *table,
461 _dbus_assert (table != NULL);
481 table->n_entries -= 1;
482 free_entry (table, entry);
486 * Initializes a hash table iterator. To iterate over all entries in a
487 * hash table, use the following code (the printf assumes a hash
493 * _dbus_hash_iter_init (table, &iter);
506 * the first valid entry or returns #FALSE if the hash table is
513 * @param table the hash table to iterate over.
517 _dbus_hash_iter_init (DBusHashTable *table,
526 real->table = table;
531 real->n_entries_on_init = table->n_entries;
554 _dbus_assert (real->n_entries_on_init >= real->table->n_entries);
560 if (real->next_bucket >= real->table->n_buckets)
564 real->table = NULL;
569 real->bucket = &(real->table->buckets[real->next_bucket]);
584 * Removes the current entry from the hash table.
589 * @param iter the hash table iterator.
598 _dbus_assert (real->table != NULL);
602 remove_entry (real->table, real->bucket, real->entry);
610 * @param iter the hash table iterator.
619 _dbus_assert (real->table != NULL);
627 * If the hash table has a value_free_function
629 * The hash table will own the passed-in value
632 * @param iter the hash table iterator.
643 _dbus_assert (real->table != NULL);
646 if (real->table->free_value_function && value != real->entry->value)
647 (* real->table->free_value_function) (real->entry->value);
656 * @param iter the hash table iterator.
665 _dbus_assert (real->table != NULL);
675 * @param iter the hash table iterator.
684 _dbus_assert (real->table != NULL);
693 * @param iter the hash table iterator.
702 _dbus_assert (real->table != NULL);
710 * table. It's efficient because you can get, set, and optionally
728 * table takes ownership of the key that's passed in.
730 * For a hash table of type #DBUS_HASH_INT, cast the int
733 * @param table the hash table.
740 _dbus_hash_iter_lookup (DBusHashTable *table,
753 entry = (* table->find_function) (table, key, create_if_not_found, &bucket, NULL);
758 real->table = table;
762 real->next_bucket = (bucket - table->buckets) + 1;
763 real->n_entries_on_init = table->n_entries;
765 _dbus_assert (&(table->buckets[real->next_bucket-1]) == real->bucket);
771 add_allocated_entry (DBusHashTable *table,
781 b = &(table->buckets[idx]);
788 table->n_entries += 1;
791 * table and remove entries safely.
793 if (table->n_entries >= table->hi_rebuild_size ||
794 table->n_entries < table->lo_rebuild_size)
795 rebuild_table (table);
799 add_entry (DBusHashTable *table,
809 entry = alloc_entry (table);
822 add_allocated_entry (table, entry, idx, key, bucket);
847 find_generic_function (DBusHashTable *table,
861 entry = table->buckets[idx];
868 *bucket = &(table->buckets[idx]);
871 _dbus_hash_table_free_preallocated_entry (table, preallocated);
880 entry = add_entry (table, idx, key, bucket, preallocated);
882 _dbus_hash_table_free_preallocated_entry (table, preallocated);
888 find_string_function (DBusHashTable *table,
896 idx = string_hash (key) & table->mask;
898 return find_generic_function (table, key, idx,
904 find_direct_function (DBusHashTable *table,
912 idx = RANDOM_INDEX (table, key) & table->mask;
915 return find_generic_function (table, key, idx,
921 rebuild_table (DBusHashTable *table)
935 growing = table->n_entries >= table->hi_rebuild_size;
937 old_size = table->n_buckets;
938 old_buckets = table->buckets;
943 if (table->n_buckets < _DBUS_INT_MAX / 4 &&
944 table->down_shift >= 0)
945 new_buckets = table->n_buckets * 4;
951 new_buckets = table->n_buckets / 4;
956 table->buckets = dbus_new0 (DBusHashEntry*, new_buckets);
957 if (table->buckets == NULL)
959 /* out of memory, yay - just don't reallocate, the table will
962 table->buckets = old_buckets;
966 table->n_buckets = new_buckets;
970 table->lo_rebuild_size = table->hi_rebuild_size;
971 table->hi_rebuild_size *= 4;
973 table->down_shift -= 2; /* keep 2 more high bits */
974 table->mask = (table->mask << 2) + 3; /* keep 2 more high bits */
978 table->hi_rebuild_size = table->lo_rebuild_size;
979 table->lo_rebuild_size /= 4;
981 table->down_shift += 2; /* keep 2 fewer high bits */
982 table->mask = table->mask >> 2; /* keep 2 fewer high bits */
986 printf ("%s table to lo = %d hi = %d downshift = %d mask = 0x%x\n",
988 table->lo_rebuild_size,
989 table->hi_rebuild_size,
990 table->down_shift,
991 table->mask);
994 _dbus_assert (table->lo_rebuild_size >= 0);
995 _dbus_assert (table->hi_rebuild_size > table->lo_rebuild_size);
996 _dbus_assert (table->mask != 0);
998 _dbus_assert (table->mask < table->n_buckets);
1012 switch (table->key_type)
1015 idx = string_hash (entry->key) & table->mask;
1019 idx = RANDOM_INDEX (table, entry->key);
1023 _dbus_assert_not_reached ("Unknown hash table type");
1027 bucket = &(table->buckets[idx]);
1035 if (old_buckets != table->static_buckets)
1040 * Looks up the value for a given string in a hash table
1044 * @param table the hash table.
1049 _dbus_hash_table_lookup_string (DBusHashTable *table,
1054 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1056 entry = (* table->find_function) (table, (char*) key, FALSE, NULL, NULL);
1065 * Looks up the value for a given integer in a hash table
1069 * @param table the hash table.
1074 _dbus_hash_table_lookup_int (DBusHashTable *table,
1079 _dbus_assert (table->key_type == DBUS_HASH_INT);
1081 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, NULL, NULL);
1090 * Looks up the value for a given integer in a hash table
1094 * @param table the hash table.
1099 _dbus_hash_table_lookup_uintptr (DBusHashTable *table,
1104 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
1106 entry = (* table->find_function) (table, (void*) key, FALSE, NULL, NULL);
1118 * @param table the hash table.
1123 _dbus_hash_table_remove_string (DBusHashTable *table,
1129 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1131 entry = (* table->find_function) (table, (char*) key, FALSE, &bucket, NULL);
1135 remove_entry (table, bucket, entry);
1146 * @param table the hash table.
1151 _dbus_hash_table_remove_int (DBusHashTable *table,
1157 _dbus_assert (table->key_type == DBUS_HASH_INT);
1159 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), FALSE, &bucket, NULL);
1163 remove_entry (table, bucket, entry);
1174 * @param table the hash table.
1179 _dbus_hash_table_remove_uintptr (DBusHashTable *table,
1185 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
1187 entry = (* table->find_function) (table, (void*) key, FALSE, &bucket, NULL);
1191 remove_entry (table, bucket, entry);
1201 * in the hash table by reference. If an entry with the
1203 * are overwritten (and freed if the hash table has
1209 * @param table the hash table.
1214 _dbus_hash_table_insert_string (DBusHashTable *table,
1220 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1222 preallocated = _dbus_hash_table_preallocate_entry (table);
1226 _dbus_hash_table_insert_string_preallocated (table, preallocated,
1235 * in the hash table by reference. If an entry with the
1237 * are overwritten (and freed if the hash table has
1243 * @param table the hash table.
1248 _dbus_hash_table_insert_int (DBusHashTable *table,
1254 _dbus_assert (table->key_type == DBUS_HASH_INT);
1256 entry = (* table->find_function) (table, _DBUS_INT_TO_POINTER (key), TRUE, NULL, NULL);
1261 if (table->free_key_function && entry->key != _DBUS_INT_TO_POINTER (key))
1262 (* table->free_key_function) (entry->key);
1264 if (table->free_value_function && entry->value != value)
1265 (* table->free_value_function) (entry->value);
1276 * in the hash table by reference. If an entry with the
1278 * are overwritten (and freed if the hash table has
1284 * @param table the hash table.
1289 _dbus_hash_table_insert_uintptr (DBusHashTable *table,
1295 _dbus_assert (table->key_type == DBUS_HASH_UINTPTR);
1297 entry = (* table->find_function) (table, (void*) key, TRUE, NULL, NULL);
1302 if (table->free_key_function && entry->key != (void*) key)
1303 (* table->free_key_function) (entry->key);
1305 if (table->free_value_function && entry->value != value)
1306 (* table->free_value_function) (entry->value);
1316 * hash table at a later time without allocating any memory.
1318 * @param table the hash table
1322 _dbus_hash_table_preallocate_entry (DBusHashTable *table)
1326 entry = alloc_entry (table);
1333 * in order to insert into the hash table.
1335 * @param table the hash table
1339 _dbus_hash_table_free_preallocated_entry (DBusHashTable *table,
1349 _dbus_mem_pool_dealloc (table->entry_pool, entry);
1353 * Inserts a string-keyed entry into the hash table, using a
1360 * @param table the hash table
1366 _dbus_hash_table_insert_string_preallocated (DBusHashTable *table,
1373 _dbus_assert (table->key_type == DBUS_HASH_STRING);
1376 entry = (* table->find_function) (table, key, TRUE, NULL, preallocated);
1380 if (table->free_key_function && entry->key != key)
1381 (* table->free_key_function) (entry->key);
1383 if (table->free_value_function && entry->value != value)
1384 (* table->free_value_function) (entry->value);
1391 * Gets the number of hash entries in a hash table.
1393 * @param table the hash table.
1394 * @returns the number of entries in the table.
1397 _dbus_hash_table_get_n_entries (DBusHashTable *table)
1399 return table->n_entries;
1408 /* If you're wondering why the hash table test takes
1413 count_entries (DBusHashTable *table)
1419 _dbus_hash_iter_init (table, &iter);
1423 _dbus_assert (count == _dbus_hash_table_get_n_entries (table));
1484 /* Insert and remove a bunch of stuff, counting the table in between
1669 /* add/remove interleaved, to check that we grow/shrink the table