Integrated red-black tree algorithm for tree allocators
[keystone-rtos/rm-lld.git] / include / rm_loc.h
index bebad4543fee3e30ca5a64394746da9931199bb7..18717972c76af0f180fcaef4c60691ca239fc741 100644 (file)
@@ -49,70 +49,13 @@ extern "C" {
 #include <ti/drv/rm/rm_policy.h>
 #include <ti/drv/rm/rm_transport.h>
 
-#if 0
-/* RM permissions structure for CPPI DMA channels and flows */
-typedef struct
-{
-    /** Array of pointers to each DMAs channel or flow permissions
-       * From CPPI LLD - DMA 0 = SRIO
-       *                          DMA 1 = AIF
-       *                          DMA 2 = FFTC A
-       *                          DMA 3 = FFTC B
-       *                          DMA 4 = PASS
-       *                          DMA 5 = QMSS
-       *                          DMA 6 = FFTC C
-       *                          DMA 7 = BCP 
-       * 
-       * Note: Some DMAs may not be supported based on the device */
-    Rm_Perms *dmaPermPtrs[RM_CPPI_MAX_DMAS];
-} Rm_CppiChAndFlowPerms;
-
-/* RM Cache Line Alignment Defines and Macros */
-
-#define RM_MAX_CACHE_ALIGN 128  /* Maximum alignment for cache line size */
-
-/* This macro generates compiler error if postulate is false, so 
- * allows 0 overhead compile time size check.  This "works" when
- * the expression contains sizeof() which otherwise doesn't work
- * with preprocessor */
-#define RM_COMPILE_TIME_SIZE_CHECK(postulate)                         \
-   do {                                                                 \
-       typedef struct {                                                 \
-         uint8_t NegativeSizeIfPostulateFalse[((int)(postulate))*2 - 1];\
-       } PostulateCheck_t;                                              \
-   }                                                                    \
-   while (0)
-
-/* Macro to pad out internal permission structures to multiple of RM_MAX_CACHE_ALIGN bytes
-  * The macro prevent something else from being placed on same cache line as the permission.  
-  * arrays.  Note that pad[0] is illegal, so must add full RM_MAX_CACHE_ALIGN if structure
-  * is already padded by chance. */
-#define RM_ALIGN_PERMISSIONS_ARRAY(numElements, permStructType) ( \
-     (((sizeof(permStructType) * (numElements)) % RM_MAX_CACHE_ALIGN) == 0) ? (numElements) : \
-     ((numElements) + \
-       (RM_MAX_CACHE_ALIGN - \
-         ((sizeof(permStructType) * (numElements)) % RM_MAX_CACHE_ALIGN))/sizeof(permStructType)))
-
-/* RM Global Sync Object (unpadded) */
-typedef struct
-{
-    /** Rm_init/Rm_start synchronization object. */
-    uint8_t globalSyncObj;
-} Rm_Sync_Obj_Unpadded;
-
-/* RM Global Sync Object (padded) */
-typedef struct
-{
-    /** Data structure without padding, so sizeof() can compute padding */
-    Rm_Sync_Obj_Unpadded obj;
-    /** Pad out to end of RM_MAX_CACHE_ALIGN bytes to prevent something else
-     * from being placed on same cache line as Rm_Synci_Obj.  Note that 
-     * pad[0] is illegal, so must add full RM_MAX_CACHE_ALIGN if structure
-     * is already padded by chance. */
-    uint8_t  pad[RM_MAX_CACHE_ALIGN - 
-                       (sizeof(Rm_Sync_Obj_Unpadded) % RM_MAX_CACHE_ALIGN)];
-} Rm_Sync_Obj;
-#endif
+/* AVL BBST includes */
+#include <ti/drv/rm/include/tree.h>
+
+/** String stored for resource elements that are not currently allocated to anyone.  If the
+ *  resource is allocated the allocatedTo field will be populated with the RM instance
+ *  name it was allocated to. */
+#define RM_NOT_ALLOCATED_STRING "\0"
 
 /** Maximum size of a transmittable RM policy in bytes */
 #define RM_MAX_POLICY_SIZE_BYTES (64)  // Placeholder: This will change 
@@ -203,9 +146,20 @@ typedef enum {
     Rm_allocatorType_TREE = 1,
 } Rm_AllocatorType;
 
+typedef enum {
+    Rm_allocatorOp_ALLOCATE = 0,
+    Rm_allocatorOp_FREE = 1,
+    Rm_allocatorOp_PRE_ALLOCATE = 2,
+} Rm_AllocatorOp;
+
+typedef struct {
+    char *srcInstName;
+    Rm_AllocatorOp operation;
+    Rm_ResourceInfo *resourceInfo;
+} Rm_AllocatorOpInfo;
+
 typedef struct {
     uint32_t value;
-    bool allocated;
     char allocatedTo[RM_INSTANCE_NAME_MAX_CHARS];
 } Rm_IntegerEntry;
 
@@ -247,6 +201,35 @@ uint32_t Rm_transactionGetSequenceNum(Rm_Inst *rmInst);
 
 void Rm_transactionProcessor (Rm_Inst *rmInst, Rm_Transaction *transaction);
 
+/**********************************************************************
+ ******************* Red-Black Tree BBST Defines **********************
+ **********************************************************************/
+
+/* Declare the tree structure nodes */
+typedef struct _Rm_ResourceTreeNode {
+    RB_ENTRY(_Rm_ResourceTreeNode) linkage;
+    uint32_t base;
+    uint32_t length;
+    char allocatedTo[RM_INSTANCE_NAME_MAX_CHARS];
+} Rm_ResourceTreeNode;
+
+/* Will need to malloc a tree of type Rm_ResourceTree for each tree i want to create */
+/* Declare the tree head structure */
+typedef RB_HEAD(_Rm_ResourceTree, _Rm_ResourceTreeNode) Rm_ResourceTree;
+
+/* Prototype for function that allocates new tree nodes */
+Rm_ResourceTreeNode *Rm_newResourceTreeNode(uint32_t resourceBase, uint32_t resourceLength);
+/* Prototype for function that frees new tree nodes */
+void Rm_freeResourceTreeNode(Rm_ResourceTreeNode *treeNode);
+/* Prototype for tree node comparison function
+ * element1 < element2 --> return < 0
+ * element1 = element2 --> return 0
+ * element1 > element2 --> return > 0 */
+int Rm_ResourceTreeNodeCompare(Rm_ResourceTreeNode *element1, Rm_ResourceTreeNode *element2); 
+
+/* Generate the tree prototypes */
+RB_PROTOTYPE(_Rm_ResourceTree, _Rm_ResourceTreeNode, linkage, Rm_ResourceTreeNodeCompare);
+
 #ifdef __cplusplus
 }
 #endif