Integrated red-black tree algorithm for tree allocators
authorJustin Sobota <jsobota@ti.com>
Mon, 10 Dec 2012 23:55:32 +0000 (18:55 -0500)
committerJustin Sobota <jsobota@ti.com>
Mon, 10 Dec 2012 23:55:32 +0000 (18:55 -0500)
include/rm_loc.h
include/rm_nameserverloc.h
include/tree.h [new file with mode: 0644]
rm_services.h
src/rm.c
src/rm_nameserver.c
src/rm_policy.c
src/rm_services.c
src/rm_transport.c

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
index a8f68c10c6198d3cfab521a7fb0e1408e11674d1..91b5a3bc99ebbb1adb55e77e00b1ad0348af0c99 100644 (file)
@@ -1,7 +1,7 @@
 /*
- *  file  rmnameserverloc.h
+ *  file  rm_nameserverloc.h
  *
- *  Private data structures of Resource Manager NameServer.
+ *  Prototypes and data structures for the Resource Manager NameServer.
  *
  *  ============================================================================
  *      (C) Copyright 2012, Texas Instruments, Inc.
@@ -37,8 +37,8 @@
  *  \par
 */
 
-#ifndef RMNAMESERVERLOC_H_
-#define RMNAMESERVERLOC_H_
+#ifndef RM_NAMESERVERLOC_H_
+#define RM_NAMESERVERLOC_H_
 
 #ifdef __cplusplus
 extern "C" {
@@ -60,5 +60,5 @@ int32_t Rm_nsDeleteObject(Rm_Inst *rmInst, char *objectString);
 }
 #endif
 
-#endif /* RMNAMESERVERLOC_H_ */
+#endif /* RM_NAMESERVERLOC_H_ */
 
