The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/libkern/kxld/kxld_dict.h

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*
    2  * Copyright (c) 2007-2008 Apple Inc. All rights reserved.
    3  *
    4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
    5  * 
    6  * This file contains Original Code and/or Modifications of Original Code
    7  * as defined in and that are subject to the Apple Public Source License
    8  * Version 2.0 (the 'License'). You may not use this file except in
    9  * compliance with the License. The rights granted to you under the License
   10  * may not be used to create, or enable the creation or redistribution of,
   11  * unlawful or unlicensed copies of an Apple operating system, or to
   12  * circumvent, violate, or enable the circumvention or violation of, any
   13  * terms of an Apple operating system software license agreement.
   14  * 
   15  * Please obtain a copy of the License at
   16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
   17  * 
   18  * The Original Code and all software distributed under the License are
   19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
   20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
   21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
   22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
   23  * Please see the License for the specific language governing rights and
   24  * limitations under the License.
   25  * 
   26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
   27  */
   28 #ifndef _KXLD_DICT_H_
   29 #define _KXLD_DICT_H_
   30 
   31 #include <sys/types.h>
   32 #if KERNEL
   33     #include <libkern/kxld_types.h>
   34 #else
   35     #include "kxld_types.h"
   36 #endif
   37 
   38 #include "kxld_array.h"
   39 
   40 /*******************************************************************************
   41 * This is a dictionary implementation for hash tables with c-string keys.  It
   42 * uses linear probing for collision resolution and supports hints for hash
   43 * table size as well as automatic resizing.  All possible sizes for it are
   44 * prime or 'pseudoprime' - good choices for number of buckets.
   45 * NOTE: NULL is NOT a valid key or value!
   46 *
   47 * The dictionary also provides a basic iterator interface.  The iterator
   48 * supports a basic walk through the dictionary in unsorted order.  If the
   49 * dictionary is changed in any way while an iterator is being used, the
   50 * iterator's behavior is undefined.
   51 *******************************************************************************/
   52 
   53 struct kxld_dict;
   54 typedef struct kxld_dict KXLDDict;
   55 typedef struct kxld_dict_iterator KXLDDictIterator;
   56 
   57 typedef u_int (*kxld_dict_hash)(const KXLDDict *dict, const void *key);
   58 typedef u_int (*kxld_dict_cmp)(const void *key1, const void *key2);
   59 
   60 struct kxld_dict {
   61     KXLDArray buckets;          // The array of buckets
   62     KXLDArray resize_buckets;   // A helper array for resizing
   63     kxld_dict_hash hash;        // Hash function
   64     kxld_dict_cmp cmp;          // Comparison function
   65     u_int num_entries;          // Num entries in the dictionary
   66     u_int resize_threshold;     // Num entries we must reach to cause a resize
   67 };
   68 
   69 struct kxld_dict_iterator {
   70     u_int idx;
   71     const KXLDDict *dict;
   72 };
   73 
   74 /*******************************************************************************
   75 * Constructors and Destructors
   76 *******************************************************************************/
   77 
   78 /* Initializes a new dictionary object.
   79  * num_entries is a hint to the maximum number of entries that will be inserted
   80  */
   81 kern_return_t kxld_dict_init(KXLDDict *dict, kxld_dict_hash hash, 
   82     kxld_dict_cmp cmp, u_int num_entries) 
   83     __attribute__((nonnull, visibility("hidden")));
   84 
   85 /* Initializes a new dictionary iterator */
   86 void kxld_dict_iterator_init(KXLDDictIterator *iter, const KXLDDict *dict)
   87     __attribute__((nonnull, visibility("hidden")));
   88 
   89 /* Removes all entries from the dictionary.  The dictionary must be
   90  * reinitialized before it can be used again.
   91  */
   92 void kxld_dict_clear(KXLDDict *dict) 
   93     __attribute__((nonnull, visibility("hidden")));
   94 
   95 /* Destroys a dictionary and all of its entries */
   96 void kxld_dict_deinit(KXLDDict *dict) 
   97     __attribute__((nonnull, visibility("hidden")));
   98 
   99 /*******************************************************************************
  100 * Accessors
  101 *******************************************************************************/
  102     
  103 /* Returns the number of entries in the dictionary */
  104 u_int kxld_dict_get_num_entries(const KXLDDict *dict)
  105     __attribute__((pure, nonnull, visibility("hidden")));
  106 
  107 /* Finds a key-value pair and assigns the value to the 'value' pointer, or NULL
  108  * when not found.
  109  */
  110 void * kxld_dict_find(const KXLDDict *dict, const void *key)
  111     __attribute__((pure, nonnull, visibility("hidden")));
  112 
  113 /*******************************************************************************
  114 * Modifiers
  115 *******************************************************************************/
  116 
  117 /* Inserts a key-value pair, and will overwrite the value for a key if that key
  118  * is already in the table.
  119  */
  120 kern_return_t kxld_dict_insert(KXLDDict *dict, const void *key, void *value)
  121     __attribute__((nonnull, visibility("hidden")));
  122 
  123 /* Removes a key-value pair and assigns the value to the 'value' pointer.
  124  * 'value' pointer will be set to NULL if value to be removed is not found.
  125  * 'value pointer may be NULL if removed value is not needed.
  126  */
  127 void kxld_dict_remove(KXLDDict *dict, const void *key, void **value)
  128     __attribute__((nonnull(1,2),visibility("hidden")));
  129 
  130 /* Gets the next item in the dictionary */
  131 void kxld_dict_iterator_get_next(KXLDDictIterator *iter, const void **key, 
  132     void **value)
  133     __attribute__((nonnull, visibility("hidden")));
  134 
  135 /* Resets the iterator to the first item in the dictionary */
  136 void kxld_dict_iterator_reset(KXLDDictIterator *iter)
  137     __attribute__((nonnull, visibility("hidden")));
  138 
  139 /*******************************************************************************
  140 * Helpers
  141 *******************************************************************************/
  142 
  143 u_int kxld_dict_string_hash(const KXLDDict *dict, const void *key)
  144     __attribute__((pure, nonnull, visibility("hidden")));
  145 u_int kxld_dict_uint32_hash(const KXLDDict *dict, const void *key)
  146     __attribute__((pure, nonnull, visibility("hidden")));
  147 u_int kxld_dict_kxldaddr_hash(const KXLDDict *dict, const void *key)
  148     __attribute__((pure, nonnull, visibility("hidden")));
  149 
  150 u_int kxld_dict_string_cmp(const void *key1, const void *key2)
  151     __attribute__((pure, visibility("hidden")));
  152 u_int kxld_dict_uint32_cmp(const void *key1, const void *key2)
  153     __attribute__((pure, visibility("hidden")));
  154 u_int kxld_dict_kxldaddr_cmp(const void *key1, const void *key2)
  155     __attribute__((pure, visibility("hidden")));
  156 
  157 #endif /* _KXLD_DICT_H_ */

Cache object: e4424344640b1162f7752059f9552891


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.