🔍 Inverted Search Engine — C Project

A terminal-based Inverted Index Search Engine written in C, using a custom hash table with chained linked lists to index words across multiple .txt files.

---

📌 Table of Contents

• Overview
• Architecture
• Data Structures
• Project Structure
• Features
• How to Build & Run
• Menu Options
• Known Limitations
• Changelog & Bug Fixes

---

Overview

This project implements an Inverted Index — a classic data structure used in search engines — entirely in C. Given one or more .txt files, the program indexes every word, recording:

• Which files each word appears in
• How many times it appears in each file

The user can then query any word (or prefix) and instantly see all matches found across all indexed files, along with occurrence counts.

---

Architecture

┌─────────────────────────────────────────────────────────────────────┐
│                        Hash Table (size 27)                         │
│   [a] → [b] → ... → [z] → [#]  (index 26 = non-alphabetic words)   │
└────────────────────────┬────────────────────────────────────────────┘
                         │
                    ┌────▼─────┐
                    │  mNode   │  ← Main Node (one per unique word)
                    │  *word   │
                    │filecount │
                    └──┬────┬──┘
                       │    └─────────────────────────────┐
                  mLink▼                             sLink▼
              ┌──────────┐                       ┌──────────┐
              │  mNode   │                       │  sNode   │  ← Sub Node
              │  "word2" │                       │*file_name│
              └──────────┘                       │  count   │
                                                 └────┬─────┘
                                                 subLink▼
                                                 ┌──────────┐
                                                 │  sNode   │
                                                 │*file_name│
                                                 └──────────┘

The hash table has 27 buckets — one per letter of the alphabet (indexed by first character, case-insensitive), and one catch-all bucket (index 26) for tokens beginning with non-alphabetic characters.

---

Data Structures

Flist — File List

A singly-linked list tracking all files that have been loaded into the system. The filename is heap-allocated via strdup.

typedef struct Node {
    char        *file_name;   /* heap-allocated via strdup */
    struct Node *link;
} Flist;

mNode — Main Node

One node per unique word. The word string is heap-allocated via strdup, removing the old 19-character fixed-buffer limit.

typedef struct mainNode {
    u_int            filecount;
    char            *word;    /* heap-allocated via strdup */
    sNode           *sLink;
    struct mainNode *mLink;
} mNode;

sNode — Sub Node

One node per file a word appears in. The filename is heap-allocated via strdup.

typedef struct subNode {
    u_int           wordcount;
    char            *file_name; /* heap-allocated via strdup */
    struct subNode  *subLink;
} sNode;

hash_T — Hash Table Entry

Array of 27 of these, each holding an index and a pointer to the head of its mNode chain.

typedef struct hashT {
    u_int  index;
    mNode *link;
} hash_T;

---

Project Structure

inverted_search/
├── main.c                  # Entry point, menu loop, user interaction
├── main.h                  # All structs, enums, and function declarations
├── color.h                 # ANSI color/style macros for terminal output
├── create_database.c       # Core indexing logic — reads files, builds the hash table
├── search_database.c       # Prefix-aware word lookup across the hash table
├── display_database.c      # Pretty-prints the entire database as a colored table
├── save_database.c         # Saves the database to database.txt
├── update_database.c       # Adds new files to an existing database (incremental)
├── validation.c            # File validation (extension, existence, empty, duplicate)
├── flist_utils.c           # Flist insert, print, free utilities
├── hash_t_utils.c          # Hash table init and free utilities
├── files_utils.c           # String utilities — strip_punctuation
└── makefile                # Build system (includes automated test target)

---

Features

Feature	Description
Multi-file indexing	Pass any number of .txt files as arguments
Prefix search	Searching "the" matches "the", "there", "they", etc.
Case-insensitive search	Hello and hello are treated as the same word
Punctuation stripping	"hello," and "hello" index as the same token
Smart apostrophe handling	it's is preserved; 'hello' strips the surrounding quotes
Duplicate file detection	The same file cannot be indexed twice
Incremental update	Add new files without re-indexing existing ones
Colorized terminal output	Full ANSI color support via color.h
Save to file	Export the full index to database.txt
Input validation	Non-numeric menu input is caught and handled gracefully
Automated testing	make test runs a full end-to-end flow automatically
Non-alphabetic word support	Tokens starting with digits or symbols go into bucket 26

---

How to Build & Run

Requirements

• GCC (any modern version)
• A POSIX-compatible terminal (Linux/macOS recommended)

Build

make

Run

./inverted_search.exe file1.txt file2.txt file3.txt

Automated Test

Generates test .txt files, runs the full menu flow (create → display → update → search → exit) automatically, and prints results to the terminal:

make test

Clean

Removes the binary, object files, all test .txt files, and database.txt:

make clean

---

Menu Options

1. Create Database    — Index all loaded files into the hash table
2. Display Database   — Print the full index as a formatted, colored table
3. Search Database    — Prefix-aware lookup (e.g. "the" matches "there", "they")
4. Update Database    — Add new .txt files to the existing index
5. Save Database      — Write the index to database.txt
6. Exit               — Save, free all memory, and quit cleanly

---

Known Limitations

• No punctuation stripping inside words containing digits — C3PO indexes as CPO since non-alpha characters are dropped entirely.
• The hash table uses only 27 buckets (keyed on first character). Words sharing a first letter share a chain, so heavily skewed text will increase chain traversal time.
• Prefix search scans the full bucket chain — it cannot use early-exit on sorted chains the way exact search can, since matching words may appear anywhere in the chain.

---

Changelog & Bug Fixes

See CHANGE_LOG.md for a full record of every bug identified, its root cause, and how it was resolved.

See PROJECT_METRICS.md for a quantified breakdown of the project.

---

Built entirely in C. Terminal colors powered by color.h using ANSI escape codes.