Changeset 3a0a4d8 in mainline for kernel/generic/include/adt

Timestamp:

2013-09-12T07:54:05Z (12 years ago)

Author:

Maurizio Lombardi <m.lombardi85@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

95027b5

Parents:

47f5a77 (diff), 64f3d3b (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

merge mainline changes

Location:

kernel/generic/include/adt

Files:

• bitmap.h (modified) (1 diff)
• list.h (modified) (4 diffs)

kernel/generic/include/adt/bitmap.h

@@ -38 +38 @@
 #include <typedefs.h>
 
-#define BITS2BYTES(bits)        (bits ? ((((bits)-1)>>3)+1) : 0)
+#define BITMAP_ELEMENT   8
+#define BITMAP_REMAINER  7
 
 typedef struct {
-        uint8_t *map;
-        size_t bits;
+        size_t elements;
+        uint8_t *bits;
+        
+        size_t block_size;
+        uint8_t *blocks;
 } bitmap_t;
 
-extern void bitmap_initialize(bitmap_t *bitmap, uint8_t *map, size_t bits);
-extern void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t bits);
-extern void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t bits);
-extern void bitmap_copy(bitmap_t *dst, bitmap_t *src, size_t bits);
+static inline void bitmap_set(bitmap_t *bitmap, size_t element,
+    unsigned int value)
+{
+        if (element < bitmap->elements) {
+                /*
+                 * The 2nd level bitmap is conservative.
+                 * Make sure we update it properly.
+                 */
+                
+                if (value) {
+                        bitmap->bits[element / BITMAP_ELEMENT] |=
+                            (1 << (element & BITMAP_REMAINER));
+                } else {
+                        bitmap->bits[element / BITMAP_ELEMENT] &=
+                            ~(1 << (element & BITMAP_REMAINER));
+                        
+                        if (bitmap->block_size > 0) {
+                                size_t block = element / bitmap->block_size;
+                                
+                                bitmap->blocks[block / BITMAP_ELEMENT] &=
+                                    ~(1 << (block & BITMAP_REMAINER));
+                        }
+                }
+        }
+}
 
-static inline int bitmap_get(bitmap_t *bitmap, size_t bit)
+static inline unsigned int bitmap_get(bitmap_t *bitmap, size_t element)
 {
-        if(bit >= bitmap->bits)
+        if (element >= bitmap->elements)
                 return 0;
         
-        return !! ((bitmap->map)[bit/8] & (1 << (bit & 7)));
+        return !!((bitmap->bits)[element / BITMAP_ELEMENT] &
+            (1 << (element & BITMAP_REMAINER)));
 }
 
+extern size_t bitmap_size(size_t, size_t);
+extern void bitmap_initialize(bitmap_t *, size_t, size_t, void *);
+
+extern void bitmap_set_range(bitmap_t *, size_t, size_t);
+extern void bitmap_clear_range(bitmap_t *, size_t, size_t);
+
+extern int bitmap_allocate_range(bitmap_t *, size_t, size_t, size_t, size_t *);
+extern void bitmap_copy(bitmap_t *, bitmap_t *, size_t);
 
 #endif

kernel/generic/include/adt/list.h

@@ -1 +1 @@
 /*
  * Copyright (c) 2001-2004 Jakub Jermar
- * Copyright (c) 2011 Jiri Svoboda
+ * Copyright (c) 2013 Jiri Svoboda
  * All rights reserved.
  *
@@ -65 +65 @@
 
 #define list_get_instance(link, type, member) \
-        ((type *) (((void *)(link)) - ((void *) &(((type *) NULL)->member))))
-
-#define list_foreach(list, iterator) \
-        for (link_t *iterator = (list).head.next; \
-            iterator != &(list).head; iterator = iterator->next)
+        ((type *) (((void *)(link)) - list_link_to_void(&(((type *) NULL)->member))))
+
+#define list_foreach(list, member, itype, iterator) \
+        for (itype *iterator = NULL; iterator == NULL; iterator = (itype *) 1) \
+            for (link_t *_link = (list).head.next; \
+            iterator = list_get_instance(_link, itype, member), \
+            _link != &(list).head; _link = _link->next)
 
 #define assert_link_not_used(link) \
@@ -204 +206 @@
 }
 
+/** Get next item in list.
+ *
+ * @param link Current item link
+ * @param list List containing @a link
+ *
+ * @return Next item or NULL if @a link is the last item.
+ */
+static inline link_t *list_next(link_t *link, const list_t *list)
+{
+        return (link->next == &list->head) ? NULL : link->next;
+}
+
+/** Get previous item in list.
+ *
+ * @param link Current item link
+ * @param list List containing @a link
+ *
+ * @return Previous item or NULL if @a link is the first item.
+ */
+static inline link_t *list_prev(link_t *link, const list_t *list)
+{
+        return (link->prev == &list->head) ? NULL : link->prev;
+}
+
 /** Split or concatenate headless doubly-linked circular list
  *
@@ -270 +296 @@
 {
         unsigned int cnt = 0;
-        
-        list_foreach(*list, link) {
+        link_t *link;
+        
+        link = list_first(list);
+        while (link != NULL) {
                 if (cnt == n)
                         return link;
                 
                 cnt++;
+                link = list_next(link, list);
         }
         
         return NULL;
+}
+
+/** Verify that argument type is a pointer to link_t (at compile time).
+ *
+ * This can be used to check argument type in a macro.
+ */
+static inline const void *list_link_to_void(const link_t *link)
+{
+        return link;
 }