summaryrefslogtreecommitdiff
AgeCommit message (Expand)Author
2006-08-08Add support for Intel i965G chipsets.Alan Hourihane
2006-08-07drm: whitespace cleanup in new filesDave Airlie
2006-08-07drm: remove extra whitespace from drm_mm.cDave Airlie
2006-08-07drm: fixup whitespace and style for Linux kernel importDave Airlie
2006-07-26Revert "Make sure busmastering gets disabled on module unload."Michel Dänzer
2006-07-26Bug #7629: Fix for CHIP_IS_AGP getting 'restored' with non-AGP cardsMichel Dänzer
2006-07-24remove incorrect exit marking on cleanup pci as this is called from other pathsDave Airlie
2006-07-24switch drm to use Linux mutexes instead of semaphore.Dave Airlie
2006-07-19Delete the pre-core DRM code with extreme prejudice.Adam Jackson
2006-07-19Make sure busmastering gets disabled on module unload.Adam Jackson
2006-07-19Use RADEON_RB3D_DSTCACHE_CTLSTAT instead of RADEON_RB2D_DSTCACHE_CTLSTAT.Michel Dänzer
2006-07-19Make sure CHIP_IS_AGP flag is set when not overriding to PCI mode.Michel Dänzer
2006-07-19When writeback isn't used, actually disable it in the hardware.Michel Dänzer
2006-07-19Implement RADEON_PARAM_SCRATCH_OFFSET getparam.Michel Dänzer
2006-07-19Some debug output when the getparam ioctl is called with an unknown parameter.Michel Dänzer
2006-07-19.cvsignore -> .gitignoreMichel Dänzer
2006-07-11Keep hashed user tokens, with the following changes:Thomas Hellstrom
2006-07-10Change drm Map handles to be arbitrary 32-bit hash tokens in the rangeThomas Hellstrom
2006-07-05SiS 315 Awareness.Thomas Hellstrom
2006-07-05Add missing semaphore release.Thomas Hellstrom
2006-06-27Disable building static libraries. Bump to 2.0.2 for header updates.Adam Jackson
2006-06-23Fix compilation problem on 2.6.9 kernels (bug #6211)Alan Hourihane
2006-06-22Remove spurious debug messages from i915 vblank config pathsKeith Packard
2006-06-21i915: Save vblank pipe configuration to restore on resumeKeith Packard
2006-06-19Add i915 ioctls to configure pipes for vblank interrupt.Keith Packard
2006-06-19Fix buffer cleanup on close. Move memory manager reset from final_contextThomas Hellstrom
2006-06-19via: Bump version number and date.Thomas Hellstrom
2006-06-16via: Return the requested size instead of the correct size of the allocatedThomas Hellstrom
2006-06-15via:Thomas Hellstrom
2006-06-06s/list_entry/drm_hash_entry/ for "drm_hash_item"s.Thomas Hellstrom
2006-06-06Fix drm_remove_magic potential memory leak / corruption. Move drmThomas Hellstrom
2006-06-06Merge in the drm-sman-branchThomas Hellstrom
2006-05-28file via_mm.c was initially added on branch drm-sman-branch.Thomas Hellstrom
2006-05-28file drm_sman.h was initially added on branch drm-sman-branch.Thomas Hellstrom
2006-05-28file sis_mm.c was initially added on branch drm-sman-branch.Thomas Hellstrom
2006-05-28file drm_sman.c was initially added on branch drm-sman-branch.Thomas Hellstrom
2006-05-26file drm_hashtab.h was initially added on branch drm-ttm-branch.Thomas Hellstrom
2006-05-24Add support for r200 vertex programs (R200_EMIT_VAP_PVS_CNTL, and newRoland Scheidegger
2006-05-20add forgotten register define for previous commitRoland Scheidegger
2006-05-20Do a tcl state flush before accessing tcl vector space. This fixes someRoland Scheidegger
2006-05-19rip out unneeded back compat codeDave Airlie
2006-05-18add consts to radeon microcode.Dave Airlie
2006-05-17Set entry->virtual for sg maps, fixing ATI PCI/PCIE GART support.Eric Anholt
2006-05-17Add the bits for vblank support on FreeBSD, which most importantly avoidsEric Anholt
2006-05-17Add the workaround that's in the kernel to suppress GCC's warning aboutEric Anholt
2006-04-23fixup GFP_COMP for older kernels and get_page/put_page for newerDave Airlie
2006-04-23Fix from Benh for ppc r300 scratchDave Airlie
2006-04-20check for __FreeBSD_kernel__ (bug 3810)Brian Paul
2006-04-18Err, use "ifndef" rather than "if !", to avoid compiler warning.Eric Anholt
2006-04-18Reorder the DRM_*_AGP enum to match linux's numbers (oops). Fixes i915Eric Anholt
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-22 06:25:40 +0000
7' href='#n377'>377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 
/* xf86drmHash.c -- Small hash table support for integer -> integer mapping
 * Created: Sun Apr 18 09:35:45 1999 by faith@precisioninsight.com
 *
 * Copyright 1999 Precision Insight, Inc., Cedar Park, Texas.
 * All Rights Reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * PRECISION INSIGHT AND/OR ITS SUPPLIERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
 * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 *
 * Authors: Rickard E. (Rik) Faith <faith@valinux.com>
 *
 * DESCRIPTION
 *
 * This file contains a straightforward implementation of a fixed-sized
 * hash table using self-organizing linked lists [Knuth73, pp. 398-399] for
 * collision resolution.  There are two potentially interesting things
 * about this implementation:
 *
 * 1) The table is power-of-two sized.  Prime sized tables are more
 * traditional, but do not have a significant advantage over power-of-two
 * sized table, especially when double hashing is not used for collision
 * resolution.
 *
 * 2) The hash computation uses a table of random integers [Hanson97,
 * pp. 39-41].
 *
 * FUTURE ENHANCEMENTS
 *
 * With a table size of 512, the current implementation is sufficient for a
 * few hundred keys.  Since this is well above the expected size of the
 * tables for which this implementation was designed, the implementation of
 * dynamic hash tables was postponed until the need arises.  A common (and
 * naive) approach to dynamic hash table implementation simply creates a
 * new hash table when necessary, rehashes all the data into the new table,
 * and destroys the old table.  The approach in [Larson88] is superior in
 * two ways: 1) only a portion of the table is expanded when needed,
 * distributing the expansion cost over several insertions, and 2) portions
 * of the table can be locked, enabling a scalable thread-safe
 * implementation.
 *
 * REFERENCES
 *
 * [Hanson97] David R. Hanson.  C Interfaces and Implementations:
 * Techniques for Creating Reusable Software.  Reading, Massachusetts:
 * Addison-Wesley, 1997.
 *
 * [Knuth73] Donald E. Knuth. The Art of Computer Programming.  Volume 3:
 * Sorting and Searching.  Reading, Massachusetts: Addison-Wesley, 1973.
 *
 * [Larson88] Per-Ake Larson. "Dynamic Hash Tables".  CACM 31(4), April
 * 1988, pp. 446-457.
 *
 */

#include <stdio.h>
#include <stdlib.h>

#define HASH_MAIN 0

#if !HASH_MAIN
# include "xf86drm.h"
#endif

#define HASH_MAGIC 0xdeadbeef
#define HASH_DEBUG 0
#define HASH_SIZE  512		/* Good for about 100 entries */
				/* If you change this value, you probably
                                   have to change the HashHash hashing
                                   function! */

#if HASH_MAIN
#define HASH_ALLOC malloc
#define HASH_FREE  free
#define HASH_RANDOM_DECL
#define HASH_RANDOM_INIT(seed)  srandom(seed)
#define HASH_RANDOM             random()
#define HASH_RANDOM_DESTROY
#else
#define HASH_ALLOC drmMalloc
#define HASH_FREE  drmFree
#define HASH_RANDOM_DECL        void *state
#define HASH_RANDOM_INIT(seed)  state = drmRandomCreate(seed)
#define HASH_RANDOM             drmRandom(state)
#define HASH_RANDOM_DESTROY     drmRandomDestroy(state)

#endif

typedef struct HashBucket {
    unsigned long     key;
    void              *value;
    struct HashBucket *next;
} HashBucket, *HashBucketPtr;

typedef struct HashTable {
    unsigned long    magic;
    unsigned long    entries;
    unsigned long    hits;	/* At top of linked list */
    unsigned long    partials;	/* Not at top of linked list */
    unsigned long    misses;	/* Not in table */
    HashBucketPtr    buckets[HASH_SIZE];
    int              p0;
    HashBucketPtr    p1;
} HashTable, *HashTablePtr;

#if HASH_MAIN
extern void *drmHashCreate(void);
extern int  drmHashDestroy(void *t);
extern int  drmHashLookup(void *t, unsigned long key, unsigned long *value);
extern int  drmHashInsert(void *t, unsigned long key, unsigned long value);
extern int  drmHashDelete(void *t, unsigned long key);
#endif

static unsigned long HashHash(unsigned long key)
{
    unsigned long        hash = 0;
    unsigned long        tmp  = key;
    static int           init = 0;
    static unsigned long scatter[256];
    int                  i;

    if (!init) {
	HASH_RANDOM_DECL;
	HASH_RANDOM_INIT(37);
	for (i = 0; i < 256; i++) scatter[i] = HASH_RANDOM;
	HASH_RANDOM_DESTROY;
	++init;
    }

    while (tmp) {
	hash = (hash << 1) + scatter[tmp & 0xff];
	tmp >>= 8;
    }

    hash %= HASH_SIZE;
#if HASH_DEBUG
    printf( "Hash(%d) = %d\n", key, hash);
#endif
    return hash;
}

void *drmHashCreate(void)
{
    HashTablePtr table;
    int          i;

    table           = HASH_ALLOC(sizeof(*table));
    if (!table) return NULL;
    table->magic    = HASH_MAGIC;
    table->entries  = 0;
    table->hits     = 0;
    table->partials = 0;
    table->misses   = 0;

    for (i = 0; i < HASH_SIZE; i++) table->buckets[i] = NULL;
    return table;
}

int drmHashDestroy(void *t)
{
    HashTablePtr  table = (HashTablePtr)t;
    HashBucketPtr bucket;
    HashBucketPtr next;
    int           i;

    if (table->magic != HASH_MAGIC) return -1; /* Bad magic */

    for (i = 0; i < HASH_SIZE; i++) {
	for (bucket = table->buckets[i]; bucket;) {
	    next = bucket->next;
	    HASH_FREE(bucket);
	    bucket = next;
	}
    }
    HASH_FREE(table);
    return 0;
}

/* Find the bucket and organize the list so that this bucket is at the
   top. */

static HashBucketPtr HashFind(HashTablePtr table,
			      unsigned long key, unsigned long *h)
{
    unsigned long hash = HashHash(key);
    HashBucketPtr prev = NULL;
    HashBucketPtr bucket;

    if (h) *h = hash;

    for (bucket = table->buckets[hash]; bucket; bucket = bucket->next) {
	if (bucket->key == key) {
	    if (prev) {
				/* Organize */
		prev->next           = bucket->next;
		bucket->next         = table->buckets[hash];
		table->buckets[hash] = bucket;
		++table->partials;
	    } else {
		++table->hits;
	    }
	    return bucket;
	}
	prev = bucket;
    }
    ++table->misses;
    return NULL;
}

int drmHashLookup(void *t, unsigned long key, void **value)
{
    HashTablePtr  table = (HashTablePtr)t;
    HashBucketPtr bucket;