| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-Id: <1361870452-6143-2-git-send-email-chenggang.qin@gmail.com>
Date: Tue, 26 Feb 2013 17:20:48 +0800
From: chenggang <chenggang.qin@...il.com>
To: linux-kernel@...r.kernel.org
Cc: chenggang <chenggang.qcg@...bao.com>,
David Ahern <dsahern@...il.com>,
Peter Zijlstra <a.p.zijlstra@...llo.nl>,
Paul Mackerras <paulus@...ba.org>,
Ingo Molnar <mingo@...hat.com>,
Arnaldo Carvalho de Melo <acme@...stprotocols.net>,
Arjan van de Ven <arjan@...ux.intel.com>,
Namhyung Kim <namhyung@...il.com>,
Yanmin Zhang <yanmin.zhang@...el.com>,
Wu Fengguang <fengguang.wu@...el.com>,
Mike Galbraith <efault@....de>,
Andrew Morton <akpm@...ux-foundation.org>
Subject: [PATCH v2 1/4] Transform xyarray to linked list
From: chenggang <chenggang.qcg@...bao.com>
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@...il.com>
Cc: Peter Zijlstra <a.p.zijlstra@...llo.nl>
Cc: Paul Mackerras <paulus@...ba.org>
Cc: Ingo Molnar <mingo@...hat.com>
Cc: Arnaldo Carvalho de Melo <acme@...stprotocols.net>
Cc: Arjan van de Ven <arjan@...ux.intel.com>
Cc: Namhyung Kim <namhyung@...il.com>
Cc: Yanmin Zhang <yanmin.zhang@...el.com>
Cc: Wu Fengguang <fengguang.wu@...el.com>
Cc: Mike Galbraith <efault@....de>
Cc: Andrew Morton <akpm@...ux-foundation.org>
Signed-off-by: Chenggang Qin <chenggang.qcg@...bao.com>
---
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@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists