summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--build.rs2
-rw-r--r--nauty/geng-iter.c74
-rw-r--r--nauty/geng.c54
-rw-r--r--nauty/geng.h18
-rw-r--r--src/main.rs44
5 files changed, 114 insertions, 78 deletions
diff --git a/build.rs b/build.rs
index f9bb718..e6f102c 100644
--- a/build.rs
+++ b/build.rs
@@ -10,7 +10,7 @@ fn main() {
cc::Build::new()
.file("nauty/geng.c")
.file("nauty/geng-iter.c")
- .flag("-O3")
+ // .flag("-O3")
.flag("-Wno-unused-parameter")
.flag("-Wno-sign-compare")
.flag("-Wno-unused-variable")
diff --git a/nauty/geng-iter.c b/nauty/geng-iter.c
index f2acf1c..cec9834 100644
--- a/nauty/geng-iter.c
+++ b/nauty/geng-iter.c
@@ -1,17 +1,9 @@
#include "gtools.h"
+#include "geng.h"
#include <ucontext.h>
#include <stdint.h>
#include <stdbool.h>
-// TODO: move that to struct so that this code would be thread-safe (probably)
-static unsigned long counter;
-static graph *cur;
-static int gn;
-extern int generate_done;
-int iter_done;
-ucontext_t geng_worker, geng_user;
-char geng_stack[1 << 20];
-
// TODO: only on macos
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
@@ -35,11 +27,11 @@ printgraph(graph *g, int n)
// TODO: probably don't need to name this function with macro
void
-OUTPROC(__attribute__((unused)) FILE *outfile, graph *g, int n)
+OUTPROC(__attribute__((unused)) FILE *outfile,
+ graph *g, int n, struct geng_iterator *iter)
{
- cur = g;
- gn = n;
- ++counter;
+ iter->cur = g;
+ iter->graph_size = n;
// TODO: add support for generating graphs in batches (for speed)
#if 0
@@ -51,25 +43,26 @@ OUTPROC(__attribute__((unused)) FILE *outfile, graph *g, int n)
i = 0;
}
#else
- swapcontext(&geng_worker, &geng_user);
+ swapcontext(&iter->geng_worker, &iter->geng_user);
#endif
}
// TODO: probably don't need to name this function with macro
-// TODO: geng.h maybe?
+// TODO: move to geng.h maybe?
extern int
GENG_MAIN(int argc, char *argv[]);
-struct geng_iterator
-{
- ucontext_t geng_worker, geng_user;
- char geng_stack[1 << 20];
-};
-
+// geng_iterator_init gives ownership of iterator memory to caller
void
-geng_iterator_init(__attribute__((unused)) struct geng_iterator *iter, int n)
+geng_iterator_create(struct geng_iterator **iterator_ptr,
+ size_t graph_size,
+ size_t batch_capacity)
{
- iter_done = 0;
+ // TODO: malloc geng_iterator batch
+ *iterator_ptr = malloc(sizeof(struct geng_iterator));
+
+ struct geng_iterator *iterator = *iterator_ptr;
+ iterator->iteration_done = false;
// TODO: add support for more arguments
int geng_argc = 3;
@@ -78,7 +71,7 @@ geng_iterator_init(__attribute__((unused)) struct geng_iterator *iter, int n)
geng_argv[0] = "geng";
geng_argv[1] = "-q";
char n_str[20];
- snprintf(n_str, sizeof(n_str), "%u", n);
+ snprintf(n_str, sizeof(n_str), "%zu", graph_size);
geng_argv[2] = n_str;
geng_argv[3] = NULL;
@@ -86,29 +79,34 @@ geng_iterator_init(__attribute__((unused)) struct geng_iterator *iter, int n)
p_argv[0] = (uint32_t) (((size_t) &geng_argv) & ((1llu << 32) - 1llu));
p_argv[1] = ((size_t) &geng_argv) >> 32;
- counter = 0;
+ uint32_t p_iter[2];
+ p_iter[0] = (uint32_t) (((size_t) &iterator) & ((1llu << 32) - 1llu));
+ p_iter[1] = ((size_t) &iterator) >> 32;
- getcontext(&geng_user);
- geng_worker = geng_user;
- geng_worker.uc_stack.ss_sp = geng_stack;
- geng_worker.uc_stack.ss_size = sizeof(geng_stack);
- geng_worker.uc_link = &geng_user;
+ getcontext(&iterator->geng_user);
+ iterator->geng_worker = iterator->geng_user;
+ iterator->geng_worker.uc_stack.ss_sp = iterator->geng_stack;
+ iterator->geng_worker.uc_stack.ss_size = sizeof(iterator->geng_stack);
+ iterator->geng_worker.uc_link = &iterator->geng_user;
- makecontext(&geng_worker, (void (*) (void)) GENG_MAIN, 3, geng_argc, p_argv[0], p_argv[1]);
- swapcontext(&geng_user, &geng_worker);
+ makecontext(
+ &iterator->geng_worker, (void (*) (void)) GENG_MAIN,
+ 5, geng_argc, p_argv[0], p_argv[1], p_iter[0], p_iter[1]
+ );
+ swapcontext(&iterator->geng_user, &iterator->geng_worker);
free(geng_argv);
}
bool
-geng_iterator_next(__attribute__((unused)) struct geng_iterator *iter, graph *g)
+geng_iterator_next(struct geng_iterator *iter, graph *g)
{
- if (iter_done == 1) return false;
+ if (iter->iteration_done) return false;
else
{
- memcpy(g, cur, sizeof(set) * gn);
- swapcontext(&geng_user, &geng_worker);
- if (iter_done == 0 && generate_done == 1)
- iter_done = 1;
+ memcpy(g, iter->cur, sizeof(set) * iter->graph_size);
+ swapcontext(&iter->geng_user, &iter->geng_worker);
+ if (!iter->iteration_done && iter->generation_done)
+ iter->iteration_done = true;
return true;
}
}
diff --git a/nauty/geng.c b/nauty/geng.c
index 8ebd629..7ea0085 100644
--- a/nauty/geng.c
+++ b/nauty/geng.c
@@ -416,8 +416,10 @@ efficient to use the res/mod feature than to split by numbers of edges.
#define ONE_WORD_SETS
#include "gtools.h" /* which includes nauty.h and stdio.h */
+#include "geng.h"
+#include <stdint.h>
-int generate_done;
+struct geng_iterator;
/* No need for TLS if not calling from a program. */
#ifndef GENG_MAIN
@@ -427,7 +429,7 @@ int generate_done;
typedef setword xword;
-static TLS_ATTR void (*outproc)(FILE*,graph*,int);
+static TLS_ATTR void (*outproc)(FILE*,graph*,int,struct geng_iterator *);
static TLS_ATTR FILE *outfile; /* file for output graphs */
static TLS_ATTR int connec; /* 1 for -c, 2 for -C, 0 for neither */
@@ -2030,7 +2032,8 @@ xbnds(int n, int ne, int dmax)
static void
spaextend(graph *g, int n, int *deg, int ne, boolean rigid,
- int xlb, int xub, void (*makeh)(graph*,xword*,int))
+ int xlb, int xub, void (*makeh)(graph*,xword*,int),
+ struct geng_iterator *iter)
/* extend from n to n+1 -- version for restricted graphs */
{
xword x,d,dlow;
@@ -2102,7 +2105,7 @@ spaextend(graph *g, int n, int *deg, int ne, boolean rigid,
haschild = TRUE;
#endif
++ecount[ne+xc];
- (*outproc)(outfile,canonise ? gcan : gx,nx);
+ (*outproc)(outfile,canonise ? gcan : gx,nx, iter);
}
}
}
@@ -2136,7 +2139,7 @@ spaextend(graph *g, int n, int *deg, int ne, boolean rigid,
#ifdef INSTRUMENT
haschild = TRUE;
#endif
- spaextend(gx,nx,degx,ne+xc,rigidx,xlbx,xubx,makeh);
+ spaextend(gx,nx,degx,ne+xc,rigidx,xlbx,xubx,makeh,iter);
}
}
}
@@ -2152,7 +2155,7 @@ spaextend(graph *g, int n, int *deg, int ne, boolean rigid,
/**************************************************************************/
static void
-genextend(graph *g, int n, int *deg, int ne, boolean rigid, int xlb, int xub)
+genextend(graph *g, int n, int *deg, int ne, boolean rigid, int xlb, int xub, struct geng_iterator *iter)
/* extend from n to n+1 -- version for general graphs */
{
xword x,d,dlow;
@@ -2224,7 +2227,7 @@ genextend(graph *g, int n, int *deg, int ne, boolean rigid, int xlb, int xub)
haschild = TRUE;
#endif
++ecount[ne+xc];
- (*outproc)(outfile,canonise ? gcan : gx,nx);
+ (*outproc)(outfile,canonise ? gcan : gx,nx, iter);
}
}
}
@@ -2256,7 +2259,7 @@ genextend(graph *g, int n, int *deg, int ne, boolean rigid, int xlb, int xub)
#ifdef INSTRUMENT
haschild = TRUE;
#endif
- genextend(gx,nx,degx,ne+xc,rigidx,xlbx,xubx);
+ genextend(gx,nx,degx,ne+xc,rigidx,xlbx,xubx,iter);
}
}
@@ -2274,12 +2277,14 @@ genextend(graph *g, int n, int *deg, int ne, boolean rigid, int xlb, int xub)
// TODO: probably rework
#ifdef GENG_MAIN
void
-GENG_MAIN(int geng_argc, unsigned int argv1, unsigned int argv2)
+GENG_MAIN(int argc, uint32_t argv1, uint32_t argv2, uint32_t iter1, uint32_t iter2)
{
- int argc = geng_argc;
size_t *p_argv = (size_t *) (((size_t) argv1) | (((size_t) argv2) << 32));
char **argv = (char **) *p_argv;
- generate_done = 0;
+
+ size_t *p_iter = (size_t *) (((size_t) iter1) | (((size_t) iter2) << 32));
+ struct geng_iterator *iter = (struct geng_iterator *) *p_iter;
+ iter->generation_done = false;
#else
int
main(int argc, char *argv[])
@@ -2297,7 +2302,6 @@ main(int argc, char *argv[])
double t1,t2;
char msg[201];
- /* HELP; PUTVERSION; */
nauty_check(WORDSIZE,1,MAXN,NAUTYVERSIONID);
badargs = FALSE;
@@ -2596,7 +2600,7 @@ PLUGIN_INIT
if (res == 0 && connec < 2)
{
++ecount[0];
- (*outproc)(outfile,g,1);
+ (*outproc)(outfile,g,1,iter);
}
}
else
@@ -2633,25 +2637,31 @@ PLUGIN_INIT
if (bipartite)
if (squarefree)
spaextend(g,1,deg,0,TRUE,
- data[1].xlb,data[1].xub,makeb6graph);
+ data[1].xlb,data[1].xub,makeb6graph,
+ iter);
else
spaextend(g,1,deg,0,TRUE,
- data[1].xlb,data[1].xub,makebgraph);
+ data[1].xlb,data[1].xub,makebgraph,
+ iter);
else if (trianglefree)
if (squarefree)
spaextend(g,1,deg,0,TRUE,
- data[1].xlb,data[1].xub,makeg5graph);
+ data[1].xlb,data[1].xub,makeg5graph,
+ iter);
else
spaextend(g,1,deg,0,TRUE,
- data[1].xlb,data[1].xub,makexgraph);
+ data[1].xlb,data[1].xub,makexgraph,
+ iter);
else if (squarefree)
spaextend(g,1,deg,0,TRUE,
- data[1].xlb,data[1].xub,makesgraph);
+ data[1].xlb,data[1].xub,makesgraph,
+ iter);
else if (savemem)
spaextend(g,1,deg,0,TRUE,
- data[1].xlb,data[1].xub,make0graph);
+ data[1].xlb,data[1].xub,make0graph,
+ iter);
else
- genextend(g,1,deg,0,TRUE,data[1].xlb,data[1].xub);
+ genextend(g,1,deg,0,TRUE,data[1].xlb,data[1].xub,iter);
}
}
t2 = CPUTIME;
@@ -2711,9 +2721,7 @@ PLUGIN_INIT
free(data[i].xinv);
free(data[i].xcard);
}
- generate_done = 1;
- // TODO: probably rework
- /* return 0; */
+ iter->generation_done = true;
#else
exit(0);
#endif
diff --git a/nauty/geng.h b/nauty/geng.h
new file mode 100644
index 0000000..751be5c
--- /dev/null
+++ b/nauty/geng.h
@@ -0,0 +1,18 @@
+#include "gtools.h"
+#include <ucontext.h>
+#include <stdbool.h>
+
+struct geng_iterator
+{
+ ucontext_t geng_worker, geng_user;
+ char geng_stack[1 << 20];
+ int graph_size;
+ bool generation_done;
+ bool iteration_done;
+ int batch_size;
+ int batch_capacity;
+ graph **batch;
+
+ // TODO: remove
+ graph *cur;
+};
diff --git a/src/main.rs b/src/main.rs
index 9e695a6..ac9995b 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -5,37 +5,47 @@ use std::ptr;
enum geng_iterator {}
extern "C" {
- fn geng_iterator_init(iter: *const geng_iterator, n: i32);
- fn geng_iterator_next(iter: *const geng_iterator, g: *mut i32) -> bool;
- fn printgraph(g: *const i32, n: i32);
+ fn geng_iterator_create(
+ iter: *const *mut geng_iterator,
+ graph_size: usize,
+ batch_size: usize,
+ );
+ fn geng_iterator_next(iter: *const geng_iterator, g: *mut u32) -> bool;
+ fn printgraph(g: *const u32, n: usize);
}
-fn print_graph(g: Vec<i32>, n: usize) {
+fn print_graph(g: Vec<u32>, n: usize) {
unsafe {
- printgraph(g.as_ptr(), n as i32);
+ printgraph(g.as_ptr(), n);
}
}
struct GengIterator {
pub size: usize,
+ iter: Box<geng_iterator>,
}
impl GengIterator {
fn new(n: usize) -> GengIterator {
- unsafe {
- geng_iterator_init(ptr::null(), n as i32);
- }
- GengIterator { size: n }
+ let iter = unsafe {
+ let iter: *mut geng_iterator = ptr::null_mut();
+ geng_iterator_create(&iter, n, 100);
+ Box::from_raw(iter)
+ };
+ GengIterator { size: n, iter }
}
}
impl Iterator for &GengIterator {
- type Item = Vec<i32>;
+ type Item = Vec<u32>;
fn next(&mut self) -> Option<Self::Item> {
let mut g = vec![0; self.size];
let res;
- unsafe { res = geng_iterator_next(ptr::null(), g.as_mut_ptr()) }
+ unsafe {
+ let ptr: *const geng_iterator = &*self.iter;
+ res = geng_iterator_next(ptr, g.as_mut_ptr())
+ }
if res {
Some(g)
} else {
@@ -45,12 +55,14 @@ impl Iterator for &GengIterator {
}
fn main() {
- let gi = GengIterator::new(12);
+ let gi = GengIterator::new(2);
- let q = gi.skip(1000).next();
- println!("{:?}", q);
- print_graph(q.unwrap(), gi.size);
- // for i in &gi {
+ // let q = gi.take(2).collect::<Vec<_>>();
+ // println!("{:?}", q);
+ // for i in q {
// print_graph(i, gi.size);
// }
+ for i in &gi {
+ print_graph(i, gi.size);
+ }
}
generated by cgit v1.2.3 (git 2.25.1) at 2025-12-17 07:25:49 +0000