Austin Group Defect Tracker

Aardvark Mark III


Viewing Issue Simple Details Jump to Notes ] Issue History ] Print ]
ID Category Severity Type Date Submitted Last Update
0001061 [1003.1(2008)/Issue 7] Base Definitions and Headers Editorial Enhancement Request 2016-07-07 21:09 2017-08-15 07:50
Reporter EdSchouten View Status public  
Assigned To ajosey
Priority normal Resolution Open  
Status Under Review  
Name Ed Schouten
Organization Nuxi, the Netherlands
User Reference
Section string.h / wchar.h
Page Number -
Line Number -
Interp Status ---
Final Accepted Text
Summary 0001061: Please add memmem() (and maybe wmemmem())
Description A decent implementation of the strstr()/wcsstr() function is rather complex. In the old days, implementations typically had to make a trade-off between in-place quadratic time algorithms (simple scanning) or linear-time/space algorithms (e.g. Knuth-Morris-Pratt). If I'm correct, an in-place linear worst-case time algorithm is only known since the 90s (Two-way string-matching). Its pseudo-code alone is already 50 lines.

The problem with strstr()/wcsstr() is that it assumes that the input strings are null terminated, which isn't always the case. This is why many operating systems (Linux, all the BSDs, Mac OS X) provide a memmem() function as well, which can reuse the same algorithm. There shouldn't be a need to handroll such a function yourself.
Desired Action Please standardize the existing memmem() function. While there, maybe we should also add wmemmem() for consistency.
Tags No tags attached.
Attached Files txt file icon memmem.txt [^] (1,492 bytes) 2017-08-15 07:47

- Relationships

-  Notes
(0003817)
EdSchouten (updater)
2017-08-15 07:50

[ Sorry if you received a partial response; I accidentally clicked the submit button ]

Hi Andrew,

As you requested, attached to this ticket you may find formatted text for inclusion into the standard. It is loosely based on the existing documentation of strstr(), except that I've decided to rename 's1' and 's2' to 'haystack' and 'needle' to prevent confusion.

Be sure to get in touch in case there are things you want me to clarify/improve.

Ed

- Issue History
Date Modified Username Field Change
2016-07-07 21:09 EdSchouten New Issue
2016-07-07 21:09 EdSchouten Status New => Under Review
2016-07-07 21:09 EdSchouten Assigned To => ajosey
2016-07-07 21:09 EdSchouten Name => Ed Schouten
2016-07-07 21:09 EdSchouten Organization => Nuxi, the Netherlands
2016-07-07 21:09 EdSchouten Section => string.h / wchar.h
2016-07-07 21:09 EdSchouten Page Number => -
2016-07-07 21:09 EdSchouten Line Number => -
2016-09-14 14:18 emaste Issue Monitored: emaste
2017-08-15 07:47 EdSchouten Note Added: 0003816
2017-08-15 07:47 EdSchouten Note Deleted: 0003816
2017-08-15 07:47 EdSchouten File Added: memmem.txt
2017-08-15 07:50 EdSchouten Note Added: 0003817


Mantis 1.1.6[^]
Copyright © 2000 - 2008 Mantis Group
Powered by Mantis Bugtracker