/* bagmatch.c, mostly by GPT-5 Mini.
 *
 * Print all words from a dictionary file whose letters (single-byte ASCII)
 * form the same multiset ("bag") as the first command-line argument.
 *
 * Usage: ./bagmatch KEYWORD DICTIONARY_FILE
 *
 * Constraints & behavior per request:
 * - Words and KEYWORD are assumed to contain only letters; no validity checks.
 * - Maximum input word length is 64 bytes; program exits with error if exceeded.
 * - Sort letters in a word using an insertion-sort subroutine into canonical order.
 * - Compare canonical forms via memcmp.
 * - Use mmap for input; be fast and avoid dynamic allocation.
 */

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <stdint.h>
#include <errno.h>
#include <string.h>
#include <inttypes.h>
#include <stddef.h>

#define MAXWORD 64

/* insertion_sort_chars:
 * Sorts n bytes in-place (array of unsigned char) using insertion sort.
 * This is optimized for small fixed-size keys (<=64).
 */
static void insertion_sort_chars(unsigned char *a, size_t n) {
  for (size_t i = 1; i < n; ++i) {
    unsigned char key = a[i];
    size_t j = i;
    while (j > 0 && a[j - 1] > key) {
      a[j] = a[j - 1];
      --j;
    }
    a[j] = key;
  }
}

int main(int argc, char *argv[]) {
  int error_return = 0;
  if (argc != 3) {
    fputs("Usage: bagmatch KEYWORD DICTIONARY_FILE\n", stderr);
    return 2;
  }

  unsigned char keybuf[MAXWORD];
  size_t keylen = strlen(argv[1]);
  if (keylen > MAXWORD) {
    fputs("Error: keyword too long (max 64 bytes)\n", stderr);
    return 2;
  }
  /* copy then sort into canonical form */
  memcpy(keybuf, argv[1], keylen);
  insertion_sort_chars(keybuf, keylen);

  const char *path = argv[2];
  int fd = open(path, O_RDONLY);
  if (fd == -1) {
    perror(path);
    return 3;
  }

  struct stat st;
  if (fstat(fd, &st) == -1) {
    perror("fstat");
    close(fd);
    return 4;
  }

  off_t filesize = st.st_size;
  if (filesize == 0) {
    close(fd);
    return 0;
  }

  const unsigned char *map = mmap(NULL, (size_t)filesize, PROT_READ, MAP_PRIVATE, fd, 0);
  if (map == MAP_FAILED) {
    perror("mmap");
    close(fd);
    return 5;
  }

  const unsigned char *nl;
  const unsigned char *end = map + filesize;

  for (const unsigned char *ptr = map; ptr < end; ptr = nl + 1) {
    /* Read file line-by-line, each word followed by '\n' including last. */
    const void *found = memchr(ptr, '\n', (size_t)(end - ptr));
    if (!found) break;
    nl = found;
    ptrdiff_t len = nl - ptr; // bytes before newline

    /* word is in ptr[0..len-1] */

    /* Skip words of the wrong length. */
    if (len != keylen) continue;

    /* sort a copy so we don't disturb original */
    unsigned char work[MAXWORD];
    memcpy(work, ptr, len);
    insertion_sort_chars(work, len);

    if (memcmp(work, keybuf, keylen) == 0) {
      /* match: print original word (as bytes) followed by newline */
      if (fwrite(ptr, 1, len, stdout) != len || putchar('\n') == EOF) {
        perror("write");
        error_return = 2;
        break;
      }
    }
  }

  if (munmap((void *)map, (size_t)filesize) == -1) {
    perror("munmap");
    error_return = 8;
  }

  close(fd);
  return error_return;
}