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/drm/drmP.h"
   40 #include "dev/drm/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 
   58 void drm_ht_verbose_list(struct drm_open_hash *ht, unsigned long key)
   59 {
   60         struct drm_hash_item *entry;
   61         struct drm_hash_item_list *h_list;
   62         unsigned int hashed_key;
   63         int count = 0;
   64 
   65         hashed_key = hash32_buf(&key, sizeof(key), ht->order);
   66         DRM_DEBUG("Key is 0x%08lx, Hashed key is 0x%08x\n", key, hashed_key);
   67         h_list = &ht->table[hashed_key & ht->mask];
   68         LIST_FOREACH(entry, h_list, head)
   69                 DRM_DEBUG("count %d, key: 0x%08lx\n", count++, entry->key);
   70 }
   71 
   72 static struct drm_hash_item *
   73 drm_ht_find_key(struct drm_open_hash *ht, unsigned long key)
   74 {
   75         struct drm_hash_item *entry;
   76         struct drm_hash_item_list *h_list;
   77         unsigned int hashed_key;
   78 
   79         hashed_key = hash32_buf(&key, sizeof(key), ht->order);
   80         h_list = &ht->table[hashed_key & ht->mask];
   81         LIST_FOREACH(entry, h_list, head) {
   82                 if (entry->key == key)
   83                         return entry;
   84                 if (entry->key > key)
   85                         break;
   86         }
   87         return NULL;
   88 }
   89 
   90 
   91 int drm_ht_insert_item(struct drm_open_hash *ht, struct drm_hash_item *item)
   92 {
   93         struct drm_hash_item *entry, *parent;
   94         struct drm_hash_item_list *h_list;
   95         unsigned int hashed_key;
   96         unsigned long key = item->key;
   97 
   98         hashed_key = hash32_buf(&key, sizeof(key), ht->order);
   99         h_list = &ht->table[hashed_key & ht->mask];
  100         parent = NULL;
  101         LIST_FOREACH(entry, h_list, head) {
  102                 if (entry->key == key)
  103                         return -EINVAL;
  104                 if (entry->key > key)
  105                         break;
  106                 parent = entry;
  107         }
  108         if (parent) {
  109                 LIST_INSERT_AFTER(parent, item, head);
  110         } else {
  111                 LIST_INSERT_HEAD(h_list, item, head);
  112         }
  113         return 0;
  114 }
  115 
  116 /*
  117  * Just insert an item and return any "bits" bit key that hasn't been
  118  * used before.
  119  */
  120 int drm_ht_just_insert_please(struct drm_open_hash *ht, struct drm_hash_item *item,
  121                               unsigned long seed, int bits, int shift,
  122                               unsigned long add)
  123 {
  124         int ret;
  125         unsigned long mask = (1 << bits) - 1;
  126         unsigned long first, unshifted_key = 0;
  127 
  128         unshifted_key = hash32_buf(&seed, sizeof(seed), unshifted_key);
  129         first = unshifted_key;
  130         do {
  131                 item->key = (unshifted_key << shift) + add;
  132                 ret = drm_ht_insert_item(ht, item);
  133                 if (ret)
  134                         unshifted_key = (unshifted_key + 1) & mask;
  135         } while(ret && (unshifted_key != first));
  136 
  137         if (ret) {
  138                 DRM_ERROR("Available key bit space exhausted\n");
  139                 return -EINVAL;
  140         }
  141         return 0;
  142 }
  143 
  144 int drm_ht_find_item(struct drm_open_hash *ht, unsigned long key,
  145                      struct drm_hash_item **item)
  146 {
  147         struct drm_hash_item *entry;
  148 
  149         entry = drm_ht_find_key(ht, key);
  150         if (!entry)
  151                 return -EINVAL;
  152 
  153         *item = entry;
  154         return 0;
  155 }
  156 
  157 int drm_ht_remove_key(struct drm_open_hash *ht, unsigned long key)
  158 {
  159         struct drm_hash_item *entry;
  160 
  161         entry = drm_ht_find_key(ht, key);
  162         if (entry) {
  163                 LIST_REMOVE(entry, head);
  164                 return 0;
  165         }
  166         return -EINVAL;
  167 }
  168 
  169 int drm_ht_remove_item(struct drm_open_hash *ht, struct drm_hash_item *item)
  170 {
  171         LIST_REMOVE(item, head);
  172         return 0;
  173 }
  174 
  175 void drm_ht_remove(struct drm_open_hash *ht)
  176 {
  177         if (ht->table) {
  178                 hashdestroy(ht->table, DRM_MEM_HASHTAB, ht->mask);
  179                 ht->table = NULL;
  180         }
  181 }

Cache object: 0a94e25fdf8cc9a056bf7746c5829b2c

[ 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/drm/drm_hashtab.c

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