Interrupt vector table in Embedded C - Time & Space Complexity

Time Complexity: Interrupt vector table

O(1)

Understanding Time Complexity

When working with an interrupt vector table, it's important to understand how the time to find and run an interrupt handler changes as the number of interrupts grows.

We want to know how the system's response time scales when more interrupts are added.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Interrupt vector table example
void (*interrupt_vector_table[10])(void);

void handle_interrupt(int interrupt_number) {
    if (interrupt_number >= 0 && interrupt_number < 10) {
        interrupt_vector_table[interrupt_number]();
    }
}
    

This code stores pointers to interrupt handlers in an array and calls the correct handler based on the interrupt number.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Accessing the interrupt handler from the array by index.
• How many times: Exactly once per interrupt handled.

How Execution Grows With Input

The time to call the interrupt handler stays the same no matter how many interrupts are in the table.

Input Size (number of interrupts)	Approx. Operations
10	1
100	1
1000	1

Pattern observation: The time to find and call the handler does not increase as the number of interrupts grows.

Final Time Complexity

Time Complexity: O(1)

This means the time to handle an interrupt is constant and does not depend on how many interrupts exist.

Common Mistake

[X] Wrong: "More interrupts mean longer time to find the right handler because the table is searched one by one."

[OK] Correct: The interrupt vector table uses direct indexing, so the handler is found immediately without searching.

Interview Connect

Understanding how direct indexing keeps interrupt handling fast shows your grasp of efficient hardware-software interaction, a valuable skill in embedded programming.

Self-Check

"What if the interrupt vector table was replaced by a linked list of handlers? How would the time complexity change?"

Practice

1.

What is the main purpose of an interrupt vector table in embedded C programming?

easy

A. To store global variables for the program

B. To link interrupt events to their handler functions

C. To manage memory allocation dynamically

D. To perform arithmetic operations automatically

Solution

1. Step 1: Understand the role of interrupt vector table

   The interrupt vector table is a special array that holds addresses of interrupt handler functions.

2. Step 2: Identify its purpose in program flow

   When an interrupt occurs, the processor uses this table to jump to the correct handler automatically.

3. Final Answer:

   To link interrupt events to their handler functions -> Option B

4. Quick Check:

   Interrupt vector table = links interrupts to handlers [OK]

Hint: Interrupt vector table connects interrupts to handlers [OK]

Common Mistakes:

• Thinking it stores variables
• Confusing with memory management
• Assuming it performs calculations

2.

Which of the following is the correct way to declare an interrupt vector table as an array of function pointers in embedded C?

void (*interrupt_vector_table[])(void) = {

easy

A. void interrupt_vector_table(void) = {handler1, handler2};

B. int interrupt_vector_table[] = {handler1, handler2};

C. void (*interrupt_vector_table[])(void) = {handler1, handler2};

D. void *interrupt_vector_table = {handler1, handler2};

Solution

1. Step 1: Recognize function pointer array syntax

   Function pointers to void functions with no parameters are declared as void (*name[])(void).

2. Step 2: Match declaration with initialization

   void (*interrupt_vector_table[])(void) = {handler1, handler2}; correctly declares an array of such pointers and initializes it with handler functions.

3. Final Answer:

   void (*interrupt_vector_table[])(void) = {handler1, handler2}; -> Option C

4. Quick Check:

   Function pointer array syntax = void (*interrupt_vector_table[])(void) = {handler1, handler2}; [OK]

Hint: Function pointer arrays use void (*name[])(void) syntax [OK]

Common Mistakes:

• Using int type instead of function pointers
• Declaring as a single function, not array
• Using void* without function pointer cast

3.

Given the following code snippet, what will be the output when the interrupt at index 1 occurs?

void handler0(void) { printf("Handler 0 called\n"); }
void handler1(void) { printf("Handler 1 called\n"); }
void (*interrupt_vector_table[])(void) = {handler0, handler1};

// Simulate interrupt 1
interrupt_vector_table[1]();

medium

A. Handler 1 called

B. Handler 0 called

C. No output, runtime error

D. Compilation error

Solution

1. Step 1: Identify the function called by interrupt_vector_table[1]

   Index 1 points to handler1, which prints "Handler 1 called".

2. Step 2: Understand the output of the function call

   Calling interrupt_vector_table[1]() executes handler1, printing the message.

3. Final Answer:

   Handler 1 called -> Option A

4. Quick Check:

   interrupt_vector_table[1]() calls handler1 [OK]

Hint: Index 1 calls handler1, prints its message [OK]

Common Mistakes:

• Confusing index 0 and 1
• Expecting no output or error
• Misreading function pointer call syntax

4.

Consider this interrupt vector table declaration:

void handlerA(void) { /* ... */ }
void handlerB(void) { /* ... */ }

void (*interrupt_vector_table[])(void) = {handlerA, handlerB};

// Somewhere else in code
interrupt_vector_table[2]();

What is the problem here?

medium

A. Index 2 is out of bounds, causing undefined behavior

B. handlerB is not a valid function pointer

C. interrupt_vector_table must be declared as int array

D. No problem, code runs fine

Solution

1. Step 1: Check the size of interrupt_vector_table

   The array has 2 elements at indices 0 and 1 only.

2. Step 2: Analyze the call to interrupt_vector_table[2]()

   Index 2 is outside the array bounds, leading to undefined behavior or crash.

3. Final Answer:

   Index 2 is out of bounds, causing undefined behavior -> Option A

4. Quick Check:

   Accessing beyond array size = out of bounds error [OK]

Hint: Array indices start at 0; index 2 is invalid here [OK]

Common Mistakes:

• Assuming array auto-expands
• Thinking handlerB is invalid
• Ignoring out-of-bounds errors

5.

You want to add a new interrupt handler handler2 to an existing vector table with 2 handlers. Which is the correct way to update the vector table to include handler2 at index 2?

void handler0(void) { /* ... */ }
void handler1(void) { /* ... */ }
void handler2(void) { /* ... */ }

// Existing vector table
void (*interrupt_vector_table[])(void) = {handler0, handler1};

// How to add handler2 correctly?

hard

A. No need to add; interrupts beyond index 1 are ignored

B. Assign handler2 directly: interrupt_vector_table[2] = handler2;

C. Use a pointer cast to add handler2 at index 2

D. Redefine the vector table with all three handlers: {handler0, handler1, handler2}

Solution

1. Step 1: Understand array size fixed at declaration

   Arrays in C have fixed size; you cannot add elements dynamically.

2. Step 2: Update vector table by redefining with all handlers

   To include handler2, redefine the array with three elements: {handler0, handler1, handler2}.

3. Final Answer:

   Redefine the vector table with all three handlers: {handler0, handler1, handler2} -> Option D

4. Quick Check:

   Arrays fixed size; redefine to add elements [OK]

Hint: Arrays fixed size; redefine to add handlers [OK]

Common Mistakes:

• Trying to assign beyond array size
• Using pointer casts unsafely
• Assuming interrupts beyond defined handlers work