Saturday, March 31, 2012

Normalize a path by removing redundant separators and resolving up-level references


Write a function to normalize a path by removing redundant separators and resolving
up-level references.  I.e., given "/foo/bar//./baz/..//boo" returns "/foo/bar/boo".
- You may assume that the given path is always absolute (i.e., begins with "/").
- You may not use any library functions.
- Ideally, the solution should function in-place without allocating any buffers.


#define E_NULL -1
#define E_INVALID -2
int
normalizePath(char* pPath,
unsigned startIndex,
unsigned writeOffset,
unsigned level)
{
  unsigned lastIndex = startIndex + 1;
  unsigned retValue = 1;
  unsigned ii, jj;

 printf("level=%d start index=%d writeOffset=%d\n", level, startIndex, writeOffset);
  if (pPath == NULL) {
    return E_NULL;
  }

  if (pPath[startIndex] == 0) {
    pPath[writeOffset] = 0;
    return 0;
  }

  if (pPath[startIndex] != '/') {
    return E_INVALID;
  }

  do {
    if (pPath[lastIndex] == 0) {
      pPath[writeOffset] = 0;
      break;
    }
      // find next / or NULL
    while (pPath[lastIndex] && pPath[lastIndex] != '/') {
      lastIndex++;
    }
  printf("%d\n", lastIndex);
    // missing ignoring series of ////
 
    if (pPath[startIndex + 1] == '.') {
if (pPath[startIndex + 2] == '.') {
if (level == 0) {
continue;
}
return 1;
} else {
retValue = normalizePath(pPath, lastIndex, writeOffset, level +1 );
}
    } else {
// startIndex to lastIndex to writeOffset

for(ii = startIndex, jj= 0; ii < lastIndex; ii++, jj++) {
pPath[writeOffset + jj] = pPath[startIndex + jj];
}
retValue = normalizePath(pPath, lastIndex, writeOffset + jj, level + 1);
    }
    startIndex = lastIndex + 1;
    lastIndex += 1;
  } while (retValue == 1);

  return 0;
}


int
main()
{
char *pPath = "/ab/../de/../mn/./..";
normalizePath(pPath, 0, 0,0 );
printf("path=%s", pPath);
return 0;
}


2 comments:

  1. Suppose input is just "/" you are checking out of bounds in below statement.

    if (pPath[startIndex + 1] == '.') {
    if (pPath[startIndex + 2] == '.') {

    ReplyDelete
  2. Thanks for pointing out. I will add an extra check at the beginning.

    ReplyDelete