[PATCH v2 1/4] Transform xyarray to linked list

From: chenggang
Date: Tue Feb 26 2013 - 04:43:34 EST


From: chenggang <chenggang.qcg@xxxxxxxxxx>

The 2-dimensional array cannot expand and shrink easily while we want to
response the thread's fork and exit events on-the-fly.
We transform xyarray to a 2-demesional linked list. The row is still a array,
but column is implemented as a list. The number of nodes in every row are same.
The interface to append and shrink a exist xyarray is provided.
1) xyarray__append()
append a column for all rows.
2) xyarray__remove()
remove a column for all rows.

Cc: David Ahern <dsahern@xxxxxxxxx>
Cc: Peter Zijlstra <a.p.zijlstra@xxxxxxxxx>
Cc: Paul Mackerras <paulus@xxxxxxxxx>
Cc: Ingo Molnar <mingo@xxxxxxxxxx>
Cc: Arnaldo Carvalho de Melo <acme@xxxxxxxxxxxxxxxxxx>
Cc: Arjan van de Ven <arjan@xxxxxxxxxxxxxxx>
Cc: Namhyung Kim <namhyung@xxxxxxxxx>
Cc: Yanmin Zhang <yanmin.zhang@xxxxxxxxx>
Cc: Wu Fengguang <fengguang.wu@xxxxxxxxx>
Cc: Mike Galbraith <efault@xxxxxx>
Cc: Andrew Morton <akpm@xxxxxxxxxxxxxxxxxxxx>
Cc: linux-kernel <linux-kernel@xxxxxxxxxxxxxxx>
Signed-off-by: Chenggang Qin <chenggang.qcg@xxxxxxxxxx>

---
tools/perf/util/xyarray.c | 85 +++++++++++++++++++++++++++++++++++++++++----
tools/perf/util/xyarray.h | 25 +++++++++++--
2 files changed, 101 insertions(+), 9 deletions(-)

diff --git a/tools/perf/util/xyarray.c b/tools/perf/util/xyarray.c
index 22afbf6..fc48bda 100644
--- a/tools/perf/util/xyarray.c
+++ b/tools/perf/util/xyarray.c
@@ -1,20 +1,93 @@
#include "xyarray.h"
#include "util.h"

-struct xyarray *xyarray__new(int xlen, int ylen, size_t entry_size)
+/*
+ * Add a column for all rows;
+ */
+int xyarray__append(struct xyarray *xy)
{
- size_t row_size = ylen * entry_size;
- struct xyarray *xy = zalloc(sizeof(*xy) + xlen * row_size);
+ struct xyentry *new_entry;
+ unsigned int x;
+
+ for (x = 0; x < xy->row_count; x++) {
+ new_entry = zalloc(sizeof(*new_entry));
+ if (new_entry == NULL)
+ return -1;
+
+ new_entry->contents = zalloc(xy->entry_size);
+ if (new_entry->contents == NULL)
+ return -1;

- if (xy != NULL) {
- xy->entry_size = entry_size;
- xy->row_size = row_size;
+ list_add_tail(&new_entry->next, &xy->rows[x].head);
}

+ return 0;
+}
+
+struct xyarray *xyarray__new(int xlen, int ylen, size_t entry_size)
+{
+ struct xyarray *xy = zalloc(sizeof(*xy) + xlen * sizeof(struct row));
+ int i;
+
+ if (xy == NULL)
+ return NULL;
+
+ xy->row_count = xlen;
+ xy->entry_size = entry_size;
+
+ for (i = 0; i < xlen; i++)
+ INIT_LIST_HEAD(&xy->rows[i].head);
+
+ for (i = 0; i < ylen; i++)
+ if (xyarray__append(xy) < 0) {
+ xyarray__delete(xy);
+ return NULL;
+ }
+
return xy;
}

+/*
+ * remove a column for all rows;
+ */
+int xyarray__remove(struct xyarray *xy, int y)
+{
+ struct xyentry *entry;
+ unsigned int x;
+ int count;
+
+ if (!xy)
+ return 0;
+
+ for (x = 0; x < xy->row_count; x++) {
+ count = 0;
+ list_for_each_entry(entry, &xy->rows[x].head, next)
+ if (count++ == y) {
+ list_del(&entry->next);
+ free(entry);
+ return 0;
+ }
+ }
+
+ return -1;
+}
+
+/*
+ * All nodes in every rows should be deleted before delete @xy.
+ */
void xyarray__delete(struct xyarray *xy)
{
+ unsigned int i;
+ struct xyentry *entry;
+
+ if (!xy)
+ return;
+
+ for (i = 0; i < xy->row_count; i++)
+ list_for_each_entry(entry, &xy->rows[i].head, next) {
+ list_del(&entry->next);
+ free(entry);
+ }
+
free(xy);
}
diff --git a/tools/perf/util/xyarray.h b/tools/perf/util/xyarray.h
index c488a07..07fa370 100644
--- a/tools/perf/util/xyarray.h
+++ b/tools/perf/util/xyarray.h
@@ -2,19 +2,38 @@
#define _PERF_XYARRAY_H_ 1

#include <sys/types.h>
+#include <linux/list.h>
+
+struct row {
+ struct list_head head;
+};
+
+struct xyentry {
+ struct list_head next;
+ char *contents;
+};

struct xyarray {
- size_t row_size;
+ size_t row_count;
size_t entry_size;
- char contents[];
+ struct row rows[];
};

struct xyarray *xyarray__new(int xlen, int ylen, size_t entry_size);
void xyarray__delete(struct xyarray *xy);
+int xyarray__append(struct xyarray *xy);
+int xyarray__remove(struct xyarray *xy, int y);

static inline void *xyarray__entry(struct xyarray *xy, int x, int y)
{
- return &xy->contents[x * xy->row_size + y * xy->entry_size];
+ struct xyentry *entry;
+ int columns = 0;
+
+ list_for_each_entry(entry, &xy->rows[x].head, next)
+ if (columns++ == y)
+ return entry->contents;
+
+ return NULL;
}

#endif /* _PERF_XYARRAY_H_ */
--
1.7.9.5

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/