diff --git a/include/tree.h b/include/tree.h
new file mode 100644 (file)
index 0000000..80d0f53
--- /dev/null
@@ -0,0 +1,748 @@
+/*     $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $       */
+/*
+ * Copyright 2002 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef        _SYS_TREE_H_
+#define        _SYS_TREE_H_
+
+/*
+ * This file defines data structures for different types of trees:
+ * splay trees and red-black trees.
+ *
+ * A splay tree is a self-organizing data structure.  Every operation
+ * on the tree causes a splay to happen.  The splay moves the requested
+ * node to the root of the tree and partly rebalances it.
+ *
+ * This has the benefit that request locality causes faster lookups as
+ * the requested nodes move to the top of the tree.  On the other hand,
+ * every lookup causes memory writes.
+ *
+ * The Balance Theorem bounds the total access time for m operations
+ * and n inserts on an initially empty tree as O((m + n)lg n).  The
+ * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
+ *
+ * A red-black tree is a binary search tree with the node color as an
+ * extra attribute.  It fulfills a set of conditions:
+ *     - every search path from the root to a leaf consists of the
+ *       same number of black nodes,
+ *     - each red node (except for the root) has a black parent,
+ *     - each leaf node is black.
+ *
+ * Every operation on a red-black tree is bounded as O(lg n).
+ * The maximum height of a red-black tree is 2lg (n+1).
+ */
+
+#define SPLAY_HEAD(name, type)                                         \
+struct name {                                                          \
+       struct type *sph_root; /* root of the tree */                   \
+}
+
+#define SPLAY_INITIALIZER(root)                                                \
+       { NULL }
+
+#define SPLAY_INIT(root) do {                                          \
+       (root)->sph_root = NULL;                                        \
+} while (0)
+
+#define SPLAY_ENTRY(type)                                              \
+struct {                                                               \
+       struct type *spe_left; /* left element */                       \
+       struct type *spe_right; /* right element */                     \
+}
+
+#define SPLAY_LEFT(elm, field)         (elm)->field.spe_left
+#define SPLAY_RIGHT(elm, field)                (elm)->field.spe_right
+#define SPLAY_ROOT(head)               (head)->sph_root
+#define SPLAY_EMPTY(head)              (SPLAY_ROOT(head) == NULL)
+
+/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
+#define SPLAY_ROTATE_RIGHT(head, tmp, field) do {                      \
+       SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field);  \
+       SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
+       (head)->sph_root = tmp;                                         \
+} while (0)
+       
+#define SPLAY_ROTATE_LEFT(head, tmp, field) do {                       \
+       SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field);  \
+       SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
+       (head)->sph_root = tmp;                                         \
+} while (0)
+
+#define SPLAY_LINKLEFT(head, tmp, field) do {                          \
+       SPLAY_LEFT(tmp, field) = (head)->sph_root;                      \
+       tmp = (head)->sph_root;                                         \
+       (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);         \
+} while (0)
+
+#define SPLAY_LINKRIGHT(head, tmp, field) do {                         \
+       SPLAY_RIGHT(tmp, field) = (head)->sph_root;                     \
+       tmp = (head)->sph_root;                                         \
+       (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);        \
+} while (0)
+
+#define SPLAY_ASSEMBLE(head, node, left, right, field) do {            \
+       SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
+       SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
+       SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
+       SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
+} while (0)
+
+/* Generates prototypes and inline functions */
+
+#define SPLAY_PROTOTYPE(name, type, field, cmp)                                \
+void name##_SPLAY(struct name *, struct type *);                       \
+void name##_SPLAY_MINMAX(struct name *, int);                          \
+struct type *name##_SPLAY_INSERT(struct name *, struct type *);                \
+struct type *name##_SPLAY_REMOVE(struct name *, struct type *);                \
+                                                                       \
+/* Finds the node with the same key as elm */                          \
+static __inline struct type *                                          \
+name##_SPLAY_FIND(struct name *head, struct type *elm)                 \
+{                                                                      \
+       if (SPLAY_EMPTY(head))                                          \
+               return(NULL);                                           \
+       name##_SPLAY(head, elm);                                        \
+       if ((cmp)(elm, (head)->sph_root) == 0)                          \
+               return (head->sph_root);                                \
+       return (NULL);                                                  \
+}                                                                      \
+                                                                       \
+static __inline struct type *                                          \
+name##_SPLAY_NEXT(struct name *head, struct type *elm)                 \
+{                                                                      \
+       name##_SPLAY(head, elm);                                        \
+       if (SPLAY_RIGHT(elm, field) != NULL) {                          \
+               elm = SPLAY_RIGHT(elm, field);                          \
+               while (SPLAY_LEFT(elm, field) != NULL) {                \
+                       elm = SPLAY_LEFT(elm, field);                   \
+               }                                                       \
+       } else                                                          \
+               elm = NULL;                                             \
+       return (elm);                                                   \
+}                                                                      \
+                                                                       \
+static __inline struct type *                                          \
+name##_SPLAY_MIN_MAX(struct name *head, int val)                       \
+{                                                                      \
+       name##_SPLAY_MINMAX(head, val);                                 \
+        return (SPLAY_ROOT(head));                                     \
+}
+
+/* Main splay operation.
+ * Moves node close to the key of elm to top
+ */
+#define SPLAY_GENERATE(name, type, field, cmp)                         \
+struct type *                                                          \
+name##_SPLAY_INSERT(struct name *head, struct type *elm)               \
+{                                                                      \
+    if (SPLAY_EMPTY(head)) {                                           \
+           SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL;    \
+    } else {                                                           \
+           int __comp;                                                 \
+           name##_SPLAY(head, elm);                                    \
+           __comp = (cmp)(elm, (head)->sph_root);                      \
+           if(__comp < 0) {                                            \
+                   SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
+                   SPLAY_RIGHT(elm, field) = (head)->sph_root;         \
+                   SPLAY_LEFT((head)->sph_root, field) = NULL;         \
+           } else if (__comp > 0) {                                    \
+                   SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
+                   SPLAY_LEFT(elm, field) = (head)->sph_root;          \
+                   SPLAY_RIGHT((head)->sph_root, field) = NULL;        \
+           } else                                                      \
+                   return ((head)->sph_root);                          \
+    }                                                                  \
+    (head)->sph_root = (elm);                                          \
+    return (NULL);                                                     \
+}                                                                      \
+                                                                       \
+struct type *                                                          \
+name##_SPLAY_REMOVE(struct name *head, struct type *elm)               \
+{                                                                      \
+       struct type *__tmp;                                             \
+       if (SPLAY_EMPTY(head))                                          \
+               return (NULL);                                          \
+       name##_SPLAY(head, elm);                                        \
+       if ((cmp)(elm, (head)->sph_root) == 0) {                        \
+               if (SPLAY_LEFT((head)->sph_root, field) == NULL) {      \
+                       (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
+               } else {                                                \
+                       __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
+                       (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
+                       name##_SPLAY(head, elm);                        \
+                       SPLAY_RIGHT((head)->sph_root, field) = __tmp;   \
+               }                                                       \
+               return (elm);                                           \
+       }                                                               \
+       return (NULL);                                                  \
+}                                                                      \
+                                                                       \
+void                                                                   \
+name##_SPLAY(struct name *head, struct type *elm)                      \
+{                                                                      \
+       struct type __node, *__left, *__right, *__tmp;                  \
+       int __comp;                                                     \
+\
+       SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+       __left = __right = &__node;                                     \
+\
+       while ((__comp = (cmp)(elm, (head)->sph_root))) {               \
+               if (__comp < 0) {                                       \
+                       __tmp = SPLAY_LEFT((head)->sph_root, field);    \
+                       if (__tmp == NULL)                              \
+                               break;                                  \
+                       if ((cmp)(elm, __tmp) < 0){                     \
+                               SPLAY_ROTATE_RIGHT(head, __tmp, field); \
+                               if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
+                                       break;                          \
+                       }                                               \
+                       SPLAY_LINKLEFT(head, __right, field);           \
+               } else if (__comp > 0) {                                \
+                       __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
+                       if (__tmp == NULL)                              \
+                               break;                                  \
+                       if ((cmp)(elm, __tmp) > 0){                     \
+                               SPLAY_ROTATE_LEFT(head, __tmp, field);  \
+                               if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
+                                       break;                          \
+                       }                                               \
+                       SPLAY_LINKRIGHT(head, __left, field);           \
+               }                                                       \
+       }                                                               \
+       SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
+}                                                                      \
+                                                                       \
+/* Splay with either the minimum or the maximum element                        \
+ * Used to find minimum or maximum element in tree.                    \
+ */                                                                    \
+void name##_SPLAY_MINMAX(struct name *head, int __comp) \
+{                                                                      \
+       struct type __node, *__left, *__right, *__tmp;                  \
+\
+       SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+       __left = __right = &__node;                                     \
+\
+       while (1) {                                                     \
+               if (__comp < 0) {                                       \
+                       __tmp = SPLAY_LEFT((head)->sph_root, field);    \
+                       if (__tmp == NULL)                              \
+                               break;                                  \
+                       if (__comp < 0){                                \
+                               SPLAY_ROTATE_RIGHT(head, __tmp, field); \
+                               if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
+                                       break;                          \
+                       }                                               \
+                       SPLAY_LINKLEFT(head, __right, field);           \
+               } else if (__comp > 0) {                                \
+                       __tmp = SPLAY_RIGHT((head)->sph_root, field);   \
+                       if (__tmp == NULL)                              \
+                               break;                                  \
+                       if (__comp > 0) {                               \
+                               SPLAY_ROTATE_LEFT(head, __tmp, field);  \
+                               if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
+                                       break;                          \
+                       }                                               \
+                       SPLAY_LINKRIGHT(head, __left, field);           \
+               }                                                       \
+       }                                                               \
+       SPLAY_ASSEMBLE(head, &__node, __left, __right, field);          \
+}
+
+#define SPLAY_NEGINF   -1
+#define SPLAY_INF      1
+
+#define SPLAY_INSERT(name, x, y)       name##_SPLAY_INSERT(x, y)
+#define SPLAY_REMOVE(name, x, y)       name##_SPLAY_REMOVE(x, y)
+#define SPLAY_FIND(name, x, y)         name##_SPLAY_FIND(x, y)
+#define SPLAY_NEXT(name, x, y)         name##_SPLAY_NEXT(x, y)
+#define SPLAY_MIN(name, x)             (SPLAY_EMPTY(x) ? NULL  \
+                                       : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
+#define SPLAY_MAX(name, x)             (SPLAY_EMPTY(x) ? NULL  \
+                                       : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
+
+#define SPLAY_FOREACH(x, name, head)                                   \
+       for ((x) = SPLAY_MIN(name, head);                               \
+            (x) != NULL;                                               \
+            (x) = SPLAY_NEXT(name, head, x))
+
+/* Macros that define a red-black tree */
+#define RB_HEAD(name, type)                                            \
+struct name {                                                          \
+       struct type *rbh_root; /* root of the tree */                   \
+}
+
+#define RB_INITIALIZER(root)                                           \
+       { NULL }
+
+#define RB_INIT(root) do {                                             \
+       (root)->rbh_root = NULL;                                        \
+} while (0)
+
+#define RB_BLACK       0
+#define RB_RED         1
+#define RB_ENTRY(type)                                                 \
+struct {                                                               \
+       struct type *rbe_left;          /* left element */              \
+       struct type *rbe_right;         /* right element */             \
+       struct type *rbe_parent;        /* parent element */            \
+       int rbe_color;                  /* node color */                \
+}
+
+#define RB_LEFT(elm, field)            (elm)->field.rbe_left
+#define RB_RIGHT(elm, field)           (elm)->field.rbe_right
+#define RB_PARENT(elm, field)          (elm)->field.rbe_parent
+#define RB_COLOR(elm, field)           (elm)->field.rbe_color
+#define RB_ROOT(head)                  (head)->rbh_root
+#define RB_EMPTY(head)                 (RB_ROOT(head) == NULL)
+
+#define RB_SET(elm, parent, field) do {                                        \
+       RB_PARENT(elm, field) = parent;                                 \
+       RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL;              \
+       RB_COLOR(elm, field) = RB_RED;                                  \
+} while (0)
+
+#define RB_SET_BLACKRED(black, red, field) do {                                \
+       RB_COLOR(black, field) = RB_BLACK;                              \
+       RB_COLOR(red, field) = RB_RED;                                  \
+} while (0)
+
+#ifndef RB_AUGMENT
+#define RB_AUGMENT(x)  do {} while (0)
+#endif
+
+#define RB_ROTATE_LEFT(head, elm, tmp, field) do {                     \
+       (tmp) = RB_RIGHT(elm, field);                                   \
+       if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) {             \
+               RB_PARENT(RB_LEFT(tmp, field), field) = (elm);          \
+       }                                                               \
+       RB_AUGMENT(elm);                                                \
+       if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {          \
+               if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
+                       RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
+               else                                                    \
+                       RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
+       } else                                                          \
+               (head)->rbh_root = (tmp);                               \
+       RB_LEFT(tmp, field) = (elm);                                    \
+       RB_PARENT(elm, field) = (tmp);                                  \
+       RB_AUGMENT(tmp);                                                \
+       if ((RB_PARENT(tmp, field)))                                    \
+               RB_AUGMENT(RB_PARENT(tmp, field));                      \
+} while (0)
+
+#define RB_ROTATE_RIGHT(head, elm, tmp, field) do {                    \
+       (tmp) = RB_LEFT(elm, field);                                    \
+       if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) {             \
+               RB_PARENT(RB_RIGHT(tmp, field), field) = (elm);         \
+       }                                                               \
+       RB_AUGMENT(elm);                                                \
+       if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) {          \
+               if ((elm) == RB_LEFT(RB_PARENT(elm, field), field))     \
+                       RB_LEFT(RB_PARENT(elm, field), field) = (tmp);  \
+               else                                                    \
+                       RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
+       } else                                                          \
+               (head)->rbh_root = (tmp);                               \
+       RB_RIGHT(tmp, field) = (elm);                                   \
+       RB_PARENT(elm, field) = (tmp);                                  \
+       RB_AUGMENT(tmp);                                                \
+       if ((RB_PARENT(tmp, field)))                                    \
+               RB_AUGMENT(RB_PARENT(tmp, field));                      \
+} while (0)
+
+/* Generates prototypes and inline functions */
+#define        RB_PROTOTYPE(name, type, field, cmp)                            \
+       RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
+#define        RB_PROTOTYPE_STATIC(name, type, field, cmp)                     \
+       RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
+#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr)            \
+attr void name##_RB_INSERT_COLOR(struct name *, struct type *);                \
+attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
+attr struct type *name##_RB_REMOVE(struct name *, struct type *);      \
+attr struct type *name##_RB_INSERT(struct name *, struct type *);      \
+attr struct type *name##_RB_FIND(struct name *, struct type *);                \
+attr struct type *name##_RB_NFIND(struct name *, struct type *);       \
+attr struct type *name##_RB_NEXT(struct type *);                       \
+attr struct type *name##_RB_PREV(struct type *);                       \
+attr struct type *name##_RB_MINMAX(struct name *, int);                        \
+                                                                       \
+
+/* Main rb operation.
+ * Moves node close to the key of elm to top
+ */
+#define        RB_GENERATE(name, type, field, cmp)                             \
+       RB_GENERATE_INTERNAL(name, type, field, cmp,)
+#define        RB_GENERATE_STATIC(name, type, field, cmp)                      \
+       RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
+#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr)             \
+attr void                                                              \
+name##_RB_INSERT_COLOR(struct name *head, struct type *elm)            \
+{                                                                      \
+       struct type *parent, *gparent, *tmp;                            \
+       while ((parent = RB_PARENT(elm, field)) &&                      \
+           RB_COLOR(parent, field) == RB_RED) {                        \
+               gparent = RB_PARENT(parent, field);                     \
+               if (parent == RB_LEFT(gparent, field)) {                \
+                       tmp = RB_RIGHT(gparent, field);                 \
+                       if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
+                               RB_COLOR(tmp, field) = RB_BLACK;        \
+                               RB_SET_BLACKRED(parent, gparent, field);\
+                               elm = gparent;                          \
+                               continue;                               \
+                       }                                               \
+                       if (RB_RIGHT(parent, field) == elm) {           \
+                               RB_ROTATE_LEFT(head, parent, tmp, field);\
+                               tmp = parent;                           \
+                               parent = elm;                           \
+                               elm = tmp;                              \
+                       }                                               \
+                       RB_SET_BLACKRED(parent, gparent, field);        \
+                       RB_ROTATE_RIGHT(head, gparent, tmp, field);     \
+               } else {                                                \
+                       tmp = RB_LEFT(gparent, field);                  \
+                       if (tmp && RB_COLOR(tmp, field) == RB_RED) {    \
+                               RB_COLOR(tmp, field) = RB_BLACK;        \
+                               RB_SET_BLACKRED(parent, gparent, field);\
+                               elm = gparent;                          \
+                               continue;                               \
+                       }                                               \
+                       if (RB_LEFT(parent, field) == elm) {            \
+                               RB_ROTATE_RIGHT(head, parent, tmp, field);\
+                               tmp = parent;                           \
+                               parent = elm;                           \
+                               elm = tmp;                              \
+                       }                                               \
+                       RB_SET_BLACKRED(parent, gparent, field);        \
+                       RB_ROTATE_LEFT(head, gparent, tmp, field);      \
+               }                                                       \
+       }                                                               \
+       RB_COLOR(head->rbh_root, field) = RB_BLACK;                     \
+}                                                                      \
+                                                                       \
+attr void                                                              \
+name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
+{                                                                      \
+       struct type *tmp;                                               \
+       while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) &&     \
+           elm != RB_ROOT(head)) {                                     \
+               if (RB_LEFT(parent, field) == elm) {                    \
+                       tmp = RB_RIGHT(parent, field);                  \
+                       if (RB_COLOR(tmp, field) == RB_RED) {           \
+                               RB_SET_BLACKRED(tmp, parent, field);    \
+                               RB_ROTATE_LEFT(head, parent, tmp, field);\
+                               tmp = RB_RIGHT(parent, field);          \
+                       }                                               \
+                       if ((RB_LEFT(tmp, field) == NULL ||             \
+                           RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
+                           (RB_RIGHT(tmp, field) == NULL ||            \
+                           RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
+                               RB_COLOR(tmp, field) = RB_RED;          \
+                               elm = parent;                           \
+                               parent = RB_PARENT(elm, field);         \
+                       } else {                                        \
+                               if (RB_RIGHT(tmp, field) == NULL ||     \
+                                   RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
+                                       struct type *oleft;             \
+                                       if ((oleft = RB_LEFT(tmp, field)))\
+                                               RB_COLOR(oleft, field) = RB_BLACK;\
+                                       RB_COLOR(tmp, field) = RB_RED;  \
+                                       RB_ROTATE_RIGHT(head, tmp, oleft, field);\
+                                       tmp = RB_RIGHT(parent, field);  \
+                               }                                       \
+                               RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
+                               RB_COLOR(parent, field) = RB_BLACK;     \
+                               if (RB_RIGHT(tmp, field))               \
+                                       RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
+                               RB_ROTATE_LEFT(head, parent, tmp, field);\
+                               elm = RB_ROOT(head);                    \
+                               break;                                  \
+                       }                                               \
+               } else {                                                \
+                       tmp = RB_LEFT(parent, field);                   \
+                       if (RB_COLOR(tmp, field) == RB_RED) {           \
+                               RB_SET_BLACKRED(tmp, parent, field);    \
+                               RB_ROTATE_RIGHT(head, parent, tmp, field);\
+                               tmp = RB_LEFT(parent, field);           \
+                       }                                               \
+                       if ((RB_LEFT(tmp, field) == NULL ||             \
+                           RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
+                           (RB_RIGHT(tmp, field) == NULL ||            \
+                           RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
+                               RB_COLOR(tmp, field) = RB_RED;          \
+                               elm = parent;                           \
+                               parent = RB_PARENT(elm, field);         \
+                       } else {                                        \
+                               if (RB_LEFT(tmp, field) == NULL ||      \
+                                   RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
+                                       struct type *oright;            \
+                                       if ((oright = RB_RIGHT(tmp, field)))\
+                                               RB_COLOR(oright, field) = RB_BLACK;\
+                                       RB_COLOR(tmp, field) = RB_RED;  \
+                                       RB_ROTATE_LEFT(head, tmp, oright, field);\
+                                       tmp = RB_LEFT(parent, field);   \
+                               }                                       \
+                               RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
+                               RB_COLOR(parent, field) = RB_BLACK;     \
+                               if (RB_LEFT(tmp, field))                \
+                                       RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
+                               RB_ROTATE_RIGHT(head, parent, tmp, field);\
+                               elm = RB_ROOT(head);                    \
+                               break;                                  \
+                       }                                               \
+               }                                                       \
+       }                                                               \
+       if (elm)                                                        \
+               RB_COLOR(elm, field) = RB_BLACK;                        \
+}                                                                      \
+                                                                       \
+attr struct type *                                                     \
+name##_RB_REMOVE(struct name *head, struct type *elm)                  \
+{                                                                      \
+       struct type *child, *parent, *old = elm;                        \
+       int color;                                                      \
+       if (RB_LEFT(elm, field) == NULL)                                \
+               child = RB_RIGHT(elm, field);                           \
+       else if (RB_RIGHT(elm, field) == NULL)                          \
+               child = RB_LEFT(elm, field);                            \
+       else {                                                          \
+               struct type *left;                                      \
+               elm = RB_RIGHT(elm, field);                             \
+               while ((left = RB_LEFT(elm, field)))                    \
+                       elm = left;                                     \
+               child = RB_RIGHT(elm, field);                           \
+               parent = RB_PARENT(elm, field);                         \
+               color = RB_COLOR(elm, field);                           \
+               if (child)                                              \
+                       RB_PARENT(child, field) = parent;               \
+               if (parent) {                                           \
+                       if (RB_LEFT(parent, field) == elm)              \
+                               RB_LEFT(parent, field) = child;         \
+                       else                                            \
+                               RB_RIGHT(parent, field) = child;        \
+                       RB_AUGMENT(parent);                             \
+               } else                                                  \
+                       RB_ROOT(head) = child;                          \
+               if (RB_PARENT(elm, field) == old)                       \
+                       parent = elm;                                   \
+               (elm)->field = (old)->field;                            \
+               if (RB_PARENT(old, field)) {                            \
+                       if (RB_LEFT(RB_PARENT(old, field), field) == old)\
+                               RB_LEFT(RB_PARENT(old, field), field) = elm;\
+                       else                                            \
+                               RB_RIGHT(RB_PARENT(old, field), field) = elm;\
+                       RB_AUGMENT(RB_PARENT(old, field));              \
+               } else                                                  \
+                       RB_ROOT(head) = elm;                            \
+               RB_PARENT(RB_LEFT(old, field), field) = elm;            \
+               if (RB_RIGHT(old, field))                               \
+                       RB_PARENT(RB_RIGHT(old, field), field) = elm;   \
+               if (parent) {                                           \
+                       left = parent;                                  \
+                       do {                                            \
+                               RB_AUGMENT(left);                       \
+                       } while ((left = RB_PARENT(left, field)));      \
+               }                                                       \
+               goto color;                                             \
+       }                                                               \
+       parent = RB_PARENT(elm, field);                                 \
+       color = RB_COLOR(elm, field);                                   \
+       if (child)                                                      \
+               RB_PARENT(child, field) = parent;                       \
+       if (parent) {                                                   \
+               if (RB_LEFT(parent, field) == elm)                      \
+                       RB_LEFT(parent, field) = child;                 \
+               else                                                    \
+                       RB_RIGHT(parent, field) = child;                \
+               RB_AUGMENT(parent);                                     \
+       } else                                                          \
+               RB_ROOT(head) = child;                                  \
+color:                                                                 \
+       if (color == RB_BLACK)                                          \
+               name##_RB_REMOVE_COLOR(head, parent, child);            \
+       return (old);                                                   \
+}                                                                      \
+                                                                       \
+/* Inserts a node into the RB tree */                                  \
+attr struct type *                                                     \
+name##_RB_INSERT(struct name *head, struct type *elm)                  \
+{                                                                      \
+       struct type *tmp;                                               \
+       struct type *parent = NULL;                                     \
+       int comp = 0;                                                   \
+       tmp = RB_ROOT(head);                                            \
+       while (tmp) {                                                   \
+               parent = tmp;                                           \
+               comp = (cmp)(elm, parent);                              \
+               if (comp < 0)                                           \
+                       tmp = RB_LEFT(tmp, field);                      \
+               else if (comp > 0)                                      \
+                       tmp = RB_RIGHT(tmp, field);                     \
+               else                                                    \
+                       return (tmp);                                   \
+       }                                                               \
+       RB_SET(elm, parent, field);                                     \
+       if (parent != NULL) {                                           \
+               if (comp < 0)                                           \
+                       RB_LEFT(parent, field) = elm;                   \
+               else                                                    \
+                       RB_RIGHT(parent, field) = elm;                  \
+               RB_AUGMENT(parent);                                     \
+       } else                                                          \
+               RB_ROOT(head) = elm;                                    \
+       name##_RB_INSERT_COLOR(head, elm);                              \
+       return (NULL);                                                  \
+}                                                                      \
+                                                                       \
+/* Finds the node with the same key as elm */                          \
+attr struct type *                                                     \
+name##_RB_FIND(struct name *head, struct type *elm)                    \
+{                                                                      \
+       struct type *tmp = RB_ROOT(head);                               \
+       int comp;                                                       \
+       while (tmp) {                                                   \
+               comp = cmp(elm, tmp);                                   \
+               if (comp < 0)                                           \
+                       tmp = RB_LEFT(tmp, field);                      \
+               else if (comp > 0)                                      \
+                       tmp = RB_RIGHT(tmp, field);                     \
+               else                                                    \
+                       return (tmp);                                   \
+       }                                                               \
+       return (NULL);                                                  \
+}                                                                      \
+                                                                       \
+/* Finds the first node greater than or equal to the search key */     \
+attr struct type *                                                     \
+name##_RB_NFIND(struct name *head, struct type *elm)                   \
+{                                                                      \
+       struct type *tmp = RB_ROOT(head);                               \
+       struct type *res = NULL;                                        \
+       int comp;                                                       \
+       while (tmp) {                                                   \
+               comp = cmp(elm, tmp);                                   \
+               if (comp < 0) {                                         \
+                       res = tmp;                                      \
+                       tmp = RB_LEFT(tmp, field);                      \
+               }                                                       \
+               else if (comp > 0)                                      \
+                       tmp = RB_RIGHT(tmp, field);                     \
+               else                                                    \
+                       return (tmp);                                   \
+       }                                                               \
+       return (res);                                                   \
+}                                                                      \
+                                                                       \
+/* ARGSUSED */                                                         \
+attr struct type *                                                     \
+name##_RB_NEXT(struct type *elm)                                       \
+{                                                                      \
+       if (RB_RIGHT(elm, field)) {                                     \
+               elm = RB_RIGHT(elm, field);                             \
+               while (RB_LEFT(elm, field))                             \
+                       elm = RB_LEFT(elm, field);                      \
+       } else {                                                        \
+               if (RB_PARENT(elm, field) &&                            \
+                   (elm == RB_LEFT(RB_PARENT(elm, field), field)))     \
+                       elm = RB_PARENT(elm, field);                    \
+               else {                                                  \
+                       while (RB_PARENT(elm, field) &&                 \
+                           (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
+                               elm = RB_PARENT(elm, field);            \
+                       elm = RB_PARENT(elm, field);                    \
+               }                                                       \
+       }                                                               \
+       return (elm);                                                   \
+}                                                                      \
+                                                                       \
+/* ARGSUSED */                                                         \
+attr struct type *                                                     \
+name##_RB_PREV(struct type *elm)                                       \
+{                                                                      \
+       if (RB_LEFT(elm, field)) {                                      \
+               elm = RB_LEFT(elm, field);                              \
+               while (RB_RIGHT(elm, field))                            \
+                       elm = RB_RIGHT(elm, field);                     \
+       } else {                                                        \
+               if (RB_PARENT(elm, field) &&                            \
+                   (elm == RB_RIGHT(RB_PARENT(elm, field), field)))    \
+                       elm = RB_PARENT(elm, field);                    \
+               else {                                                  \
+                       while (RB_PARENT(elm, field) &&                 \
+                           (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
+                               elm = RB_PARENT(elm, field);            \
+                       elm = RB_PARENT(elm, field);                    \
+               }                                                       \
+       }                                                               \
+       return (elm);                                                   \
+}                                                                      \
+                                                                       \
+attr struct type *                                                     \
+name##_RB_MINMAX(struct name *head, int val)                           \
+{                                                                      \
+       struct type *tmp = RB_ROOT(head);                               \
+       struct type *parent = NULL;                                     \
+       while (tmp) {                                                   \
+               parent = tmp;                                           \
+               if (val < 0)                                            \
+                       tmp = RB_LEFT(tmp, field);                      \
+               else                                                    \
+                       tmp = RB_RIGHT(tmp, field);                     \
+       }                                                               \
+       return (parent);                                                \
+}
+
+#define RB_NEGINF      -1
+#define RB_INF 1
+
+#define RB_INSERT(name, x, y)  name##_RB_INSERT(x, y)
+#define RB_REMOVE(name, x, y)  name##_RB_REMOVE(x, y)
+#define RB_FIND(name, x, y)    name##_RB_FIND(x, y)
+#define RB_NFIND(name, x, y)   name##_RB_NFIND(x, y)
+#define RB_NEXT(name, x, y)    name##_RB_NEXT(y)
+#define RB_PREV(name, x, y)    name##_RB_PREV(y)
+#define RB_MIN(name, x)                name##_RB_MINMAX(x, RB_NEGINF)
+#define RB_MAX(name, x)                name##_RB_MINMAX(x, RB_INF)
+
+#define RB_FOREACH(x, name, head)                                      \
+       for ((x) = RB_MIN(name, head);                                  \
+            (x) != NULL;                                               \
+            (x) = name##_RB_NEXT(x))
+
+#define RB_FOREACH_SAFE(x, name, head, y)                              \
+       for ((x) = RB_MIN(name, head);                                  \
+           ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1);              \
+            (x) = (y))
+
+#define RB_FOREACH_REVERSE(x, name, head)                              \
+       for ((x) = RB_MAX(name, head);                                  \
+            (x) != NULL;                                               \
+            (x) = name##_RB_PREV(x))
+
+#define RB_FOREACH_REVERSE_SAFE(x, name, head, y)                      \
+       for ((x) = RB_MAX(name, head);                                  \
+           ((x) != NULL) && ((y) = name##_RB_PREV(x), 1);              \
+            (x) = (y))
+
+#endif /* _SYS_TREE_H_ */
index 15904bc60d13ba09832321fddb7bd031ebfd86c1..f9914adbeaad9206c4f98fbf5f9ae2f1eaaefca5 100644 (file)
@@ -66,11 +66,24 @@ extern "C" {
 #define RM_SERVICE_PROCESSING (RM_SERVICE_STATE_BASE+1)
 /** RM service was approved.  The resource data in the response is valid if
  *  the service has been approved. */
-#define RM_SERVICE_APPROVED (RM_SERVICE_STATE_BASE+2)
+#define RM_SERVICE_APPROVED_AND_COMPLETED (RM_SERVICE_STATE_BASE+2)
 /** Beginning of resource denied reasons */
 #define RM_SERVICE_DENIED_BEGIN (RM_SERVICE_STATE_BASE+3)
+/** RM could not find an allocator for the resource specified with the provided name */
+#define RM_SERVICE_DENIED_RESOURCE_DOES_NOT_EXIST (RM_SERVICE_DENIED_BEGIN)
+/** A resource value within the specifed base+range could not be found within the resource's
+ *  allocator.  No action was taken on the resources. */
+#define RM_SERVICE_DENIED_RESOURCE_VALUE_IN_RANGE_DOES_NOT_EXIST (RM_SERVICE_DENIED_BEGIN+1)
+/** A resource value within the specifed base+range was not allocated to the RM instance
+ *  that is the source of the request.  No action was taken on the resources. */
+#define RM_SERVICE_DENIED_RESOURCE_NOT_ALLOCATED_TO_INSTANCE_REQUESTING_THE_SERVICE (RM_SERVICE_DENIED_BEGIN+2)
+/** A resource value within the specifed base+range is already free */
+#define RM_SERVICE_DENIED_RESOURCE_ALREADY_FREE (RM_SERVICE_DENIED_BEGIN+3)
+/** A resource value within the specifed base+range is already allocated to another
+ *  RM instance. */
+#define RM_SERVICE_DENIED_RESOURCE_ALREADY_ALLOCATED (RM_SERVICE_DENIED_BEGIN+4)
 /** End of resource denied reasons */
-#define RM_SERVICE_DENIED_END (RM_SERVICE_STATE_BASE+3)
+#define RM_SERVICE_DENIED_END (RM_SERVICE_DENIED_BEGIN+4)
 
 /** RM Service Request Error Code Base */
 #define RM_SERVICE_ERROR_BASE (-64)
@@ -110,6 +123,7 @@ extern "C" {
 /** Invalid NameServer object modification on non-Server instance */
 #define RM_SERVICE_ERROR_NAMESERVER_OBJECT_MOD_ON_INVALID_INSTANCE (RM_SERVICE_ERROR_BASE-12)
 
+
 /**
  * @brief Maximum number of characters in the resource names
  */
index 64a9dafa2025076d5dcf36341d9835d33e25be30..16b3dd72ebab462338aba2d5934295e6f44de774 100644 (file)
--- a/src/rm.c
+++ b/src/rm.c
 /* RM LIBFDT includes */\r
 #include <ti/drv/rm/src/libfdt/libfdt.h>\r
 \r
+/* AVL BBST includes */\r
+#include <ti/drv/rm/include/tree.h>\r
+\r
 /* RM OSAL layer */\r
 #include <rm_osal.h>\r
 \r
 /**********************************************************************\r
  ************************** Globals ***********************************\r
  **********************************************************************/\r
-#if 0\r
-/* Place QMSS PDSP permissions array */\r
-#pragma DATA_SECTION (rmQmssPdspFirmwarePerms, ".rm");\r
-#pragma DATA_ALIGN (rmQmssPdspFirmwarePerms, 128)\r
-Rm_Perms rmQmssPdspFirmwarePerms[RM_ALIGN_PERMISSIONS_ARRAY(RM_QMSS_FIRMWARE_PDSPS, Rm_Perms)];\r
-#endif\r
-\r
 char rmIntegerAllocator[] = "integer";\r
 char rmTreeAllocator[] = "tree";\r
 \r
@@ -79,6 +75,64 @@ extern char rmDtbStartingNode[];
 /** @brief Global Variable which describes the RM Version Information */\r
 const char   rmVersionStr[] = RM_VERSION_STR ":" __DATE__  ":" __TIME__;\r
 \r
+/**********************************************************************\r
+ ************** Red-Black BBST Tree Allocator Functions ***************\r
+ **********************************************************************/\r
+\r
+/* TODO: This needed? */\r
+/* Prototype for function that allocates new tree nodes */\r
+Rm_ResourceTreeNode *Rm_newResourceTreeNode(uint32_t resourceBase, uint32_t resourceLength)\r
+{\r
+    Rm_ResourceTreeNode *newNode = NULL;\r
+\r
+    newNode = Rm_osalMalloc(sizeof(Rm_ResourceTreeNode));\r
+\r
+    /* Populate the RM relevant fields */\r
+    newNode->base = resourceBase;\r
+    newNode->length = resourceLength;\r
+\r
+    return(newNode);\r
+}\r
+\r
+/* TODO: This needed? */\r
+/* Prototype for function that frees new tree nodes */\r
+void Rm_freeResourceTreeNode(Rm_ResourceTreeNode *treeNode)\r
+{\r
+    /* Free the memory associated with the tree node. */\r
+    Rm_osalFree((void *)treeNode, sizeof(Rm_ResourceTreeNode));\r
+}\r
+\r
+/* Prototype for tree node comparison function\r
+ * element1 < element2 --> return < 0\r
+ * element1 = element2 --> return 0\r
+ * element1 > element2 --> return > 0 */\r
+int Rm_ResourceTreeNodeCompare(Rm_ResourceTreeNode *element1, Rm_ResourceTreeNode *element2)\r
+{\r
+    uint32_t element1End = element1->base + element1->length - 1;\r
+    uint32_t element2End = element2->base + element2->length - 1;\r
+\r
+    if (element1End < element2->base)\r
+    {\r
+        /* End of element1 range is less than the start of element2's range.  Return a negative\r
+         * value */\r
+        return (-1);\r
+    }\r
+    else if (element1->base > element2End)\r
+    {\r
+        /* Start of element1 range is after end of element2's range.  Return a positive value */\r
+        return (1);\r
+    }\r
+    else\r
+    {\r
+        /* If neither of the latter conditions were satisfied there is some overlap between\r
+         * element1 and element2.  Return 0 since the application must handle this overlap. */\r
+        return (0);\r
+    }\r
+}\r
+\r
+/* Generate the red-black tree manipulation functions */\r
+RB_GENERATE(_Rm_ResourceTree, _Rm_ResourceTreeNode, linkage, Rm_ResourceTreeNodeCompare);\r
+\r
 /**********************************************************************\r
  ********************** Internal Functions ****************************\r
  **********************************************************************/\r
@@ -356,6 +410,30 @@ Rm_Allocator *Rm_allocatorAdd(Rm_Inst *rmInst, const char *resourceName, Rm_Allo
     return (newAllocator);\r
 }\r
 \r
+Rm_Allocator *Rm_allocatorFind(Rm_Inst *rmInst, char *resourceName)\r
+{\r
+    Rm_Allocator *allocator = (Rm_Allocator *)rmInst->allocators;\r
+\r
+    /* Make sure there is at least one allocator in the allocator list */\r
+    if (allocator != NULL)\r
+    {\r
+        /* Find the resource name within the allocator list.  If the end of the\r
+         * allocator list is reached without finding the resource name the \r
+         * allocator pointer will be NULL */\r
+        while (allocator != NULL)\r
+        {\r
+            if (strcmp(allocator->resourceName, resourceName) == 0)\r
+            {\r
+                /* Match: break out of loop and return the allocator */\r
+                break;             \r
+            }\r
+            allocator = allocator->nextAllocator;\r
+        }\r
+    }\r
+\r
+    return (allocator);\r
+}\r
+\r
 int32_t Rm_allocatorDelete(Rm_Inst *rmInst, char *resourceName)\r
 {\r
     Rm_Allocator *allocator = (Rm_Allocator *) rmInst->allocators;\r
@@ -447,6 +525,8 @@ int32_t Rm_createIntegerAllocator(Rm_Inst *rmInst, const char *resourceName, Rm_
             for (i = range->base; i < (range->base + range->length); i++, entryIndex++)\r
             {\r
                 intRootEntry->resourceArrayBase[entryIndex].value = i;\r
+                /* Initialize the allocatedTo field to the NOT_ALLOCATED string */\r
+                strcpy(intRootEntry->resourceArrayBase[entryIndex].allocatedTo, RM_NOT_ALLOCATED_STRING);\r
             }\r
             \r
             range = range->nextRange;\r
@@ -465,6 +545,66 @@ int32_t Rm_createIntegerAllocator(Rm_Inst *rmInst, const char *resourceName, Rm_
     return(0);  /* TODO: FIX THIS RETURN */\r
 }\r
 \r
+int32_t Rm_createTreeAllocator(Rm_Inst *rmInst, const char *resourceName, Rm_ResourceRange *range)\r
+{\r
+    Rm_Allocator *allocator = NULL;\r
+    Rm_ResourceTree *treeRootEntry = NULL;\r
+    Rm_ResourceTreeNode *treeNode = NULL;\r
+    Rm_ResourceTreeNode *collidingNode = NULL;\r
+\r
+    /* Create the new base integer allocator */\r
+    allocator = Rm_allocatorAdd(rmInst, resourceName, Rm_allocatorType_TREE);\r
+\r
+    /* Create the tree root entry and initialize it */\r
+    treeRootEntry = Rm_osalMalloc(sizeof(Rm_ResourceTree));\r
+    RB_INIT(treeRootEntry);\r
+\r
+    /* Create a node in the tree for resource range and insert them into the tree. */\r
+    while (range != NULL)\r
+    {\r
+        treeNode = Rm_osalMalloc(sizeof(Rm_ResourceTreeNode));\r
+        treeNode->base = range->base;\r
+        treeNode->length = range->length;\r
+        /* Initialize the allocatedTo field to the NOT_ALLOCATED string */\r
+        strcpy(treeNode->allocatedTo, RM_NOT_ALLOCATED_STRING);\r
+\r
+        /* Insert the node into the tree */\r
+        collidingNode = RB_INSERT(_Rm_ResourceTree, treeRootEntry, treeNode);\r
+\r
+        if (collidingNode)\r
+        {\r
+            Rm_ResourceTreeNode *nextNode = NULL;\r
+            \r
+            /* Node that was inserted colliding with an existing node.  Clean up the tree\r
+             * that's been allocated thus far and return an error since there should be no\r
+             * collisions */\r
+            for (treeNode = RB_MIN(_Rm_ResourceTree, treeRootEntry); treeNode != NULL; treeNode = nextNode)\r
+            {\r
+                       nextNode = RB_NEXT(_Rm_ResourceTree, treeRootEntry, treeNode);\r
+                       RB_REMOVE(_Rm_ResourceTree, treeRootEntry, nextNode);\r
+                       Rm_osalFree((void *)treeNode, sizeof(Rm_ResourceTreeNode));\r
+               }\r
+            /* Delete the tree root entry and the allocator */\r
+            Rm_osalFree((void *)treeRootEntry, sizeof(Rm_ResourceTree));\r
+            Rm_allocatorDelete(rmInst, allocator->resourceName);\r
+            return (-24); /* TODO FIX RETURN */\r
+        }\r
+\r
+        range = range->nextRange;\r
+    }\r
+\r
+    /* Assign the tree's root to the allocator */\r
+    allocator->allocatorRootEntry = treeRootEntry;\r
+\r
+    /* Print the base values as a test */\r
+    RB_FOREACH(treeNode, _Rm_ResourceTree, (Rm_ResourceTree *) allocator->allocatorRootEntry)\r
+    {\r
+        Rm_osalLog("Tree node base: %d length: %d and allocated to: %s\n", treeNode->base, treeNode->length, treeNode->allocatedTo);\r
+    }\r
+\r
+    return(0);   /* TODO: FIX THIS RETURN */\r
+}\r
+\r
 int32_t Rm_createAndInitAllocator(Rm_Inst *rmInst, const char *resourceName, \r
                                   Rm_ResourceProperties *resourceProperties)\r
 {\r
@@ -492,6 +632,7 @@ int32_t Rm_createAndInitAllocator(Rm_Inst *rmInst, const char *resourceName,
     else if (strcmp(allocatorType, &rmTreeAllocator[0]) == 0)\r
     {\r
         /* Create a tree allocator using the resource properties */\r
+        retVal = Rm_createTreeAllocator(rmInst, resourceName, range); \r
     }\r
     else\r
     {\r
@@ -670,92 +811,313 @@ int32_t Rm_parseResourceNode(Rm_Inst *rmInst, void *globalResourceDtb, int32_t n
     return (RM_DTB_UTIL_RESULT_OKAY);\r
 }\r
 \r
-int32_t Rm_initializeAllocators(Rm_Inst *rmInst, void *globalResourceDtb)\r
+/* Called when an allocate request is made but the base is unspecified.  RM must preallocate\r
+ * resources which then must be checked against the RM policy for the instance.  If the\r
+ * policy does not agree another resource(s) must be preallocated and tested against the \r
+ * policy.  Policy will provide initialize the preallocate with the base that it allows\r
+ * for the rm instance for the specified resource. */\r
+int32_t Rm_integerPreAllocate(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
 {\r
-    int32_t nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;\r
-    int32_t startDepth = RM_DTB_UTIL_STARTING_DEPTH;\r
-    int32_t result = RM_DTB_UTIL_RESULT_OKAY;\r
-\r
-    /* Recursively parse the Global Resource List, creating an allocator for\r
-     * each resource as specified in the node */\r
-    result = Rm_parseResourceNode(rmInst, globalResourceDtb, nodeOffset, startDepth);\r
-\r
-    return(result);\r
+    \r
 }\r
-         \r
-int32_t Rm_reserveLinuxResources(void *linuxResourceDtb)\r
+\r
+int32_t Rm_integerAllocate(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
 {\r
-    return(0);\r
+    Rm_IntegerAllocatorRootEntry *root = allocator->allocatorRootEntry;\r
+    uint16_t resourceIndex, i, j;\r
+    bool resourcesValidated = TRUE;\r
+    int32_t retVal;\r
+\r
+    /* Find the specified resource base within the allocator */\r
+    for (resourceIndex = 0; resourceIndex < root->numResourceElements; resourceIndex++)\r
+    {\r
+        if (root->resourceArrayBase[resourceIndex].value == opInfo->resourceInfo->base)\r
+        {\r
+            /* Found the resource base in the allocator.  Break from the loop */\r
+            break;\r
+        }\r
+    }\r
+\r
+    /* Only execute the allocate operation if the resource base was found in the allocator\r
+     * and the base+range does not exceed the number of entries in the allocator */\r
+    if (resourceIndex + opInfo->resourceInfo->range <= root->numResourceElements)\r
+    {\r
+        /* Verify all resource values from base to base+range exist in the allocator and\r
+         * are not allocated to another instance. */\r
+        for (i = resourceIndex, j = opInfo->resourceInfo->base; \r
+             i < (resourceIndex + opInfo->resourceInfo->range);\r
+             i++, j++)\r
+        {\r
+            if (root->resourceArrayBase[i].value != j)\r
+            {\r
+                /* A value in the range did not match. */\r
+                retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_IN_RANGE_DOES_NOT_EXIST;\r
+                resourcesValidated = FALSE;\r
+                break;\r
+            }\r
+            else if (strcmp(root->resourceArrayBase[i].allocatedTo, RM_NOT_ALLOCATED_STRING) != 0)\r
+            {\r
+                /* A value in the range is already allocated. */\r
+                retVal = RM_SERVICE_DENIED_RESOURCE_ALREADY_ALLOCATED;\r
+                resourcesValidated = FALSE;\r
+                break;            \r
+            }\r
+        }\r
 \r
+        if (resourcesValidated)\r
+        {\r
+            /* Allocate all resources from base to base+range */\r
+            for (i = resourceIndex; i < (resourceIndex + opInfo->resourceInfo->range); i++)\r
+            {\r
+                strcpy(root->resourceArrayBase[i].allocatedTo, opInfo->srcInstName);\r
+            }\r
+            retVal = RM_SERVICE_APPROVED_AND_COMPLETED;\r
+        }\r
+    }\r
+    else\r
+    {\r
+        retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_IN_RANGE_DOES_NOT_EXIST;\r
+    }\r
+\r
+    return(retVal); \r
 }\r
 \r
-void Rm_allocationHandler (Rm_Inst *rmInst, Rm_Transaction *transaction)\r
+int32_t Rm_integerFree(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
 {\r
-    if (rmInst->instType == Rm_instType_CLIENT_DELEGATE)\r
+    Rm_IntegerAllocatorRootEntry *root = allocator->allocatorRootEntry;\r
+    uint16_t resourceIndex, i, j;\r
+    bool resourcesValidated = TRUE;\r
+    int32_t retVal;\r
+\r
+    /* Find the specified resource base within the allocator */\r
+    for (resourceIndex = 0; resourceIndex < root->numResourceElements; resourceIndex++)\r
     {\r
-#if 0        \r
-        /* Check local policy to see if the request can be satisfied with the\r
-         * resources stored locally */\r
-        Rm_policy...API()\r
+        if (root->resourceArrayBase[resourceIndex].value == opInfo->resourceInfo->base)\r
+        {\r
+            /* Found the resource base in the allocator.  Break from the loop */\r
+            break;\r
+        }\r
+    }\r
 \r
-        if (policy check approves the resource)\r
+    /* Only execute the free operation if the resource base was found in the allocator\r
+     * and the base+range does not exceed the number of entries in the allocator */\r
+    if (resourceIndex + opInfo->resourceInfo->range <= root->numResourceElements)\r
+    {\r
+        /* Verify all resource values from base to base+range exist in the allocator,\r
+         * were not already free and were allocated to the instance that is the source\r
+         * of the free request. */\r
+        for (i = resourceIndex, j = opInfo->resourceInfo->base; \r
+             i < (resourceIndex + opInfo->resourceInfo->range);\r
+             i++, j++)\r
         {\r
-            /* call the allocator to allocate the resource */\r
-            if (allocator returns resource)\r
+            if (root->resourceArrayBase[i].value != j)\r
             {\r
-                /* Populate the transaction with the allocated resources and the result */\r
-                transaction->state = approve reason;\r
-                return ...\r
+                /* A value in the range did not match. */\r
+                retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_IN_RANGE_DOES_NOT_EXIST;\r
+                resourcesValidated = FALSE;\r
+                break;\r
             }\r
-            else\r
+            else if (strcmp(root->resourceArrayBase[i].allocatedTo, RM_NOT_ALLOCATED_STRING) == 0)\r
             {\r
-                /* allocator ran out of resources, need to contact Server for more\r
-                 * resources */\r
-                Rm_resourcePoolModRequest(...);\r
+                /* A value in the range is already free. */\r
+                retVal = RM_SERVICE_DENIED_RESOURCE_ALREADY_FREE;\r
+                resourcesValidated = FALSE;\r
+                break;            \r
+            }            \r
+            else if (strcmp(root->resourceArrayBase[i].allocatedTo, opInfo->srcInstName) != 0)\r
+            {\r
+                /* A value in the range was not allocated to the source of\r
+                 * the free request */\r
+                retVal = RM_SERVICE_DENIED_RESOURCE_NOT_ALLOCATED_TO_INSTANCE_REQUESTING_THE_SERVICE;\r
+                resourcesValidated = FALSE;\r
+                break;\r
             }\r
         }\r
-        else if (policy check denies resource)\r
+\r
+        if (resourcesValidated)\r
         {\r
-            /* Policy check denied resource. */\r
-            transaction->state= deny reason;\r
-            return ...\r
+            /* Free all resources from base to base+range */\r
+            for (i = resourceIndex; i < (resourceIndex + opInfo->resourceInfo->range); i++)\r
+            {\r
+                strcpy(root->resourceArrayBase[i].allocatedTo, RM_NOT_ALLOCATED_STRING);\r
+            }\r
+            retVal = RM_SERVICE_APPROVED_AND_COMPLETED;\r
         }\r
-        else if (policy check says forward to Server for validation)\r
+    }\r
+    else\r
+    {\r
+        retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_IN_RANGE_DOES_NOT_EXIST;\r
+    }\r
+\r
+    return(retVal);\r
+}\r
+\r
+/* Called when an allocate request is made but the base is unspecified.  RM must preallocate\r
+ * resources which then must be checked against the RM policy for the instance.  If the\r
+ * policy does not agree another resource(s) must be preallocated and tested against the \r
+ * policy */\r
+int32_t Rm_treePreAllocate(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
+{\r
+\r
+}\r
+\r
+int32_t Rm_treeAllocate(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
+{\r
+    \r
+}\r
+\r
+int32_t Rm_treeFree(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
+{\r
+\r
+}\r
+\r
+int32_t Rm_allocatorOperation(Rm_Inst *rmInst, Rm_AllocatorOpInfo *opInfo)\r
+{\r
+    Rm_Allocator *allocator = NULL;\r
+    int32_t retVal;\r
+    void *key;\r
+\r
+    /* Lock access to the RM instance's transaction queue */\r
+    key = Rm_osalMtCsEnter();\r
+\r
+    /* Get the specified resource's allocator */\r
+    allocator = Rm_allocatorFind(rmInst, opInfo->resourceInfo->name);\r
+\r
+    if (allocator)\r
+    {\r
+        /* Call the allocator's type-based allocation function */\r
+        if(allocator->type == Rm_allocatorType_INTEGER)\r
         {\r
-            /* Forward the transaction to the Server */\r
-            Rm_transactionForwarder(rmInst, transaction);\r
+            if (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE)\r
+            {\r
+                retVal = Rm_integerPreAllocateUnspecified(allocator, opInfo);\r
+            }            \r
+            else if (opInfo->operation == Rm_allocatorOp_ALLOCATE)\r
+            {\r
+                retVal = Rm_integerAllocate(allocator, opInfo);\r
+            }\r
+            else if (opInfo->operation == Rm_allocatorOp_FREE)\r
+            {\r
+                retVal = Rm_integerFree(allocator, opInfo);\r
+            }\r
         }\r
-#endif         \r
+        else if (allocator->type == Rm_allocatorType_TREE)\r
+        {\r
+            if (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE)\r
+            {\r
+                retVal = Rm_treePreAllocateUnspecified(allocator, opInfo);\r
+            }               \r
+            else if (opInfo->operation == Rm_allocatorOp_ALLOCATE)\r
+            {\r
+                retVal = Rm_treeAllocate(allocator, opInfo);\r
+            }\r
+            else if (opInfo->operation == Rm_allocatorOp_FREE)\r
+            {\r
+                retVal = Rm_treeFree(allocator, opInfo);\r
+            }  \r
+        }        \r
     }\r
-    else if (rmInst->instType == Rm_instType_SERVER)\r
+    else\r
     {\r
-#if 0        \r
-        /* Check global policy to see if resource can be allocated. return result\r
-         * no matter what */\r
-        Rm_policy...API()\r
+        /* Allocator could not be found for resource */\r
+        retVal = RM_SERVICE_DENIED_RESOURCE_DOES_NOT_EXIST;\r
+    }\r
 \r
-        if (policy approves)\r
+    Rm_osalMtCsExit(key);\r
+    return(retVal);\r
+}\r
+\r
+void Rm_allocationHandler (Rm_Inst *rmInst, Rm_Transaction *transaction)\r
+{\r
+    if (rmInst->instType == Rm_instType_CLIENT_DELEGATE)\r
+    {\r
+#if 0        \r
+        if (resourceBase is unspecified)\r
         {\r
-            /* call allocator to allocate resource */\r
+           while (policy does not approve)\r
+           {\r
+               Rm_policy check get allowed base as starting point for prealloc\r
+               preallocate resource based on the range and alignment\r
+               Rm_policy...check\r
+           }\r
         }\r
+        else\r
+        {\r
+            /* Check local policy to see if the request can be satisfied with the\r
+             * resources stored locally */\r
+            Rm_policy...API()\r
 \r
-        transaction->state = approve or deny reason;\r
-        transaction->resourceInfo.base = ...;\r
-        transaction->resourceInfo.range = ...;\r
-\r
-        /* If source instance name does not match the current instance\r
-         * name the allocation request came from a Client.  The result\r
-         * must be sent back to the Client */\r
-        if (strcmp(transaction->sourceInstName, rmInst->name))\r
+            if (policy check approves the resource)\r
+            {\r
+                /* call the allocator to allocate the resource */\r
+                if (allocator returns resource)\r
+                {\r
+                    /* Populate the transaction with the allocated resources and the result */\r
+                    transaction->state = approve reason;\r
+                    return ...\r
+                }\r
+                else\r
+                {\r
+                    /* allocator ran out of resources, need to contact Server for more\r
+                     * resources */\r
+                    Rm_resourcePoolModRequest(...);\r
+                }\r
+            }\r
+            else if (policy check denies resource)\r
+            {\r
+                /* Policy check denied resource. */\r
+                transaction->state= deny reason;\r
+                return ...\r
+            }\r
+            else if (policy check says forward to Server for validation)\r
+            {\r
+                /* Forward the transaction to the Server */\r
+                Rm_transactionForwarder(rmInst, transaction);\r
+            }\r
+        }\r
+#endif         \r
+    }\r
+    else if (rmInst->instType == Rm_instType_SERVER)\r
+    {\r
+#if 0       \r
+        if (resourceBase is unspecified)\r
         {\r
-            /* Names don't match.  Send the transaction back to the Client */\r
-            Rm_transactionResponder(rmInst, transaction);\r
+           while (policy does not approve)\r
+           {\r
+               Rm_policy check get allowed base as starting point for prealloc\r
+               preallocate resource based on the range and alignment\r
+               Rm_policy...check\r
+           }\r
         }\r
         else\r
         {\r
-            /* Resource allocation request originated locally on the active\r
-             * instance. Send the response via the service responder. */          \r
-            Rm_serviceResponder(rmInst, transaction);                            \r
+            /* Check global policy to see if resource can be allocated. return result\r
+             * no matter what */\r
+            Rm_policy...API()\r
+\r
+            if (policy approves)\r
+            {\r
+                /* call allocator to allocate resource */\r
+            }\r
+\r
+            transaction->state = approve or deny reason;\r
+            transaction->resourceInfo.base = ...;\r
+            transaction->resourceInfo.range = ...;\r
+\r
+            /* If source instance name does not match the current instance\r
+             * name the allocation request came from a Client.  The result\r
+             * must be sent back to the Client */\r
+            if (strcmp(transaction->sourceInstName, rmInst->name))\r
+            {\r
+                /* Names don't match.  Send the transaction back to the Client */\r
+                Rm_transactionResponder(rmInst, transaction);\r
+            }\r
+            else\r
+            {\r
+                /* Resource allocation request originated locally on the active\r
+                 * instance. Send the response via the service responder. */          \r
+                Rm_serviceResponder(rmInst, transaction);                            \r
+            }\r
         }\r
 #endif        \r
     }   \r
@@ -1003,7 +1365,7 @@ void Rm_transactionProcessor (Rm_Inst *rmInst, Rm_Transaction *transaction)
                         if (Rm_nsAddObject(rmInst, transaction->resourceInfo.nsName,\r
                                            transaction->resourceInfo.base) == RM_NS_ACTION_APPROVED)\r
                         {\r
-                            transaction->state = RM_SERVICE_APPROVED;\r
+                            transaction->state = RM_SERVICE_APPROVED_AND_COMPLETED;\r
                         }\r
                         else\r
                         {\r
@@ -1018,7 +1380,7 @@ void Rm_transactionProcessor (Rm_Inst *rmInst, Rm_Transaction *transaction)
                         if (Rm_nsDeleteObject(rmInst, transaction->resourceInfo.nsName) == \r
                             RM_NS_ACTION_APPROVED)\r
                         {\r
-                            transaction->state = RM_SERVICE_APPROVED;\r
+                            transaction->state = RM_SERVICE_APPROVED_AND_COMPLETED;\r
                         }\r
                         else\r
                         {\r
@@ -1046,6 +1408,25 @@ void Rm_transactionProcessor (Rm_Inst *rmInst, Rm_Transaction *transaction)
     }\r
 }\r
 \r
+int32_t Rm_initializeAllocators(Rm_Inst *rmInst, void *globalResourceDtb)\r
+{\r
+    int32_t nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;\r
+    int32_t startDepth = RM_DTB_UTIL_STARTING_DEPTH;\r
+    int32_t result = RM_DTB_UTIL_RESULT_OKAY;\r
+\r
+    /* Recursively parse the Global Resource List, creating an allocator for\r
+     * each resource as specified in the node */\r
+    result = Rm_parseResourceNode(rmInst, globalResourceDtb, nodeOffset, startDepth);\r
+\r
+    return(result);\r
+}\r
+         \r
+int32_t Rm_reserveLinuxResources(Rm_Inst *rmInst, void *linuxResourceDtb)\r
+{\r
+    return(0);\r
+\r
+}\r
+\r
 /**********************************************************************\r
  ********************** Application visible APIs **********************\r
  **********************************************************************/\r
@@ -1102,7 +1483,7 @@ Rm_Handle Rm_init(Rm_InitCfg *initCfg)
         {\r
             linuxResourceDtb = initCfg->linuxDtb;\r
             fdt_open_into(linuxResourceDtb, linuxResourceDtb, fdt_totalsize(linuxResourceDtb));            \r
-            Rm_reserveLinuxResources(linuxResourceDtb);\r
+            Rm_reserveLinuxResources(rmInst, linuxResourceDtb);\r
         }\r
     }\r
 \r
index 9abbe2b325a95c745c762b0ba459b884c3093f4c..858a9931974ad65684eca59072ff6eb779f68027 100644 (file)
@@ -1,5 +1,5 @@
 /**
- *   @file  rmnameserver.c
+ *   @file  rm_nameserver.c
  *
  *   @brief   
  *      This is the Resource Manager NameServer source.
index f2b11a58d10cfee01059a50a2095b535baf52e74..07525a7a148e2baaa38005b7d071e88400f533e6 100644 (file)
 
 /* RM internal API includes */
 //#include <ti/drv/rm/include/rm_policyloc.h>
+#include <ti/drv/rm/include/rm_dtb_utilloc.h>
+
+/* RM LIBFDT includes */
+#include <ti/drv/rm/src/libfdt/libfdt.h>
 
 /* RM OSAL layer */
 #include <rm_osal.h>
index 46d07fffea9ece00937f4c5ac7047e171a1fa917..fbe8119cd12ffa87294f2cf7f7fd087d99615bf2 100644 (file)
@@ -112,7 +112,7 @@ void Rm_serviceHandler (void *rmHandle, Rm_ServiceReqInfo *serviceRequest,
              * via the provided callback function */
             serviceResponse->serviceId = transaction->localId;
         }
-        else if (serviceResponse->serviceState == RM_SERVICE_APPROVED)
+        else if (serviceResponse->serviceState == RM_SERVICE_APPROVED_AND_COMPLETED)
         {
             /* Service was approved and service was an allocate request the resource
              * data is passed back to the component */
@@ -155,7 +155,7 @@ void Rm_serviceResponder (Rm_Inst *rmInst, Rm_Transaction *transaction)
 
     /* Service was approved and service was an allocate request.  The resource
      * data is passed back to the component */
-    if ((serviceResponse.serviceState == RM_SERVICE_APPROVED) &&
+    if ((serviceResponse.serviceState == RM_SERVICE_APPROVED_AND_COMPLETED) &&
         ((transaction->type == Rm_service_RESOURCE_ALLOCATE) ||
          (transaction->type == Rm_service_RESOURCE_BLOCK_ALLOCATE) ||
          (transaction->type == Rm_service_RESOURCE_ALLOCATE_BY_NAME)))
index 9864eae679a78ed33991a4d10a8b8b8488d05976..8c49337b3cdd74575cbe1d3a80045faa4a59bda8 100644 (file)
@@ -593,7 +593,7 @@ int32_t Rm_receivePktIsr(Rm_TransportHandle transportHandle, Rm_Packet *pkt)
                 /* Transfer the result of the request to the transaction */\r
                 transaction->state = resourceRespPkt->requestState;\r
 \r
-                if ((transaction->state == RM_SERVICE_APPROVED) &&\r
+                if ((transaction->state == RM_SERVICE_APPROVED_AND_COMPLETED) &&\r
                     ((transaction->type == Rm_service_RESOURCE_ALLOCATE) ||\r
                      (transaction->type == Rm_service_RESOURCE_BLOCK_ALLOCATE) ||\r
                      (transaction->type == Rm_service_RESOURCE_ALLOCATE_BY_NAME)))\r