drivers/staging/imgtec/rogue/uniq_key_splay_tree.h

   1 /*************************************************************************/ /*!
   2 @File
   3 @Title          Splay trees interface
   4 @Copyright      Copyright (c) Imagination Technologies Ltd. All Rights Reserved
   5 @Description    Provides debug functionality
   6 @License        Dual MIT/GPLv2
   7
   8 The contents of this file are subject to the MIT license as set out below.
   9
  10 Permission is hereby granted, free of charge, to any person obtaining a copy
  11 of this software and associated documentation files (the "Software"), to deal
  12 in the Software without restriction, including without limitation the rights
  13 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  14 copies of the Software, and to permit persons to whom the Software is
  15 furnished to do so, subject to the following conditions:
  16
  17 The above copyright notice and this permission notice shall be included in
  18 all copies or substantial portions of the Software.
  19
  20 Alternatively, the contents of this file may be used under the terms of
  21 the GNU General Public License Version 2 ("GPL") in which case the provisions
  22 of GPL are applicable instead of those above.
  23
  24 If you wish to allow use of your version of this file only under the terms of
  25 GPL, and not to allow others to use your version of this file under the terms
  26 of the MIT license, indicate your decision by deleting the provisions above
  27 and replace them with the notice and other provisions required by GPL as set
  28 out in the file called "GPL-COPYING" included in this distribution. If you do
  29 not delete the provisions above, a recipient may use your version of this file
  30 under the terms of either the MIT license or GPL.
  31
  32 This License is also included in this distribution in the file called
  33 "MIT-COPYING".
  34
  35 EXCEPT AS OTHERWISE STATED IN A NEGOTIATED AGREEMENT: (A) THE SOFTWARE IS
  36 PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING
  37 BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
  38 PURPOSE AND NONINFRINGEMENT; AND (B) IN NO EVENT SHALL THE AUTHORS OR
  39 COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  40 IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  41 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  42 */ /**************************************************************************/
  43
  44 #ifndef UNIQ_KEY_SPLAY_TREE_H_
  45 #define UNIQ_KEY_SPLAY_TREE_H_
  46
  47 #include "img_types.h"
  48 #include "pvr_intrinsics.h"
  49
  50 #if defined(PVR_CTZLL)
  51   /* map the is_bucket_n_free to an int.
  52    * This way, the driver can find the first non empty without loop
  53    */
  54   typedef IMG_UINT64 IMG_ELTS_MAPPINGS;
  55 #endif
  56
  57 /* head of list of free boundary tags for indexed by pvr_log2 of the
  58    boundary tag size */
  59 #define FREE_TABLE_LIMIT 40
  60
  61 struct _BT_;
  62
  63 typedef struct img_splay_tree
  64 {
  65         /* left child/subtree */
  66     struct img_splay_tree * psLeft;
  67
  68         /* right child/subtree */
  69     struct img_splay_tree * psRight;
  70
  71     /* Flags to match on this span, used as the key. */
  72     IMG_UINT32 ui32Flags;
  73 #if defined(PVR_CTZLL)
  74         /* each bit of this int is a boolean telling if the corresponding
  75            bucket is empty or not */
  76     IMG_ELTS_MAPPINGS bHasEltsMapping;
  77 #endif
  78         struct _BT_ * buckets[FREE_TABLE_LIMIT];
  79 } IMG_SPLAY_TREE, *IMG_PSPLAY_TREE;
  80
  81 IMG_PSPLAY_TREE PVRSRVSplay (IMG_UINT32 ui32Flags, IMG_PSPLAY_TREE psTree);
  82 IMG_PSPLAY_TREE PVRSRVInsert(IMG_UINT32 ui32Flags, IMG_PSPLAY_TREE psTree);
  83 IMG_PSPLAY_TREE PVRSRVDelete(IMG_UINT32 ui32Flags, IMG_PSPLAY_TREE psTree);
  84
  85
  86 #endif /* !UNIQ_KEY_SPLAY_TREE_H_ */