drm_hashtab.c

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  *
    3  * Copyright 2006 Tungsten Graphics, Inc., Bismarck, ND. USA.
    4  * All Rights Reserved.
    5  *
    6  * Permission is hereby granted, free of charge, to any person obtaining a
    7  * copy of this software and associated documentation files (the
    8  * "Software"), to deal in the Software without restriction, including
    9  * without limitation the rights to use, copy, modify, merge, publish,
   10  * distribute, sub license, and/or sell copies of the Software, and to
   11  * permit persons to whom the Software is furnished to do so, subject to
   12  * the following conditions:
   13  *
   14  * The above copyright notice and this permission notice (including the
   15  * next paragraph) shall be included in all copies or substantial portions
   16  * of the Software.
   17  *
   18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
   19  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
   20  * FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT. IN NO EVENT SHALL
   21  * THE COPYRIGHT HOLDERS, AUTHORS AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM,
   22  * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
   23  * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
   24  * USE OR OTHER DEALINGS IN THE SOFTWARE.
   25  *
   26  *
   27  **************************************************************************/
   28 
   29 #include <sys/cdefs.h>
   30 __FBSDID("$FreeBSD$");
   31 
   32 /*
   33  * Simple open hash tab implementation.
   34  *
   35  * Authors:
   36  * Thomas Hellström <thomas-at-tungstengraphics-dot-com>
   37  */
   38 
   39 #include <dev/drm2/drmP.h>
   40 #include <dev/drm2/drm_hashtab.h>
   41 
   42 #include <sys/hash.h>
   43 
   44 int drm_ht_create(struct drm_open_hash *ht, unsigned int order)
   45 {
   46         ht->size = 1 << order;
   47         ht->order = order;
   48         ht->table = NULL;
   49         ht->table = hashinit_flags(ht->size, DRM_MEM_HASHTAB, &ht->mask,
   50             HASH_NOWAIT);
   51         if (!ht->table) {
   52                 DRM_ERROR("Out of memory for hash table\n");
   53                 return -ENOMEM;
   54         }
   55         return 0;
   56 }
   57 EXPORT_SYMBOL(drm_ht_create);
   58 
   59 void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key)
   60 {
   61         struct drm_hash_item *entry;
   62         struct drm_hash_item_list *h_list;
   63         unsigned int hashed_key;
   64         int count = 0;
   65 
   66         hashed_key = hash32_buf(&key, sizeof(key), ht->order);
   67         DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key);
   68         h_list = &ht->table[hashed_key & ht->mask];
   69         LIST_FOREACH(entry, h_list, head)
   70                 DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key);
   71 }
   72 
   73 static struct drm_hash_item *drm_ht_find_key(struct drm_open_hash *ht,
   74                                           unsigned long key)
   75 {
   76         struct drm_hash_item *entry;
   77         struct drm_hash_item_list *h_list;
   78         unsigned int hashed_key;
   79 
   80         hashed_key = hash32_buf(&key, sizeof(key), ht->order);
   81         h_list = &ht->table[hashed_key & ht->mask];
   82         LIST_FOREACH(entry, h_list, head) {
   83                 if (entry->key == key)
   84                         return entry;
   85                 if (entry->key > key)
   86                         break;
   87         }
   88         return NULL;
   89 }
   90 
   91 
   92 int drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item)
   93 {
   94         struct drm_hash_item *entry, *parent;
   95         struct drm_hash_item_list *h_list;
   96         unsigned int hashed_key;
   97         unsigned long key = item->key;
   98 
   99         hashed_key = hash32_buf(&key, sizeof(key), ht->order);
  100         h_list = &ht->table[hashed_key & ht->mask];
  101         parent = NULL;
  102         LIST_FOREACH(entry, h_list, head) {
  103                 if (entry->key == key)
  104                         return -EINVAL;
  105                 if (entry->key > key)
  106                         break;
  107                 parent = entry;
  108         }
  109         if (parent) {
  110                 LIST_INSERT_AFTER(parent, item, head);
  111         } else {
  112                 LIST_INSERT_HEAD(h_list, item, head);
  113         }
  114         return 0;
  115 }
  116 EXPORT_SYMBOL(drm_ht_insert_item);
  117 
  118 /*
  119  * Just insert an item and return any "bits" bit key that hasn't been
  120  * used before.
  121  */
  122 int drm_ht_just_insert_please(struct drm_open_hash *ht, struct drm_hash_item *item,
  123                               unsigned long seed, int bits, int shift,
  124                               unsigned long add)
  125 {
  126         int ret;
  127         unsigned long mask = (1 << bits) - 1;
  128         unsigned long first, unshifted_key = 0;
  129 
  130         unshifted_key = hash32_buf(&seed, sizeof(seed), unshifted_key);
  131         first = unshifted_key;
  132         do {
  133                 item->key = (unshifted_key << shift) + add;
  134                 ret = drm_ht_insert_item(ht, item);
  135                 if (ret)
  136                         unshifted_key = (unshifted_key + 1) & mask;
  137         } while(ret && (unshifted_key != first));
  138 
  139         if (ret) {
  140                 DRM_ERROR("Available key bit space exhausted\n");
  141                 return -EINVAL;
  142         }
  143         return 0;
  144 }
  145 EXPORT_SYMBOL(drm_ht_just_insert_please);
  146 
  147 int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key,
  148                      struct drm_hash_item **item)
  149 {
  150         struct drm_hash_item *entry;
  151 
  152         entry = drm_ht_find_key(ht, key);
  153         if (!entry)
  154                 return -EINVAL;
  155 
  156         *item = entry;
  157         return 0;
  158 }
  159 EXPORT_SYMBOL(drm_ht_find_item);
  160 
  161 int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key)
  162 {
  163         struct drm_hash_item *entry;
  164 
  165         entry = drm_ht_find_key(ht, key);
  166         if (entry) {
  167                 LIST_REMOVE(entry, head);
  168                 return 0;
  169         }
  170         return -EINVAL;
  171 }
  172 
  173 int drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item)
  174 {
  175         LIST_REMOVE(item, head);
  176         return 0;
  177 }
  178 EXPORT_SYMBOL(drm_ht_remove_item);
  179 
  180 void drm_ht_remove(struct drm_open_hash *ht)
  181 {
  182         if (ht->table) {
  183                 hashdestroy(ht->table, DRM_MEM_HASHTAB, ht->mask);
  184                 ht->table = NULL;
  185         }
  186 }
  187 EXPORT_SYMBOL(drm_ht_remove);

Cache object: fa0574ef0a203e4d00f09b7f0da47b5c

[ 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.

FreeBSD/Linux Kernel Cross Reference sys/dev/drm2/drm_hashtab.c

FreeBSD/Linux Kernel Cross Reference
sys/dev/drm2/drm_hashtab.c