lib/names-hash.c

   1 /*
   2  *      The PCI Library -- ID to Name Hash
   3  *
   4  *      Copyright (c) 1997--2008 Martin Mares <mj@ucw.cz>
   5  *
   6  *      Can be freely distributed and used under the terms of the GNU GPL.
   7  */
   8
   9 #include <string.h>
  10
  11 #include "internal.h"
  12 #include "names.h"
  13
  14 struct id_bucket {
  15   struct id_bucket *next;
  16   unsigned int full;
  17 };
  18
  19 #ifdef __GNUC__
  20 #define BUCKET_ALIGNMENT __alignof__(struct id_bucket)
  21 #else
  22 union id_align {
  23   struct id_bucket *next;
  24   unsigned int full;
  25 };
  26 #define BUCKET_ALIGNMENT sizeof(union id_align)
  27 #endif
  28 #define BUCKET_ALIGN(n) ((n)+BUCKET_ALIGNMENT-(n)%BUCKET_ALIGNMENT)
  29
  30 static void *id_alloc(struct pci_access *a, unsigned int size)
  31 {
  32   struct id_bucket *buck = a->current_id_bucket;
  33   unsigned int pos;
  34
  35   if (!a->id_hash)
  36     {
  37       a->id_hash = pci_malloc(a, sizeof(struct id_entry *) * HASH_SIZE);
  38       memset(a->id_hash, 0, sizeof(struct id_entry *) * HASH_SIZE);
  39     }
  40
  41   if (!buck || buck->full + size > BUCKET_SIZE)
  42     {
  43       buck = pci_malloc(a, BUCKET_SIZE);
  44       buck->next = a->current_id_bucket;
  45       a->current_id_bucket = buck;
  46       buck->full = BUCKET_ALIGN(sizeof(struct id_bucket));
  47     }
  48   pos = buck->full;
  49   buck->full = BUCKET_ALIGN(buck->full + size);
  50   return (byte *)buck + pos;
  51 }
  52
  53 static inline unsigned int id_hash(int cat, u32 id12, u32 id34)
  54 {
  55   unsigned int h;
  56
  57   h = id12 ^ (id34 << 3) ^ (cat << 5);
  58   return h % HASH_SIZE;
  59 }
  60
  61 int
  62 pci_id_insert(struct pci_access *a, int cat, int id1, int id2, int id3, int id4, char *text, enum id_entry_src src)
  63 {
  64   u32 id12 = id_pair(id1, id2);
  65   u32 id34 = id_pair(id3, id4);
  66   unsigned int h = id_hash(cat, id12, id34);
  67   struct id_entry *n = a->id_hash ? a->id_hash[h] : NULL;
  68   int len = strlen(text);
  69
  70   while (n && (n->id12 != id12 || n->id34 != id34 || n->cat != cat))
  71     n = n->next;
  72   if (n)
  73     return 1;
  74   n = id_alloc(a, sizeof(struct id_entry) + len);
  75   n->id12 = id12;
  76   n->id34 = id34;
  77   n->cat = cat;
  78   n->src = src;
  79   memcpy(n->name, text, len+1);
  80   n->next = a->id_hash[h];
  81   a->id_hash[h] = n;
  82   return 0;
  83 }
  84
  85 char
  86 *pci_id_lookup(struct pci_access *a, int flags, int cat, int id1, int id2, int id3, int id4)
  87 {
  88   struct id_entry *n, *best;
  89   u32 id12 = id_pair(id1, id2);
  90   u32 id34 = id_pair(id3, id4);
  91
  92   if (a->id_hash)
  93     {
  94       n = a->id_hash[id_hash(cat, id12, id34)];
  95       best = NULL;
  96       for (; n; n=n->next)
  97         {
  98           if (n->id12 != id12 || n->id34 != id34 || n->cat != cat)
  99             continue;
 100           if (n->src == SRC_LOCAL && (flags & PCI_LOOKUP_SKIP_LOCAL))
 101             continue;
 102           if (n->src == SRC_NET && !(flags & PCI_LOOKUP_NETWORK))
 103             continue;
 104           if (n->src == SRC_CACHE && !(flags & PCI_LOOKUP_CACHE))
 105             continue;
 106           if (!best || best->src < n->src)
 107             best = n;
 108         }
 109       if (best)
 110         return best->name;
 111     }
 112   return NULL;
 113 }
 114
 115 void
 116 pci_id_hash_free(struct pci_access *a)
 117 {
 118   pci_mfree(a->id_hash);
 119   a->id_hash = NULL;
 120   while (a->current_id_bucket)
 121     {
 122       struct id_bucket *buck = a->current_id_bucket;
 123       a->current_id_bucket = buck->next;
 124       pci_mfree(buck);
 125     }
 126 }