Mercurial > ~dholland > hg > ag > index.cgi
view anagram/agcore/binsort.cpp @ 7:57b2cc9b87f7
Use memcpy instead of strncpy when we know the length anyway.
Modern gcc seems to think it knows how to detect misuse of strncpy,
but it's wrong (in fact: very, very wrong) and the path of least
resistance is to not try to fight with it.
author | David A. Holland |
---|---|
date | Mon, 30 May 2022 23:47:52 -0400 |
parents | 13d2b8934445 |
children |
line wrap: on
line source
/* * AnaGram, A System for Syntax Directed Programming * Copyright 1993-1999 Parsifal Software. All Rights Reserved. * See the file COPYING for license and usage terms. * * binsort.cpp - Bin sort module (also known as radix sort) */ #include <string.h> #include "port.h" #include "binsort.h" #include "minmax.h" #include "myalloc.h" #include "tsd.h" static long *bin_sort_tuples( unsigned char *ss, unsigned w, long *x, unsigned nt, unsigned *cp ) { unsigned bin_tail[256]; unsigned bin_a[256]; unsigned bin_b[256]; unsigned *bins[2]; unsigned *new_bin_head; unsigned *old_bin_head; int m; unsigned i,j,k; unsigned bin,old_bin; unsigned *link; long *y, *yp; unsigned char *sp; yp = y = ALLOCATE(nt, long); ALLOCATE_ST(link, nt); //link = ALLOCATE(nt, unsigned); bins[0] = bin_a; bins[1] = bin_b; m = 0; new_bin_head = bins[m]; m ^= 1; memset(new_bin_head, 0xff, 256*sizeof(*new_bin_head)); memset(bin_tail, 0xff, 256*sizeof(*bin_tail)); sp = ss + *cp++; for (i = 0; i<nt; i++) { bin = sp[(int) x[i]]; if ((k = bin_tail[bin]) == (unsigned) -1) { new_bin_head[bin] = i; } else { link[k] = i; } bin_tail[bin] = i; link[i] = (unsigned) -1; } while (--w) { sp = ss + *cp++; old_bin_head = new_bin_head; new_bin_head = bins[m]; m ^= 1; memset(new_bin_head, 0xff, 256*sizeof(*new_bin_head)); memset(bin_tail, 0xff, 256*sizeof(*bin_tail)); for (old_bin = 0; old_bin < 256; old_bin++) { j = old_bin_head[old_bin]; while (j != (unsigned) -1) { j = link[i=j]; bin = sp[(int) x[i]]; if ((k = bin_tail[bin]) == (unsigned) -1){ new_bin_head[bin] = i; } else { link[k] = i; } bin_tail[bin] = i; link[i] = (unsigned) -1; } } } for (i = 256; i-- > 0;) { j = *new_bin_head++; while (j != (unsigned) -1){ *yp++ = j; j = link[j]; } } DEALLOCATE(link); return y; } void sort_tuples(tsd *ts, unsigned nc) { long *x,p, *y; unsigned nt; unsigned i,j; unsigned wb,sw; unsigned char *data, *newdata; unsigned tw; unsigned pv[100]; ok_ptr(ts); nt = ts->nt; tw = ts->tw; if (nt == 0 || nc == 0 || tw == 0) { return; } p = 0; i = min(nc,tw); sw = i*sizeof(*ts->sb); wb = tw * sizeof(*ts->sb); j = 0; while (i--) { unsigned k; for (k = 0; k < sizeof(*ts->sb); k++) { pv[j++] = i*sizeof(*ts->sb) + k; } } ALLOCATE_ST(x, nt); /* x = allocate(nt, long); */ for (i = 0; i< nt; i++) { x[i] = p; p += wb; } data = (unsigned char *) ts->sb; y = bin_sort_tuples(data, sw, x, nt,pv); newdata = (unsigned char *)(ALLOCATE_ST(ts->sb, nt * tw)); /* ts->sb = allocate(nt*tw, int); newdata = (unsigned char *) ts->sb; */ ts->na = nt; for (i = 0; i < nt; i++) { memmove(newdata + (int) x[i], data + (int) x[(int) y[i]], wb); } DEALLOCATE(x); DEALLOCATE(data); DEALLOCATE(y); } /* End BINSORT.C */