CWE Rule 462

Duplicate Key in Associative List (Alist)

Since R2026a

Description

Duplicate Key in Associative List (Alist)

Polyspace Implementation

The rule checker checks for the issue Inappropriate associative list.

Examples

Inappropriate associative list

Issue

This issue occurs if an associative list is implemented in such a way that allows for duplicated keys. Polyspace^® reports a violation if an array of struct or a pointer to a struct pointer is defined where:

• The struct is not a union or class.

• The struct has two elements.

• The name of an element contains name or key, or finishes with _id, or is id.

In C++ code, Polyspace reports a violation if An std::vector, std::array, or std::list container is instantiated with the type std::pair.

These use pattern indicate that code is storing key-value pairs in plain arrays or sequence containers. Polyspace reports violations.

Violations are not reported on a struct that is a node in a linked list or on multidimensional arrays.

Risk

Duplicate keys in associative lists can cause ambiguity and result in unexpected behavior.

Fix

Use appropriate associative containers such as std::map or std::set. When implementing associative lists in C, avoid techniques that allow duplicated keys.

Example

This code uses an array of the structure Entry to implement an associative list. The structure has two elements, key and value. Polyspace reports a violation.

#include <stdio.h>
#include <string.h>

#define MAX_ENTRIES 16
#define MAX_KEY_LENGTH 32

struct Entry {
	char key[MAX_KEY_LENGTH];
	int value;
};

struct Entry map[MAX_ENTRIES];  //Noncompliant

void init_map() {
	for(int i = 0; i < MAX_ENTRIES; i++) {
		map[i].key[0] = '\0';
	}
}

void put(const char *key, int value) {
	for(int i = 0; i < MAX_ENTRIES; i++) {
		if(map[i].key[0] == '\0' || strcmp(map[i].key, key) == 0) {
			strncpy(map[i].key, key, MAX_KEY_LENGTH - 1);
			map[i].value = value;
			return;
		}
	}
	printf("Map is full!\n");
}

int get(const char *key) {
	for(int i = 0; i < MAX_ENTRIES; i++) {
		if(map[i].key[0] != '\0' && strcmp(map[i].key, key) == 0) {
			return map[i].value;
		}
	}
	return -1;
}

int main() {
	init_map();

	put("apple", 5);
	put("banana", 8);
	put("orange", 3);
	put("apple", 10);  // Updates existing key

	printf("apple: %d\n", get("apple"));    // prints 10
	printf("banana: %d\n", get("banana"));  // prints 8
	printf("orange: %d\n", get("orange"));  // prints 3
	printf("grape: %d\n", get("grape"));    // prints -1

	return 0;
}

Correction

Use associative containers from the Standard template Library (STL) when using C++11 or later. When implementing associative lists in C, check for duplicated keys. For example, this code an associative list using a linked list and checks for duplicated keys.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_KEY_LENGTH 32

struct Entry {
    char key[MAX_KEY_LENGTH];
    int value;
    struct Entry* next;
};

struct Entry* map = NULL; //Compliant

void put(const char* key, int value) {
    struct Entry* current = map;
    
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            current->value = value;
            return;
        }
        current = current->next;
    }
    
    struct Entry* new_entry = malloc(sizeof(struct Entry));
    strncpy(new_entry->key, key, MAX_KEY_LENGTH - 1);
    new_entry->value = value;
    new_entry->next = map;
    map = new_entry;
}

int get(const char* key) {
    struct Entry* current = map;
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value;
        }
        current = current->next;
    }
    return -1;
}

void free_map() {
    struct Entry* current = map;
    while (current != NULL) {
        struct Entry* next = current->next;
        free(current);
        current = next;
    }
}

int main() {
    put("apple", 5);
    put("banana", 8);
    put("orange", 3);
    put("apple", 10);  // Updates existing key

    printf("apple: %d\n", get("apple"));    // prints 10
    printf("banana: %d\n", get("banana"));  // prints 8
    printf("orange: %d\n", get("orange"));  // prints 3
    printf("grape: %d\n", get("grape"));    // prints -1

    free_map();
    return 0;
}

Check Information

Category: Others

PQL Name: std.cwe_native.R462

Version History

Introduced in R2026a